To get better at c++, problem solving, vector math, programming, and rendering -- I embarked on a project to build a game from scratch in c++ and modern OpenGL.
The crux of this engine revolves around the collision system I wrote. Rather than use a library like bullet or PhysX I wanted to learn a bit about these types of problems. In a data structures course I was introduced to spatial hashing. With my spatial hashing I essentially hash a cell location (a vector3 of ints) into a single value and use that as a key to a hashmap. Separately I discovered the separating axis theorem (SAT). Which is a way to test collision between two convex shapes.
I've combined these two ideas to achieve performant collision. With a basic collision implementation, testing collision between n ships means that for every single ship, you must check that against every other active ship in the game. So that is n*n collision tests. So I figure O(n*n).
What I've done instead is create a world grid of cells. Before checking collision, a ship will project the vertices of its minimum bounding box onto the spatial hash grid. This tells me the cells that the ship overlaps. I hash these cell locations and look up the the contents of the overlapped cells. I then only do SAT collision with the contents of those cells. The vast majority of the time the cells are empty, except for the ship doing the test, so no collision tests are done. So, I figure the expected case is n collision tests; ie O(n). Technically I guess it could still be O(n*n) if all the ships are within a single cell. But the cells are sized relative to the fighter ships, there's really not room to fit all the ships within a single cell. So this is not practically going to happen.
Since this is a learning project, I've attempted to implement these algorithms without referencing code online (I did reference high level ideas of the algorithms). So keep that in mind if viewing the code, there's probably plenty of optimizations that can be done. It isn't glorious code.
This game is open source and not commercial.
DevBlog 1 - Spatial Hashing and Separating Axis Theorem
Space Battle Arcade uses a custom collision implementation designed for large scale battles. It leverages Spatial Hashing and Separating Axis Theorem.
Posted by wafflemaker72 on
