Hi,

I've implemented a potential-field planner for a 2d-world in which there are lots of individual units and fairly sparse obstacles. It works pretty well, so far -- having static map fields split from dynamic ones generated by moving units was the only performance work I've done so far.

I've never actually tried A* searching for each unit; how does it compare? What're pros/cons of it vs potential fields?

-- vs

How do you compute your potential fields? Are you using something like the brushfire algorithm, or do you simply have an attractive term for your goal and repulsive terms for your obstacles?

If it's the former (brushfire), then what you're doing is really intimately related to A*. You get exactly the same paths, but the complexity is a little different. If you simply wanted to get a single agent to a single goal, A* would be faster. However, if you had multiple agents who wanted to reach the same goal, they could all share the same potential field, and as you increased the number of agents, at some point the potential field approach would become faster.

If it's the latter (a sum of ad-hoc attraction and repulsion terms), then the advantage is that it can be quite fast, but the disadvantage is that there are no guarantees of optimality, or even of getting from point A to point B (you can get stuck in local minima). Also note that, in order for this to be fast, if you have a large number of obstacles, you'll need to avoid the naive implementation that is O(n^2) in the number of obstacles. This means choosing repulsive forces that are exactly zero outside of bounded sets surrounding the obstacles, and having an efficient broad-phase to determine which obstacles are close (and which therefore need to be included in the sum) -- e.g. spatial grids/trees and/or sweep-and-prune.