4
\$\begingroup\$

I've heard of of both flow fields and potential fields for pathfinding in games. They sound similar, but I never see them mentioned in the same contexts. Places that mention one never mention the other, as if they're completely unrelated.

How are they different? Why would I choose one over the other?

\$\endgroup\$
9
\$\begingroup\$

A potential field is a type of scalar field. In contrast, a flow field is a vector field. These are essentially just multidimensional arrays that are used as low level data structures for various pathfinding designs; there really is no "standard" algorithm equivalent to the ubiquity of A* for point-to-point pathfinding.

Typically, a potential field maps the "desirability" of a particular location on the terrain for AI entities (henceforth I will call them agents). They will try to travel in whichever direction will cause the greatest increase in potential. Hence, if you think of the potential as a height, they're playing a game of king of the hill. Once agents reach a local maximum, they stop moving. This can be a problem depending on how the field is generated, because agents can get stuck in corners and dead-ends.

One ingenious method of getting around this problem with potential fields is to allow the field to be modified in real-time. This is known as collaborative diffusion. In this system, "potential" acts somewhat like molasses or lava; it diffuses slowly toward any adjacent location with less potential. The target becomes a producer of potential, as if a mountain were constantly springing up beneath its feet. Agents become consumers of potential, simultaneously moving towards locations with greater potential, and reducing the amount of potential on their current location. In addition to solving the problem of local maxima, this means multiple agents will tend to move away from each other, taking different paths towards the target, and thus appearing to collaborate. Additionally, potential may naturally decay over time to prioritize the current and recent locations of the target over older locations.

For flow fields, I'll assume you're talking about a system similar to this one. In this system, you have two scalar fields and a vector field. You start out with a scalar travel cost field, which is integrated to find the total cost to travel from any starting location to the target location. Essentially, this integration field is a potential field, but instead of seeking higher potentials, agents seek lower potentials, and thanks to the integration that generates it, the potential field is well behaved: agents won't get stuck in a local minimum because there is only one minimum (the target location). Finally, a vector field is created by taking the gradient of the potential field (essentially the local derivative at each point in the field). This type of system can be thought of as an answer to the question "What direction would Dijkstra's algorithm (or A*, or any other algorithm that guarantees minimum path length) initially direct me to reach a specific target from every other location on the map?"

TL;DR A flow field is usually just the gradient of a potential field. If the number of agents in the simulation is significantly smaller than the number of locations in the field, then a potential field is probably better, because it uses less memory (a vector is larger than a scalar). On the other hand, if you have tons and tons of agents, you might be recalculating the same partial derivatives over and over for each agent, and caching them in a flow field might be beneficial.

\$\endgroup\$
  • \$\begingroup\$ Would you mind adding some more details about the travel cost field for flow fields? I'm a little unclear on how to they're constructed. \$\endgroup\$ – spiffytech Sep 25 '14 at 17:15
  • \$\begingroup\$ Could you please elaborate on how the flow field integration field avoids local minima? I'm not clear on how seeking lower potential instead of higher addresses the problem. \$\endgroup\$ – spiffytech Sep 25 '14 at 17:16
  • \$\begingroup\$ @spiffytech The travel cost is the same as is typically used in A* pathfinding; it gives more or less weight to the distance that needs to be traveled through it. So traveling through 6 cells with a cost of 1 is considered equally as good a path as one that travels through two cells, with one having a cost of 4 and one with a cost of 2. \$\endgroup\$ – bcrist Sep 26 '14 at 17:59
  • \$\begingroup\$ @spiffytech The fact that the flow field example seeks lower potentials doesn't have any bearing on eliminating local extrema, I only mentioned that to recognize that it is inverted compared to the previous collaborative diffusion example. The absence of local minima outside the origin is only guaranteed if the travel cost is guaranteed to be positive over the entire field. We're integrating the travel cost over each path from the origin to another location, and if the travel cost is always positive, then each location in that path moving away from the origin must be larger than the last. \$\endgroup\$ – bcrist Sep 26 '14 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.