Hierarchical Oriented Bounding Boxes (OBB)

In this OGRE demo, the player is able to shoot out small bullets (considered points) to hit the character. The collision detection check is hierachical, meaning that the check is done on the larger, less accurate bounding volumes before checking their smaller, more accurate children recursively. This reduces the time complexity from O(n) to O(lg n), assuming a more or less constant branching factor, which makes the collision detection a lot faster.

OBBs are constructed for each joint of the character and a point+OBB test was to be done to detect collision. However, I transformed the colliding point into the space of the OBB so that this converts the OBB to an Axis-Aligned Bounding Box (AABB). This means the algorithm will run faster since less checks are needed to detect collisions between the colliding point and the AABBs.

In the video of the demo below, bullets are shot towards the character. Notice that the bounding boxes which the bullets have collided into have turned red, indicating that the collision detection algorithm is working.

Video showing the collision detection algorithm at work.
OBBs get highlighted in red when the bullet hits them.

Note: Scene setup done by Goh Cheng Teng. Model and animation provided by Dr Golam Ashraf.

Back To Top

Steering Using Influence Maps

A pre-defined influence map was created to map out the region where the character is not suppose to move into. Using such a steering method, we can prevent characters from moving to prohibited areas by simulating collision detectiong without doing the actual expensive calculations.

In the demo program, the repulsion influence maps are pre-defined using an algorithm to mark out regions which the character will be pushed away. This prevents the character from walking through the obstacles. The force exerted by the influence map onto the character is inversely proportional to the distance from the center of the obstacles i.e. if the character gets nearer to the center, it will be repelled more.

The video below shows the algorithm at work. The character is scheduled to walk straight through the obstacle but her path is changed due to the repulsive forces. The white markings on the ground indicates the influence map (which will be hidden in actual games).

Video showing how a character steers round obstacles due to influence maps

An enhancement made to this program is that the influence map will affect the character less as it is more perpendicular to the influence force vectors. What this does is that the character will not be repelled by the walls when it is near the walls but not going against the wall.

Note: Scene setup done by Goh Cheng Teng. Model and animation provided by Dr Golam Ashraf.

Back To Top