PathFinding.js | Hacker News Reader

PathFinding.js

qiao.github.io

215 pointskamaal47 comments

Some friends and I made pathfinding visualizations that use real map data from the OpenStreetMap project, it gets messy pretty fast.

http://kevanahlquist.com/osm_pathfinding/

That's really good. Is it open source? I couldn't find any licensing info

Github link is in the lower-right .. uses MapBox, which in itself is a beautiful mapping service, but .. its not open source.

Pretty much the definitive guide for pathfinding how-to/visualization (the author used D3.js for the examples):

http://www.redblobgames.com/pathfinding/a-star/introduction....

amazing resource to learn! thanks for sharing :)

Amit also writes on http://aigamedev.com

You sorta need to use other tools with A* in order to fully utilise it. Steering forces, behaviour trees an etc :)

I found myself trying to place paths in front of the algorithm, trying to delay it from reaching its end goal.

With a bit of tweaking, I imagine this could be turned into a little game.

It would be cool if it ran all the algorithms and showed you how many steps it took and the final path length for each one.

Also, a "random maze" button would be nice.

It never checks the target is actually reachable, meaning it just keeps going if you make reaching it impossible.

How can you tell if the target is reachable other than finding a path?

Check if either the source or destination are completely enclosed.

Until the algorithm runs out of nodes to explore it can't know that the destination is unreachable. Checking if a node is enclosed is determining if its graph is disjoint from the graph that the other node is on. The only way to prove the graphs are disjoint is to explore every node in the graph.

In this case it's enough to set the algorithm to "bi-directional". If one side is enclosed it will stop. This only breaks if both disjoint parts are infinite (for example, an infinite wall between start and end.

You preprocess the grid into connected components, marking every grid cell with the CC it is in. Then before pathfinding check that the start and end are in the same component. This is an O(1) check, albeit with a potential of O(n log n) space required for storing the array of CC lookups.

Whoops, make that an O(log n) check, technically speaking, as the index of which CC a cell belongs to may take O(log n) space worst-case.

Though you can treat it as effectively O(1) time and O(n) space.

I think checking whether target is reachable has the same complexity as reaching it

Not really.

Or rather, yes, sort of, but you only need to do it once (or once per update on a changing grid):

You find the connected components of the grid. This is easy (loop over the entire grid. Any grid cell that has not been assigned a CC, assign the first free CC and floodfill from there.) Then to check if a is reachable from b, just check that a and b are in the same connected component. This is O(1) time (albeit with O(n log n) worst case spacial complexity for the CC structure required).

The problem with the naive version of this is that updates can, in the worst case, require a scan and update of arbitrarily close to the full grid. There are better versions for when updates are frequent, but they take longer to query (although still sublinear time!) and are substantially more complex.

Flood fill is the hard part - A* is basicaly flood fill too, just with heuristic and quick stop condition.

Preprocessing is cheating :). If you preprocess and floodfill the map anyway, you can go one step further, do Dijkstra, save the results using a trick, and you don't need run-time pathfinding at all.

And you can store full paths from each cell to each cell using just O(N * N) memory, no matter the path lengths - that's a neat trick BTW:

you store for each cell pair (P,Q) what is the next cell you should go from P if you want to eventually get to Q. that allows yu to reconstruct full path between each pair of cells quickly.

EDIT to clarify - cheating is good, it's just I don't think O(N log N) is good tradeoff for the ability to return quicker, if you can do away with the whole pathfinding for O(N * N).

EDIT 2: why O(N log N)? It seems you could write the resulting component for each cell, so worst case O(N) space?

Why O(n log n) space? Because you require O(n) connected components in the worst case, which means that you need O(log n) space per cell in the worst case. Although now that I think about it that pushes the amount of time to O(log n).

In practice you can treat it as O(1) time and O(n) space, though.

Also, that preprocessing with result saving is substantially slower than the connectivity alone. The connectivity alone is O(n) / O(n log n) preprocessing time - you check each cell a maximum of 5 / 9 times (depending on 4 or 8 way connectivity).

Also, that preprocessing with result saving fails miserably when you do updates to the graph.

But you can just write for each cell the index of component it belongs to. It can't belong to many, right?

So it is O(N) in space?

I'm not sure we're talking about the same thing. I mean space requirements for the results of preprocessing.

Preprocessign itself may require computing cluster for all I care.

> I'm not sure we're talking about the same thing.

We are.

> But you can just write for each cell the index of component it belongs to. It can't belong to many, right?

Right. Each cell belongs to 1 and only 1 connected component.

However, there can be O(n) connected components overall. Think of a grid of cells all blocked off from each other, for instance.

As such, storing which connected component a cell belongs to technically requires O(log n) space, worst-case. Which means have overall you have n cells each requiring O(log n) space, or O(n log n) space overall.

In practice you can treat this as effectively O(n), however.

So you treat 1 integer as log n? That's very technical, but in that case OK.

