Ray Casting Hierarchical Bounding Volumes API
CSS452 Game Engine Development course studies the technical fundamentals and implementation details of a game engine. Topics include software architecture, input, resource management, textures, animation, coordinate systems, object behaviors and interactions, camera manipulations, illumination and special effects, physics, and scene management. Based on the 2D game engine developed by Dr. Kelvin Sung. In this course, I collaborated with 2 other classmates to extend this engine to utilize Hierarchical Bounding Volumes (HBV) API to improve ray cast collision performance from O(n) to O(log(n)). This API can be used by other game developers of this game engine to improve their performance. I developed two games to demonstrate the ray cast HBV API.
Play the Two Games that Use the HBV API Here
(Must Run on Chromium Browser)
Shooter Level: Red ray cast sent from player-character towards the right that intercepts the HBV head node but none of the blue boxes. The grey boxes are HBV nodes. The darker the grey boxes are, the more layered they are.
Turret Level: Red ray cast sent from turret game object towards the player, intercepting various HBV nodes and one of the blue boxes. When a blue box is intercepted, it turns red.
When a ray cast is projected (the red line) it will not check if it collides with all the game objects (the blue boxes). That would be O(n), very time-consuming. It will instead check if it collides with the head node of the HBV, and if so, then check if the ray cast collides with any of the node's children... recursive divide and conquer until it reaches a leaf node, and checks if it hits any of the game objects in that leaf node. This is O(log(n)), far more efficient to check for ray cast collisions. However, it takes O(n * log(n)) to create an HBV, so it should be done sparingly. I designed and implemented the HBV data structure, how it is constructed and fits all the game objects into leaf nodes, and how a ray cast checks for HBV collisions.