8 ms·
PathFinding.js
- zyxley 11y agoSo... 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.
- rcfox 11y agoCould anyone recommend a Javascript pathfinding library that doesn't assume a grid-based graph?
- keslag 11y agoI've not come across a node or mesh based pathfinding library, though you can roll your own A* with modifications.
- iamdave 11y agoIt'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/ https://www.mapbox.com/developers/api/directions/ So...somewhat relevant to what you're asking.
- imaginenore 11y agoDirections 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.
- rcfox 11y agoI'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.
- imaginenore 11y agoThe point is, if you add traffic into consideration, you can't have almost anything precalculated.
- amitp 11y agoA* 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.
- amitp 11y agoBetter 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 http://research.microsoft.com/pubs/64511/tr-2004-24.pdf (PDF link) (or these slides http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lectures/reach-mit.pdf 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)
- nacs 11y agoYou 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 https://en.wikipedia.org/wiki/Navigation_mesh
- malkia 11y agoAt previous job some folks used recastnagivation (C/C++) library for what you are looking for - https://github.com/memononen/recastnavigation 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/recastnavigation 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 http://three-arena.com/examples/#simplest.js and the compiled emacsen source here - http://three-arena.com/node_modules/recastjs/lib/recast.js http://three-arena.com/node_modules/recastjs/lib/recast.js also this one: https://github.com/vincent/recast.js https://github.com/vincent/recast.js found by looking here - https://groups.google.com/forum/#!searchin/recastnavigation/emscripten/recastnavigation/1i2xwXudO8c/rOzfG-1U_tMJ https://groups.google.com/forum/#!searchin/recastnavigation/... Also test from there: https://vincent.github.io/recast.js/tests/test.webgl.html https://vincent.github.io/recast.js/tests/test.webgl.html
- seshakiran 11y agoOn 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.
- jaunkst 11y agoI have had to roll my own. I have been meaning to release a library for a graph based datastructure and path fining for games
- sagivo 11y agoI love A*, used it in all of the games i developed.
- sytelus 11y agoI wonder if there are patterns that makes A* take unruly amount of time when there is an "obvious" solution from human point of view.
- rcfox 11y agoSomething 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.
- hayksaakian 11y agotry the "bi-directional" checkbox on the website
- rcfox 11y agoNice, I didn't notice that. Waaay better.
- TazeTSchnitzel 11y agoIt never checks the target is actually reachable, meaning it just keeps going if you make reaching it impossible.
- Buttons840 11y agoHow can you tell if the target is reachable other than finding a path?
- TazeTSchnitzel 11y agoCheck if either the source or destination are completely enclosed.
- kevan 11y agoUntil 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.
- jankassens 11y agoIn 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.
- TheLoneWolfling 11y agoYou 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.
- TheLoneWolfling 11y ago
- kevan 11y agoSome 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/ http://kevanahlquist.com/osm_pathfinding/
- nacs 11y agoPretty 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.html http://www.redblobgames.com/pathfinding/a-star/introduction....
- hitekker 11y agoI 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.
- tlrobinson 11y agoIt 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.
- koopuluri 11y agoThis is really cool! Reminds me of the Berkeley PACMAN Ai project: (http://ai.berkeley.edu/project_overview.html http://ai.berkeley.edu/project_overview.html), but seems easier to customize, try out different edge cases and compare algorithms.
- z3t4 11y agoI 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 ;)
- nacs 11y ago> 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 http://www.redblobgames.com/grids/hexagons/#pathfinding
- ww520 11y agoOT: How does potential field perform vs A* path finding?
- Grue3 11y agoIDA* almost hanged my browser. It didn't seem to be able to find the path, just bumping into a wall constantly.