Pathfinding 1000s of units over a large map efficiently?

[wispy ruin]

Looking for some pointers on how to achieve this:

• I'm developing a 'Total War' style game (many units, large maps, varied terrain)
• There is no overlapping/underhang terrain paths so the map coordinates can be completely 2D
• Units will need some degree of local avoidance boids flocking style grouping up to move as a mass
• Not all units path across the same terrain, eg some can or cannot cross terrain types
• Likewise not all paths are weighted equally; some are faster/slower to move on for specific units, or provide more/less defense so every individual unit may potentially have its own prefered path

As far as my own research into this has gone, flow fields seems to be the ticket, but the part I'm not sure how to reconcile is that flow-fields seem to assume all units move over the same terrain at the same speed/cost weight. If Unit X move fast on Roads and Unit Y moves fast on Mountains, I can't use the same flowfield for both, can I? What's the cost of having dozens of flow fields? Is there a better alternative?

[turbid hawk]

The cost is just more memory. And possibly less parallelization, if your algorithm is highly patallelized.

Either way, the flow fields are probably gonna only one part of the algorithm. The main challenge would be to generate the path for each unit and move it along the path.
You might need to look at multithreaded implementations of A* or implement one yourself.

[wispy ruin]

Good points. I havent done multithreading in unity before so that'll be an area Ill have to research into

[hardy beacon]

In general if there are different units with different characteristics that would affect how they pathfind, you need a separate flowfield for each of those unit types.

Each flow field is also tuned for one specific destination. If you have multiple destinations or destinations that change/move during the game, you need one flow field for each destination and you need to recalculate them when the destinations change.

In short flow fields are really optimized for situations where you have a lot of units that share pathfinding characteristics (movement characteristics and the destination) and the destinations don't change much.

Something like a tower defense game lends itself well to this.

[manic wind]

Hey! Your project looks really interesting 😄
I’d love to see how it’s coming along, if you don’t mind sharing.
Also, I’d be curious to hear your thoughts on it!

One small thing I noticed: the standard A* algorithm you’re planning might get pretty slow with a lot of agents.
Instead of using it the same way everywhere, you could try adjusting the algorithm’s weights depending on the terrain — might help with performance.

[pulsar whale]

Flow fields are convenient, because if you unit is pushed off the path through local avoidance, it can still find its way efficiently by sampling the flow field at its new position. However, they're not the only way to do it

If your terrain does not change, you can actually cache path pairs. Even if it does change, there are ways to deal with that, too; Eizenhorn goes into depth a bit on their system for Diplomacy Is Not An Option:
https://discussions.unity.com/t/unity-dots-case-study-in-production/716170
and Eizenhorn's post here:
https://discussions.unity.com/t/how-to-organize-the-data-for-flowfield-pathfinding-what-datastructures-to-use/893198/3

[wispy ruin]

Thanks! I was having problems with the re-written terrain shader that turned into a huge slog, I only just fixed it so that all the terrain layers use dither blending based on the pixel camera
I only just finally fixed that so I'm closing the book on shadering for the time being and opening the book on starting to figure out this pathfinding stuff.

Yeah terrain-based weights on the pathing was in the plan. The more I look into how I want them to navigate the more it seems like every unit needs to have its own intelligence. My first attempt is going to be to generate a node graph of terrain by type and A* through that, and rely on short range searches to steer the immediate surroundings only a few cells out in the small true size grid

[wispy ruin]

pathfinding nodes grouped by terrain type

I am wondering if it would make more sense to subdivide very large nodes, even if the resulting groupings are still all the same terrain type

[wispy ruin]

implemented voronoi cell division for the metagrid, right now it starts to noticably lag around 800 agents

and thats without multithreading, and before doing any kind of pathfinding logic beyond 'navigate the metagrid of regions via center points'