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

Login with username, password and session length

 
Advanced search

1395911 Posts in 67318 Topics- by 60442 Members - Latest Member: JohannesID

October 16, 2021, 07:40:55 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityDevLogs[Star Stretching Light Speed Effect Explanation] Massive Ship Battle Game
Pages: [1] 2
Print
Author Topic: [Star Stretching Light Speed Effect Explanation] Massive Ship Battle Game  (Read 3175 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: October 12, 2021, 05:13:25 AM 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
enigma27
Level 0
**


View Profile
« Reply #12 on: July 02, 2021, 08:04:24 AM »

I created a behavior tree system that is defined completely within c++.
AI entities have a brain which spins up a behavior tree.

The nodes in the behavior tree are heap allocated, which I believe does have some noticeable performance cost.
The reason for this was to easily use virtual methods and inheritance of nodes.
But I think I should investigate managing the memory so that they are all allocated in a contiguous block.
Though I am not certain that is worth doing without a bit more profiling.
The problem I observed is that it is much faster to encode logic within branches (ie if statements) than it is to use the structure of the tree to perform logic.
I think that will be true regardless of how I create the true.
But perhaps worthwhile for a refactor.
All that being said, the performance is not bad with a large number of ships.

The behavior tree nodes are partly event based; using the delegates I created as a way to implement communication events.
For example, nodes listen to updates to the tree's memory (eg like blackboards in other behavior trees).
When a reference to something in memory changes, a delegate is broadcast, and nodes can respond to the change (such as updating cached state, etc.).

However there is some ticking involved in querying state. That can be converted to being event based but that has not been done yet.
When a node in the tree finishes, it broadcasts an event and causes the tree to process another node.

I added a compile time flag to turn on debug logging, but it can be compiled out and removed from the executable.
You can also filter which AI entity you are debugging with a little bit of work with breakpoints and setting values directly in the debugger.



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 #13 on: July 09, 2021, 05:56:07 AM »

Using the behavior tree system I created, I have created an AI brain that lets fighter ships dog fight one another.
I've created several sub trees.
there are subtrees to evade.
subtrees to dogfight.
I ran into some performance issues during rapid state transitions in the behavior tree.
I was able to mitigate most of this by collapsing the complex logic into single nodes in the tree, rather than defining the entire logic based on tree structure.




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 #14 on: July 17, 2021, 06:12:42 AM »

I created a camera system in c++ from scratch to control fighter ships.
fast fastest iteration, I created a tool to tweak parameter in real time, using ImGui.
this let me find the "feel" I was imagining for the ship, without needing to recompile code
being able to pilot the ships let me test fighting ai.
this made me aware that while the ai vs ai tree works well, player vs ai wasn't ideal.
So, there's need to create special case behavior for fighting players to make the game more fun.



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 #15 on: July 24, 2021, 05:50:00 AM »

I've created a starfield environment to give the game some life.
no longer do you have to fly around in pitch black, getting lost in the void.
now there are stars, planets, and a local sun.
the fighters are now lit via the local star's direction vector from the origin.

the planets are also lit from this star.
the earth planet is built by composing many textures together.
I use a sort of mapping texture that selects water/terrain based on color values.
On the side of shadow, the earth-like planet has emissive city lights being rendered

I used no cube maps for the environmental stars.
rather I instance rendered many small spheres that have an emissive shader.
by locking the environmental rendering to the origin, stars and planets appear to be at a significant distance away.
by not using cube maps, I can use the 3d locatiosn of these stars to do things like lightspeed effects.

but right now everything is SDR, and I want to convert to HDR before attempting the lightspeed/wormhole effect.



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 #16 on: July 29, 2021, 04:22:34 PM »





Adding hand-made collision to the large ships so that fighters cannot fly through them.
I tweaked the model editor so it can load in models to define collision shapes.
There now is an XRay mode that lets you see wireframe of the ship with colored rendering of collision shapes.
To debug collision in the editor, you can pilot a quaternion based camera that has a box collision shape attached to it; the camera can fly and collide with objects in the viewport.
Collision is done using Separating Axis Theorem (SAT).
The camera resolves collision by using the minimum translation vector returned from SAT to get the camera out of collision.
For the remainder of the video, I did incremental updates to show what dev on a from scratch project is really like.
First there was a bug with scaling, the ships were much smaller than their collision shapes suggested.
while fixing that, I got distracted with a color bug and fixed that, only to get hit by a shutdown crash. I decided to fix the shutdown crash later.
I then fixed the scaling bug, but still crashing every time I close the game.
The particles size were incorrect, so I would fix that before fixing the shutdown crash.
There were some performance issues, so I increased the spatial hash cell size so that the large ships take up fewer spatial hash grid cells.
Finally fixed shutdown crash, which was due to a special pointer I created called a lifetime pointer.
Essentially there was an edge case situation that didn't account for the global engine pointer being null during a shutdown.
I realized that only projectiles collide with the large ships, I still needed to do ship v ship collision.
I added that bug had many issues with the carrier ship trying to deflect off of the small ships.
I fixed that bug by making the large ship not be blocked by small ships.
I found it funny how the small fighter ships bounced along the faces of the large ship. This is because there was no AI mechanism in place that helped the ship avoid the large ship.

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 #17 on: August 07, 2021, 07:35:13 AM »





An algorithm created to make AI not fly into things (it's not boids).
The high level idea is to create avoidance spheres.
When an ai agent enters a sphere, it avoids the center.
The deeper the agent goes, the more avoidance it has applied to it.

The avoidance removes a portion of its desired direction vector.
We create a vector from the ship towards the center of the sphere; let's call it ToCenterVector.
Then, we project the ships current movement direction onto this ToCenterVector.
This ToCenterVector  is a vector that only contains the movement direction that we do not want.
So if we entirely remove this projection-derived ToCenterVector from the movement direction vector, then the ship will not move towards the center.

But just removing this vector from the movement direction would look rigid and sudden.
It also isn't useful if something (ie another ship) occupies a large of the sphere, as collision can still occur.
So what I have done is remove some percentage of this vector, based on how deep the ship is into the avoidance sphere.
At some specified depth (not at the center) the ship has 100% of the ToCenterVector removed.
With some tweaking, you can achieve really natural looking avoidance.
I created a few debug utilities to help visualize what is going on.
With this many ships, it is difficult to use traditional debugging techniques.
So having visual feedback makes it easy to determine what is happening.
I find that to be true for many things in gameplay programming.

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 #18 on: August 13, 2021, 07:45:25 AM »

My firsts idea was to just slap a collision shape around a camera, but this has some issues.
By surrounding the camera with an OBB (oriented bounding box), we can use that to collide with shapes.
When a collision occurs, through Separating Axis Theorem (SAT), we get a Minimum Translation Vector (MTV) that will get the moving shape out of collision.
We can offset the camera with the MTV, and then project the new position onto a vector from the original camera location toward the player ship, to get a new position to place the camera.
This works in many cases, but the MTV approach has some issues.
Most noticeable is when the camera is far behind the colliding object; in this case the MTV can actually create more distance between the camera and the player, rather than shortening the distance.

So, my second idea to fix this was to ensure that we are always moving the camera towards the player ship.
When a collision occurs, we do not know how far towards the ship we should move.
So, I take inspiration from the binary search algorithm, and move the camera half of the distance between its current position and the player position.
We then check for collision again.
If we collide, we move it another half distance towards the player and repeat.
if we do not collide, we move it a half distance away from the player (half of the distance between camera current position and previous position).
This allows the camera to home in on the correction location that is not colliding.

This binary searching camera works surprisingly well, but it does have issues.
When there is collision between the ship and camera, but the camera doesn't collide, we can end up in a situation where we cannot see the player ship.
So, rather than surrounding the camera with a collision shape, we create a collision shape from the player to the camera.
We only shrink this shape from the end on the camera.
This means we will never get collisions between the camera and the player ship.
This is the camera system I am currently using.

Unrelated to cameras, I also fixed the collision on the large ships so the the small fighter ships would not clip into them as easily.




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 #19 on: August 21, 2021, 06:34:29 AM »

What's a game without something to do?
My ships can dogfight one another, but there was no real match progression.
I created some objectives that must be destroyed on the large carrier ships.
After destroying all the objectives, you can destroy the carrier ship.

So, it becomes a race to see which team can take down the other team's carrier ship.
Currently the objectives do not have any gameplay, other than being able to be destroyed.
There's a gun turret, a generator, and a satellite.

In this update I also fixed some bugs with shield effects so that they better conform to the model.
Rather than scaling up a shield effect, which doesn't correctly wrap a model, I slide the shield effect's vertices based on the mesh normal. seems to have a much better look.
Though there are still issues with flat shaded models, that do not have smooth normals. (creates seams).
 Probably the easiest way to fix that is use smooth normals and add in bevels at locations that to define sharp edges.

To test all of this, I needed a cheat system.
So I defined a way to create cheats in the engine and add your own to it.
The next update will be to add gameplay (like turrets shooting at you) to all of these.



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] 2
Print
Jump to:  

Theme orange-lt created by panic