http://roguebasin.com/index.php?title=Pathfinding&feed=atom&action=history
Pathfinding - Revision history
2024-03-28T19:09:44Z
Revision history for this page on the wiki
MediaWiki 1.36.0
http://roguebasin.com/index.php?title=Pathfinding&diff=12167&oldid=prev
Slash: fixed < and >
2008-01-07T04:31:20Z
<p>fixed &lt and &gt</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 04:31, 7 January 2008</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l22">Line 22:</td>
<td colspan="2" class="diff-lineno">Line 22:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>/* pathfind.c - simple path finder - public domain */</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>/* pathfind.c - simple path finder - public domain */</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>#include <del style="font-weight: bold; text-decoration: none;">&ltstdio</del>.h></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>#include <ins style="font-weight: bold; text-decoration: none;"><stdio</ins>.h></div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>#include <del style="font-weight: bold; text-decoration: none;">&ltstdlib</del>.h></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>#include <ins style="font-weight: bold; text-decoration: none;"><stdlib</ins>.h></div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>#include <del style="font-weight: bold; text-decoration: none;">&lttime</del>.h></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>#include <ins style="font-weight: bold; text-decoration: none;"><time</ins>.h></div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>#include <del style="font-weight: bold; text-decoration: none;">&ltstring</del>.h></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>#include <ins style="font-weight: bold; text-decoration: none;"><string</ins>.h></div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#define MAP_WIDTH 70</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#define MAP_WIDTH 70</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l324">Line 324:</td>
<td colspan="2" class="diff-lineno">Line 324:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#ifdef ASTAR</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#ifdef ASTAR</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> if ( !element-<del style="font-weight: bold; text-decoration: none;">&gtestimate_ </del>)</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> if ( !element-<ins style="font-weight: bold; text-decoration: none;">>estimate_ </ins>)</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> element-<del style="font-weight: bold; text-decoration: none;">&gtestimate_ </del>=</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> element-<ins style="font-weight: bold; text-decoration: none;">>estimate_ </ins>=</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> path_distance( element-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_</del>, element-<del style="font-weight: bold; text-decoration: none;">&gty_pos_</del>, goalx, goaly );</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> path_distance( element-<ins style="font-weight: bold; text-decoration: none;">>x_pos_</ins>, element-<ins style="font-weight: bold; text-decoration: none;">>y_pos_</ins>, goalx, goaly );</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#endif</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#endif</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> return element-<del style="font-weight: bold; text-decoration: none;">&gtcost_ </del>+ element-<del style="font-weight: bold; text-decoration: none;">&gtestimate_</del>;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> return element-<ins style="font-weight: bold; text-decoration: none;">>cost_ </ins>+ element-<ins style="font-weight: bold; text-decoration: none;">>estimate_</ins>;</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l350">Line 350:</td>
<td colspan="2" class="diff-lineno">Line 350:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#if 0</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#if 0</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> if ( path_distance( next-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_</del>, next-<del style="font-weight: bold; text-decoration: none;">&gty_pos_</del>, goalx, goaly ) <</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> if ( path_distance( next-<ins style="font-weight: bold; text-decoration: none;">>x_pos_</ins>, next-<ins style="font-weight: bold; text-decoration: none;">>y_pos_</ins>, goalx, goaly ) <</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> path_distance( current-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_</del>, current-<del style="font-weight: bold; text-decoration: none;">&gty_pos_</del>, goalx,</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> path_distance( current-<ins style="font-weight: bold; text-decoration: none;">>x_pos_</ins>, current-<ins style="font-weight: bold; text-decoration: none;">>y_pos_</ins>, goalx,</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>goaly ) )</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>goaly ) )</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#else</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#else</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l419">Line 419:</td>
<td colspan="2" class="diff-lineno">Line 419:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* If not processed yet, add to open set */</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* If not processed yet, add to open set */</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> if ( pos-<del style="font-weight: bold; text-decoration: none;">&gtstate_ </del>== path_element_empty )</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> if ( pos-<ins style="font-weight: bold; text-decoration: none;">>state_ </ins>== path_element_empty )</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> pos-<del style="font-weight: bold; text-decoration: none;">&gtstate_ </del>= path_element_open;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> pos-<ins style="font-weight: bold; text-decoration: none;">>state_ </ins>= path_element_open;</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> pos-<del style="font-weight: bold; text-decoration: none;">&gtparent_ </del>= parent;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> pos-<ins style="font-weight: bold; text-decoration: none;">>parent_ </ins>= parent;</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_update_cost( parent, pos );</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_update_cost( parent, pos );</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l437">Line 437:</td>
<td colspan="2" class="diff-lineno">Line 437:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* New path is better than old. */</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* New path is better than old. */</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> int was_open = ( pos-<del style="font-weight: bold; text-decoration: none;">&gtstate_ </del>== path_element_open );</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> int was_open = ( pos-<ins style="font-weight: bold; text-decoration: none;">>state_ </ins>== path_element_open );</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> *pos = tmp;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> *pos = tmp;</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> pos-<del style="font-weight: bold; text-decoration: none;">&gtparent_ </del>= parent;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> pos-<ins style="font-weight: bold; text-decoration: none;">>parent_ </ins>= parent;</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> pos-<del style="font-weight: bold; text-decoration: none;">&gtstate_ </del>= path_element_open;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> pos-<ins style="font-weight: bold; text-decoration: none;">>state_ </ins>= path_element_open;</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> if ( was_open )</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> if ( was_open )</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l481">Line 481:</td>
<td colspan="2" class="diff-lineno">Line 481:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* Push first element to stack. */</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* Push first element to stack. */</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> pos-<del style="font-weight: bold; text-decoration: none;">&gtstate_ </del>= path_element_open;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> pos-<ins style="font-weight: bold; text-decoration: none;">>state_ </ins>= path_element_open;</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_push_open( pos, real_goal_x, real_goal_y );</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_push_open( pos, real_goal_x, real_goal_y );</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l489">Line 489:</td>
<td colspan="2" class="diff-lineno">Line 489:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* Did we reach target? */</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* Did we reach target? */</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> if ( ( current-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_ </del>== real_goal_x ) &&</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> if ( ( current-<ins style="font-weight: bold; text-decoration: none;">>x_pos_ </ins>== real_goal_x ) &&</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> ( current-<del style="font-weight: bold; text-decoration: none;">&gty_pos_ </del>== real_goal_y ) )</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> ( current-<ins style="font-weight: bold; text-decoration: none;">>y_pos_ </ins>== real_goal_y ) )</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> found = 1;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> found = 1;</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l497">Line 497:</td>
<td colspan="2" class="diff-lineno">Line 497:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* Current is closed. */</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* Current is closed. */</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> current-<del style="font-weight: bold; text-decoration: none;">&gtstate_ </del>= path_element_closed;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> current-<ins style="font-weight: bold; text-decoration: none;">>state_ </ins>= path_element_closed;</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* Generate positions reachable from current position. */</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* Generate positions reachable from current position. */</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_check( current,</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_check( current,</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> current-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_ </del>+ 1, current-<del style="font-weight: bold; text-decoration: none;">&gty_pos_</del>,</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> current-<ins style="font-weight: bold; text-decoration: none;">>x_pos_ </ins>+ 1, current-<ins style="font-weight: bold; text-decoration: none;">>y_pos_</ins>,</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> real_goal_x, real_goal_y );</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> real_goal_x, real_goal_y );</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_check( current,</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_check( current,</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> current-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_ </del>- 1, current-<del style="font-weight: bold; text-decoration: none;">&gty_pos_</del>,</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> current-<ins style="font-weight: bold; text-decoration: none;">>x_pos_ </ins>- 1, current-<ins style="font-weight: bold; text-decoration: none;">>y_pos_</ins>,</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> real_goal_x, real_goal_y );</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> real_goal_x, real_goal_y );</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_check( current,</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_check( current,</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> current-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_</del>, current-<del style="font-weight: bold; text-decoration: none;">&gty_pos_ </del>+ 1,</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> current-<ins style="font-weight: bold; text-decoration: none;">>x_pos_</ins>, current-<ins style="font-weight: bold; text-decoration: none;">>y_pos_ </ins>+ 1,</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> real_goal_x, real_goal_y );</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> real_goal_x, real_goal_y );</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_check( current,</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> path_check( current,</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> current-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_</del>, current-<del style="font-weight: bold; text-decoration: none;">&gty_pos_ </del>- 1,</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> current-<ins style="font-weight: bold; text-decoration: none;">>x_pos_</ins>, current-<ins style="font-weight: bold; text-decoration: none;">>y_pos_ </ins>- 1,</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> real_goal_x, real_goal_y );</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> real_goal_x, real_goal_y );</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* So if you want to allow diagonal movement, add four</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> /* So if you want to allow diagonal movement, add four</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l528">Line 528:</td>
<td colspan="2" class="diff-lineno">Line 528:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> int result = 0;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> int result = 0;</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> struct path_element* pos = path_element_map( *nextx, *nexty );</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> struct path_element* pos = path_element_map( *nextx, *nexty );</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> if ( pos-<del style="font-weight: bold; text-decoration: none;">&gtparent_ </del>)</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> if ( pos-<ins style="font-weight: bold; text-decoration: none;">>parent_ </ins>)</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> *nextx = pos-<del style="font-weight: bold; text-decoration: none;">&gtparent_</del>-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_</del>;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> *nextx = pos-<ins style="font-weight: bold; text-decoration: none;">>parent_</ins>-<ins style="font-weight: bold; text-decoration: none;">>x_pos_</ins>;</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> *nexty = pos-<del style="font-weight: bold; text-decoration: none;">&gtparent_</del>-<del style="font-weight: bold; text-decoration: none;">&gty_pos_</del>;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> *nexty = pos-<ins style="font-weight: bold; text-decoration: none;">>parent_</ins>-<ins style="font-weight: bold; text-decoration: none;">>y_pos_</ins>;</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> result = ( pos-<del style="font-weight: bold; text-decoration: none;">&gtparent_</del>-<del style="font-weight: bold; text-decoration: none;">&gtparent_ </del>!= NULL );</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> result = ( pos-<ins style="font-weight: bold; text-decoration: none;">>parent_</ins>-<ins style="font-weight: bold; text-decoration: none;">>parent_ </ins>!= NULL );</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l553">Line 553:</td>
<td colspan="2" class="diff-lineno">Line 553:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#ifndef MAP_VARIYING_COST</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#ifndef MAP_VARIYING_COST</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> pos-<del style="font-weight: bold; text-decoration: none;">&gtcost_ </del>= parent-<del style="font-weight: bold; text-decoration: none;">&gtcost_ </del>+ 1;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> pos-<ins style="font-weight: bold; text-decoration: none;">>cost_ </ins>= parent-<ins style="font-weight: bold; text-decoration: none;">>cost_ </ins>+ 1;</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#else</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#else</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> int dx = pos-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_ </del>- parent-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_ </del>+ 1; /* dx = 0, 1, 2 */</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> int dx = pos-<ins style="font-weight: bold; text-decoration: none;">>x_pos_ </ins>- parent-<ins style="font-weight: bold; text-decoration: none;">>x_pos_ </ins>+ 1; /* dx = 0, 1, 2 */</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> int dy = pos-<del style="font-weight: bold; text-decoration: none;">&gty_pos_ </del>- parent-<del style="font-weight: bold; text-decoration: none;">&gty_pos_ </del>+ 1; /* dy = 0, 1, 2 */</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> int dy = pos-<ins style="font-weight: bold; text-decoration: none;">>y_pos_ </ins>- parent-<ins style="font-weight: bold; text-decoration: none;">>y_pos_ </ins>+ 1; /* dy = 0, 1, 2 */</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> if ( pos-<del style="font-weight: bold; text-decoration: none;">&gtx_pos_ </del>& 1 )</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> if ( pos-<ins style="font-weight: bold; text-decoration: none;">>x_pos_ </ins>& 1 )</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> pos-<del style="font-weight: bold; text-decoration: none;">&gtcost_ </del>= parent-<del style="font-weight: bold; text-decoration: none;">&gtcost_ </del>+ cost_table_a[dx][dy];</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> pos-<ins style="font-weight: bold; text-decoration: none;">>cost_ </ins>= parent-<ins style="font-weight: bold; text-decoration: none;">>cost_ </ins>+ cost_table_a[dx][dy];</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> else</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> else</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> {</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> pos-<del style="font-weight: bold; text-decoration: none;">&gtcost_ </del>= parent-<del style="font-weight: bold; text-decoration: none;">&gtcost_ </del>+ cost_table_b[dx][dy];</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> pos-<ins style="font-weight: bold; text-decoration: none;">>cost_ </ins>= parent-<ins style="font-weight: bold; text-decoration: none;">>cost_ </ins>+ cost_table_b[dx][dy];</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> }</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#endif // MAP_VARIYING_COST</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>#endif // MAP_VARIYING_COST</div></td></tr>
</table>
Slash
http://roguebasin.com/index.php?title=Pathfinding&diff=10383&oldid=prev
Lochok at 12:07, 12 September 2006
2006-09-12T12:07:45Z
<p></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 12:07, 12 September 2006</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l574">Line 574:</td>
<td colspan="2" class="diff-lineno">Line 574:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Pekka Nurminen</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Pekka Nurminen</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></pre></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></pre></div></td></tr>
<tr><td colspan="2"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Category:Articles]][[Category:AI]]</ins></div></td></tr>
</table>
Lochok
http://roguebasin.com/index.php?title=Pathfinding&diff=3209&oldid=prev
Lochok at 12:07, 12 September 2006
2006-09-12T12:07:19Z
<p></p>
<p><b>New page</b></p><div><pre><br />
The most generic algorithm is something like:<br />
<br />
1. Start with empty priority queue P<br />
2. Start with empty set of previously visited nodes V<br />
3. Add start node s to P with cost f(s)<br />
4. If P is empty, then stop, no solution.<br />
5. Remove node x with lowest f(x) from P.<br />
6. If x is goal, stop with success.<br />
7. For each nx in successors of x:<br />
a) calculate f(nx) (= f(x) + delta)<br />
b) if nx not visited yet OR<br />
nx is in the priority queue P but with higher f(nx) OR<br />
nx has been visited but with higher f(nx)<br />
then place/update nx to P with new cost and<br />
update V to include (nx, f(nx), x)<br />
8. Go to 4<br />
<br />
Then if<br />
f(x) equals to cost from start node, it is djikstra<br />
f(x) equals to cost from start node + estimate to goal, the algorithm is A*.<br />
<br />
/* pathfind.c - simple path finder - public domain */<br />
#include &ltstdio.h><br />
#include &ltstdlib.h><br />
#include &lttime.h><br />
#include &ltstring.h><br />
<br />
#define MAP_WIDTH 70<br />
#define MAP_HEIGHT 25<br />
#define MAP_SIZE MAP_WIDTH*MAP_HEIGHT<br />
<br />
#define MAP_BLOCKERS 500<br />
#define MAP_BLOCKERS_POS_TRIES 100<br />
#define MAP_PATHS 10000<br />
#define MAP_PATHS_POS_TRIES 100<br />
<br />
//#define ASTAR<br />
//#define MAP_VARIYING_COST<br />
<br />
/* Map - 1 means blocked, 0 means passable */<br />
static int map[ MAP_SIZE ];<br />
<br />
/* States of path elements */<br />
enum path_element_state<br />
{<br />
path_element_empty,<br />
path_element_open,<br />
path_element_closed<br />
};<br />
<br />
/* Structure for path elements */<br />
struct path_element<br />
{<br />
int x_pos_;<br />
int y_pos_;<br />
int cost_;<br />
int estimate_;<br />
enum path_element_state state_;<br />
struct path_element* parent_;<br />
};<br />
<br />
/* Nodes - one per cell in map */<br />
static struct path_element path_nodes[ MAP_SIZE ];<br />
<br />
/* Open nodes */<br />
static struct path_element* path_open[ MAP_SIZE ];<br />
<br />
/* Top index */<br />
static int path_open_top;<br />
<br />
/* Calculates distance between two points */<br />
int path_distance( int x0, int y0, int x1, int y1 );<br />
/* Checks if position is blocked */<br />
int path_blocked( int x, int y );<br />
/* Initialises path structures */<br />
void path_init( void );<br />
/* Maps coordinate to one dimensional array */<br />
int path_map( int x, int y );<br />
/* Returns pointer to path element, or NULL if position is invalid */<br />
struct path_element* path_element_map( int x, int y );<br />
/* Calculates cost from element to goal. */<br />
int path_cost( struct path_element* element, int goalx, int goaly );<br />
/* Pushes element to open stack */<br />
void path_push_open( struct path_element* element, int goalx, int goaly );<br />
/* Pops element from open stack */<br />
struct path_element* path_pop_open( void );<br />
/* Removes element from stack */<br />
void path_remove( struct path_element* element );<br />
/* Checks if there are elements in open stack */<br />
int path_open_not_empty( void );<br />
/* Pushes position to open stack when needed */<br />
void path_check( struct path_element* parent,<br />
int posx, int posy, int goalx, int goaly );<br />
/* Finds path from start towards goal */<br />
int path_find( int startx, int starty, int goalx, int goaly );<br />
/* Gets next step towards goal. */<br />
int path_get_next( int* nextx, int* nexty );<br />
/* Updates cost to pos which is adjacent to parent */<br />
void path_update_cost( struct path_element* parent, struct path_element*<br />
pos );<br />
<br />
int main()<br />
{<br />
int i, j, k;<br />
int seed = time( NULL );<br />
memset( map, 0, MAP_SIZE*sizeof( int ) );<br />
<br />
/* Put some dirt to the map */<br />
for ( i = 0; i < MAP_WIDTH; i++ )<br />
{<br />
map[ path_map( i, 0 ) ] = 1;<br />
map[ path_map( i, MAP_HEIGHT - 1 ) ] = 1;<br />
}<br />
for ( j = 0; j < MAP_HEIGHT; j++ )<br />
{<br />
map[ path_map( 0, j ) ] = 1;<br />
map[ path_map( MAP_WIDTH - 1, j ) ] = 1;<br />
}<br />
for ( i = 0; i < MAP_BLOCKERS; i++ )<br />
{<br />
for ( j = 0; j < MAP_BLOCKERS_POS_TRIES; j++ )<br />
{<br />
int x = rand() % MAP_WIDTH;<br />
int y = rand() % MAP_HEIGHT;<br />
<br />
if ( !path_blocked( x, y ) )<br />
{<br />
map[ path_map( x, y ) ] = 1;<br />
break;<br />
}<br />
}<br />
}<br />
<br />
srand( seed );<br />
<br />
/* Show map */<br />
printf( "Map with seed = %x:\n", seed );<br />
k = 0;<br />
for ( j = 0; j < MAP_HEIGHT; j++ )<br />
{<br />
if ( j )<br />
{<br />
printf( "\n" );<br />
}<br />
<br />
for ( i = 0; i < MAP_WIDTH; i++ )<br />
{<br />
if ( !map[ k ] )<br />
{<br />
printf( "." );<br />
}<br />
else<br />
{<br />
printf( "#" );<br />
}<br />
<br />
k++;<br />
}<br />
}<br />
<br />
printf( "\n" );<br />
<br />
/* Generate some paths */<br />
for ( k = 0; k < MAP_PATHS; k++ )<br />
{<br />
int start_x;<br />
int start_y;<br />
int goal_x;<br />
int goal_y;<br />
int path;<br />
int steps;<br />
<br />
printf( "Path %d:\n", k + 1 );<br />
<br />
for ( i = 0; i < MAP_PATHS_POS_TRIES; i++ )<br />
{<br />
start_x = rand() % MAP_WIDTH;<br />
start_y = rand() % MAP_HEIGHT;<br />
<br />
if ( !path_blocked( start_x, start_y ) )<br />
{<br />
break;<br />
}<br />
}<br />
<br />
for ( j = 0; j < MAP_PATHS_POS_TRIES; j++ )<br />
{<br />
goal_x = rand() % MAP_WIDTH;<br />
goal_y = rand() % MAP_HEIGHT;<br />
<br />
if ( !path_blocked( goal_x, goal_y ) )<br />
{<br />
break;<br />
}<br />
}<br />
if ( ( i == MAP_PATHS_POS_TRIES ) ||<br />
( j == MAP_PATHS_POS_TRIES ) )<br />
{<br />
printf( "\tFailed to generate start & goal\n" );<br />
continue;<br />
}<br />
<br />
/* Goal & start location are Ok, generate path */<br />
printf( "\tStart = (%d, %d), goal = (%d, %d)\n",<br />
start_x, start_y, goal_x, goal_y );<br />
<br />
path = path_find( start_x, start_y, goal_x, goal_y );<br />
if ( path )<br />
{<br />
/* Print out steps to goal. */<br />
steps = 0;<br />
while ( path )<br />
{<br />
int prev_x = start_x;<br />
int prev_y = start_y;<br />
<br />
path = path_get_next( &start_x, &start_y );<br />
<br />
if ( !steps )<br />
{<br />
printf( "\t(%2d, %2d) -> (%2d, %2d)",<br />
prev_x, prev_y, start_x, start_y );<br />
}<br />
else<br />
{<br />
if ( ( steps + 1 ) & 7 )<br />
{<br />
printf( " -> (%2d, %2d)", start_x, start_y );<br />
}<br />
else<br />
{<br />
printf( " ->\n\t(%2d, %2d)", start_x, start_y );<br />
}<br />
}<br />
<br />
steps++;<br />
}<br />
<br />
if ( ( start_x == goal_x ) &&<br />
( start_y == goal_y ) )<br />
{<br />
printf( "\n\tFound target!\n" );<br />
}<br />
}<br />
else<br />
{<br />
printf( "\tCould not find path\n" );<br />
}<br />
}<br />
<br />
return EXIT_SUCCESS;<br />
}<br />
<br />
/* Calculate distance between two points */<br />
int path_distance( int x0, int y0, int x1, int y1 )<br />
{<br />
int xd = ( x0 - x1 );<br />
int yd = ( y0 - y1 );<br />
<br />
if ( xd < 0 )<br />
{<br />
xd = -xd;<br />
}<br />
if ( yd < 0 )<br />
{<br />
yd = -yd;<br />
}<br />
<br />
return xd + yd;<br />
}<br />
<br />
/* Checks if position is blocked */<br />
int path_blocked( int x, int y )<br />
{<br />
return map[ path_map( x, y ) ];<br />
}<br />
<br />
/* Initialises path structures. */<br />
void path_init( void )<br />
{<br />
int i, j;<br />
int p;<br />
<br />
/* Everything done here is not absolutely necessary. */<br />
memset( path_nodes, 0, MAP_SIZE * sizeof( struct path_element ) );<br />
memset( path_open, 0, MAP_SIZE * sizeof( struct path_element* ) );<br />
path_open_top = 0;<br />
<br />
p = 0;<br />
for ( j = 0; j < MAP_HEIGHT; j++ )<br />
{<br />
for ( i = 0; i < MAP_WIDTH; i++ )<br />
{<br />
path_nodes[ p ].x_pos_ = i;<br />
path_nodes[ p ].y_pos_ = j;<br />
p++;<br />
}<br />
}<br />
}<br />
<br />
/* Maps coordinates to one dimensional array indices. */<br />
int path_map( int x, int y )<br />
{<br />
return y * MAP_WIDTH + x;<br />
}<br />
<br />
/* Returns pointer to path element structure or NULL if invalid position. */<br />
struct path_element* path_element_map( int x, int y )<br />
{<br />
struct path_element* result = NULL;<br />
<br />
if ( ( x >= 0 && x < MAP_WIDTH ) &&<br />
( y >= 0 && y < MAP_HEIGHT ) )<br />
{<br />
result = &path_nodes[ path_map( x, y ) ];<br />
}<br />
<br />
return result;<br />
}<br />
<br />
/* Returns cost from position defined by element to goal.*/<br />
int path_cost( struct path_element* element, int goalx, int goaly )<br />
{<br />
#ifdef ASTAR<br />
if ( !element-&gtestimate_ )<br />
{<br />
element-&gtestimate_ =<br />
path_distance( element-&gtx_pos_, element-&gty_pos_, goalx, goaly );<br />
}<br />
#endif<br />
<br />
return element-&gtcost_ + element-&gtestimate_;<br />
}<br />
<br />
/* Pushes pointer to one element to the open stack */<br />
void path_push_open( struct path_element* element, int goalx, int goaly )<br />
{<br />
int i;<br />
<br />
path_open[ path_open_top ] = element;<br />
path_open_top++;<br />
<br />
/* Keep elements in ascending order by distance to goal<br />
- we want to find one of the shortest paths */<br />
for ( i = path_open_top - 1; i >= 1; i-- )<br />
{<br />
struct path_element* current = path_open[ i ];<br />
struct path_element* next = path_open[ i - 1 ];<br />
<br />
#if 0<br />
if ( path_distance( next-&gtx_pos_, next-&gty_pos_, goalx, goaly ) <<br />
path_distance( current-&gtx_pos_, current-&gty_pos_, goalx,<br />
goaly ) )<br />
#else<br />
int next_total = path_cost( next, goalx, goaly );<br />
int current_total = path_cost( current, goalx, goaly );<br />
if ( next_total < current_total )<br />
{<br />
#endif<br />
/* Swap pointers */<br />
path_open[ i ] = next;<br />
path_open[ i - 1 ] = current;<br />
}<br />
}<br />
}<br />
<br />
/* Pops one element from the open stack */<br />
struct path_element* path_pop_open( void )<br />
{<br />
path_open_top--;<br />
struct path_element* result = path_open[ path_open_top ];<br />
path_open[ path_open_top ] = NULL;<br />
return result;<br />
}<br />
<br />
/* Removes element from stack */<br />
void path_remove( struct path_element* element )<br />
{<br />
int i;<br />
for ( i = 0; i < path_open_top; i++ )<br />
{<br />
if ( element == path_open[ i ] )<br />
{<br />
break;<br />
}<br />
}<br />
<br />
if ( i != path_open_top )<br />
{<br />
/* Element was found. */<br />
path_open[ i ] = NULL;<br />
for ( ; i < ( path_open_top - 1 ); i++ )<br />
{<br />
path_open[ i ] = path_open[ i + 1 ];<br />
}<br />
<br />
path_open_top--;<br />
}<br />
}<br />
<br />
/* Checks that open stack is not empty. */<br />
int path_open_not_empty( void )<br />
{<br />
return path_open_top;<br />
}<br />
<br />
/* Pushes to open stack unless already open, closed or impassable */<br />
void path_check(<br />
struct path_element* parent,<br />
int posx, int posy, int goalx, int goaly )<br />
{<br />
struct path_element* pos = path_element_map( posx, posy );<br />
if ( pos )<br />
{<br />
/* We can ignore blocked positions (consider that cost is<br />
infinite).*/<br />
if ( !path_blocked( posx, posy ) )<br />
{<br />
/* If not processed yet, add to open set */<br />
if ( pos-&gtstate_ == path_element_empty )<br />
{<br />
pos-&gtstate_ = path_element_open;<br />
pos-&gtparent_ = parent;<br />
path_update_cost( parent, pos );<br />
<br />
path_push_open( pos, goalx, goaly );<br />
}<br />
else<br />
{<br />
/* Now element is either in open or closed set. */<br />
const int orig_cost = path_cost( pos, goalx, goaly );<br />
struct path_element tmp = *pos;<br />
path_update_cost( parent, &tmp );<br />
<br />
if ( orig_cost > path_cost( &tmp, goalx, goaly ) )<br />
{<br />
/* New path is better than old. */<br />
int was_open = ( pos-&gtstate_ == path_element_open );<br />
<br />
*pos = tmp;<br />
pos-&gtparent_ = parent;<br />
pos-&gtstate_ = path_element_open;<br />
<br />
if ( was_open )<br />
{<br />
path_remove( pos );<br />
}<br />
<br />
path_push_open( pos, goalx, goaly );<br />
}<br />
}<br />
}<br />
}<br />
}<br />
<br />
/* Updates startx and starty one step towards (goalx, goaly). */<br />
int path_find( int startx, int starty, int goalx, int goaly )<br />
{<br />
int found = 0;<br />
<br />
/* Parent points towards start of search. So if we start from goal,<br />
then those parent pointers are automatically ok.<br />
<br />
Of course, the following assumption is made (reflexivity):<br />
if there is path from A to B, then there is path from B to A.<br />
(this holds in this application)<br />
*/<br />
const int real_goal_x = startx;<br />
const int real_goal_y = starty;<br />
const int real_start_x = goalx;<br />
const int real_start_y = goaly;<br />
<br />
path_init();<br />
<br />
struct path_element* pos = path_element_map( real_start_x,<br />
real_start_y );<br />
struct path_element* start = path_element_map( real_goal_x,<br />
real_goal_y );<br />
if ( pos && start ) /* Both should be acceptable */<br />
{<br />
/* Push first element to stack. */<br />
pos-&gtstate_ = path_element_open;<br />
path_push_open( pos, real_goal_x, real_goal_y );<br />
<br />
while ( path_open_not_empty() )<br />
{<br />
struct path_element* current = path_pop_open();<br />
<br />
/* Did we reach target? */<br />
if ( ( current-&gtx_pos_ == real_goal_x ) &&<br />
( current-&gty_pos_ == real_goal_y ) )<br />
{<br />
found = 1;<br />
break;<br />
}<br />
<br />
/* Current is closed. */<br />
current-&gtstate_ = path_element_closed;<br />
<br />
/* Generate positions reachable from current position. */<br />
path_check( current,<br />
current-&gtx_pos_ + 1, current-&gty_pos_,<br />
real_goal_x, real_goal_y );<br />
path_check( current,<br />
current-&gtx_pos_ - 1, current-&gty_pos_,<br />
real_goal_x, real_goal_y );<br />
path_check( current,<br />
current-&gtx_pos_, current-&gty_pos_ + 1,<br />
real_goal_x, real_goal_y );<br />
path_check( current,<br />
current-&gtx_pos_, current-&gty_pos_ - 1,<br />
real_goal_x, real_goal_y );<br />
/* So if you want to allow diagonal movement, add four<br />
additional<br />
path_check calls. */<br />
}<br />
}<br />
<br />
return found;<br />
}<br />
<br />
/* Gets next step towards goal - path_find must have been called beforehand.<br />
Results are erased after next path_find call.<br />
*/<br />
int path_get_next( int* nextx, int* nexty )<br />
{<br />
int result = 0;<br />
struct path_element* pos = path_element_map( *nextx, *nexty );<br />
if ( pos-&gtparent_ )<br />
{<br />
*nextx = pos-&gtparent_-&gtx_pos_;<br />
*nexty = pos-&gtparent_-&gty_pos_;<br />
result = ( pos-&gtparent_-&gtparent_ != NULL );<br />
}<br />
<br />
return result;<br />
}<br />
<br />
const static int cost_table_a[3][3] =<br />
{ { 1, 1, 1 },<br />
{ 3, 1, 3 },<br />
{ 1, 1, 1 } };<br />
<br />
const static int cost_table_b[3][3] =<br />
{ { 1, 3, 1 },<br />
{ 1, 1, 1 },<br />
{ 1, 3, 1 } };<br />
<br />
/* Updates cost to pos which is adjacent to parent. */<br />
void path_update_cost( struct path_element* parent, struct path_element*<br />
pos )<br />
{<br />
#ifndef MAP_VARIYING_COST<br />
pos-&gtcost_ = parent-&gtcost_ + 1;<br />
#else<br />
int dx = pos-&gtx_pos_ - parent-&gtx_pos_ + 1; /* dx = 0, 1, 2 */<br />
int dy = pos-&gty_pos_ - parent-&gty_pos_ + 1; /* dy = 0, 1, 2 */<br />
<br />
if ( pos-&gtx_pos_ & 1 )<br />
{<br />
pos-&gtcost_ = parent-&gtcost_ + cost_table_a[dx][dy];<br />
}<br />
else<br />
{<br />
pos-&gtcost_ = parent-&gtcost_ + cost_table_b[dx][dy];<br />
}<br />
#endif // MAP_VARIYING_COST<br />
}<br />
<br />
/* End of file */<br />
<br />
<br />
Pekka Nurminen<br />
</pre></div>
Lochok