Week 4#
This week I Implemented massive Pathfinding in my game. It can manage 40 000 entities at 60~70 fps.
(I plan to support only 20K entities maximum when I release).
This is a basic map of 1500x1500x128 tiles :
My goal is to find a path from point A to point B.
Running a simple Astar pathfinding can takes 5 seconds in the worst case scenario on this map, so this algorithm is definitely not suitable for managing 40K entities.
I tried to simplify the map by using Quadtree. The results were way better, but still not satisfying. The more collisions there are on the map, the less effective the graph becomes :
Finally, I implemented HPA for the pathfinding, which consists in dividing the map into uniform chunks (in blue) and then pre-computing all the possible paths (in green) between each chunks. Besides building the graph which take 4~ seconds with my implementation, It give result really fast ! Once all the paths are cached, but I do a astar on the node of the graph and at this point it's almost like a lookup table. The worst cast scenario computes a path within 5~10 milliseconds, but most of the time it's under 1ms :
More details here :
https://i.imgur.com/A17eU6H.png gives this graph :
https://i.imgur.com/WilwVKx.pnghttps://i.imgur.com/hzEGOQ9.png ->
https://i.imgur.com/LfyFO0J.pngI will later make another iteration of my HPA implementation to make the entities behave more like a crowd, I have some ideas how to do it, but this is not a priority for now.
The rendering part is also important. Instead of computing and sending 40 000 matrices each frames for the entity, I use instanced rendering to only send 4 float to the GPU for each entity (X, Y, Z and an Angle. I then compute these data directly inside the vertex shader). Later, I think I will use 8 float (8x32bit) per entity to store other information such as the size, the color, animation...
Week 5#
During this 5th week of development, I've reduced memory consumption from to 1.8gb to 400mb by temporarily compressing unused chunks(32x32x32 blocks of 4bytes each) with zlib and did massive code clean up.
I don't have much to show visually this week, so I will show you the process I follow to make the assets I use in my game :
And the result :
https://www.youtube.com/watch?v=1dwTI0gBMkQNext week I will be focusing on making a playable prototype.