Potential Fields: Navigation

click to randomize goal position

The above swf illustrates how potential fields can be generated with obstacles in the way. It forms part of a series on potential fields. It highlights how the potential field is used when determining where the agent must move next.

SWF DETAILS

  • Goal is represented by full blue
  • Potential degrades further away from the goal (represented by gradient in blue)
  • Pink is the agent
  • Green are the obstacles
  • SWF size 400×400 pixels
  • Grid size = 100×100 cells
  • Cell size = 4×4 pixels
  • Obstacle fill 85%
  • Agents = 1
  • 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

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