Design Patterns summarize the common solutions for particular problems. Book "Gang Of Four Design Pattern" is classic. Book "Game programming pattern" shows solutions to a variety of game related problems.
Here, I will summarize the optimization patterns I used often, mainly in the game of ArmaGallant and a recent mobile game. Both work is carried on in Unity C#.
Optimize Pattern 1-----Cache the result, compute once, retrieve later
string operation often generate gc, for example, int.tostring(). to avoid gc, can cache the result in a dictionary.
Optimization Pattern 2---Temporary parameter for an object
2.1 find common set of two sets.
Given problem: when you have two sets of same type objects, how to find the common objects?
One easy solution would be introduce a Tempbool variable to the object type. then,
1. loop set1, and the TempBool for all objects to be false
2. loop set2, set the TempBool for all objects to be true
3. loop set1, extract all the objects with TempBool true. The result is the common set of set1 and set2
O(m+n) to find the common set of set1 and set2. Notice, this solution works for single thread execution only.
2.2 sort a list of object base on the distance value to another object
Given problem: a list of enemy, the player need to sort the enemy based on the distance?
One simple solution could be, introduce a TempFloat in the object, then
1. Loop the enemy list, compute the square distance to the player and store in TempFloat
2. List.Sort with comparer comparing TempFloat
O(nlogn) default quick sort and minimize the code writing. You do not need to implement your sorting algorithm, just rely on the existing quick sort default implementation.
Optimization Pattern 3--Compute less, achieve same
check whether a player is within a monster's angry radius, compute the squareDistance, and compare it with radius*radius. Reason: square root operation is super expensive comparing with multiplication
Optimization Pattern 4--Avoid shrunk resizing array, lazy update to achieve minimal gc, tolerant junk data in the array, but never use
Problem: For the mobile game, a mesh is generated to show a player's finger draw. The mesh is keep updating, with mesh's vertice number reducing as time goes on, which will require resize of the vertex array. Resize the array would generate big amount of gc, slow the application.
Solution: Avoid vertex array resizing if the new size is smaller. Tolerate the junk vertices data, but never use it for the triangulation(triangle is the default element to show any mesh/model)
Optimize Pattern 5--Minimize usage of string. Store integer value as Enum, rather than querying by string. Query dictionary by integer rather than string.
For example, object layer in unity with layer mask(computed as 1 << layer) are required too.
Querying by string introduce several issues
1. Programmer might type the wrong string
2. Layer and LayerMask both integer value, programmer might easy misuse these two as typing too fast.
However if just define LayerEnum provide the value of each layer, example
Enum LayerEnum{
UI
}
Public class LayerUtil{
public static int GetLayerMask(LayerEnum layer){
return 1 << (int)layer;
}
}
when layer and layer mask could be computed as
int layer = (int) LayerEnum.UI
int layerMask = LayerUtil.GetLayerMask(LayerEnum.UI)
Query dictionary by integer rather than string if possible.
it is much faster to query a dictionary by an integer comparing with by string, example, query by 9527, 24601 not by "9527", "24601"
Optimization Pattern 6---Object pool for use/recycle and usage verify
It is important to avoid memory leaking to minimize gc. So a common approach is recycling an object when finish using, push to stack
try pop from stack, return the item if got, otherwise create a new one
Notice that the Object often could be an object Container, example List<Character>Example,
List<Character> characters = CharacterListPool.GetNew();
GetAllEnemiesWithRadius(characters, 5);
//carry on process the data of
CharacterListPool.Recycle(characters);
Verifying the use/recycle by counting the nubmer of GetNew() and Recycle(...), give you confident that data fully reused.
Optimization Pattern 7--avoid intermediate garbage generation pattern
During function call, a lot of convertion might happen. Not need call "new" to generate gc.
Optimization Pattern 8--Exchange C# container for customized container(same feature, more control)Example, make a list implementation call FastList to
1. allow direct access the array
2. Output warning if the FastList double the capacity (if you have initialize the capacity correctly, then most likely it is a bug)
Self implemented FastList could support feature---defragment
example, remove m element from a list, in standard list, it could be O(m * n)
but in customized list, it could O(n) by
1. first loop the list, if element need to remove, just set the entry to be null
2. loop the list, defragment the null entry by swapping with next not null entry
Optimization Pattern 9--Data to be same interface, to be interpreted by different implementation
Behavior Tree is often used to handle game AI. Behavior Designer provides behavior tree customization in unity very well, however, the implementation is slow as it is full featured, generalized and too many layer of item pushing and poping and huge gc during the initial serialization.
I have to address this issue as ArmarGallant server is session based and authoritative. Each server should be expected to run at least around 200(session) x 32(max unit per session) behavior trees.
Solution: write a customized BehaviorTree with minimal feature which could interpret the data generated by BehaviorDesigner. So the work process becomes,
1. use BehaviorDesigner in the editor to plan the behavior tree and do the debug in the editor mode
2. when release the game, use customized mini-implementation to run
Optimization Pattern 10--Dirty flag
(from book Game Programming Pattern
"A set of primary data changes overtime. A set of derived data is determined from this using some expensive process. A "dirty" flag tracks when the derived data is out of sync with the primary data. It is set when the primary data changes. If the flag is set when the derived data is needed, then it is reprocessed and the flag is cleared. Otherwise the previous cached derived data is used.")
It is worth to mention that dirty flag pattern is used to handle object's transform update in unity. It is very often used to mark a value as dirty by a bool, when retrieving the value and make the re-computation.
Here, I will summarize the optimization patterns I used often, mainly in the game of ArmaGallant and a recent mobile game. Both work is carried on in Unity C#.
Optimize Pattern 1-----Cache the result, compute once, retrieve later
string operation often generate gc, for example, int.tostring(). to avoid gc, can cache the result in a dictionary.
- Cache result for int.tostring
- Cache result for string.split(':')
- Double key-cache result of str1 + "." + str2 or str1+str2 Dictionary<string, Dictionary<string, string>>
Optimization Pattern 2---Temporary parameter for an object
2.1 find common set of two sets.
Given problem: when you have two sets of same type objects, how to find the common objects?
One easy solution would be introduce a Tempbool variable to the object type. then,
1. loop set1, and the TempBool for all objects to be false
2. loop set2, set the TempBool for all objects to be true
3. loop set1, extract all the objects with TempBool true. The result is the common set of set1 and set2
O(m+n) to find the common set of set1 and set2. Notice, this solution works for single thread execution only.
2.2 sort a list of object base on the distance value to another object
Given problem: a list of enemy, the player need to sort the enemy based on the distance?
One simple solution could be, introduce a TempFloat in the object, then
1. Loop the enemy list, compute the square distance to the player and store in TempFloat
2. List.Sort with comparer comparing TempFloat
O(nlogn) default quick sort and minimize the code writing. You do not need to implement your sorting algorithm, just rely on the existing quick sort default implementation.
Optimization Pattern 3--Compute less, achieve same
check whether a player is within a monster's angry radius, compute the squareDistance, and compare it with radius*radius. Reason: square root operation is super expensive comparing with multiplication
Optimization Pattern 4--Avoid shrunk resizing array, lazy update to achieve minimal gc, tolerant junk data in the array, but never use
Problem: For the mobile game, a mesh is generated to show a player's finger draw. The mesh is keep updating, with mesh's vertice number reducing as time goes on, which will require resize of the vertex array. Resize the array would generate big amount of gc, slow the application.
Solution: Avoid vertex array resizing if the new size is smaller. Tolerate the junk vertices data, but never use it for the triangulation(triangle is the default element to show any mesh/model)
Optimize Pattern 5--Minimize usage of string. Store integer value as Enum, rather than querying by string. Query dictionary by integer rather than string.
For example, object layer in unity with layer mask(computed as 1 << layer) are required too.
Querying by string introduce several issues
1. Programmer might type the wrong string
example in LayerMask.NameToLayer("TransparentFX")2. Layer and LayerMask both integer value, programmer might easy misuse these two as typing too fast.
However if just define LayerEnum provide the value of each layer, example
Enum LayerEnum{
UI
}
Public class LayerUtil{
public static int GetLayerMask(LayerEnum layer){
return 1 << (int)layer;
}
}
when layer and layer mask could be computed as
int layer = (int) LayerEnum.UI
int layerMask = LayerUtil.GetLayerMask(LayerEnum.UI)
Query dictionary by integer rather than string if possible.
it is much faster to query a dictionary by an integer comparing with by string, example, query by 9527, 24601 not by "9527", "24601"
Optimization Pattern 6---Object pool for use/recycle and usage verify
It is important to avoid memory leaking to minimize gc. So a common approach is recycling an object when finish using, push to stack
try pop from stack, return the item if got, otherwise create a new one
Notice that the Object often could be an object Container, example List<Character>Example,
List<Character> characters = CharacterListPool.GetNew();
GetAllEnemiesWithRadius(characters, 5);
//carry on process the data of
CharacterListPool.Recycle(characters);
Verifying the use/recycle by counting the nubmer of GetNew() and Recycle(...), give you confident that data fully reused.
Optimization Pattern 7--avoid intermediate garbage generation pattern
During function call, a lot of convertion might happen. Not need call "new" to generate gc.
- call Compute(p1, object[]p2); // a default array will auto generated
- anonymous function
- use List.sort(CompareFunction), if CompareFunction is not initialized
- Dictionary should not use Enum as key in C#, just convert the Enum to integer to key access dictionary.
Optimization Pattern 8--Exchange C# container for customized container(same feature, more control)Example, make a list implementation call FastList to
1. allow direct access the array
2. Output warning if the FastList double the capacity (if you have initialize the capacity correctly, then most likely it is a bug)
Self implemented FastList could support feature---defragment
example, remove m element from a list, in standard list, it could be O(m * n)
but in customized list, it could O(n) by
1. first loop the list, if element need to remove, just set the entry to be null
2. loop the list, defragment the null entry by swapping with next not null entry
Optimization Pattern 9--Data to be same interface, to be interpreted by different implementation
Behavior Tree is often used to handle game AI. Behavior Designer provides behavior tree customization in unity very well, however, the implementation is slow as it is full featured, generalized and too many layer of item pushing and poping and huge gc during the initial serialization.
I have to address this issue as ArmarGallant server is session based and authoritative. Each server should be expected to run at least around 200(session) x 32(max unit per session) behavior trees.
Solution: write a customized BehaviorTree with minimal feature which could interpret the data generated by BehaviorDesigner. So the work process becomes,
1. use BehaviorDesigner in the editor to plan the behavior tree and do the debug in the editor mode
2. when release the game, use customized mini-implementation to run
Optimization Pattern 10--Dirty flag
(from book Game Programming Pattern
"A set of primary data changes overtime. A set of derived data is determined from this using some expensive process. A "dirty" flag tracks when the derived data is out of sync with the primary data. It is set when the primary data changes. If the flag is set when the derived data is needed, then it is reprocessed and the flag is cleared. Otherwise the previous cached derived data is used.")
It is worth to mention that dirty flag pattern is used to handle object's transform update in unity. It is very often used to mark a value as dirty by a bool, when retrieving the value and make the re-computation.
Comments
Post a Comment