4 ms·
Jump Point Search Explained
- hayksaakian 13y agoSo what are the downsides of JPS? Why is A* still the default ?
- davmre 13y agoJPS assumes a very particular geometric structure, i.e., a grid with uniform weights, while A* is much more general and works on any graph with arbitrary edge weights. So there are lots of problems where the JPS tricks don't apply, but you can still use A*.
- goldfeld 13y agoWhat if each tile had a different attrition score (not necessarily making movement slower but e.g. consuming more resources in a game)? Would that conceptually be the be same as edge weights and thus more fit for A*?
- davmre 13y agoYes, you could represent the score of a tile as the cost of an edge leading into (or out of) that tile. I don't know if it's possible to generalize any of the JPS ideas to this setting (my guess is that it'd be tricky), but basic A* would definitely work.
- philsnow 13y agoI haven't looked at the paper. JPS might be generalizable to graphs with non-uniform weights, by considering adjacent nodes with _lower_ cost than the current node as a "forced neighbor" (to use the term from the link).
- Schwolop 13y agoSure, but then you have to visit all the adjacent node to deduce whether or not they're lower cost - and that uses equivalent CPU time to A* anyway. A* has been formally proven to be faster than any other graph algorithm using the same heuristic. I do wish people would stop trying to beat it by constraining the rules of the game!
- philsnow 13y agoI'm confused. JPS checks whether an adjacent node is a "wall" (or otherwise-arbitrarily-high cost node), and uses that information to either keep going in the same direction or add more "open" nodes. It seems that it assumes each node has "local" information about local nodes. I think JPS's main contribution is that there are fewer "open" nodes added over the life of the algorithm than A*, right ? The number of open nodes is roughly the "branching factor", and reducing that reduces the total amount of work done.
- Schwolop 13y agoBecause Hart and Nilsson proved in 1968 that (paraphrasing) no other graph algorithm using the same heuristic can visit a lesser number of nodes than A*. This algorithm is using a specialised heuristic that only applies on constrained grids of this type (effectively graphs with equal edge weights and constant branching factor at each node). In short, JPS is much less general.
- highCs 13y agoAt least, I don't think A* is used in any decent high-end video games anymore - it has been dethroned by the open source recast-navigation library and its algorithm [1]. I even suspect the real-time strategy game starcraft 2 from using it or a modified version of it. It is not based on a 2d grid but could be. Also, at one step of the algorithm, recast use A* but somewhat orthogonaly from the main pathfinding algorithm which ultimately could stand on its own. It don't like real-time changes of the world-state, but with some work it could. [1] https://code.google.com/p/recastnavigation/ https://code.google.com/p/recastnavigation/
- csense 13y agoLooking at the page, it looks to me like most of the innovation in the Recast library (at least, the stuff they're proud enough to advertise on the front page) is not the algorithm that does pathfinding on the graph. Rather, it's about automatically constructing a graph suitable for use in a graph pathfinding algorithm like A* from a 3D polygon mesh. So this library's less about graph pathfinding algorithms (like the article), and more about parsing 3D scenes. But thanks anyway, it's good to know this exists!
- deleted 13y ago[deleted]
- b6 13y agoThis is a beautifully done explanation, especially the JS solver.