The significance of AABBs
There are several reasons why aabb’s are a good choice for a game such as Gunbird. For a start they can be represented compactly thus taking up little memory which can be important when so many objects are involved. All that is needed to fully represent an aabb in 2d is 4 values. This can either be a center pos combined with the width and height, or its 4 extreme values, minX (posX – width), maxX (posX + width), minY (posY – height), and maxY (posy + height). We’ll be using the later representation. Although less intuitive it is better for our means later on. The more important reason for aabb’s though is that collision detection between them is extremely quick and easy as I’ll demonstrate:
struct AABB
{
int objId; // the id of the object which owns this box
float vals[2][2]; // the values of the minimum and maximum extremes of the enpoints in each axis
// vals[0][0] = minX
// vals[0][1] = minY
// vals[1][0] = maxX
// vals[1][1] = maxY
}
bool Collide(AABB boxA, AABB boxB)
{
if(boxA.vals[1][0] < boxB.vals[0][0]) { return false; }
if(boxA.vals[0][0] > boxB.vals[1][0]) { return false; }
if(boxA.vals[1][1] < boxB.vals[0][1]) { return false; }
if(boxA.vals[0][1] > boxB.vals[1][1]) { return false; }
return true;
}
(Please note, like I mentioned in my intro, the code is written in a simplistic way for ease of understanding for those not using C++. If you were to implement this you’d want to use const references to the input aabb’s to the function so that the copy constructor isn’t called. Just thought I’d mention it again since this is the first code example I’ve given, please keep it in mind). Ignore the objId in the aabb structure for now I’ll come back to that later, and I apologise for the confusing layout of values but again this is for a purpose later on. What the collision function here is saying is that if the right most extreme of box A is to the left of the left most extreme of box B then they can’t possibly be colliding so it returns false. The same condition applies for all extremes and so all are tested. If it turns out that none of these tests cause the function to exit then the boxes must be intersecting and hence true is returned. You can try this for yourself by drawing aabb’s on paper or getting two playing cards and moving them around relative to each other. As you can see the maths and logic involved is very simple and there are many early exit opportunities which makes the test very quick. You can even squeeze a little extra performance out of this if you know before hand the type of layouts you’ll be dealing with. For example if your play area is deeper than it is wide and your objects are usually more spread out in the vertical direction, then by placing the height tests before the width tests, on average you will drop out of the function quicker.
The real significance of the collision scheme in Gunbird however is that there are aabb’s and nothing but aabb’s. This lets us use a special technique called “sweep and prune” rather than just colliding every box against every other box each frame. I’ll give an overview of the technique first before I delve into specifics to give you a better idea of what we’re trying to achieve. First of all we need to think of our aabb’s a little differently. Rather than a box, think of them as spanning an interval along the x axis between their left most extent to their right most extent, and similarly spanning an interval along the y axis. The problem of colliding all our boxes can now be reduced to two one dimensional problems across each axis. If the intervals of two boxes overlap on both axes simultaneously then they pass all the conditions in the aabb collision test in the code example above and hence they are intersecting. In order to do this we put all our boxes’ x interval endpoints (minX and maxX) into one array and all our y interval endpoints (minY and maxY) into another and sort those arrays so the values are arranged in numerical order. This is where the power of the technique really starts to shine through. We know each frame that each box is only going to move a small amount, and hence re-sorting these arrays each frame is very quick since values only need to check those next to them in the array to see if they need to swap places and these swaps will only happen infrequently. As well as this we know that the collision state of the scene only changes when endpoints do these swaps and so we can completely ignore most of our boxes each frame, only dealing with those corresponding to swaps. By taking advantage of this coherence between frames we have drastically reduced the amount of work we need to perform. It really doesn’t get any faster than this.
So how do we implement this technique? I’ll give you a code dump since that can explain the implementation much more efficiently than I could do with words. Don’t worry; I’ve included plenty of comments which should explain everything you need to know. All the mundane and easy management type stuff I’ll leave for you to fill in though. The best thing is probably to have a quick scan over it and then read the rest of the article before studying it in detail.
struct Encounter
{
int objIds[2]; // the id’s of the objects which are colliding
}
struct Endpoint
{
int type; // 0 = startPoint (min extreme), 1 = endPoint (max extreme)
int boxId; // id of the box this endpoint belongs to
}
struct SweepAndPrune
{
Encounter encounters[MAX_ENCOUNTERS]; // a store of encounters this frame
AABB boxes[MAX_BOXES]; // our boxes
Endpoint endpoints[2*MAX_BOXES][2]; // our endpoint arrays –> 2 endpoints per box per axis
int numEncounters; // current number of active encounters
int numBoxes; // current number of boxes we have
void Update();
void ResolveEncounters();
void AddEncounter(int objIdA, int objIdB);
void RemoveEncounter(int objIdA, int objIdB);
int AddBox(int objId, float minX, float maxX, float minY, float maxY);
void RemoveBox(int boxId);
void UpdateBox(int boxId, float minX, float maxX, float minY, float maxY);
}
void SweepAndPrune::Update()
{
// sort lists on each axis
for(int axis = 0; axis < 2; axis += 1)
{
// go through each endpoint in turn
for(int j = 1; j < numBoxes*2; j += 1)
{
int keyType = endpoints[j][axis].type;
int keyBoxId = endpoints[j][axis].boxId;
// get the min val if this is a startPoint else get the max val
float keyVal = boxes[keyBoxId].vals[keyType][axis];
// Compare the keyval to the value one before it in the array (our comparison value) and swap places if need be.
// Keep doing this until no more swaps are needed or until we reach the start of the array
int i = j-1;
while(i >= 0)
{
// get our comparison value in the same way we got the key value
int compType = endpoints[i][axis].type;
int compBoxId = endpoints[i][axis].boxId;
int compVal = boxes[compBoxId].vals[compType][axis];
if(compVal < keyVal)
{
// these values are in the correct order so break out of this while loop
break;
}
// these vals are swapping places which relates to a change in the state of the scene
// so update our encounter list accordingly
// if and endpoint is swapping to the left on a startpoint then we know these objects are leaving contact
// so remove any encounters relating to these objects
if((compType == 0) && (keyType == 1))
{
RemoveEncounter(compBoxId, keyBoxId);
}
else
{
// else if a startpoint is swapping to the left of an end point, these object might be colliding
if((compType == 1) && (keyType == 0))
{
// this only tells us that they overlap on one axis
// to be sure of collision we must do an intersection test
if(Collide(boxes[compBoxId], boxes[keyBoxId]))
{
AddEncounter(compBoxId, keyBoxId); // these AABBs now intersect
}
}
}
// finaly we must swap the points
endpoints[i+1][axis].type = compType;
endpoints[i][axis].type = keyType;
endpoints[i+1][axis].boxId = compBoxId;
endpoints[i][axis].boxId = keyBoxId;
// we must decriment i so that we continue searching down the array
i -= 1;
}
}
}
}
void SweepAndPrune::ResolveEncounters()
{
// Iterate through your encounter list and trigger collision resolution code
// for each pair of objects in there
}
void SweepAndPrune::AddEncounter(int objIdA, int objIdB)
{
// Add encounter between the inputted objects to the list
// being careful not to duplicate existing ecounters
}
void SweepAndPrune::RemoveEncounter(int objIdA, int objIdB)
{
// Remove encounter between the inputted objects from the
// list if it exists
}
int SweepAndPrune::AddBox(int objId, float minX, float maxX, float minY, float maxY)
{
// I'll fill this one out since it shows how to set up the various structures
// add box
boxes[numBoxes].objId = objId;
boxes[numBoxes].vals[0][0] = minX;
boxes[numBoxes].vals[0][1] = minY;
boxes[numBoxes].vals[1][0] = maxX;
boxes[numBoxes].vals[1][1] = maxY;
// add endpoints
endpoints[2*numBoxes][0].type = 0;
endpoints[2*numBoxes][0].boxId = numBoxes;
endpoints[2*numBoxes+1][0].type = 1;
endpoints[2*numBoxes+1][0].boxId = numBoxes;
endpoints[2*numBoxes][1].type = 0;
endpoints[2*numBoxes][1].boxId = numBoxes;
endpoints[2*numBoxes+1][1].type = 1;
endpoints[2*numBoxes+1][1].boxId = numBoxes;
// note that its not important to insert these in their correct sorted value position
// as I havn't since the next call to Update() will sort that out for us.
numBoxes += 1;
// return the id of this box so that objects know which box to update when they move
return numBoxes-1;
}
void SweepAndPrune::RemoveBox(int boxId)
{
// Remove the box with the corresponding id being careful to remove all its
// endpoints as well as any encounters relating to this boxes object
}
void SweepAndPrune::UpdateBox(int boxId, float minX, float maxX, float minY, float maxY)
{
// Replace the vals of the box with the inputted boxId
// Whenever an object moves it should call this to update its collision box(es)
// Each object will know which boxId to pass in since it should store the boxId value
// returned when AddBox() is called.
}
So the general idea here is that as objects such as enemies, power-ups, and bullets are created, they add their collision aabb’s to the sweep and prune system and store the returned box ids. Each frame, after each object updates its position it also updates the collision box in the sweep and prune system using the stored id. Once all objects have finished, the sweep and prune Update() method is then called which works out all collision encounters. You then call the ResolveEncounters() method which will call the collision resolution code for each pair of colliding objects that frame for you to respond to as you wish. As you can see, once implemented the system becomes very simple to use and is very ‘black box’, i.e. we can interface with it and use it without really having to worry about what goes on inside. Because of this you should be able to re-use this system to quickly get collision detection and management running in any of your future projects as well as this one.
As a quick aside, the sharp minded amongst you are probably asking, “If the sort method on each axis is used to detect the collisions, then why is there a call to an explicit collision function in there?” Well the reason is that we can only be sure there is a collision when the box intervals overlap simultaneously on both axes like I mention above. Now we could try and be clever and implement some sort of method with counts and keeps track of end swaps and overlaps on each axes for each object so that we can detect when this is the case. However given the simplicity of the explicit collision test you’ll likely find using a clever technique gives no speed advantage and hence we might as well keep it simple and use the explicit test to check for this when we need to. The reason the interval sorting gives us such a performance boost is not because it completely replaces the explicit test, but severely reduces the number of times we need to call it.
Note that the above code is the simplest implementation I could give so that you can focus on the important elements without getting bogged down by the details. There’s no error checking or anything like that for a start which you should definitely include for yourself. This means that there’s plenty of room for improvements. Here are some ideas:
Many encounters that are reported you’ll no doubt be uninterested in such as enemy bullets colliding with each other etc. Remember the attribute flagging I talked about in the first section where each box was given a colour? Well if you give each aabb an additional member which stores its type, such as player, power-up, ground enemy, etc, then you could implement a collision map. This will simply be a little matrix which stores a yes/no value for each object type when cross referenced with another object type. Then in the sweep and prune Update() method, just before the collision test is performed when endpoints swap position, you can check the collision map to see if this is something you’re interested in reporting. If not then simply assume the collision test returns false without performing it. Not only will this remove those encounters you’re not interested in it will also give you a performance boost.
Secondly you’ll find that encounters keep getting reported for as long as two objects are in contact. This is likely not the type of behaviour you want, or at least you want the option to ignore this after the first report. For example, in Gunbird when you collide with a flying enemy it powers you down one level but neither you nor the enemy is destroyed. In such a system this collision will get reported every frame and you’d very quickly power down to the minimum level rather than just loosing the one. To give a bit more flexibility on how you want to respond to collisions I recommend you double buffer the encounter list. By comparing the current encounter list with the last frame’s you’ll be able to report events only at the time of first collision as well as time of first leaving collision if you so desire. You can then have objects query the sweep and prune system each frame if they wish to know about continuous collisions. Keep in mind though that when swapping buffers we can’t just discard the contents like we do with a render buffer for example, since these results are important. After all, the reason we get continued reporting of encounters is not because they are redetected each frame, in fact the collision is only detected once when the initial endpoint swap that puts it in a colliding state takes place. Rather the encounters simply aren’t removed from the encounter list until a separation event is detected. Therefore it’s probably easier if the sweep and prune works on the same current frame buffer each frame rather than swapping buffers, but at the start of the Update() function you copy the buffer to a separate buffer for comparison purposes.
Another area which will likely need to some extra thought is when adding and removing objects since this will happen fairly frequently. Although this can be handled nicely for the box arrays since we don’t need a continuous array and can instead track empty slots, there is the seemingly unavoidable situation that removals will need to be made in the interior of the endpoint arrays (note that insertions can be avoided by tagging additions onto the end and letting the update method sort it out). This kind of stuff can hit you pretty hard if not handled well since you’ll be copying memory around all over the place to create space for taking out gaps for removals. You can limit the damage caused by storing desired endpoint removals in separate arrays until you’ve collected them all for that frame and then do the work in one big batch so that this array shuffling only happens once a frame for any frame were removals are requested. Alternatively you could try replacing the endpoint arrays with linked lists which will solve this problem but in general are slower to traverse (I don’t really recommend this). If you do though then I suggest implementing your own linked list class which allocates itself a block of continuous memory to work with at initialisation so you don’t thrash the cache. There is however a rather sneaky alternative I’ve thought of. When you wish to remove a box, set all of the box vals to a high value off the edge of your playing area (eg 1e22f) and set the box type to one you’ve created specifically for this purpose that has no positive entries in the collision map. What happens now is that after the next Update call, all the endpoints you wish to remove will get pushed to the end of the arrays without triggering any collision tests or generating encounters and removing them simply becomes a matter of looking at the last entries in the arrays and popping them off the end if they has this special box type (or decrementing your numEndpoints counter if you don’t use stl – note that number of boxes and number of endpoints will need to be tracked separately). This way no separate memory shuffling is required at all, it becomes a natural process of the algorithm. Ingenious
.
Lastly a short and special note for c++ users. If you wish to implement this for yourself, there’s much better ways to do it than I have here by using c++ style functionality. Again remember that I’ve kept it simple and c++ free like this on purpose. You should bare in mind that stl is your friend. There’s lots of members in that code that would be much better implemented as vectors or lists, not to mention that you can put the built in stl sorting algorithms to good effect. Also instead of linking back to objects through ids for the encounter resolution phase you may want to inherit all your objects from a common base class with pure virtual functions built in to handle these complications for you.
SHMUP-DEV » SHMUP DEV FORUMS » Training Grounds » Tutorials
Art Of Collision [part 1] : Gunbird Collision
Print