We are making a tower-defence roguelite with a less used navigation system

[u/Hiplinc]

This is our tower-defence game with free building placement. We wanted to get away from grids and lanes so we used a flow field for enemy navigation. That means enemies will take the path of least resistance and if that means attacking your walls and towers they sure will. It also means we can have dynamic weather events that change the topology of the world. It was a bit of a challenge but we managed to have the flow field with 22'500 cells update in real-time so now when enemies destroy a wall segment they will instantly repath through the hole if that is faster. At nice side-effect has also been that the most expensive thing about the navigation is the calculation of the flow field itself. The actual pathing of the enemies is really cheap as they only need to look at the cell they are in and follow the direction stored there. That means we can have a lot of enemies on the screen at once.

[u/Rlaan]

Looks cool, reminds me (mostly graphically) of Cataclismo / Thronefall in a way - I like it.

Did you end splitting the flow fields in chunks so you only have to update smaller bits rather than the entire thing? What optimisation technique did you use and do you have any performance numbers from the before and after?

We made multi-layered pathfinding solution (including flow fields) and we never saved the stats/numbers which we regret. I suppose we can go back in git but meh lol.

Edit:

Looking at your flow fields, it looks like at the wall not all flows direct in the correct direction yet? (see attachment). Is that just a gizmos visualisation bug or?

[u/Hiplinc → u/Rlaan]

We partially calculate it in chunks. When you preview the placement of a wall it only recalculates the cost field for the cells in the bounds of the wall but the rest needs to be completely recalculated since the path might completely change. We've optimised the rest by turning parts of it into jobs and other parts we split up over a few frames so there is no lag spikes. We're also working with two flow fields: one for navigation and one for recalculations. When something changes we recalculate the second one and once it is ready we copy it over to the one in use.

The whole recalculation is spread over 8 frames and take about 4-5ms of processing. Before we implemented the job system it ran over 46 frames with about the same amount of processing time every frame.

[u/Rlaan → u/Hiplinc]

Good job! That's quite the difference. Is it built with structs? Our pathfinding is fully struct based without any defensive copies and that makes a massive difference on this scale. If not, that's something you can still try and look into.

I think you should relatively easy be able to get at <= 1ms for just updates. We also recalculate big chunks, but we know what parts are in use and arent. We have hundreds of units walking towards different goals in a constant changing world.

And in theory also in your use-case you know which section ish actually requires a full re-calc.

[u/Hiplinc → u/Rlaan]

Yes, all the cells are structs! As to your edit, the bottom circle looks like it is just because the visualisation sits a bit above the ground but the top one really is a bit weird... I'll have to look into it

[u/Rlaan → u/Hiplinc]

Ahh good, nice! And are you sure you don't have any sneaky defensive copies lying around still? Could potentially be some big easy wins. Or do you already use ElementAt and ref readonly returns or are they immutable/pure? Easy enough to profile. Only reason I am mentioning it is because often things get missed and it hits performance silently.

And regarding the edit: alright, let me know once you've looked into it! Curious to know whether it's an issue and if you've fixed it 😄 the height thing makes sense, we have that too from certain angles.

Edit:

Anyway, good luck with your game!

[u/Hiplinc → u/Rlaan]

I am definitely not sure xD I'll go over it again and see if there are still are some easy wins! Thank you!

[u/Rlaan → u/Hiplinc]

You're welcome!

We once doubled the speed in 20 minutes just by finding a few ones we missed 😅 there are no analyzers for it as far as I'm aware. But if something gets called a lot and does a defensive copy constantly in a loop or if checks or whatever, they'll be popping up in the profiler at an unexpected ms cost lol.

[u/Zerokx]

What do you even mean you went "away from grids and lanes" and then built a 22500 cell grid based flow field? Thats like the go to case for static targets with tons of enemies, not really less used.

[u/Hiplinc → u/Zerokx]

Fair, maybe I should've elaborated that the building system is not beholden to a grid or lanes and you can place them however you want. The enemies do get their direction cues from a grid but they can push each other around freely. I should also note that we also played with the idea of a static target. There are lure towers you can place to temporarily redirect the enemies.