u/Duc_de_Guermantes

I think my favorite part of gamedev is adding these small things

The game name is Cult Defense. What do you guys think?

I was having a problem in my game where FPS dropped dramatically when unit count rose above 400 units. The source of that problem was unit targeting: every frame, every unit searched through the entire enemy array to find the nearest targetable enemy. That's a O(n²) cost of operation, very expensive, very slow, tough on large quantities of enemies.

My first solution was to stagger these searches. instead of every unit being active every frame, only about 10 units searched for available enemies every frame. That worked - but now units were suuuper slow to respond. During large battles a unit could take almost 3 seconds to properly target and shoot at an enemy, sometimes even longer in cases where the unit they targeted was already dead by the time they were in range.

By this point multiple people were already telling me to look into spatially partitioning the units: assigning a cell to each unit, and only searching neighboring cells for enemies. The problem with that is my units have an engagement distance of 15, 20, some even 30 meters. The circle where the player can place cultists has a radius of 35. The only way spatial partitioning would work is if the cell size was enormous or if every unit searched through a large amount of cells, which would reduce the benefits.

But it did lead me to realize something during gameplay: most units, both cultists and the police, tend to clump together. The nearest enemy of unit A is almost always the nearest enemy of unit B,C and D.

This led me to create this TargetCache solution: every time a unit searches for a nearby enemy, it STORES that enemy in a cell. And after that, when a different unit wants to find an enemy, it first asks the TargetCache "did anyone else already find an enemy close to the cell I am standing on?" and if yes, "how long ago was this information stored?".

This saves a TON of performance. In my tests, only about 1 out of every 10 units actually needs to search through the entire enemy array. The others just grab the information from that first unit.

This does have a small downside - units no longer always target the absolute nearest enemy. But the difference is always smaller than the cell_size, which on a battle with >1000 units is impossible to tell.

So far this was the greatest improvement to performance on my game, reducing operations such as findNearestEnemy from 4-5ms, to 0.5ms. Right now the biggest hit on performance are on the graphics side (>1000 units with animations and shadows enabled) and agent avoidance (RVO), which are the next things I'm going to tackle.

Really happy with how the explosion effect turned out

Sent it for review last week and today it was finally approved! I've been sharing it with everyone lol

I'm still updating it, but if anyone has feedback I would love to hear it.

Almost makes me want to make a full game like this lol. Unfortunately it's too unreadable for my use case.

But it's going to be super helpful for highlighting selected units

Not shown in the video: the 20FPS counter on the top right lol

The godot navmesh tools are so, so helpful.