Collision detection is a major problem in game programming; not because the detection itself is difficult to implement (most of the time a simple distance check is enough) but because the game engine has to cope with thousands of entities for which the naive implementation yields catastrophic results due to the O(n2) property of the algorithm. This is not only true for collision detection but also for AI vision, finding entities within a given distance (useful for grenade damages) and so on. I will focus here on collision detection through a simple example but the technique can be extended to more sophisticated scenarios.
In the example, I generate 100 discs which bounce on each other inside the dialog window. A snapshot is given on Figure 1. The collision method is a simple square-distance law (the square of the distance between two candidates is tested against the square of the sum of their bounding radius - to avoid computing a square root). When a given disc is found in collision with another one, its speed is updated for the next frame.
In the naive implementation, each disc entity is tested with all the others to detect eventual collisions leading to the O(n2) performance. With N entities, there are N(N-1)/2 tests to perform (it is not necessary to test an entity with itself and when A has been tested with B, there are no need to test B with A because the collision test is symmetric). However, for more general tests, we may have to do up to N(N-1) calculations. As a consequence, I will use N(N-1) as a reference for the rest of the post. With 100 entities, this results in 9900 tests per frame.
Looking at Figure 1, it looks obvious that it is not necessary to test the entity in the top-left corner with the entities in the bottom-right corner as there is no chance that they could be colliding (they are too far away from each other). By looking at nearby entities only, we can reduce the number of tests to do. For example, if we have two equal sets of particles (each set being far away from the other), we have roughly 2(N/2)2=N2/2 computations to do instead of N2 ones. By having more sets we can reduce the number of computations even more.
The problem is to get the list of nearby entities as it is itself a variant of collision detection. There are clever solutions to cope with the problem that are well known to game developers such as binary space partitioning trees, quadtrees/octrees etc. For example, in quadtrees we begin with a main (global) rectangle which contains the whole world and subdivide it in four equal rectangles by using two split axis (three split axis and cubes in the case of octrees). Each rectangle is then subdivided again and so on. Finally, each entity is placed in a leaf (a node with no subnode) of the tree by testing its centre position against the node boundaries. Octrees and BSP are often used to accelerate the rendering of a 3D world by testing each node with the view frustum in order to reject large batches of polygon that are out of the view area. If you are already using them for your rendering pipeline, you may use the existing tree although I prefer having a separate tree for AI as the requirements are a bit different (and so we split the tree differently).
From experience I would not recommend using quadrees and octrees, except in very specific cases. The major issue is that we divide each node equally without taking care of its dimensions. In classical FPS or action 3D worlds, the height of the map is usually much smaller than its transversal XY extends (so-called "2.5D problem"). By dividing equally each node, we end up with cubes that have extremely tiny height which make them almost useless or, at least, not optimal.
I now consider that a better way is to rely on a specific BSP tree where the cut planes are restricted to the major XYZ axis. Each node is then divided in only two nodes according either to the X, Y or Z axis. To prevent the dimension issue, I use the plane that cuts the largest dimension axis. In the case of Figure 1, where the dialog is larger on the X axis than on the Y axis, I first cut the rectangle in the centre along the vertical axis. I then cut along the horizontal axis and so on. An example of three subdivisions is given on Figure 2.
The implementation for the 2D case is straightforward:
class Node
{
public:
Node(const Vector2& rCenter, const Vector2& rDim)
{
this->m_vCenter = rCenter;
this->m_vDim = rDim;
this->m_pParent = null;
this->m_pLeft = null;
this->m_pRight = null;
}
~Node(void)
{
/* recursively delete children nodes */
delete this->m_pLeft;
this->m_pLeft = null;
delete this->m_pRight;
this->m_pRight = null;
}
void subdivide(double fMinDim)
{
/* subdivide along X */
if(this->m_vDim.x >= fMinDim && this->m_vDim.x >= this->m_vDim.y)
{
this->m_pLeft = new Node(Vector2(this->m_vCenter.x - this->m_vDim.x * 0.5, this->m_vCenter.y), Vector2(this->m_vDim.x * 0.5, this->m_vDim.y));
this->m_pRight = new Node(Vector2(this->m_vCenter.x + this->m_vDim.x * 0.5, this->m_vCenter.y), Vector2(this->m_vDim.x * 0.5, this->m_vDim.y));
}
/* subdivide along Y */
else if(this->m_vDim.y >= fMinDim && this->m_vDim.y >= this->m_vDim.x)
{
this->m_pLeft = new Node(Vector2(this->m_vCenter.x, this->m_vCenter.y - this->m_vDim.y * 0.5), Vector2(this->m_vDim.x, this->m_vDim.y * 0.5));
this->m_pRight = new Node(Vector2(this->m_vCenter.x, this->m_vCenter.y + this->m_vDim.y * 0.5), Vector2(this->m_vDim.x, this->m_vDim.y * 0.5));
}
/* recursive behaviour. !! watch for stack size !! */
if(this->m_pLeft != null)
{
this->m_pLeft->m_pParent = this;
this->m_pLeft->subdivide(fMinDim);
}
if(this->m_pRight != null)
{
this->m_pLeft->m_pParent = this;
this->m_pRight->subdivide(fMinDim);
}
}
private:
Vector2 m_vCenter, m_vDim;
Node *m_pParent, *m_pLeft, *m_pRight;
};
The algorithm is obvious for entities within the same node (we know that we have to test the entities contained in the same node) but the detection is harder for the entities nearby the border of nodes as they may be colliding with entities contained in adjacent nodes. To cope with this, we should assign entities to the whole tree and not only to the leafs.
First, each node should have a list of belonging entities. An entity belongs to a node if it is contained within the node. If the entity lies on the border of the node, it belongs to a parent node:
typedef enum
{
NODE_TEST_INSIDE=0,
NODE_TEST_OUTSIDE,
NODE_TEST_BORDER,
} node_test_e;
class Node
{
public:
node_test_e testPoint(const Vector2& rCenter, double fRadius)
{
/* test if inside */
if((rCenter.x - fRadius) >= (this->m_vCenter.x - this->m_vDim.x) && (rCenter.x + fRadius) <= (this->m_vCenter.x + this->m_vDim.x) && (rCenter.y - fRadius) >= (this->m_vCenter.y - this->m_vDim.y) && (rCenter.y + fRadius) <= (this->m_vCenter.y + this->m_vDim.y))
return NODE_TEST_INSIDE;
/* test if outside */
if((rCenter.x + fRadius) < (this->m_vCenter.x - this->m_vDim.x) || (rCenter.x - fRadius) > (this->m_vCenter.x + this->m_vDim.x) || (rCenter.y + fRadius) < (this->m_vCenter.y - this->m_vDim.y) || (rCenter.y - fRadius) > (this->m_vCenter.y + this->m_vDim.y))
return NODE_TEST_OUTSIDE;
/* if neither inside nor outside, then it's touching the borders */
return NODE_TEST_BORDER;
}
Node *findNode(const Vector2& rCenter, double fRadius)
{
node_test_e eTest = testPoint(rCenter, fRadius);
/* if we are inside the current node check the children */
if(eTest == NODE_TEST_INSIDE)
{
if(this->m_pLeft != null)
{
eTest = this->m_pLeft->testPoint(rCenter, fRadius);
if(eTest == NODE_TEST_INSIDE)
return this->m_pLeft->findNode(rCenter, fRadius);
}
if(this->m_pRight != null)
{
eTest = this->m_pRight->testPoint(rCenter, fRadius);
if(eTest == NODE_TEST_INSIDE)
return this->m_pRight->findNode(rCenter, fRadius);
}
/* if not inside any children, then it's the current node */
return this;
}
/* if we are outside or touching the borders, check the parent node */
if(this->m_pParent != null)
return this->m_pParent->findNode(rCenter, fRadius);
return null;
}
};
To retrieve a list of collision candidates for a given entity, we have to test the entities contained within the same node but also to all the entities contained in the parents node plus the children node that are touching the entity upon testing. This translates to:
class Entity;
class Node
{
public:
List<Entity*> getCollisionCandidates(const Vector2& rEntityCenter, double fEntityRadius)
{
List<Entity*> ret_list;
/* add all touching nodes */
if(this->m_pLeft != null)
{
node_test_e eTest = this->m_pLeft->testPoint(rEntityCenter, fEntityRadius);
if(eTest != NODE_TEST_OUTSIDE)
ret_list += this->m_pLeft-getCollisionCandidates(rEntityCenter, fEntityRadius);
}
if(this->m_pRight != null)
{
node_test_e eTest = this->m_pRight->testPoint(rEntityCenter, fEntityRadius);
if(eTest != NODE_TEST_OUTSIDE)
ret_list += this->m_pRight-getCollisionCandidates(rEntityCenter, fEntityRadius);
}
/* get belonging entities of self and parents */
ret_list += getCollisionCandidates2();
return ret_list;
}
private:
void getCollisionCandidates2(void)
{
List<Entity*> ret_list = this->m_sNodeEntities;
/* parent list */
if(this->m_pParent != null)
ret_list += getCollisionCandidates2();
return ret_list;
}
/* implementation is up to you */
List<Entity*> m_sNodeEntities;
};
Finally, each entity should keep a track of its own node and this node should be updated when the entity moves:
extern Node *g_pRootNode;
class Entity
{
public:
Entity(void)
{
this->m_pCurrentNode = null;
}
private:
void updateNode(void)
{
/* locate the current node either by update or from the root node */
if(this->m_pCurrentNode != null)
pNewNode = this->m_pCurrentNode->findNode(this->m_vCenter, this->m_fRadius);
else if(g_pRootNode != null)
pNewNode = g_pRootNode->findNode(this->m_vCenter, this->m_fRadius);
/* if the node has changed */
if(this->m_pCurrentNode != pNewNode)
{
/* remove from old node list */
if(this->m_pCurrentNode != null)
this->m_pCurrentNode->unsubscribe(this);
/* add to new node list */
if(pNewNode != null)
pNewNode->subscribe(this);
this->m_pCurrentNode = pNewNode;
}
}
Node *m_pCurrentNode;
};
class Node
{
public:
void subscribe(Entity *pEntity)
{
this->m_sNodeEntities.add(pEntity);
}
void unsubscribe(Entity *pEntity)
{
this->m_sNodeEntities.remove(pEntity);
}
};
It is usually not necessary to traverse the whole tree every time we need to get the current node as the findNode function can eventually go back to a parent node. That way, we keep the amount of processing power used to a minimum. This kind of optimization is important because the function is going to be called frequently for some entities.
The application was tested and yielded a maximum performance over the N2 reference of 3.2% (more than 30 times speed increase) for nodes of less than 32x32 pixels. The performance changed with the number of nodes but did not do better with more subdivisions. More nodes usually give better results (up to some point) but also require more RAM to be used. You should test various node sizes and see what behaves best for your application.
Also, with the same node size, more than 99% of the nodes were containing 5 entities or less. So it might be interesting for you to have a look at how many entities are contained in your nodes and change your implementation of the list holder class.
As a conclusion, the results are worth the trial since the complexity of the implementation is relatively low. It should be easily scalable to the 3D or 2.5D case with very few modifications. Also, it may easily be modified to cope with the find-in-radius and find-in-view-cone functions required in many games.
[⇈] Top of PageYou may also like: