Path-finding simulator for grid based games

My Sokoban game with path-finding for boxes.<p><a href="http://sokoban.ws/sokoplayer/SokoPlayer_HTML5_en.php" rel="nofollow">http://sokoban.ws/sokoplayer/SokoPlayer_HTML5_en.php</a>

I found a bug.<p>A*, Chebyshev, Allow Diagonal:<p><pre><code> WWWWWW GWR WWWWW </code></pre> Optimal path should go underneath, but the simulator chooses to go over.

Neat! I was just researching SVG and Canvas for a drawing application. Apparently SVG performance degrades as you increase the number of objects but it can handle changes in scale (zooming in for instance) much better than Canvas can. It seems you've gone with SVG (Raphael) for all your rendering. Have you seen any performance degradation in your tests?

I like how it shows that bi-directional search is way faster than one-way. It's something that you may easily miss during AI class.

I love how with a little experimentation and no prior knowledge of these algorithms I was very quickly able to produce paths that produced sub optimal pathing with each of the algorithms. It really highlights how bad relative to humans our algorithms are at this sort of thing.<p>This is a fantastic learning tool in many ways.

Warning: the Reset button doesn't just reset the colored squares, but also deletes the walls you have drawn. I have made a pull request with button labels that make that more clear: <a href="https://github.com/qiao/PathFinding.js/pull/3" rel="nofollow">https://github.com/qiao/PathFinding.js/pull/3</a>.

I am a noob on this AI stuff but it seems to me that heuristics would be better if they take into account distance to the target without being permitted to go through already visited nodes (so they can only go through unknown nodes treating them as empty) Say this example:<p>BBBBBBBBBBBBBBBB<p>GBR<p>BBBBBBBBBBBBBBBB<p>(switch off diagonal for stronger effect)<p>Shows how badly A* and best first algorithms suffer from open spaces problem and would benefit from that change. I realize that computing such heuristic exactly would be costly but even something like 2x weight for nodes already visited in straight line to the target would improve it a lot.

I thought A* _was_ Best-first-search. <a href="https://en.wikipedia.org/wiki/Best-first_search" rel="nofollow">https://en.wikipedia.org/wiki/Best-first_search</a><p>Can someone explain the difference here?

As someone who doesn't fully understand these algorithms, are these algorithms the same as what's used in GPS/mapping systems, and potentially even internet routing systems?

I find it very fascinating how horribly bad A* is at finding it's way though a spiral shape. Some of the more primitive algorithms did better.

This is interesting. I wonder whether the perceived (in a few minutes of testing) superiority of best-first-search with Chebyshev is some feature of the implementation or fact, because they "forgot" to tell us about both the algorithm and the metric in AI classes.