Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
89 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:


 What is a
 potential field?

 Forward... march!
 Filling local

 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