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 3 : It is better to prevent...

We may have found a way to get out of local minima in our previous solution, but it would be better if we could just find a way to have no local minima at all. To accomplish this we need to change the way in which we build our potential field.

Instead of directly calculating the distance between a pixel and the destination, we'll give our destination zero as value and then apply this algorithm : Every direct (horizontal and vertical but not diagonal) neighbor of the destination gets value 1, then their direct neighbors get 2, and so on...

We can then start of where our unit is and glide down the numbers to our goal. Since only our destination has a zero value and every other pixel always has a neighbor with a lower value we'll be successful when a path exists. This method is also known as a wavefront-expansion.

If you look at the picture you'll notice that local minima now get a higher value (indicated by a brighter yellow) because it's a longer way around an object to get there than in a straight line. The path we follow is indicated by the blue line moving east and then south.

Next : Technique 4 : Get away from the edges