Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411280 Posts in 69323 Topics- by 58380 Members - Latest Member: bob1029

March 28, 2024, 06:06:24 PM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityTownhallC++ Giant Space Battle Game (open source)
Pages: [1]
Print
Author Topic: C++ Giant Space Battle Game (open source)  (Read 1076 times)
enigma27
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

I like to make tutorials and devblogs. youtube: https://www.youtube.com/channel/UC9CQOdT1A9JlAks0-PF5vvw
moller trumbore ray triangle intersection:
https://youtu.be/fK1RPmF_zjQ?list=PL22CMuqloY0pRNhvBXowdpMtEin8-RFtb
Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic