Potential Fields: Multiple Agents

click to randomize goal position

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.

SWF DETAILS

  • Goal is represented by full blue
  • Potential degrades further away from the goal (represented by gradient in blue)
  • Pink are the agents
  • Obstacles are shown in green
  • SWF size 400×400 pixels
  • Grid size = 200×200 cells
  • Cell size = 2×2 pixels
  • Obstacles fill 85% of total area
  • Agents = 500
  • Goals = 1

POTENTIAL FIELD GENERATION PSEUDO ALGORITHM

  • Start with FIFO queue
  • Set goal cell potential to 1
  • Add goal cell position 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.

Side Note: I was thinking when fiddling with this experiment that if you were to hide the obstacles when the system becomes stable, you could end up with a potentially fun rooting algorithm for plants or something similar.

Download the Flash Develop 4 project