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 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...