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

Login with username, password and session length

 
Advanced search

1392736 Posts in 66997 Topics- by 59854 Members - Latest Member: N1mb4t

June 23, 2021, 10:26:23 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityDevLogs[Particles Update 8] 3p Massive Ship Battle Game
Pages: [1]
Print
Author Topic: [Particles Update 8] 3p Massive Ship Battle Game  (Read 1493 times)
enigma27
Level 0
**


View Profile
« on: April 24, 2021, 11:16:48 AM »

Latest Update:



______________________________________________________________________________________________
Original Post:

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.

Got clarification and it is fine to post this in devlogs (the game is mostly done and this is basically a post-mortem thread). So I'm Essentially moving my townhall post here, rather than continue the thread in townhall (unfortunately I cannot delete the town hall post).

« Last Edit: June 20, 2021, 03:45:50 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
vivaladav
Level 1
*



View Profile WWW
« Reply #1 on: April 24, 2021, 08:52:54 PM »

Hey, it's nice to see another C++ dev on here, I was starting to feel pretty lonely!

As you have already finished the development of this game, are you planning to go back to it to add new features/content or are you going to move to a new project?
Logged

Creating "Virtueror, the virtual conqueror" (RTS + 4x + RPG)

[Wishlist on Steam]
[TIGS devlog][YouTube devlog][website]
enigma27
Level 0
**


View Profile
« Reply #2 on: April 27, 2021, 03:32:59 PM »

Hey Smiley
There were a few features I ended up cutting. I might go back and implement them, but I think it is more likely I will start another project. I want to get some experience with DirectX11 (eventual 12 and vulkan too). So I think my next c++ project will be something with those. I'm not sure what to make though. Preferably something smaller scoped so it doesn't take nearly as long to make. But first I have a few game dev books I want to read -- and explore some other engines to get an idea of their feature sets. In the mean time I'm going to go back through these devblogs and freshen up the thumbnails and descriptions since I kind of rushed all that when creating the videos.
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
enigma27
Level 0
**


View Profile
« Reply #3 on: May 02, 2021, 03:29:07 PM »

Update: Ray casting a line through my spatial hash.  Wizard

(skip to 2:48 to get right to the spatial hash stuff)




My spatial hash grid has the ability to look up collision shapes within a given spatial hash cell.
But I did not really have the ability to easily query a line of individual cells.
If I wanted to trace a line through the spatial hash, I would need a shape encompassed the entire line.
This was extremely wasteful, as it would include a lot of insignificant cells (imagine a big box around the line trace).
So I wrote code that determines which cells the line passes through.
I can then run a special query only for those cells, which is much faster than a large box overlap.

The goal of this this ray casting system is assist projectiles.
Since projectiles are moving very fast, there is the potential that they may skip space if there is a large delta time.
But I can determine the line representing the projectile's movement since the last frame.
I can use this line to figure out which cells it intersects, and query those cells to see if any ships are within that portion of the grid.
If this line then also intersects any shapes contained within a cell, then it should process that as a collision.


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
jarmick
Level 0
*



View Profile
« Reply #4 on: May 02, 2021, 03:51:42 PM »

Rad.  So inspiring to watch someone test, think, and make.  Hypnotizing - similar to watching Jonathan Blow's development webcasts.  Look forward to following your progress.
Logged
enigma27
Level 0
**


View Profile
« Reply #5 on: May 09, 2021, 05:57:24 AM »

Thanks, I appreciate the kind words Smiley
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
enigma27
Level 0
**


View Profile
« Reply #6 on: May 16, 2021, 06:56:33 AM »

End goal is to stretch projectiles from frame(n-1) location to frame(n) location.

Here demonstrates something I often encountered when doing things mostly from scratch:
you very often find yourself needing to implement supporting systems to implement what you want.

I wanted to just create a debug visualization of of my projectile stretching idea, but needed a separate place to test that.

So, I did some house keeping and created a level system.

This necessitated some UI code, so I would not have to hardcode which level loads every time I wanted to change levels.
Another case of needing supporting system Wink
I went with the IMGUI library as it is really easy to integrate and is set up for GLFW/OpenGL.

Now I have created a "projectile editor" level where I can visually debug the projectile stretching behavior.
But this behavior is not implemented yet, that will be in the next update.




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
enigma27
Level 0
**


View Profile
« Reply #7 on: May 23, 2021, 07:51:27 AM »

With editor ui and a level system integrated, I can visualize my idea for stretching projectiles.

It roughly works like this:
The projectile end points are determined based on delta time, and the distance between them.
The model is offset and scaled so that we can use one tip of the projectile as something like a pivot point
The model is first scaled in local space (eg along z axis) by the distance between the two points.
Then the model is rotated so that it is moving in the correct direction of the projectile.
After rotation, the model is translated to the correct location.
Now the projectile is essentially occupying the space between the last frame's position and the current frame's position.

I skipped a bit of steps to be conversational, SAProjectileSystem.cpp `Projectile::stretchToDistance ` defines actual stretching implementation. Code in video description. Wizard




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
enigma27
Level 0
**


View Profile
« Reply #8 on: May 30, 2021, 01:54:02 PM »

How I made a custom engine project modifiable by the players. Toast Left





I decided I wanted my game to be modifiable.
To make sure the mod tools worked well and were bug free, I decided it was best to use them to build the actual game.
When running the game, you have tools available to create and delete mods.
These ultimately serialize out as json files, which makes it easy to change via a text editor.
When creating mods, all files (such as 3d models) are placed within the created mod folder structure.
You can then load these models at runtime and configure their collision shapes within the editor.
Underneath the hood, collision is achieved via separating axis theorem.
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
enigma27
Level 0
**


View Profile
« Reply #9 on: June 08, 2021, 02:38:01 PM »

Time dilation allows me to speed up or slow down the passage of time.
The way this is implemented is rather simple.
The frame's global delta time is multiplied by a time dilation factor.
As I prepared my space ship models for collision, I needed a way to test if it was working.
Unfortunately for debugging projectiles are fast moving objects.
The addition of time dilation allows me to observe fast moving objects in a slow motion.
I even created the ability to manually step the frame time.
While on the topic if time, I created an engine feature of being able to set timers.
Because of the systemic nature of timers, I created an automation test system.
This allows me to make changes to the timer system and catch bugs without needing to test the game.



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
enigma27
Level 0
**


View Profile
« Reply #10 on: June 14, 2021, 04:00:40 AM »





I've set up firing an a lot of projectiles to push performance to its limits.
To assist with this I created various debug tools, such as a projectile tweaker.
Projectiles are configured via a json file and can be serialized to the disk, and referenced by other configs (such as a fighter ship config).
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
enigma27
Level 0
**


View Profile
« Reply #11 on: June 20, 2021, 03:48:12 PM »





I created a particle system that uses instance rendering to efficiently draw thousands of particles with very little overhead.

I had a nondeterminism bug that renderdoc helped me solve.
If I recall correctly, the nondeterminism ultimately came from a delegate subscription happening in different orders on release mode. The instance render and the clear screen were subscribed to the same delegate but the order of subscription was not well defined. I've created my own c++ delegates, which are like c# delegates, using templates.
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