dijikstra.htm

3D游戏开发领域专家撰写的经典游戏开发启迪性文章之一

the pseudo-code more readable, let:

<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
	f_x(x) = x - o_x + DELTA
	f_y(y) = y - o_y + DELTA
</FONT></PRE>
</BLOCKQUOTE>

<P>be two functions which translate the coordinates.

<P>The following two arrays are used to store the "augmented" information
discussed in the earlier explanation.  These store the following information:

<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
	w[x'][y'] The weight of the current shortest path from (o_x, o_y) to
        	  (o_x + x' - DELTA, o_y + y' - DELTA).
	p[x'][y'] The parent node of that shortest path

	int w[2*DELTA+1][2*DELTA+1];
	int p[2*DELTA+1][2*DELTA+1][2];
</FONT></PRE>
</BLOCKQUOTE>

<H3><FONT COLOR=YELLOW><I>Algorithm: (origin at (o_x, o_y))</I></FONT></H3>

<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
	set each w[i][j] = infinity
	set each p[i][j] = (infinity, infinity)

	set w[f_x(o_x)][f_y(o_y)] = 0
	push (o_x, o_y) onto the priority queue, say pq.                     [**]

	while (pop (x,y) from pq is possible)
                                                                        [***]
	foreach each square (x',y') adjacent to (x,y) and where
		|x-o_x| <= DELTA and |y-o_y| <= DELTA
		if w[f_x(x)][f_y(y)] + wt(x',y') < w[f_x(x')][f_y(y')] then
		{
			we have found a new shortest path
		}
		w[f_x(x')][f_y(y')] = w[f_x(x)][f_y(y)] + wt(x',y')
		p[f_x(x')][f_y(y')] = (x,y)
		push (x',y') onto the priority queue                      [**]
</FONT></PRE>
</BLOCKQUOTE>

<P>And you now have the shortest paths from (o_x,o_y) to every square in
the range { o_x - DELTA, o_y - DELTA, o_x + DELTA, o_y + DELTA } and
this will print the path from some point (x,y) to (o_x, o_y):

<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
	do
		print (x,y)
		(x,y) = p[f_x(x)][f_(y)]
	while (x,y) != (infinity, infinity)
</FONT></PRE>
</BLOCKQUOTE>

<p>and any square, (x,y), which is not reachable from (o_x, o_y) will have:

<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
	p[f_x(x)][f_y(y)] = (infinity, infinity)
	w[f_x(x)][f_y(y)] = infinity
</FONT></PRE>
</BLOCKQUOTE>

<H3><FONT COLOR=YELLOW><I>Sample Code:</I></FONT></H3>

<P>I have written a simple example of implementing this algorithm for a grid
map game.  The source code is zipped (pkzip).  The code itself is quite
simple.

<P>I have been able to compile and run the code on several UNIX boxes and DOS
with both the Microsoft C compiler (version 7, I think) and GCC (2.6.3 with
the version of DJGPP current as of June 1, 1995).  It should be quite easy
to port to any system.

<P>Included in the source code is a single map which should give you the gist
of what sort of input it expects and you should read the file sp.c which
explains how to use the demo.

<P>This source code is release with the understanding that I retain ownership
of the code.  You are free to make use of it in any way you see fit and
by transferring the code, you accept all responsibility for any damages
which result from using it.

<P>Having accepted that, you may get the source code:

<P><a href=sp_demo.zip>Sample C source code, simple grid map</a>

<P><I>NOTE</I> I've also got a modified version of the same code with a link
a little further down into the document.  The second version can use a simple
heuristic to find the path quickly.

<H3><FONT COLOR=YELLOW><I>Adding a Heuristic</I></FONT></H3>

<P>If you are more interested in finding the shortest path between two nodes
(and not all shortest paths to a node), you may be interested in applying
a heuristic function to the search.

<P><I>Author's Note:</I> My apologies on this section.  It is not overly
clear and is a little too brief.  If you don't follow what I'm saying,
you may wish to look at the source code I've supplied and then compare
the algorith in this page to the actual source code.  It should be
fairly clear.

