I’m at present engaged on getting easy multi-agent pathfinding and navigation working. I’ve gone via a number of papers in these areas and carried out them. What I’m a bit confused about now as to what the final strategy needs to be for multi-agent programs basically (say for an RTS recreation).

From what I’ve been capable of glean to date evidently there are two most important parts to this drawback:

1. Pathfinding – The first step is after all to have the ability to discover a path to the vacation spot, and be capable of inform when a sure location is inaccessible. There are a number of approaches to this:

• 1.1 Dijkstra-type algorithms reminiscent of A* – The most clearly strategy would simply be A*, however this has well-known issues with multi-agent
  habits as a result of generally items clump up at choke factors. This is a
  main flaw with Starcraft’s algorithm. I feel this challenge was
  notably obtrusive with the Dragoon unit.
• 1.2 Improvements on 1.1 – There are a number of approaches right here. Some contain calculating a gaggle of locations for a gaggle of items and
  pausing them after they’re about to hit one other unit. There’s additionally a
  fancy strategy which makes use of time has a third spatial dimension and runs A*
  via the brand new 3D house.
• 1.3 Potential fields – Assign a scalar discipline (the potential) to every level in house and use gradient descent to maneuver brokers towards the
  desired purpose(s). Problem: items might get caught in native minima.
• 1.4 Flowfields – This is probably the most lovely strategy I’ve seen to date. Basically the pathfinding drawback is modelled as discovering a
  answer to the Eikonal equation in 2D. Then through the use of the finite
  distinction methodology to resolve a discretized model of the Eikonal
  equation, we get a vector discipline at every level in house that factors to
  the optimum path for the agent to go to.

2. Navigation – For the approaches above, a standard drawback (along with those already listed) is that when brokers get shut to one another, the collisions aren’t resolved very properly. In my experiments I’ve discovered that in case you simply use a physics engine to resolve collisions, there could also be lots of “pushing”, whereas the fascinating final result could be brokers figuring out to make approach for others. I’ve discovered the next approaches for this space:

• 2.1 Boids/Flocking – This strategy mainly mimics massive flocks of animals like birds or bugs. Several averaging algorithms are used to make sure that an enormous group retains a steady form, do not collide with each other, types some sort of alignment in formation, and so forth.

• 2.2 Velocity Obstacles – This strategy assigns a field of regard to every agent in entrance of them and has them predict their very own motion to see if there’s an object forward of them. Then alter their trajectories accordingly.

My query is then: Is the dichotomy I’ve described an correct description of how multi-agent programs are developed in video video games? If so, how do you determine when to make use of one or the opposite? My hunch is that to seek out paths to locations you’d use one of many pathfinding algorithms from 1., and for native collision decision you’d use one of many navigation algorithms from 2. Is that what individuals often do? I’m largely searching for a high-level technique/overview right here.

I’m at present making an attempt 1.4 (flowfield) + 2.1 (boids) for an RTS/RTT sort recreation and the outcomes are respectable. I’m simply questioning if there are higher approaches as properly.