Contents  Introduction  What is a  potential field?  Forward... march!  Filling local  minima  It is better  to prevent...  Get away from  the edges  Printable version

Technique 2 : Filling local minima

As we saw in the first technique it is possible to get stuck. This happens when the unit enters a local minimum. In the potential field this is represented by a pixel that has neighbors which are either objects or are accessible but have a higher value, yet they are not our destination. If you have some experience with theoretical algorithms you may have noticed that we performed a depth-first search in the grid.

We'll improve our algorithm by using a best-first search. We'll do this by building a tree with the pixels in the grid. Our root in the tree is the starting location. This root has the 8 directions in which our unit can travel as children. We'll take the child with the lowest value and evaluate all the directions we can travel from here, but not the ones that are already in the tree. We then evaluate all the leaves in the tree and repeat the process for the leave with the lowest value. We continue to do this until we either find our destination or until we have evaluated all leaves and cannot find another pixel to move to (which will happen if the destination is simply unreachable from our starting location). If we are successful the path is defined by traversing the tree from the root to the leave containing our destination.

If you do a graphical representation of building the tree, you can see that local minima are 'filled' until the 'bucket runs over' and we can continue a straight line to our goal. In the picture, the members of the tree are blue, except for the leaves which are yellow. Obstacles are represented in white.

Next : Technique 3 : It is better to prevent...