<P>A <I>heuristic function</I> is a fancy way of saying a function which guesses
at an answer.  In this case, our heurisitic function will be guessing
at the length of the shortest path from any node to the destination node.

<P><I>IMPORTANT</I>: It is important that your function always be at most the
real shortest distance.  If you are using a real valued cartesian playing
field, you would want to use sqrt(dist(x)^2 + dist(y)^2) distance function.
Using a heurtistic function of 0 will get you back to the original algorithm.

<P>The effect of adding a good heuristic function would be to direct the search
so that very few bad paths will be considered.  I'm not going to bother
much with the theory that this is a shortest path or even why it works.
If you're avidly reading this part, you probably just want to get a
short path as quickly as possible and are willing to trust a little magic.

<P>To add the heuristic to my algorithm, let <I>h((x,y), (dest_x, dest_y))</I>
be a function which estimates the shortest path betwen two points.

<P>In the algorith, in each line that has ** beside it, add the heuristic
function applied to the current node.  At the point marked with ***
add the line:

<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
if (x,y) = (dest_x, dest_y) then done.
</FONT></PRE>
</BLOCKQUOTE>

<P>And voila!  You have a function which can rapidly find the shortest path
between any two points.

<P>The following source code uses exactly the same algorith with a heuristic
function that corresponds to the shortest distance on a grid.

<BLOCKQUOTE>
<PRE><FONT SIZE=2 COLOR=RED>
	H(x_1, y_1, x_2, y_2) = max( |x_2 - x_1|, |y_2 - y_1| )
</FONT></PRE>
</BLOCKQUOTE>

<p>which is the shortest possible distance on a grid between the points
(x_1, y_1) and (x_2, y_2).  The only changes to the original source code
are to add this value to the priority when entries are added to the
priority queue and a simple if statement which stops processing when we
have found the node for which we are searching.

<P>To compare the different techniques, you can use two command line options.
<B>-a</B> will request that processing stop when the destination has been
located and <B>-h</B> will request that the heuristic be applied.  Thus
running the program with -a and then with -a -h will give you a good
comparison between Djisktra's and Djisktra's with the heuristic.

<P><B>Disclaimer</B> I have not compiled this code on any machine except
a DEC Alpha (OSF).  The <I>zip</I> file was created using that system's
zip command.  I don't guarantee that anyone else will be able to get and
compile this code.  For this reason, I'm continuing to provide the original
source code (just in case).

<P><a href=sp_new.zip>Sample C source code, Djisktra's with a heuristic</a></p>

<!--Bottom Navigation-->
<A NAME="bottom"></A>
<!--End Bottom Navigation-->
</STRONG>
</FONT>
<!--End Body-->
<!--Bottom-->
<BR>
<IMG SRC="gradbar.jpg">
<BR>
<FONT SIZE=2 COLOR=#8B8B8B FACE=Helvetica>
<I><font color="#FBFBFB">T</font><font color="#F7F7F7">h</font><font color="#F3F3F3">e</font><font color="#EFEFEF"> </font><font color="#EBEBEB">G</font><font color="#E7E7E7">a</font><font color="#E3E3E3">m</font><font color="#DFDFDF">e</font><font color="#DBDBDB"> </font><font color="#D7D7D7">P</font><font color="#D3D3D3">r</font><font color="#CFCFCF">o</font><font color="#CBCBCB">g</font><font color="#C7C7C7">r</font><font color="#C3C3C3">a</font><font color="#BFBFBF">m</font><font color="#BBBBBB">m</font><font color="#B7B7B7">i</font><font color="#B3B3B3">n</font><font color="#AFAFAF">g</font><font color="#ABABAB"> </font><font color="#A7A7A7">M</font><font color="#A3A3A3">e</font><font color="#9F9F9F">g</font><font color="#9B9B9B">a</font><font color="#979797">S</font><font color="#939393">i</font><font color="#8F8F8F">t</font><font color="#8B8B8B">e</font> -