<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en-GB">
	<id>https://wiki.gideros.rocks/index.php?action=history&amp;feed=atom&amp;title=Pathfinding</id>
	<title>Pathfinding - Revision history</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.gideros.rocks/index.php?action=history&amp;feed=atom&amp;title=Pathfinding"/>
	<link rel="alternate" type="text/html" href="https://wiki.gideros.rocks/index.php?title=Pathfinding&amp;action=history"/>
	<updated>2026-11-17T14:14:57Z</updated>
	<subtitle>Revision history for this page on the wiki</subtitle>
	<generator>MediaWiki 1.43.11</generator>
	<entry>
		<id>https://wiki.gideros.rocks/index.php?title=Pathfinding&amp;diff=24992&amp;oldid=prev</id>
		<title>MoKaLux at 00:34, 23 January 2026</title>
		<link rel="alternate" type="text/html" href="https://wiki.gideros.rocks/index.php?title=Pathfinding&amp;diff=24992&amp;oldid=prev"/>
		<updated>2026-01-23T00:34:09Z</updated>

		<summary type="html">&lt;p&gt;&lt;/p&gt;
&lt;table style=&quot;background-color: #fff; color: #202122;&quot; data-mw=&quot;interface&quot;&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;tr class=&quot;diff-title&quot; lang=&quot;en-GB&quot;&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;← Older revision&lt;/td&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;Revision as of 00:34, 23 January 2026&lt;/td&gt;
				&lt;/tr&gt;&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l1&quot;&gt;Line 1:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Line 1:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;__TOC__&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;__TOC__&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;=== Pathfinding ===&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;=== Jumper by Roland Yonaba ===&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;=&lt;/del&gt;=== Jumper by Roland Yonaba &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;=&lt;/del&gt;===&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;The &lt;/ins&gt;&#039;&#039;&#039;&#039;&#039;Jumper&#039;&#039;&#039;&#039;&#039; &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;pathfinding &lt;/ins&gt;library&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;, &lt;/ins&gt;written by &#039;&#039;&#039;Roland Yonaba&#039;&#039;&#039;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;, &lt;/ins&gt;is optimized for Lua and has 6 pathfinding algorithms: &quot;&#039;&#039;&#039;ASTAR&#039;&#039;&#039;&quot;, &quot;&#039;&#039;&#039;DIJKSTRA&#039;&#039;&#039;&quot;, &quot;&#039;&#039;&#039;THETASTAR&#039;&#039;&#039;&quot;, &quot;&#039;&#039;&#039;BFS&#039;&#039;&#039;&quot;, &quot;&#039;&#039;&#039;DFS&#039;&#039;&#039;&quot;, &quot;&#039;&#039;&#039;JPS&#039;&#039;&#039;&quot;.&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&quot;&lt;/del&gt;&#039;&#039;&#039;&#039;&#039;Jumper&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;, very fast pathfinder for 2d grid based games&lt;/del&gt;&#039;&#039;&#039;&#039;&#039;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&quot;&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt; &lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Our first Pathfinder &lt;/del&gt;library &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;will be &#039;&#039;&#039;&#039;&#039;Jumper&#039;&#039;&#039;&#039;&#039; &lt;/del&gt;written by &#039;&#039;&#039;Roland Yonaba&#039;&#039;&#039;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;. It &lt;/del&gt;is optimized for Lua and has 6 pathfinding algorithms: &quot;&#039;&#039;&#039;ASTAR&#039;&#039;&#039;&quot;, &quot;&#039;&#039;&#039;DIJKSTRA&#039;&#039;&#039;&quot;, &quot;&#039;&#039;&#039;THETASTAR&#039;&#039;&#039;&quot;, &quot;&#039;&#039;&#039;BFS&#039;&#039;&#039;&quot;, &quot;&#039;&#039;&#039;DFS&#039;&#039;&#039;&quot;, &quot;&#039;&#039;&#039;JPS&#039;&#039;&#039;&quot;.&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;* GH: &amp;#039;&amp;#039;&amp;#039;https://github.com/Yonaba/Jumper&amp;#039;&amp;#039;&amp;#039;&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;* GH: &amp;#039;&amp;#039;&amp;#039;https://github.com/Yonaba/Jumper&amp;#039;&amp;#039;&amp;#039;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;* GF: &amp;#039;&amp;#039;&amp;#039;http://forum.giderosmobile.com/discussion/1081/jumper-very-fast-pathfinder-for-2d-grid-based-games&amp;#039;&amp;#039;&amp;#039;&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;* GF: &amp;#039;&amp;#039;&amp;#039;http://forum.giderosmobile.com/discussion/1081/jumper-very-fast-pathfinder-for-2d-grid-based-games&amp;#039;&amp;#039;&amp;#039;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&quot;&#039;&#039;&#039;&#039;&#039;Jumper, very fast pathfinder for 2d grid based games&#039;&#039;&#039;&#039;&#039;&quot;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;The Gideros version of &amp;#039;&amp;#039;Jumper&amp;#039;&amp;#039; has:&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;The Gideros version of &amp;#039;&amp;#039;Jumper&amp;#039;&amp;#039; has:&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l17&quot;&gt;Line 17:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Line 16:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;You can download the Library and extract it as is in your &amp;#039;&amp;#039;assets&amp;#039;&amp;#039; folder:&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;You can download the Library and extract it as is in your &amp;#039;&amp;#039;assets&amp;#039;&amp;#039; folder:&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;==== &lt;/del&gt;&#039;&#039;&#039;[[Media:GJumper.zip]]&#039;&#039;&#039; &lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;====&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;*&lt;/ins&gt;&#039;&#039;&#039;[[Media:GJumper.zip]]&#039;&#039;&#039;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;=== Demos ===&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;=&lt;/ins&gt;=== Demos &lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;=&lt;/ins&gt;===&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&amp;lt;syntaxhighlight lang=&amp;quot;lua&amp;quot;&amp;gt;&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;&amp;lt;syntaxhighlight lang=&amp;quot;lua&amp;quot;&amp;gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;-- https://github.com/Yonaba/Jumper/tree/master/examples&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;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;&quot;&gt;&lt;div&gt;-- https://github.com/Yonaba/Jumper/tree/master/examples&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;/table&gt;</summary>
		<author><name>MoKaLux</name></author>
	</entry>
	<entry>
		<id>https://wiki.gideros.rocks/index.php?title=Pathfinding&amp;diff=23226&amp;oldid=prev</id>
		<title>MoKaLux: Created page with &quot;__TOC__  === Pathfinding === ==== Jumper by Roland Yonaba ==== &quot;&#039;&#039;&#039;&#039;&#039;Jumper, very fast pathfinder for 2d grid based games&#039;&#039;&#039;&#039;&#039;&quot;  Our first Pathfinder library will be &#039;&#039;&#039;&#039;&#039;Jump...&quot;</title>
		<link rel="alternate" type="text/html" href="https://wiki.gideros.rocks/index.php?title=Pathfinding&amp;diff=23226&amp;oldid=prev"/>
		<updated>2023-12-06T08:49:52Z</updated>

		<summary type="html">&lt;p&gt;Created page with &amp;quot;__TOC__  === Pathfinding === ==== Jumper by Roland Yonaba ==== &amp;quot;&amp;#039;&amp;#039;&amp;#039;&amp;#039;&amp;#039;Jumper, very fast pathfinder for 2d grid based games&amp;#039;&amp;#039;&amp;#039;&amp;#039;&amp;#039;&amp;quot;  Our first Pathfinder library will be &amp;#039;&amp;#039;&amp;#039;&amp;#039;&amp;#039;Jump...&amp;quot;&lt;/p&gt;