Yes. Although, as I said, in practice you can treat the integer index as constant space.

That's because it's meant to illustrate how each pathfinding algorithm/heuristic works and their search scope, not to do project-specific pathing.

I wonder if there are patterns that makes A* take unruly amount of time when there is an "obvious" solution from human point of view.

Something like this performs pretty poorly for all of the algorithms:

    ===========          ================
             s=          =e
    ===========          ================

I think if you searched from both ends, it would perform much better.

try the "bi-directional" checkbox on the website

Nice, I didn't notice that. Waaay better.

I use this in one of my games. The API could be slightly simpler/better though. But having abstractions like this available makes me so much more productive.

Now I'm just waiting for a library/API for hexagon map's ;)

> Now I'm just waiting for a library/API for hexagon map's ;)

You can use A* and co with hex maps too. There's more info on hex maps and an illustration of pathing here:

http://www.redblobgames.com/grids/hexagons/#pathfinding

So... with a screen sized to about 1280x580 (a comfortable size on my 13-inch BMA), the "Start Search" button starts completely off the screen. Any smaller than that, and the "Select Algorithm" box is partially clipped off the screen. In any case, there's no scroll bar, which really confused me.

That aside, this is really neat, and it's interesting to see a visual representation of the different algorithms.

This is really cool! Reminds me of the Berkeley PACMAN Ai project: (http://ai.berkeley.edu/project_overview.html), but seems easier to customize, try out different edge cases and compare algorithms.

On Mac 15 inch, visualization is very neat. very good implementation of the algorithms. Regarding Zyxley's comments; this can be made responsive so that it works on all screen sizes.

I love A*, used it in all of the games i developed.

I have had to roll my own. I have been meaning to release a library for a graph based datastructure and path fining for games

IDA* almost hanged my browser. It didn't seem to be able to find the path, just bumping into a wall constantly.

Could anyone recommend a Javascript pathfinding library that doesn't assume a grid-based graph?

I've not come across a node or mesh based pathfinding library, though you can roll your own A* with modifications.

It's not a javascript library, but MapBox recently released the Directions API for pathfinding within the context of mapping: https://www.mapbox.com/developers/api/directions/

So...somewhat relevant to what you're asking.

Directions algorithms on real life maps are quite different from what they teach you in CS classes. Just think of the amount of computation to get the best directions between SF and NYC, taking traffic into consideration. I'm pretty sure none of the services actually give you the best solution, but something that's pretty close to it.

Full USA map graph contains around 24 million nodes, 58 million edges. Your regular A* just doesn't cut it.

I'm sure you're right, but it seems like traffic would be easy enough to consider by simply increasing specific edges' costs.

As for the scale issue: most of these nodes and edges will never change, so it might be possible to calculate a Dijkstra map.

The point is, if you add traffic into consideration, you can't have almost anything precalculated.

A* runs faster if you have better path cost estimates. To get the shortest paths, you want an estimate that's as close to the true cost, but not greater than it. You can precalculate to generate good estimates. Traffic makes the costs higher than normal, so those precalculated estimates are still useable (if you raise the costs because of traffic, the estimates continue to be lower than the true cost), and still much better than what you get without precalculation.

Better distance estimates and better graphs can push A* to work on larger problems. ALT gives better distance estimates: http://research.microsoft.com/pubs/64511/tr-2004-24.pdf (PDF link) (or these slides http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lec... ). Transit nodes do too, I think. Contraction hierarchies and arc flags let you preprocess the graph to give better information to A*.

(I've not implemented any of these myself)

You could use pretty much any pathfinding algorithm (A* for example) even if you don't have a grid based graph.

In the implementation, you would just need to modify how the algorithm transverses each valid walkable/unwalkable node (how to go from waypoint to waypoint) and possibly how much extra cost each node has (water/mountainous terrain could have increased cost for example) instead of letting it go the usual up/down/left/right and possibly diagonals for grids.

If the waypoint based approach isn't ideal for you, then you should look up "navigation mesh" [1] pathing which is a bit trickier to implement but works well when you have a bunch of large empty/walkable areas.

[1]: https://en.wikipedia.org/wiki/Navigation_mesh

At previous job some folks used recastnagivation (C/C++) library for what you are looking for - https://github.com/memononen/recastnavigation

And there seems to be "emscripten" version of it (just googled it) - https://github.com/vincent/three-arena/tree/master/recastnav... - as part of the "three-arena" project

demo here - http://three-arena.com/examples/#simplest.js

and the compiled emacsen source here - http://three-arena.com/node_modules/recastjs/lib/recast.js

also this one:

https://github.com/vincent/recast.js found by looking here - https://groups.google.com/forum/#!searchin/recastnavigation/...

Also test from there:

https://vincent.github.io/recast.js/tests/test.webgl.html

OT: How does potential field perform vs A* path finding?

Reply on news.ycombinator.com