Which navigation methods would be the most performant and flexible for a game with a very large number of AI on a dynamic playfield?

user_6009901 0
Viewed 1713

I'm not 100% sure what factors are important when deciding whether to use Unity's NavMesh vs an advanced pathing algorithm such as HPA* or similar. When considering the mechanics below, what are the implications of using Unity's NavMesh vs rolling my own algorithms:

  • Grid based real-time building.
  • Large number of AI, friendly, hostile, neutral. Into the hundreds. Not all visible on screen at once but the playfield would be very large.
  • AI adheres to a hierarchy. Basically does things where AI entities issues commands, receive commands, and execute them in tandem with one-another. This could allow for advanced pathing to be done on a single unit that relays rough directions to others where they can commence lower-level pathing to save on performance.
  • World has a strong chance of being procedural. I wanted to go infinite proc-gen but I think that's out of scope. I don't intend on having the ground plane being very diverse in regards to actual height, just the objects placed on it.
  • Additions and removals within the environment will be dynamic at run-time by both the player and AI entities.

I've read some posts talking about how NavMesh can't handle runtime changes very well but have seen tutorials/store assets that are contrary to that. Maybe I could combine methods too? The pathing is going to be a heavy investment of time so any advice here would be greatly appreciated.

navmesh unity3d path-finding a-star performance
1 Answers

There are lots of solutions. It's way too much for a single answer, but here's some keywords to look into:

  • Swarm pathfinding
  • Potential fields
  • Flocking algorithms
  • Boids
  • Collision avoidance

Which one you use depends on how many units will be pathing at a time, whether they're pathing to the same place or different places, and how you want them to behave if multiple are going to the same place (eg. should they intentionally avoid collisions with each other? Take alternate routes when one is gridlocked? Or all just stupidly cram into the same hallway?)

user_2384190
Related