School Specialization

This was a project that I did as a specialization assignment in school where we had a duration of 4 weeks at the end of the school semester to work on it.

The project I chose to do was a efficient crowd pathfinder. The idea was to make it work somewhat like a survival game where enemies spawn and keep going towards you. The problem I was solving was that it isn't good for the performance if every single enemy searches for it's own path towards you so I reduced the paths needed.

Project Code

Basic Info

Worlds

I chose to use multiple worlds for performance reasons and in a real game there would be another with all the graphics

Collision World is optimized using as few triangles as possible for better collision performance
Navigation World is optimized with more triangles but only where enemies can walk to get better paths

Navigation Mesh

The navigation mesh is created on world creation to make pathfinding possible and fast by only creating it once and saving all the nodes for later use

Octree

The octree is static and created based on the navigation mesh to reduce nodes needed by only creating nodes that is close to the navigation mesh

It is then used to group enemies together and find overlapping paths so the amount of paths can be reduced by giving the same path to multiple enemies

Enemies also use the octree to reduce how many other enemies we collision check against by only doing it against the enemies in the nearest octree nodes

Pathfinding

The pathfinding is done using the A* algorithm to first get a path and is then funneled to get a more realistic path

I am also using multithreading to avoid blocking the main thread to get better performance because the paths are constantly being updated one by one

Enemies

The enemies are simply walking towards the next point on the path it is assigned while also avoiding walls and each other

The enemy models are also gpu instanced to increase performance

How it works
( Gameloop )

Step by Step

Update Player Movement

Update Pathfinding Manager

Remove paths that start in an octree node without enemies
Add paths that start in an octree node with enemies, if it didn't already exist
Loop through all paths and remove the ones that has another path through it
Change path to calculate, if the current one is done

Update Enemy Manager

Set path goal position to player position and assign path to the enemies in the same octree node as the path start
Update Enemies
Update enemy in octree
Update enemy instancing buffer

Update Enemies

Change the target point to the farthest point it can see or one further if the closest point is the same point or further
Collide with other nearby enemies and turn away from them. Go idle if we turn to many times because then there are to many enemies around
Update rotation and movement
Make sure enemy is on the ground and doesn't go through walls

( Pathfinder Manager )

White lines is the calculated paths

( Enemies )

Blue lines is the chosen target point

Middle enemy chose next point because it is close to the one it can see