&lt;p&gt;&lt;b&gt;New page&lt;/b&gt;&lt;/p&gt;&lt;div&gt;__TOC__&lt;br /&gt;
&lt;br /&gt;
=== Pathfinding ===&lt;br /&gt;
==== Jumper by Roland Yonaba ====&lt;br /&gt;
&amp;quot;&amp;#039;&amp;#039;&amp;#039;&amp;#039;&amp;#039;Jumper, very fast pathfinder for 2d grid based games&amp;#039;&amp;#039;&amp;#039;&amp;#039;&amp;#039;&amp;quot;&lt;br /&gt;
&lt;br /&gt;
Our first Pathfinder library will be &amp;#039;&amp;#039;&amp;#039;&amp;#039;&amp;#039;Jumper&amp;#039;&amp;#039;&amp;#039;&amp;#039;&amp;#039; written by &amp;#039;&amp;#039;&amp;#039;Roland Yonaba&amp;#039;&amp;#039;&amp;#039;. It is optimized for Lua and has 6 pathfinding algorithms: &amp;quot;&amp;#039;&amp;#039;&amp;#039;ASTAR&amp;#039;&amp;#039;&amp;#039;&amp;quot;, &amp;quot;&amp;#039;&amp;#039;&amp;#039;DIJKSTRA&amp;#039;&amp;#039;&amp;#039;&amp;quot;, &amp;quot;&amp;#039;&amp;#039;&amp;#039;THETASTAR&amp;#039;&amp;#039;&amp;#039;&amp;quot;, &amp;quot;&amp;#039;&amp;#039;&amp;#039;BFS&amp;#039;&amp;#039;&amp;#039;&amp;quot;, &amp;quot;&amp;#039;&amp;#039;&amp;#039;DFS&amp;#039;&amp;#039;&amp;#039;&amp;quot;, &amp;quot;&amp;#039;&amp;#039;&amp;#039;JPS&amp;#039;&amp;#039;&amp;#039;&amp;quot;.&lt;br /&gt;
&lt;br /&gt;
* GH: &amp;#039;&amp;#039;&amp;#039;https://github.com/Yonaba/Jumper&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
* GF: &amp;#039;&amp;#039;&amp;#039;http://forum.giderosmobile.com/discussion/1081/jumper-very-fast-pathfinder-for-2d-grid-based-games&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
&lt;br /&gt;
The Gideros version of &amp;#039;&amp;#039;Jumper&amp;#039;&amp;#039; has:&lt;br /&gt;
* pull requests (PRs) present on &amp;#039;&amp;#039;Jumper&amp;#039;&amp;#039; GH but not merged by the original author&lt;br /&gt;
* specific Gideros Luau Enhancements&lt;br /&gt;
&lt;br /&gt;
The library has been tested quite thoroughly but I am no Pathfinding expert.&lt;br /&gt;
&lt;br /&gt;
You can download the Library and extract it as is in your &amp;#039;&amp;#039;assets&amp;#039;&amp;#039; folder:&lt;br /&gt;
==== &amp;#039;&amp;#039;&amp;#039;[[Media:GJumper.zip]]&amp;#039;&amp;#039;&amp;#039; ====&lt;br /&gt;
&lt;br /&gt;
=== Demos ===&lt;br /&gt;
&amp;lt;syntaxhighlight lang=&amp;quot;lua&amp;quot;&amp;gt;&lt;br /&gt;
-- https://github.com/Yonaba/Jumper/tree/master/examples&lt;br /&gt;
&lt;br /&gt;
local Grid = require &amp;quot;Jumper/grid&amp;quot;&lt;br /&gt;
local Pathfinder = require &amp;quot;Jumper/pathfinder&amp;quot;&lt;br /&gt;
&lt;br /&gt;
-- bg&lt;br /&gt;
application:setBackgroundColor(0x555555)&lt;br /&gt;
&lt;br /&gt;
-- pathfinding map (must be rectangle/square shaped)&lt;br /&gt;
local mapping = {&lt;br /&gt;
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,},&lt;br /&gt;
	{1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,1,},&lt;br /&gt;
	{1,0,5,0,0,0,0,0,0,0,0,0,0,0,0,1,},&lt;br /&gt;
	{1,0,0,3,3,0,0,0,0,0,0,0,0,0,0,1,},&lt;br /&gt;
	{1,0,2,2,2,2,0,0,0,2,0,0,0,0,0,1,},&lt;br /&gt;
	{1,0,0,0,0,0,2,2,2,0,0,0,0,0,0,1,},&lt;br /&gt;
	{1,0,0,0,0,0,2,2,2,0,0,0,0,0,0,1,},&lt;br /&gt;
	{1,0,0,0,0,0,2,2,2,0,0,0,0,0,0,1,},&lt;br /&gt;
	{1,0,0,2,2,2,2,0,0,0,0,0,0,0,0,1,},&lt;br /&gt;
	{1,0,0,0,2,0,0,0,0,0,0,0,0,0,0,1,},&lt;br /&gt;
	{1,0,0,3,3,0,0,0,0,0,0,0,0,0,0,1,},&lt;br /&gt;
	{1,0,3,3,0,0,0,0,0,0,0,0,0,0,0,1,},&lt;br /&gt;
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,},&lt;br /&gt;
}&lt;br /&gt;
&lt;br /&gt;
-- map settings&lt;br /&gt;
local CELL_W, CELL_H = 32, 32&lt;br /&gt;
&lt;br /&gt;
-- a player1&lt;br /&gt;
local player1 = Pixel.new(0x550000, 1, 8*2, 8*2)&lt;br /&gt;
local p1w, p1h = player1:getDimensions()&lt;br /&gt;
player1:setAnchorPosition(-(CELL_W-p1w)/2, -(CELL_H-p1h)/2)&lt;br /&gt;
local p1col, p1row -- we set the player1 position when we draw the map&lt;br /&gt;
local mc = MovieClip.new({{0,0,player1}}, true) -- movieclip to simulate player1 movement&lt;br /&gt;
&lt;br /&gt;
-- pathfinding walkable&lt;br /&gt;
--local walkable = 0 -- for a single value&lt;br /&gt;
local function walkable(value) -- for multiple values&lt;br /&gt;
--	return value:match(&amp;quot;[#.*]&amp;quot;) -- for special characters&lt;br /&gt;
	return value == 0 or value == 3 -- values 0 and 3 are walkable&lt;br /&gt;
end&lt;br /&gt;
&lt;br /&gt;
-- drawing the map&lt;br /&gt;
local map = Sprite.new()&lt;br /&gt;
for row = 1, #mapping do&lt;br /&gt;
	for col = 1, #mapping[1] do&lt;br /&gt;
		local pix = Pixel.new(0xaaff00, 1, CELL_W, CELL_H)&lt;br /&gt;
		if mapping[row][col] == 0 then pix:setColor(0xaaff00) -- ground&lt;br /&gt;
		elseif mapping[row][col] == 1 then pix:setColor(0xff5500) -- walls&lt;br /&gt;
		elseif mapping[row][col] == 2 then pix:setColor(0xffaa00) -- sand&lt;br /&gt;
		elseif mapping[row][col] == 3 then pix:setColor(0x00aaff) -- water&lt;br /&gt;
		elseif mapping[row][col] == 5 then p1col = col; p1row = row -- 5 = player1 starting position&lt;br /&gt;
		else pix:setColor(math.random(0xff0000)) -- unknown cell&lt;br /&gt;
		end&lt;br /&gt;
		pix:setPosition(col*CELL_W, row*CELL_H)&lt;br /&gt;
		map:addChild(pix)&lt;br /&gt;
	end&lt;br /&gt;
end&lt;br /&gt;
&lt;br /&gt;
local grid = Grid(mapping)&lt;br /&gt;
local myFinder = Pathfinder(grid, &amp;quot;ASTAR&amp;quot;, walkable) -- steps&lt;br /&gt;
--local myFinder = Pathfinder(grid, &amp;quot;DIJKSTRA&amp;quot;, walkable) -- steps&lt;br /&gt;
--local myFinder = Pathfinder(grid, &amp;quot;THETASTAR&amp;quot;, walkable) -- straight&lt;br /&gt;
--local myFinder = Pathfinder(grid, &amp;quot;BFS&amp;quot;, walkable) -- steps&lt;br /&gt;
--local myFinder = Pathfinder(grid, &amp;quot;DFS&amp;quot;, walkable) -- the longest steps path!!!&lt;br /&gt;
--local myFinder = Pathfinder(grid, &amp;quot;JPS&amp;quot;, walkable) -- straight, the fastest&lt;br /&gt;
&lt;br /&gt;
-- finder params&lt;br /&gt;
--myFinder:setTunnelling(true)&lt;br /&gt;
&lt;br /&gt;
-- position&lt;br /&gt;
player1:setPosition(p1col*CELL_W, p1row*CELL_H)&lt;br /&gt;
mapping[p1row][p1col] = 0 -- make player1 starting position walkable (row, col)&lt;br /&gt;
&lt;br /&gt;
-- order&lt;br /&gt;
stage:addChild(map)&lt;br /&gt;
stage:addChild(player1)&lt;br /&gt;
stage:addChild(mc)&lt;br /&gt;
&lt;br /&gt;
-- listeners&lt;br /&gt;
local anims = {} -- for the movieclip&lt;br /&gt;
local timing = 8*1.5 -- for the movieclip&lt;br /&gt;
local completed = true -- allows movement only when previous completed&lt;br /&gt;
local function pathmove(path)&lt;br /&gt;
--	print((&amp;#039;Step: %d -&amp;gt; x: %d -&amp;gt; y: %d&amp;#039;):format(count, node:getX(), node:getY()))&lt;br /&gt;
	completed = false -- processing movements&lt;br /&gt;
	for node, count in path:nodes() do&lt;br /&gt;
		p1col, p1row = node:getX(), node:getY() -- set new player1 position&lt;br /&gt;
		anims[count] = {&lt;br /&gt;
			(count-1)*timing+1, count*timing, player1,&lt;br /&gt;
			{&lt;br /&gt;
				x = p1col*CELL_W,&lt;br /&gt;
				y = p1row*CELL_H,&lt;br /&gt;
			}&lt;br /&gt;
		}&lt;br /&gt;
	end&lt;br /&gt;
	mc = MovieClip.new(anims)&lt;br /&gt;
	mc:play() -- play only once&lt;br /&gt;
	mc:addEventListener(Event.COMPLETE, function()&lt;br /&gt;
		completed = true -- movements complete&lt;br /&gt;
		anims = {}&lt;br /&gt;
	end)&lt;br /&gt;
end&lt;br /&gt;
&lt;br /&gt;
local walls = {} -- create a list of walls we can add/remove&lt;br /&gt;
&lt;br /&gt;
map:addEventListener(Event.MOUSE_UP, function(e)&lt;br /&gt;
	if map:hitTestPoint(e.x, e.y) then&lt;br /&gt;
		local x, y = map:globalToLocal(e.x, e.y) -- mouse coords on the map&lt;br /&gt;
		local button, _modifier = e.button, e.modifiers&lt;br /&gt;
		local mapcol, maprow = x//CELL_W, y//CELL_H -- convert mouse coords to map coords&lt;br /&gt;
		if button == 2 then -- RMB add/remove walls&lt;br /&gt;
--			if mapping[maprow][mapcol] == 0 then -- one walkable&lt;br /&gt;
			if walkable(mapping[maprow][mapcol]) then -- multiple walkable&lt;br /&gt;
				if not walls[maprow..mapcol] then -- create only one wall per cell&lt;br /&gt;
					walls[maprow..mapcol] = {&lt;br /&gt;
						index=mapping[maprow][mapcol],&lt;br /&gt;
						pixel=Pixel.new(0x000000, 0.5, CELL_W, CELL_H),&lt;br /&gt;
					}&lt;br /&gt;
				end&lt;br /&gt;
				walls[maprow..mapcol].pixel:setPosition(mapcol*CELL_W, maprow*CELL_H)&lt;br /&gt;
				map:addChild(walls[maprow..mapcol].pixel)&lt;br /&gt;
				mapping[maprow][mapcol] = 1 -- set the cell as being a wall&lt;br /&gt;
			else -- wall already exist hide it&lt;br /&gt;
				if walls[maprow..mapcol] then&lt;br /&gt;
					walls[maprow..mapcol].pixel:setVisible(false)&lt;br /&gt;
					mapping[maprow][mapcol] = walls[maprow..mapcol].index -- reset original index&lt;br /&gt;
				end&lt;br /&gt;
			end&lt;br /&gt;
		else -- LMB&lt;br /&gt;
			if walkable(mapping[maprow][mapcol]) and completed then -- cell is walkable and player1 has finished moving&lt;br /&gt;
				local path = myFinder:getPath(p1col, p1row, mapcol, maprow) -- pathfinding&lt;br /&gt;
				if path then pathmove(path) end&lt;br /&gt;
			else&lt;br /&gt;
				print(&amp;quot;UNREACHABLE DESTINATION!&amp;quot;)&lt;br /&gt;
			end&lt;br /&gt;
		end&lt;br /&gt;
		e:stopPropagation()&lt;br /&gt;
	end&lt;br /&gt;
end)&lt;br /&gt;
&amp;lt;/syntaxhighlight&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Left click somewhere on the grass to move the player, right click to add/remove walls&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
&lt;br /&gt;
{{#widget:GApp|app=JumperDemo1.GApp|width=480|height=320}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Demo 2: clearance&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
&amp;lt;syntaxhighlight lang=&amp;quot;lua&amp;quot;&amp;gt;&lt;br /&gt;
-- Tests sample for clearance metrics calculation&lt;br /&gt;
-- See Figure 10 at http://aigamedev.com/open/tutorial/clearance-based-pathfinding/&lt;br /&gt;
-- https://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/&lt;br /&gt;
local Grid = require &amp;quot;Jumper/grid&amp;quot;&lt;br /&gt;
local PF = require &amp;quot;Jumper/pathfinder&amp;quot;&lt;br /&gt;
local map = {&lt;br /&gt;
	{0,0,0,0,0,0,0,0,0,0},&lt;br /&gt;
	{0,0,0,0,0,0,0,0,1,0},&lt;br /&gt;
	{0,0,0,0,0,0,0,0,0,0},&lt;br /&gt;
	{0,0,0,1,0,0,0,0,0,0},&lt;br /&gt;
	{0,0,1,0,0,0,0,0,2,0},&lt;br /&gt;
	{0,0,1,1,1,0,0,2,0,0},&lt;br /&gt;
	{0,0,0,1,1,0,2,0,0,2},&lt;br /&gt;
	{0,0,0,0,1,0,0,0,0,2},&lt;br /&gt;
	{0,0,0,0,0,0,0,0,0,0},&lt;br /&gt;
	{0,0,0,0,0,0,0,0,0,0},&lt;br /&gt;
}&lt;br /&gt;
local grid = Grid(map)&lt;br /&gt;
local walkable = function(v) return v~=2 end&lt;br /&gt;
local finder = PF(grid, &amp;quot;ASTAR&amp;quot;, walkable)&lt;br /&gt;
finder:annotateGrid()&lt;br /&gt;
&lt;br /&gt;
for y = 1, #map do&lt;br /&gt;
	local s = &amp;quot;&amp;quot;&lt;br /&gt;
	for x = 1, #map[y] do&lt;br /&gt;
		local node = grid:getNodeAt(x, y)&lt;br /&gt;
		s = (s .. &amp;quot; &amp;quot; .. node:getClearance(walkable))&lt;br /&gt;
	end&lt;br /&gt;
	print(s)&lt;br /&gt;
end&lt;br /&gt;
&lt;br /&gt;
--[[&lt;br /&gt;
-- Expected output&lt;br /&gt;
--  6 6 5 5 4 4 4 3 2 1&lt;br /&gt;
--  6 5 5 4 4 3 3 3 2 1&lt;br /&gt;
--  6 5 4 4 3 3 2 2 2 1&lt;br /&gt;
--  6 5 4 3 3 2 2 1 1 1&lt;br /&gt;
--  6 5 4 3 2 2 1 1 0 1&lt;br /&gt;
--  5 5 4 3 2 1 1 0 1 1&lt;br /&gt;
--  4 4 4 3 2 1 0 2 1 0&lt;br /&gt;
--  3 3 3 3 3 3 3 2 1 0&lt;br /&gt;
--  2 2 2 2 2 2 2 2 2 1&lt;br /&gt;
--  1 1 1 1 1 1 1 1 1 1&lt;br /&gt;
]]&lt;br /&gt;
&amp;lt;/syntaxhighlight&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Demo 3: Heuristics&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
&amp;lt;syntaxhighlight lang=&amp;quot;lua&amp;quot;&amp;gt;&lt;br /&gt;
--- Example of use for Heuristics&lt;br /&gt;
&lt;br /&gt;
local Grid = require &amp;quot;Jumper/grid&amp;quot;&lt;br /&gt;
local Pathfinder = require &amp;quot;Jumper/pathfinder&amp;quot;&lt;br /&gt;
&lt;br /&gt;
local map = {&lt;br /&gt;
	  {0,0,0,0,0,0,0},&lt;br /&gt;
	  {0,0,0,0,0,0,0},&lt;br /&gt;
	  {0,1,1,0,1,1,0},&lt;br /&gt;
	  {0,1,1,0,1,1,0},&lt;br /&gt;
	  {0,1,1,0,1,1,0},&lt;br /&gt;
	  {0,1,1,0,1,1,0},&lt;br /&gt;
	  {0,1,1,0,1,1,0},&lt;br /&gt;
	  {0,1,1,0,1,1,0},&lt;br /&gt;
	  {0,1,1,0,1,1,0},&lt;br /&gt;
	  {0,0,0,0,0,0,0},&lt;br /&gt;
	  {0,0,0,0,0,0,0},&lt;br /&gt;
}&lt;br /&gt;
&lt;br /&gt;
local walkable = 0&lt;br /&gt;
local grid = Grid(map)&lt;br /&gt;
local myFinder = Pathfinder(grid, &amp;quot;ASTAR&amp;quot;, walkable)&lt;br /&gt;
&lt;br /&gt;
-- Use Euclidean heuristic to evaluate distance&lt;br /&gt;
myFinder:setHeuristic(&amp;quot;EUCLIDEAN&amp;quot;)&lt;br /&gt;
myFinder:setHeuristic(&amp;quot;DIAGONAL&amp;quot;)&lt;br /&gt;
myFinder:setHeuristic(&amp;quot;MANHATTAN&amp;quot;)&lt;br /&gt;
&lt;br /&gt;
-- Custom&lt;br /&gt;
local h = function(nodeA, nodeB)&lt;br /&gt;
	return (&lt;br /&gt;
		0.1 * (-(nodeA:getX() - nodeB:getX()) &amp;lt;&amp;gt; (nodeA:getX() - nodeB:getX())) +&lt;br /&gt;
		0.9 * (-(nodeA:getY() - nodeB:getY()) &amp;lt;&amp;gt; (nodeA:getY() - nodeB:getY()))&lt;br /&gt;
	)&lt;br /&gt;
end&lt;br /&gt;
myFinder:setHeuristic(h)&lt;br /&gt;
&lt;br /&gt;
local p = myFinder:getPath(1,1, 6,10)&lt;br /&gt;
for node, count in p:nodes() do&lt;br /&gt;
	print((&amp;quot;%d. Node(%d,%d)&amp;quot;):format(count, node:getX(), node:getY()))&lt;br /&gt;
end&lt;br /&gt;
print((&amp;quot;Path length: %.2f&amp;quot;):format(p:getLength()))&lt;br /&gt;
&lt;br /&gt;
-- etc ...&lt;br /&gt;
&amp;lt;/syntaxhighlight&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Demo 4: Benchmark&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
&amp;lt;syntaxhighlight lang=&amp;quot;lua&amp;quot;&amp;gt;&lt;br /&gt;
-- A stress test for the pathfinding library Jumper (v1.8.1)&lt;br /&gt;
-- Source: https://github.com/Yonaba/Jumper/tree/jumper-1.8.1-1&lt;br /&gt;
&lt;br /&gt;
-- The purpose of this is to compare the relative performance of different&lt;br /&gt;
-- search algorithms implemented in Jumper. Time measurements uses Lua&amp;#039;s &lt;br /&gt;
-- native os.clock with (milliseconds precision).&lt;br /&gt;
&lt;br /&gt;
-- Library setup&lt;br /&gt;
local Grid = require &amp;quot;Jumper/grid&amp;quot;&lt;br /&gt;
local Pathfinder = require &amp;quot;Jumper/pathfinder&amp;quot;&lt;br /&gt;
&lt;br /&gt;
-- Local references&lt;br /&gt;
local cg = collectgarbage&lt;br /&gt;
local floor, rand = math.floor, math.random&lt;br /&gt;
local ipairs = ipairs&lt;br /&gt;
&lt;br /&gt;
-- Random seed for random generation&lt;br /&gt;
math.randomseed(os.time())&lt;br /&gt;
&lt;br /&gt;
-- This function adds unwalkable tiles to a given map.&lt;br /&gt;
-- P is the percentage of unwalkable locations, in [0 .. 1]&lt;br /&gt;
-- In this demo, we can let it be 0.3 (i.e. 30%)&lt;br /&gt;
local function obstruct(map, h, w, p)&lt;br /&gt;
	-- skipping the borders to ensure generating a solvable problem&lt;br /&gt;
	for y = 2, h-1 do&lt;br /&gt;
		for x = 2, w-1 do&lt;br /&gt;
			map[y][x] = math.random() &amp;lt; p and 1 or 0 -- random weighting&lt;br /&gt;
		end&lt;br /&gt;
	end&lt;br /&gt;
end&lt;br /&gt;
&lt;br /&gt;
-- A custom function to draw visually the collision map.&lt;br /&gt;
local function drawGrid(m)&lt;br /&gt;
	for y,row in ipairs(m) do print(table.concat(row)) end&lt;br /&gt;
end&lt;br /&gt;
&lt;br /&gt;
-- Creates the collision map, adds unwalkable tiles&lt;br /&gt;
-- and returns it along with the memory consumed to store the grid&lt;br /&gt;
local function makeGrid(w, h, p)&lt;br /&gt;
	local m = {}&lt;br /&gt;
	for y = 1, h do m[y] = {}&lt;br /&gt;
		for x = 1, w do m[y][x] = 0 end&lt;br /&gt;
	end&lt;br /&gt;
	obstruct(m, h, w, p)&lt;br /&gt;
	-- drawGrid(m)&lt;br /&gt;
	local sizeCount = cg(&amp;quot;count&amp;quot;)&lt;br /&gt;
	local grid = Grid(m)&lt;br /&gt;
	return grid, (cg(&amp;quot;count&amp;quot;)-sizeCount)&lt;br /&gt;
end&lt;br /&gt;
&lt;br /&gt;
-- Performs a path request and return the path, its length and the time of search in ms.&lt;br /&gt;
local function findPath(finder, w, h)&lt;br /&gt;
	local tm = os.clock()&lt;br /&gt;
	local path = finder:getPath(1, 1, w, h)&lt;br /&gt;
	local etm = os.clock()&lt;br /&gt;
	assert(path, &amp;quot;path not found&amp;quot;)&lt;br /&gt;
	return path, path:getLength(), (etm-tm)*1000&lt;br /&gt;
end&lt;br /&gt;
&lt;br /&gt;
local walkable = 0&lt;br /&gt;
--local test_sizes = {10, 20, 50, 100, 250, 500, 600, 1000} -- set of grid resolutions to be tested&lt;br /&gt;
local test_sizes = {8, 16, 32, 256} -- set of grid resolutions to be tested&lt;br /&gt;
local percentage_of_unwalkable_tiles = 0.3&lt;br /&gt;
&lt;br /&gt;
for i, resol in ipairs(test_sizes) do&lt;br /&gt;
	collectgarbage()&lt;br /&gt;
	print((&amp;quot;\nGenerating a grid of : %d cells x %d cells...&amp;quot;):format(resol, resol))&lt;br /&gt;
	local grid, size = makeGrid(resol, resol, percentage_of_unwalkable_tiles)&lt;br /&gt;
	print((&amp;quot;Memory used to store the grid (%d x %d): %d kiB&amp;quot;):format(resol, resol, size))&lt;br /&gt;
&lt;br /&gt;
	local results = {}&lt;br /&gt;
	for _, finderName in ipairs(Pathfinder:getFinders()) do&lt;br /&gt;
		local finder = Pathfinder:new(grid, finderName, walkable)&lt;br /&gt;
		local p, len, tm = findPath(finder, resol, resol)&lt;br /&gt;
		if p then&lt;br /&gt;
			results[#results+1] = {f = finderName, len = len, time = tm}&lt;br /&gt;
		end&lt;br /&gt;
	end&lt;br /&gt;
	table.sort(results, function(a,b) return a.time &amp;lt; b.time end)&lt;br /&gt;
	for k, v in ipairs(results) do&lt;br /&gt;
		print((&amp;quot;  %-08s - path length: %d - Time: %.2f ms&amp;quot;):format(v.f, v.len, v.time))&lt;br /&gt;
	end&lt;br /&gt;
end&lt;br /&gt;
&amp;lt;/syntaxhighlight&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{GIDEROS IMPORTANT LINKS}}&lt;/div&gt;</summary>
		<author><name>MoKaLux</name></author>
	</entry>
</feed>