Path-finding simulator for grid based games | Hacker News Reader

Path-finding simulator for grid based games

qiao.github.com

95 pointsadito21 comments

My Sokoban game with path-finding for boxes.

http://sokoban.ws/sokoplayer/SokoPlayer_HTML5_en.php

I found a bug.

A*, Chebyshev, Allow Diagonal:

    WWWWWW
      GWR
     WWWWW

Optimal path should go underneath, but the simulator chooses to go over.

A* isn't guaranteed to find the best route. Since the algorithm stops as soon as a route is found, a bad heuristic can make it find a relatively poor path.

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.

It's not faster in all cases. You can construct mazes on which bi-directional is a lot slower.

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.

This is a fantastic learning tool in many ways.

Hmm, A-star is supposed to be optimal. Can you describe how you tricked it?

Edit: never mind, I didn't see all the options. Using Manhattan distance when diagonal moves are allowed causes the heuristic to be invalid, so you can make it take an L path instead of a diagonal if the diagonal path would force it to move slightly backwards at the start.

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: https://github.com/qiao/PathFinding.js/pull/3.

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:

BBBBBBBBBBBBBBBB

GBR

BBBBBBBBBBBBBBBB

(switch off diagonal for stronger effect)

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.

The algorithms themselves are almost unaware of a path, they simply visit nodes, check their neighbours, then continue with another node from the queue. Breadth First Search simply does this in a predictable order, but of course it isn't prioritising nodes closest to the goal; that's where the other three come in. Every node has a path cost, how many moves it took to make it to the node. You can also define a distance heuristic, that calculates geometric distance to the goal as a strict underestimate. All these algorithms simply exit when the goal node is reached, and a path has been created by the algorithm.

Dijkstra, or also known as Uniform Cost Search, will pick nodes with the lowest path cost from the queue first. This works well on graphs, but not so well on open spaces. It should be mentioned that this algorithm is complete, and optimal. That is, it will find a path if one exists, and it will find the path of lowest path cost (note there may be many such paths of equal path cost).

Then we have A, which is also complete and optimal. This uses the sum of path cost and distance heuristic. This means it will nodes closer to the goal, but long-windy paths will confuse it.

Finally we have Best First Search. It should be mentioned this is actually a family, of which Dijkstra and A are members. In this program, it only considers distance heuristic. So nodes that are geometrically closer to the goal are evaluated first. It should be mentioned that it isn't optimal - it might not find the path of lowest cost. If the optimal path requires at first winds away form the goal, these nodes aren't considered until later, or maybe never.

I thought A* _was_ Best-first-search. https://en.wikipedia.org/wiki/Best-first_search

Can someone explain the difference here?

Best-First Search is a family of algorithms. Specifically, it picks the best candidate node that has been discovered. A* and Dijkstra/Uniform Cost Search are in this family.

In this website, Best-First Search uses only the heuristic distance function (distance from current node to goal, in terms of coordinates). This means it will prioritise nodes geometrically closest to the target first. In most cases this works well, but paths with lots of twists that are close to the goal will get longer paths. This also means it isn't optimal (returns the path of lowest cost), whereas A* and Dijkstra/Uniform Cost Search are optimal.

Now Dijkstra/Uniform Cost Search only considers path cost to prioritise nodes, and A* considers the sum of path cost and heuristic. This means they do find the path of lowest cost.

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?

These kinds of algorithms wouldn't be good for mapping systems as they are - they would send you through lots of side streets. You want to travel on main roads where possible, so you need to 'layer' them (highways, main roads, side streets). You would also try to cache data, which with different layers, might work well.

As for internet routing, I do think they use Dijkstra and Bellman–Ford quite a bit.

They would work, just not using the obvious heuristic/distance of physical distance.

One could use travel time (smaller roads are slower) or some more complicated weighting which could take into account the size of the road, speed limit, and even include parameters that allow the user to adjust how much it biases towards large roads (for example).

Dijkstra's algorithm with low edge weights on fast roads, and high weights on side streets might work.

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.

The problem is Best-First Search (Best First Search) isn't optimal (finds the path of lowest cost), whereas A* and Dijkstra/UCS (Uniform Cost Search) are. (It should be noted Best-First Search is a family of search algorithms, of which A* and Dijkstra are a part of).

Here, Best-First Search uses geometric distance (estimated with a heuristic) from the goal to prioritise nodes. UCS uses pathcost only and A* uses the sum of pathcost and heuristic. This means this implementation of Best-First Search will expand nodes that are closest to the goal first, even if it has a high path cost. A simple example is a straight path and a path with lots of twists, with the straight path starting a few nodes further away from the goal. Best-First Search will proceed on the path with twists first, till it reaches the goal. The result of this Best-First Search isn't optimal, since the straight path is shorter. Both A* and UCS will get the shorter path (there are conditions though, UCS needs strictly positive path weights, and the distance heuristic must be an underestimate).

Chebyshev distance is the right metric to use if you can move on a grid horizontally/vertically/diagonally, which is the case here. Manhattan distance corresponds to h/v but no diagonal movement, and Euclidian distance corresponds to arbitrary non-gridded movement.

(That said, which one functions best as a heuristic can vary problem to problem.)

Reply on news.ycombinator.com