The following discussion is based on the source code :1000OgresOource.zip. This code uses the “xinf” haxelib module to provide support for cross platform (browser, downloadable) structures.
The Ogre demo uses a grid to check for collisions between objects. So,rather than checking 1000 sprites against 1000 others, requiring 1000000 checks per frame, each sprite only checks sprites in the local viscinity, running much faster. The 2D grid is independent of the tile grid, and its spacing can be optimised based on object size and density etc.
The code deals, in part, with “GOB”s (Game OBjects) and the GOBGrid. I tried to decouple the grid from the objects, but I could not, because the haXe template system is not powerful enough. The coding issue I’m going to talk about here is how to best separate the task of examining objects in the local visinity, from how the objects are stored in the grid. In other words, iterators.
The algorithm I’m going to talk about is something like the following pseudo code fragment:
GOB::Move()
{
x += velocity_x
y += velocity_y
for_all_nearby_objects_in_grid
if (obj_is_close_to_me)
-> dont move.
The question is, what does the “for\_all\_nearby\_objects\_in\_grid” look like. I have tried the following:
Object List. Here, the GOBGrid produces an Array of candidate objects. The GOB then iterates over these, checking distances between the potential move position and these candidate objects. An important point to note is that the following:
var objs = mGrid.GetCloseObjs(x,y);
for(obj in objs)
...
was *much* slower than:
var objs = mGrid.GetCloseObjs(x,y);
for(i in 0...objs.length)
{
var obj = objs[i];
...
this should be considered when writing high-performance code.
HaXe Iterator. Writing the iterator was slightly tricky, because you need to think in a slightly different way than you would normally. Here I have made the assumption that “getNext” will be called exactly once after each successful “hasNext” call. I’m pretty sure this is right. This assumption places all the logic in “hasNext” and makes “getNext” trivial. The big advantage of the iterator is that it is syntactically identical to the object list code above (first example), eg:
var objs = mGrid.GetCloseObjs(x,y);
for(obj in objs)
...
and runs much faster. This leaves open the possibility of staring with a list and then moving to an iterator if the performace is required. The iterator code looks like this:
class GOBIterator
{
var mGrid:GOBsList;
var mGridPos:Int;
var mGridEnd : Int;
var mYStep:Int;
var mWidth:Int;
var mCurrentList : GOBs;
var mListPos : Int;
var mX:Int;
var mNext : GOB;
public function new(inGrid:GOBsList,
inX0:Int,inY0:Int, inX1:Int,inY1:Int, inWidth:Int)
{
mGrid = inGrid;
mWidth = inX1-inX0;
mYStep = inWidth - mWidth + 1;
mX = 0;
mGridPos = inY0*inWidth + inX0;
mGridEnd = (inY1-1)*inWidth + inX1;
mCurrentList = mGrid[mGridPos];
mListPos = 0;
}
// Haxe iterator interface
public function hasNext()
{
if (mGridPos >= mGridEnd)
return false;
while(true)
{
if (mListPos=mGridEnd)
return false;
}
else
{
mGridPos++;
}
mCurrentList = mGrid[mGridPos];
mListPos = 0;
}
return false;
}
public function next() : GOB
{
return mNext;
}
}
The mGrid is an Array of cells, each of which is an array of GOBs that are centred in that cell. To go from (x,y) coordinate to cell, the x and y are first quantised and then an index is calculated using cell=y*xcells + x. Another possiblity would be to have a 2D array of cells. I have not tried this, and it may be better or worse, I don’t know.
HaXe while loop. This is very similar to the above code, except that the getNext and hasNext code are combined, and return “null” at the end. The code is simiar- it uses the same constuctor and the function:
// This combines hasNext with next, and returns null when done.
public function getNext() : GOB
{
if (mGridPos >= mGridEnd)
return null;
while(true)
{
//var n = mWidth + mYStep - 1;
//trace( "[" + (mGridPos%n) + "," + Math.floor( mGridPos/n ) + "]" );
if (mListPos=mGridEnd)
return null;
}
else
{
mGridPos++;
}
mCurrentList = mGrid[mGridPos];
mListPos = 0;
}
return null;
}
The problem with this is that you have to use the “while” loop, rather than the “for”, taking 3 lines instead of 1.
Closure/Callback. This method keeps the grid and GOB decoupled by asking the grid to iterate over the neadby objects, calling a callback function for each candidate object.
var self = this;
return mGrid.VisitCloseClosure( mMoveX, mMoveY, m2Rad,
function(inObj:GOB)
{
var obj:GOB = inObj;
if (obj==self) return true;
var dx = self.mMoveX-obj.mX;
var dy = self.mMoveY-obj.mY;
return dx*dx+dy*dy >= 2;
} );
This type of inline-function definition is just the sort of thing I’ve been craving in C++ for years. It takes a bit to get your brain around, but it does provide a very elegant way of decoupling code.
The above 4 methods are attractive because there is a large decoupling between the grid and the objects it stores. The grid could quite easily deal simply with dynamic objects, and the GOB need only know that the grid returns some kind of logical list. Unfortunately, they are not the fastest methods. The following methods introduce tighter coupling between the grid and the GOB in order to improve speed.
Visitor Callback. This method is very similar the the callback method above, except that the grid is passed an object of known type and calls a particular member function on it, rather than a anonymous function, for each candidate object. The problem is that this can only call one particular function, and thus can’t be adapted to a different function.
Inline GOB. This method, the GOB knows everything about the grid implementation and iterates over the elements directly. While it is not *too* much code in this case, this may soon grow unweildly if we consider such things as multi-resolution grids. This does not allow us the change the grid implementation without changing the GOB code too.
Inline Grid. Here the grid knows about GOB collisions and interrogates the objects directly. This binds part of the GOB implementation to the Grid and is also specialised for one particular function (eg, “collision detection”). However, it does let us change the grid implementation without changing the GOB code.
Results
The results are summarised in the following table.
| Method |
Time (ms/frame) |
Pros |
Cons |
| Object List |
31.8 |
Easy to understand/debug. |
Slowest. Causes stutter while garbage collection runs |
| HaXe Iterator |
21.0 |
Improved performace over Object List.
Direct “drop in” replacement for Object List.
Decoupled data. |
Slightly complex to write. Slightly slower than most. |
| While Iterator |
20.0 |
Slightly faster than for-iterator. Slightly easier to write |
Slightly more complex to use. |
| Closure/Callback |
20.7 |
Slightly faster than for-iterator. Decoupled. Interesting way of writing code. |
Interesting way of writing code. |
| Member Callback |
16.4 |
Faster than anonymous callback. |
Member function name is explicit in code. |
| Inline GOB |
17.6 |
Faster. |
Couples GOB code to grid implementation. Requires separate code for each function |
| Inline Grid |
14.8 |
Fastest. Easy to understand/debug. Not as badly coupled as Inline GOB. |
Couples Grid code to GOB implementation. Requires separate code for each function |
So, there you have it. *No definitive answers!*. Decoupling is sacraficed for performance in most cases. Except perhaps that the grid should loop over the objects, rather than the other way around. I think I will use the Inline Grid method for collision detection.
However, if I need to write code like “All ogres run away from all skeletons” then I will need one of the first 4 generic ways of iterating. The iterator methods may get too complex if I have “multi-resolution” grids, in which case, the anonymous function callback may be the way to go. There may also be a way to bring the anonymous function performace up to match the member-function performace – this would be the best of all worlds (fully customisable, and only slightly slower than Inline Grid). Any ideas anyone?
You can download the code and comment/uncomment these various options in GOB.hx.
