Potential Fields: Multiple Agents, Multiple Goals

The below SWF takes a while to generate initially

Even though it is only 3.02KB, most of it is procedural

click to randomize goals

The major benefit of potential fields are that they can be generated once and used for calculations by many agents without need for recalculation. This experiment forms part of my series on potential fields. It highlights how the potential field is used when determining where the agents must move next. The benefit of how I calculate the potential field is that you can add multiple goals of the same [type/priority] to the map with no overhead. This example has 1000 agents moving towards 4 different goals in near real-time!!!

SWF DETAILS

  • Goals are represented by full blue
  • Potential degrades further away from the goals (represented by gradient in blue)
  • Pink are the agents
  • Obstacles are in green
  • SWF size 400×400 pixels
  • Grid size = 400×400 cells
  • Cell size = 1×1 pixels
  • Obstacles fill 85% of total area
  • Agents = 1000
  • Goals = 4

POTENTIAL FIELD GENERATION PSEUDO ALGORITHM

  • Start with FIFO queue
  • Set goal cells potential to 1
  • Add goal cell positions to queue
  • While the queue is not empty (tip: add in check to make sure queue does not grow larger than max cells)
  • Pop the position to be evaluated
  • Check if neighbors have been calculated
  • For each unset neighbor set neighbor = current energy * decay factor
  • For each unset neighbor add it’s position to the queue

AGENT MOVEMENT PSEUDO ALGORITHM

  • Determine neighbor with the most energy that is also higher than current energy
  • Move agent to that neighbor’s position if the space is open
  • Optionally: it can be implemented to choose the next available space that is higher in energy (this will prevent the queuing behavior)

OPTIMIZATION

If you are to represent the potential field as a vector field, then when the agent needs to determine where to move next, it only has to evaluate its current node for direction, instead of evaluating each neighbor for the highest energy neighbor.

Download the Flash Develop 4 project