Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

Advanced search

1390782 Posts in 66796 Topics- by 59536 Members - Latest Member: boruok

April 16, 2021, 06:32:08 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityTownhallC++ Giant Space Battle Game (open source)
Pages: [1]
Author Topic: C++ Giant Space Battle Game (open source)  (Read 61 times)
Level 0

View Profile
« on: April 03, 2021, 02:44:39 PM »

Hey everyone.

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 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 referene 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.

If you're wondering why I posted here instead of devblogs, I don't believe I meet the rules to post this to devblogs since this is essentially a post-mortem thread.

For now I'm calling the project "Space Battle Arcade"

Anyways, thanks for looking Smiley Hope someone gets a kick out of it!
« Last Edit: April 05, 2021, 05:13:00 PM by enigma27 » Logged
Pages: [1]
Jump to:  

Theme orange-lt created by panic