http://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&feed=atom&action=historyThe Incredible Power of Dijkstra Maps - Revision history2024-03-28T17:54:27ZRevision history for this page on the wikiMediaWiki 1.36.0http://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&diff=52051&oldid=prevHernaldo at 01:45, 11 September 20222022-09-11T01:45:57Z<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 01:45, 11 September 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l37">Line 37:</td>
<td colspan="2" class="diff-lineno">Line 37:</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>* [[C#]]: [https://github.com/azsdaja/FloodSpill-CSharp FloodSpill]</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>* [[C#]]: [https://github.com/azsdaja/FloodSpill-CSharp FloodSpill]</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>* [[Go]]: [https://github.com/japanoise/dmap dmap]</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>* [[Go]]: [https://github.com/japanoise/dmap dmap]</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>* [[Python]]: [https://github.com/HenrYxZ/<del style="font-weight: bold; text-decoration: none;">flood flood</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>* [[Python]]: [https://github.com/HenrYxZ/<ins style="font-weight: bold; text-decoration: none;">dijkstra-map dijkstra-map</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;"><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>[[Category:Articles]][[Category:AI]][[Category:Maps]]</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>[[Category:Articles]][[Category:AI]][[Category:Maps]]</div></td></tr>
</table>Hernaldohttp://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&diff=51209&oldid=prevHernaldo: /* Implementations */2021-08-14T23:03:19Z<p><span dir="auto"><span class="autocomment">Implementations</span></span></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 23:03, 14 August 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l37">Line 37:</td>
<td colspan="2" class="diff-lineno">Line 37:</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>* [[C#]]: [https://github.com/azsdaja/FloodSpill-CSharp FloodSpill]</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>* [[C#]]: [https://github.com/azsdaja/FloodSpill-CSharp FloodSpill]</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>* [[Go]]: [https://github.com/japanoise/dmap dmap]</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>* [[Go]]: [https://github.com/japanoise/dmap dmap]</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;">* [[Python]]: [https://github.com/HenrYxZ/flood flood]</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;"><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>[[Category:Articles]][[Category:AI]][[Category:Maps]]</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>[[Category:Articles]][[Category:AI]][[Category:Maps]]</div></td></tr>
</table>Hernaldohttp://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&diff=48000&oldid=prevJapanoise: Add Go implementation2018-12-25T15:36:15Z<p>Add Go implementation</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 15:36, 25 December 2018</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l36">Line 36:</td>
<td colspan="2" class="diff-lineno">Line 36:</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>* [[Lua]]: [http://paulofmandown.github.io/rotLove/modules/ROT.DijkstraMap.html rotLove]</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>* [[Lua]]: [http://paulofmandown.github.io/rotLove/modules/ROT.DijkstraMap.html rotLove]</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>* [[C#]]: [https://github.com/azsdaja/FloodSpill-CSharp FloodSpill]</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>* [[C#]]: [https://github.com/azsdaja/FloodSpill-CSharp FloodSpill]</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;">* [[Go]]: [https://github.com/japanoise/dmap dmap]</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;"><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>[[Category:Articles]][[Category:AI]][[Category:Maps]]</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>[[Category:Articles]][[Category:AI]][[Category:Maps]]</div></td></tr>
</table>Japanoisehttp://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&diff=47949&oldid=prevDeaven: added a C# implementation2018-12-10T09:20:11Z<p>added a C# implementation</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 09:20, 10 December 2018</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l35">Line 35:</td>
<td colspan="2" class="diff-lineno">Line 35:</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>* [[Javascript]]: [http://ondras.github.io/rot.js/manual/#path rot.js]</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>* [[Javascript]]: [http://ondras.github.io/rot.js/manual/#path rot.js]</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>* [[Lua]]: [http://paulofmandown.github.io/rotLove/modules/ROT.DijkstraMap.html rotLove]</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>* [[Lua]]: [http://paulofmandown.github.io/rotLove/modules/ROT.DijkstraMap.html rotLove]</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;">* [[C#]]: [https://github.com/azsdaja/FloodSpill-CSharp FloodSpill]</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;"><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>[[Category:Articles]][[Category:AI]][[Category:Maps]]</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>[[Category:Articles]][[Category:AI]][[Category:Maps]]</div></td></tr>
</table>Deavenhttp://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&diff=47571&oldid=prevSugiivy: Changed value >=2 to >1 when calculating the map to avoid issues when creating safety maps (when parameter is greater than -2 - i.e. -1.2) and minor orthographic corrections2018-09-15T19:57:25Z<p>Changed value >=2 to >1 when calculating the map to avoid issues when creating safety maps (when parameter is greater than -2 - i.e. -1.2) and minor orthographic corrections</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 19:57, 15 September 2018</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</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>This article describes a few simple, mechanical techniques that do not involve any hand-waving or complicated state machines, but that can nevertheless give rise to <del style="font-weight: bold; text-decoration: none;">behavior </del>that is eerie in its seeming intelligence. I came up with these while developing [[Brogue]].</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>This article describes a few simple, mechanical techniques that do not involve any hand-waving or complicated state machines, but that can nevertheless give rise to <ins style="font-weight: bold; text-decoration: none;">behaviour </ins>that is eerie in its seeming intelligence. I came up with these while developing [[Brogue]].</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>I don't know if there is a better name for these things. I call them Dijkstra maps because of their similarity to the basic Dijkstra pathfinding algorithm, but rather than conducting a strict breadth-first search from a single point or set of points, I mean doing the following:</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>I don't know if there is a better name for these things. I call them Dijkstra maps because of their similarity to the basic Dijkstra pathfinding algorithm, but rather than conducting a strict breadth-first search from a single point or set of points, I mean doing the following:</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>To get a Dijkstra map, you start with an integer array representing your map, with some set of goal cells set to zero and all the rest set to a very high number. Iterate through the map's "floor" cells -- skip the impassable wall cells. If any floor tile has a value <del style="font-weight: bold; text-decoration: none;">that is at least 2 </del>greater than its lowest-value floor <del style="font-weight: bold; text-decoration: none;">neighbor </del>(in a cardinal direction - i.e. up, down, left or right), set it to be exactly 1 greater than its lowest value neighbor. Repeat until no changes are made. The resulting grid of numbers represents the number of steps that it will take to get from any given tile to the nearest goal.</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>To get a Dijkstra map, you start with an integer array representing your map, with some set of goal cells set to zero and all the rest set to a very high number. Iterate through the map's "floor" cells -- skip the impassable wall cells. If any floor tile has a value greater than <ins style="font-weight: bold; text-decoration: none;">1 regarding to </ins>its lowest-value floor <ins style="font-weight: bold; text-decoration: none;">neighbour </ins>(in a cardinal direction - i.e. up, down, left or right<ins style="font-weight: bold; text-decoration: none;">; a cell next to the one we are checking</ins>), set it to be exactly 1 greater than its lowest value neighbor. Repeat until no changes are made. The resulting grid of numbers represents the number of steps that it will take to get from any given tile to the nearest goal.</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>The obvious application is pathfinding. Make a Dijkstra map around a single goal point, and then no matter where you're starting from, you can just "roll downhill" on the Dijkstra map and you will reach the goal in an optimal number of moves. Note that this 'rolling' works with both 4 and 8-way movement, though you might want to add additional code to ensure units don't clip through non-walkable cells if moving diagonally.</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>The obvious application is pathfinding. Make a Dijkstra map around a single goal point, and then no matter where you're starting from, you can just "roll downhill" on the Dijkstra map and you will reach the goal in an optimal number of moves. Note that this 'rolling' works with both 4 and 8-way movement, though you might want to add additional code to ensure units don't clip through non-walkable cells if moving diagonally.</div></td></tr>
</table>Sugiivyhttp://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&diff=43126&oldid=prevPratyeka: add implementations2016-09-12T03:38:03Z<p>add implementations</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 03:38, 12 September 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l31">Line 31:</td>
<td colspan="2" class="diff-lineno">Line 31:</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>Want even more intelligence? Use more Dijkstra maps. Can a monster use wands but not swords? Instead of a single "items" map, have a separate "wands" map and "swords" map -- then you can have wizard monsters, tank monsters and gold-hoarding greedy monsters. The technique is scalable since (1) a Dijkstra map needs to be updated only when the underlying goal points change, so you need to recalculate the wands map only when a wand is picked up or dropped -- not every turn -- and (2) the Dijkstra maps will work for all monsters at the same time; adding more monsters to the map is cheap because each monster needs to keep track only of its desire coefficients, so even though monsters will have qualitatively different goals and behavior, there is no need to generate additional maps for each monster.</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>Want even more intelligence? Use more Dijkstra maps. Can a monster use wands but not swords? Instead of a single "items" map, have a separate "wands" map and "swords" map -- then you can have wizard monsters, tank monsters and gold-hoarding greedy monsters. The technique is scalable since (1) a Dijkstra map needs to be updated only when the underlying goal points change, so you need to recalculate the wands map only when a wand is picked up or dropped -- not every turn -- and (2) the Dijkstra maps will work for all monsters at the same time; adding more monsters to the map is cheap because each monster needs to keep track only of its desire coefficients, so even though monsters will have qualitatively different goals and behavior, there is no need to generate additional maps for each monster.</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;">== Implementations==</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;">* [[Javascript]]: [http://ondras.github.io/rot.js/manual/#path rot.js]</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;">* [[Lua]]: [http://paulofmandown.github.io/rotLove/modules/ROT.DijkstraMap.html rotLove]</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;"><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>[[Category:Articles]][[Category:AI]][[Category:Maps]]</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>[[Category:Articles]][[Category:AI]][[Category:Maps]]</div></td></tr>
</table>Pratyekahttp://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&diff=41768&oldid=prevMadrayken: In implementing this algorithm I realized that generation had to use cardinal directions in order to work, but movement could be 4 or 8-way.2016-01-14T19:13:13Z<p>In implementing this algorithm I realized that generation had to use cardinal directions in order to work, but movement could be 4 or 8-way.</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 19:13, 14 January 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3">Line 3:</td>
<td colspan="2" class="diff-lineno">Line 3:</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>I don't know if there is a better name for these things. I call them Dijkstra maps because of their similarity to the basic Dijkstra pathfinding algorithm, but rather than conducting a strict breadth-first search from a single point or set of points, I mean doing the following:</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>I don't know if there is a better name for these things. I call them Dijkstra maps because of their similarity to the basic Dijkstra pathfinding algorithm, but rather than conducting a strict breadth-first search from a single point or set of points, I mean doing the following:</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>To get a Dijkstra map, you start with an integer array representing your map, with some set of goal cells set to zero and all the rest set to a very high number. Iterate through the map's "floor" cells -- skip the impassable wall cells. If any floor tile has a value that is at least 2 greater than its lowest-value floor neighbor, set it to be exactly 1 greater than its lowest value neighbor. Repeat until no changes are made. The resulting grid of numbers represents the number of steps that it will take to get from any given tile to the nearest goal.</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>To get a Dijkstra map, you start with an integer array representing your map, with some set of goal cells set to zero and all the rest set to a very high number. Iterate through the map's "floor" cells -- skip the impassable wall cells. If any floor tile has a value that is at least 2 greater than its lowest-value floor neighbor <ins style="font-weight: bold; text-decoration: none;">(in a cardinal direction - i.e. up, down, left or right)</ins>, set it to be exactly 1 greater than its lowest value neighbor. Repeat until no changes are made. The resulting grid of numbers represents the number of steps that it will take to get from any given tile to the nearest goal.</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>The obvious application is pathfinding. Make a Dijkstra map around a single goal point, and then no matter where you're starting from, you can just "roll downhill" on the Dijkstra map and you will reach the goal in an optimal number of moves.</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>The obvious application is pathfinding. Make a Dijkstra map around a single goal point, and then no matter where you're starting from, you can just "roll downhill" on the Dijkstra map and you will reach the goal in an optimal number of moves<ins style="font-weight: bold; text-decoration: none;">. Note that this 'rolling' works with both 4 and 8-way movement, though you might want to add additional code to ensure units don't clip through non-walkable cells if moving diagonally</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;"><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>But there is SO MUCH MORE that these things can do. Here are the revelations I've had while making [[Brogue]]:</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>But there is SO MUCH MORE that these things can do. Here are the revelations I've had while making [[Brogue]]:</div></td></tr>
</table>Madraykenhttp://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&diff=36891&oldid=prevPender: Updated the third use case with a more powerful solution.2013-12-07T02:37:14Z<p>Updated the third use case with a more powerful solution.</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 02:37, 7 December 2013</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l13">Line 13:</td>
<td colspan="2" class="diff-lineno">Line 13:</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>'''2) [[Autoexplore]].''' We've all watched the [[Angband Borg]], right? And the [[Crawl]] autoexplore feature? With these methods, you can add an autoexplore feature in 20 minutes. For the goal points, use every tile that the player has not discovered. Pretend that undiscovered wall tiles are really floor tiles. Run the scan every turn. When the player rolls downhill on this continually updated map, he will automatically blaze around the level until there are no more unexplored tiles that he can reach. Have the function stop whenever a message appears on the screen or whenever a previously unseen monster comes into view so that the player can use it without extreme risk. Want him to collect items along the way? Set items that the player has not yet stepped on to be goal points along with the undiscovered tiles. Now your player can skip through mindless exploration with a single keystroke and get control back the moment something interesting occurs. In fact, it's trivial to take this a step further: cut out all of the interruptions and have the player attack any monster adjacent to him. When there is no more exploration to be done, set the downstairs as a goal point. When that is the case and he is standing on the downstairs tile, have him use the stairs and continue on the next level. In less than an hour, I had a single keystroke that would make the computer start playing automatically -- collecting items and fighting bad guys and descending -- until interrupted or killed.</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>'''2) [[Autoexplore]].''' We've all watched the [[Angband Borg]], right? And the [[Crawl]] autoexplore feature? With these methods, you can add an autoexplore feature in 20 minutes. For the goal points, use every tile that the player has not discovered. Pretend that undiscovered wall tiles are really floor tiles. Run the scan every turn. When the player rolls downhill on this continually updated map, he will automatically blaze around the level until there are no more unexplored tiles that he can reach. Have the function stop whenever a message appears on the screen or whenever a previously unseen monster comes into view so that the player can use it without extreme risk. Want him to collect items along the way? Set items that the player has not yet stepped on to be goal points along with the undiscovered tiles. Now your player can skip through mindless exploration with a single keystroke and get control back the moment something interesting occurs. In fact, it's trivial to take this a step further: cut out all of the interruptions and have the player attack any monster adjacent to him. When there is no more exploration to be done, set the downstairs as a goal point. When that is the case and he is standing on the downstairs tile, have him use the stairs and continue on the next level. In less than an hour, I had a single keystroke that would make the computer start playing automatically -- collecting items and fighting bad guys and descending -- until interrupted or killed.</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>'''3) <del style="font-weight: bold; text-decoration: none;">"Fuel low" warnings</del>.''' [[Brogue]] features Potions of Levitation, which cause the player to fly for a limited number of turns. It also features deadly lakes of lava that the player can fly over. It also features various automation features such as auto-travel and auto- explore that will plot routes based on what kinds of terrain are <del style="font-weight: bold; text-decoration: none;">currently </del>passable for the player. However, a levitating player can pass over lava, <del style="font-weight: bold; text-decoration: none;">and would therefore </del>get routed over a lava lake 20 spaces wide <del style="font-weight: bold; text-decoration: none;">-- even </del>when his levitation had only 10 turns left. What to do? Use a Dijkstra map, calculated once at level generation, to keep track of how many turns it takes to get out of a lava lake and back to solid ground from any given space in the lake -- just treat all land tiles as goals in the Dijkstra scan. If the number of turns to escape from the lake is equal to or one greater than the number of turns remaining in the levitation effect, a very stern warning pops up, and that interrupts auto-travel.</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>'''3) <ins style="font-weight: bold; text-decoration: none;">Dynamic routing</ins>.''' [[Brogue]] features Potions of Levitation, which cause the player to fly for a limited number of turns. It also features deadly lakes of lava that the player can fly over. It also features various automation features such as auto-travel and auto- explore that will plot routes based on what kinds of terrain are passable for the player. However, a levitating player can pass over lava, <ins style="font-weight: bold; text-decoration: none;">but he shouldn't </ins>get routed over a lava lake 20 spaces wide when his levitation had only 10 turns left<ins style="font-weight: bold; text-decoration: none;">. Nor do you want the player to wander out too far without realizing his error; much better to keep track of such details for him</ins>. What to do? Use a Dijkstra map, calculated once at level generation, to keep track of how many turns it takes to get out of a lava lake and back to solid ground from any given space in the lake -- just treat all land tiles as goals in the Dijkstra scan. If the number of turns to escape from the lake is equal to or one greater than the number of turns remaining in the levitation effect, a very stern warning pops up, and that interrupts auto-travel<ins style="font-weight: bold; text-decoration: none;">. To further constrain auto-travel and auto-explore, use a distance map calculated from the player's location as a way to determine how many turns it would take the player to reach each location. Then, if the player's levitation will have worn off before the player reaches a particular lava tile from his current location, mark that lava tile as impassible. If you calculate the auto-explore or auto-travel route with those tiles marked as impassible, you'll gracefully avoid taking the player over lava if (and only if) he doesn't have enough levitation to make it all the way across</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;"><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>'''4) Desire-driven AI.''' Most of the things a monster will do involve moving toward something or moving away from it. Here are some examples:</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>'''4) Desire-driven AI.''' Most of the things a monster will do involve moving toward something or moving away from it. Here are some examples:</div></td></tr>
</table>Penderhttp://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&diff=25887&oldid=prevBear: I'm creating a Maps category. This belongs in it.2011-10-22T15:28:18Z<p>I'm creating a Maps category. This belongs in it.</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 15:28, 22 October 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l32">Line 32:</td>
<td colspan="2" class="diff-lineno">Line 32:</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>Want even more intelligence? Use more Dijkstra maps. Can a monster use wands but not swords? Instead of a single "items" map, have a separate "wands" map and "swords" map -- then you can have wizard monsters, tank monsters and gold-hoarding greedy monsters. The technique is scalable since (1) a Dijkstra map needs to be updated only when the underlying goal points change, so you need to recalculate the wands map only when a wand is picked up or dropped -- not every turn -- and (2) the Dijkstra maps will work for all monsters at the same time; adding more monsters to the map is cheap because each monster needs to keep track only of its desire coefficients, so even though monsters will have qualitatively different goals and behavior, there is no need to generate additional maps for each monster.</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>Want even more intelligence? Use more Dijkstra maps. Can a monster use wands but not swords? Instead of a single "items" map, have a separate "wands" map and "swords" map -- then you can have wizard monsters, tank monsters and gold-hoarding greedy monsters. The technique is scalable since (1) a Dijkstra map needs to be updated only when the underlying goal points change, so you need to recalculate the wands map only when a wand is picked up or dropped -- not every turn -- and (2) the Dijkstra maps will work for all monsters at the same time; adding more monsters to the map is cheap because each monster needs to keep track only of its desire coefficients, so even though monsters will have qualitatively different goals and behavior, there is no need to generate additional maps for each monster.</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>[[Category:Articles]][[Category:AI]]</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>[[Category:Articles]][[Category:AI<ins style="font-weight: bold; text-decoration: none;">]][[Category:Maps</ins>]]</div></td></tr>
</table>Bearhttp://roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps&diff=25382&oldid=prevPender: Formatting; polish2011-09-05T02:59:51Z<p>Formatting; polish</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 02:59, 5 September 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</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>This article describes a few simple, mechanical techniques that do not involve any hand-waving or complicated state machines, but that can nevertheless give rise to behavior that is eerie in its seeming intelligence. I came up with these while developing [[Brogue]].</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>This article describes a few simple, mechanical techniques that do not involve any hand-waving or complicated state machines, but that can nevertheless give rise to behavior that is eerie in its seeming intelligence. I came up with these while developing [[Brogue]].</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>I <del style="font-weight: bold; text-decoration: none;">don’t </del>know if there is a better name for these things. I call them Dijkstra maps because of their similarity to the basic Dijkstra pathfinding algorithm, but rather than conducting a strict breadth-first search from a single point or set of points, I mean doing the following:</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>I <ins style="font-weight: bold; text-decoration: none;">don't </ins>know if there is a better name for these things. I call them Dijkstra maps because of their similarity to the basic Dijkstra pathfinding algorithm, but rather than conducting a strict breadth-first search from a single point or set of points, I mean doing the following:</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>To get a Dijkstra map, you start with an integer array representing your map, with some set of goal cells set to zero and all the rest set to a very high number. Iterate through the <del style="font-weight: bold; text-decoration: none;">map’s </del>"floor" cells -- skip the impassable wall cells. If any floor tile has a value that is at least 2 greater than its lowest-value floor neighbor, set it to be exactly 1 greater than its lowest value neighbor. Repeat until no changes are made.</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>To get a Dijkstra map, you start with an integer array representing your map, with some set of goal cells set to zero and all the rest set to a very high number. Iterate through the <ins style="font-weight: bold; text-decoration: none;">map's </ins>"floor" cells -- skip the impassable wall cells. If any floor tile has a value that is at least 2 greater than its lowest-value floor neighbor, set it to be exactly 1 greater than its lowest value neighbor. Repeat until no changes are made<ins style="font-weight: bold; text-decoration: none;">. The resulting grid of numbers represents the number of steps that it will take to get from any given tile to the nearest goal</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;"><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>The obvious application is pathfinding. Make a Dijkstra map around a single goal point, and then no matter where <del style="font-weight: bold; text-decoration: none;">you’re </del>starting from, you can just "roll downhill" on the Dijkstra map and you will reach the goal in an optimal number of moves.</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>The obvious application is pathfinding. Make a Dijkstra map around a single goal point, and then no matter where <ins style="font-weight: bold; text-decoration: none;">you're </ins>starting from, you can just "roll downhill" on the Dijkstra map and you will reach the goal in an optimal number of moves.</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>But there is SO MUCH MORE that these things can do. Here are the revelations <del style="font-weight: bold; text-decoration: none;">I’ve </del>had while making [[Brogue]]:</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>But there is SO MUCH MORE that these things can do. Here are the revelations <ins style="font-weight: bold; text-decoration: none;">I've </ins>had while making [[Brogue]]:</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>'''1) Safety maps.''' Everyone likes monsters that know how to flee. The problem is that <del style="font-weight: bold; text-decoration: none;">it’s </del>not easy to get them to flee intelligently. If they just run away from the player, <del style="font-weight: bold; text-decoration: none;">they’ll </del>bang their heads against the nearest corner of the room that they start in. This happens even if you use a Dijkstra map and try to roll uphill instead of downhill. Solution: Start with a Dijkstra map calculated around goal points at the player's location and at any player allies from which your monsters will also want to flee. Treat monsters that <del style="font-weight: bold; text-decoration: none;">haven’t </del>moved since last turn as obstacles. Multiply every value in the map by a negative number somewhere in the neighborhood of -1.2. Take the result and pass it back through the Dijkstra scanning function. Rolling downhill on the result (recalculated each time the player moves) will cause monsters to flee for the nearest door. If cornered, they will try to sprint past the player and escape. If you think of the amount of "safety" that a cell has as the distance between it and the player, the negative coefficient determines how much the monsters will prefer a global safety maximum to a local safety maximum -- e.g. how close the player has to get to a cornered monster before the monster tries to make a break for it. Using more negative numbers (i.e. negative numbers with a greater absolute value) will also make monsters more likely to exploit large loops in the level geometry and "pillar dance" as the player chases it. You can have as many fleeing monsters as you like, and they can all share this same map so that it needs to be updated only once per turn.</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>'''1) Safety maps.''' Everyone likes monsters that know how to flee. The problem is that <ins style="font-weight: bold; text-decoration: none;">it's </ins>not easy to get them to flee intelligently. If they just run away from the player, <ins style="font-weight: bold; text-decoration: none;">they'll </ins>bang their heads against the nearest corner of the room that they start in. This happens even if you use a Dijkstra map and try to roll uphill instead of downhill. Solution: Start with a Dijkstra map calculated around goal points at the player's location and at any player allies from which your monsters will also want to flee. Treat monsters that <ins style="font-weight: bold; text-decoration: none;">haven't </ins>moved since last turn as obstacles. Multiply every value in the map by a negative number somewhere in the neighborhood of -1.2. Take the result and pass it back through the Dijkstra scanning function. Rolling downhill on the result (recalculated each time the player moves) will cause monsters to flee for the nearest door. If cornered, they will try to sprint past the player and escape. If you think of the amount of "safety" that a cell has as the distance between it and the player, the negative coefficient determines how much the monsters will prefer a global safety maximum to a local safety maximum -- e.g. how close the player has to get to a cornered monster before the monster tries to make a break for it. Using more negative numbers (i.e. negative numbers with a greater absolute value) will also make monsters more likely to exploit large loops in the level geometry and "pillar dance" as the player chases it. You can have as many fleeing monsters as you like, and they can all share this same map so that it needs to be updated only once per turn.</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>'''2) [[Autoexplore]].''' <del style="font-weight: bold; text-decoration: none;">We’ve </del>all watched the [[Angband Borg]], right? And the [[Crawl]] autoexplore feature? With these methods, you can add an autoexplore feature in 20 minutes. For the goal points, use every tile that the player has not discovered. Pretend that undiscovered wall tiles are really floor tiles. Run the scan every turn. When the player rolls downhill on this continually updated map, he will automatically blaze around the level until there are no more unexplored tiles that he can reach. Have the function stop whenever a message appears on the screen or whenever a previously unseen monster comes into view so that the player can use it without extreme risk. Want him to collect items along the way? Set items that the player has not yet stepped on to be goal points along with the undiscovered tiles. Now your player can skip through mindless exploration with a single keystroke and get control back the moment something interesting occurs. In fact, <del style="font-weight: bold; text-decoration: none;">it’s </del>trivial to take this a step further: cut out all of the interruptions and have the player attack any monster adjacent to him. When there is no more exploration to be done, set the downstairs as a goal point. When that is the case and he is standing on the downstairs tile, have him use the stairs and continue on the next level. In less than an hour, I had a single keystroke that would make the computer start playing automatically -- collecting items and fighting bad guys and descending -- until interrupted or killed.</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>'''2) [[Autoexplore]].''' <ins style="font-weight: bold; text-decoration: none;">We've </ins>all watched the [[Angband Borg]], right? And the [[Crawl]] autoexplore feature? With these methods, you can add an autoexplore feature in 20 minutes. For the goal points, use every tile that the player has not discovered. Pretend that undiscovered wall tiles are really floor tiles. Run the scan every turn. When the player rolls downhill on this continually updated map, he will automatically blaze around the level until there are no more unexplored tiles that he can reach. Have the function stop whenever a message appears on the screen or whenever a previously unseen monster comes into view so that the player can use it without extreme risk. Want him to collect items along the way? Set items that the player has not yet stepped on to be goal points along with the undiscovered tiles. Now your player can skip through mindless exploration with a single keystroke and get control back the moment something interesting occurs. In fact, <ins style="font-weight: bold; text-decoration: none;">it's </ins>trivial to take this a step further: cut out all of the interruptions and have the player attack any monster adjacent to him. When there is no more exploration to be done, set the downstairs as a goal point. When that is the case and he is standing on the downstairs tile, have him use the stairs and continue on the next level. In less than an hour, I had a single keystroke that would make the computer start playing automatically -- collecting items and fighting bad guys and descending -- until interrupted or killed.</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>'''3) "Fuel low" warnings.''' [[Brogue]] features Potions of Levitation, which cause the player to fly for a limited number of turns. It also features deadly lakes of lava that the player can fly over. It also features various automation features such as auto-travel and auto- explore that will plot routes based on what kinds of terrain are currently passable for the player. However, a levitating player can pass over lava, and would therefore get routed over a lava lake 20 spaces wide -- even when his levitation had only 10 turns left. What to do? Use a Dijkstra map, calculated once at level generation, to keep track of how many turns it takes to get out of a lava lake and back to solid ground from any given space in the lake -- just treat all land tiles as goals in the Dijkstra scan. If the number of turns to escape from the lake is equal to or one greater than the number of turns remaining in the levitation effect, a very stern warning pops up, and that interrupts auto-travel.</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>'''3) "Fuel low" warnings.''' [[Brogue]] features Potions of Levitation, which cause the player to fly for a limited number of turns. It also features deadly lakes of lava that the player can fly over. It also features various automation features such as auto-travel and auto- explore that will plot routes based on what kinds of terrain are currently passable for the player. However, a levitating player can pass over lava, and would therefore get routed over a lava lake 20 spaces wide -- even when his levitation had only 10 turns left. What to do? Use a Dijkstra map, calculated once at level generation, to keep track of how many turns it takes to get out of a lava lake and back to solid ground from any given space in the lake -- just treat all land tiles as goals in the Dijkstra scan. If the number of turns to escape from the lake is equal to or one greater than the number of turns remaining in the levitation effect, a very stern warning pops up, and that interrupts auto-travel.</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l24">Line 24:</td>
<td colspan="2" class="diff-lineno">Line 24:</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>* Sounds: Investigate them, or avoid them.</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>* Sounds: Investigate them, or avoid them.</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>* Hive queen: Stay near her.</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>* Hive queen: Stay near her.</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>* Stealth: Prefer to be in cells that the player <del style="font-weight: bold; text-decoration: none;">can’t </del>currently see.</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>* Stealth: Prefer to be in cells that the player <ins style="font-weight: bold; text-decoration: none;">can't </ins>currently see.</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>Etc. Create one Dijkstra map for each of the above items, and update it every turn. (We also need another one if fleeing behavior is also relevant to that item -- see item (1) above for how to create a fleeing map). Now for each monster, keep track of how much it desires to be near that item; higher numbers indicate a desire to be near that item, zero indicates complete indifference, and negative numbers indicate a desire to be far away from that item. These numbers can change dynamically each turn. A <del style="font-weight: bold; text-decoration: none;">monster’s </del>desire for food might steadily rise every turn and be set back to zero if the monster is on a tile that contains food. A monster that sees the player might start out indifferent but want to approach the player if it sees the player do something it <del style="font-weight: bold; text-decoration: none;">doesn’t </del>like. Or if it sees the player reduce another monster to a smoldering crater with a single-syllable incantation, perhaps the monster will want very much not to be near the player and its number will go sharply negative. Each of these values should be set independently.</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>Etc. Create one Dijkstra map for each of the above items, and update it every turn. (We also need another one if fleeing behavior is also relevant to that item -- see item (1) above for how to create a fleeing map). Now for each monster, keep track of how much it desires to be near that item; higher numbers indicate a desire to be near that item, zero indicates complete indifference, and negative numbers indicate a desire to be far away from that item. These numbers can change dynamically each turn. A <ins style="font-weight: bold; text-decoration: none;">monster's </ins>desire for food might steadily rise every turn and be set back to zero if the monster is on a tile that contains food. A monster that sees the player might start out indifferent but want to approach the player if it sees the player do something it <ins style="font-weight: bold; text-decoration: none;">doesn't </ins>like. Or if it sees the player reduce another monster to a smoldering crater with a single-syllable incantation, perhaps the monster will want very much not to be near the player and its number will go sharply negative. Each of these values should be set independently.</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>Now, the key insight is that Dijkstra maps can be multiplied by the strength of these desires and then added together. To calculate how much a monster desires to move in a given direction, take each desire, multiply the <del style="font-weight: bold; text-decoration: none;">monster’s </del>coefficient for that desire by the value of the cell of the Dijkstra map that is in that direction, and sum over all desires. For positive desires, use the desire number as the coefficient; for negative numbers, turn the number positive and use it for the "fleeing" map of the same desire. Do this for each possible direction and let the monster move in the most desirable direction overall. With nine weighted sums, you will have a monster intelligently weighing conflicting ideas: "<del style="font-weight: bold; text-decoration: none;">can’t </del>stay near the queen because the player is too powerful for that to be a useful fight, and while east is a slightly more efficient escape route, west will take me past water (I am very thirsty) and also toward another of my compatriots -- so <del style="font-weight: bold; text-decoration: none;">I’ll </del>go west."</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>Now, the key insight is that Dijkstra maps can be multiplied by the strength of these desires and then added together. To calculate how much a monster desires to move in a given direction, take each desire, multiply the <ins style="font-weight: bold; text-decoration: none;">monster's </ins>coefficient for that desire by the value of the cell of the Dijkstra map that is in that direction, and sum over all desires. For positive desires, use the desire number as the coefficient; for negative numbers, turn the number positive and use it for the "fleeing" map of the same desire. Do this for each possible direction and let the monster move in the most desirable direction overall. With nine weighted sums, you will have a monster intelligently weighing conflicting ideas: "<ins style="font-weight: bold; text-decoration: none;">can't </ins>stay near the queen because the player is too powerful for that to be a useful fight, and while east is a slightly more efficient escape route, west will take me past water (I am very thirsty) and also toward another of my compatriots -- so <ins style="font-weight: bold; text-decoration: none;">I'll </ins>go west."</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>Want even more intelligence? Use more Dijkstra maps. Can a monster use wands but not swords? Instead of a single "items" map, have a separate "wands" map and "swords" map -- then you can have wizard monsters, tank monsters and gold-hoarding greedy monsters. The technique is scalable since (1) a Dijkstra map needs to be updated only when the underlying goal points change, so you need to recalculate the wands map only when a wand is picked up or dropped -- not every turn -- and (2) the Dijkstra maps will work for all monsters at the same time; adding more monsters to the map is cheap because each monster needs to keep track only of its desire coefficients, so even though monsters will have qualitatively different goals and behavior, there is no need to generate additional maps for each monster.</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>Want even more intelligence? Use more Dijkstra maps. Can a monster use wands but not swords? Instead of a single "items" map, have a separate "wands" map and "swords" map -- then you can have wizard monsters, tank monsters and gold-hoarding greedy monsters. The technique is scalable since (1) a Dijkstra map needs to be updated only when the underlying goal points change, so you need to recalculate the wands map only when a wand is picked up or dropped -- not every turn -- and (2) the Dijkstra maps will work for all monsters at the same time; adding more monsters to the map is cheap because each monster needs to keep track only of its desire coefficients, so even though monsters will have qualitatively different goals and behavior, there is no need to generate additional maps for each monster.</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>[[Category:Articles]][[Category:AI]]</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>[[Category:Articles]][[Category:AI]]</div></td></tr>
</table>Pender