Debugging and Profiling Your Game - Game Coding Complete - page 848

Actor* FindActor(ActorId id)
{

auto it = actorMap.find(id);
if (if != actorMap.end())
return it->second;
return NULL;

}
This function uses the map ' s find() function, which searches the tree for the key. A
binary tree is a divide-and-conquer data structure, so as long as the tree remains bal-
anced, you won

t visit every node. This type of algorithm is O(log2n), which means
that the time the algorithm takes to run is proportional to the base-2 log of the num-
ber of elements. If visiting each node takes 1ms and there are 100 nodes, the node
has a worst-case time of about 6.64ms. That

'

s much better than the 100ms that list
was going to take! This is a huge improvement, assuming that the actor data struc-
ture is accessed often enough using the ActorId as the key.
The final optimization technique I want to talk about is with scripting languages like
Lua. Scripting languages execute code slower than a compiled language like C++. One
thing you can do is move some of the more expensive script functions into C++. This is
commonly done for heavy math functions. For example, you probably don ' twanttodo
your pathing algorithm in Lua. This should be in C++ and called from Lua.

'

Tradeoffs
Not every optimization is going to be as simple as swapping out an STL data struc-
ture. Most of the time, you

ll have to make a trade. The classic trade is memory ver-
sus performance. In the actor example you saw in the previous section, you might do
some tests and find that about 25 percent of the time, you

'

' re searching for the

'

player s Actor object. One optimization would be to cache that actor directly so

that retrieving the player is a simple getter function that doesn ' t have to go into the
actor map at all. The cost of this is the memory required to store the extra pointer,
which is probably worth it.
Caching values is a very common optimization. In general, you could precompute and
cache everything you can, especially right before a big algorithm is about to run. On The
Sims Medieval, we cached certain routing paths in the pathing system that were both
extremely common and very expensive. This cost us a bit of memory because we had
tostorethosepaths,butmanyofourlong-distanceroutesdidn thavetoruntheexpen-

sive path-finding algorithm, it just had to verify that the path hadn

'

t become invalid.
Another common optimization is to sacrifice reactivity for performance stability. A
good example of this can be found in the event system in Chapter 11,

'

“

Game Event