8 ms·
JPS+: Over 100x Faster than A* (2015) [video]
- justinhj 10y agoNot to take anything away from the work but I think the title is misleading. A* is an optimal algorithm for graph search so you cannot make it 100x faster. What this does is make path finding faster by changing the structure of the graph.
- chrisseaton 10y agoI'm sure you're right in this case, but I wonder if it would be possible for an 'optimal' algorithm, where the optimality is in terms of high-level operations like compares required, to be out-performed by a non-optimal algorithm due to practical considerations such as cache utilisation. An order of magnitude more loads but in a cache oblivious pattern could be a win compared to a pathological pattern.
- mcguire 10y agoCertainly. Jon Bentley had an article on two string reversal algorithms with the same algorithmic complexity. On a very large string, one would finish almost immediately; the other was pessimal for paged virtual memory and wouldn't finish for hours.
- fao_ 10y agoFTA: "It has been said that "pathfinding is a solved problem." Just because something is "solved" doesn't mean it can't be improved especially with regards to execution time."
- simias 10y agoIt's a very practical optimization (not just a theoretical algorithm) so I don't think it's really misleading in the context of game development. That being said there's an important gotcha, those techniques require a significant amount of precomputations (especially the bounding box one) so it might not be practical if you have very dynamic maps.
- Kiro 10y agoThe map in my game is completely dynamic and every pathfinding technique I've tried is way too slow. I've had to resort to a really stupid path finding algorithm where the enemies just looks a few tiles ahead (meaning they get stuck very easily). Any pointers?
- chrisseaton 10y agoAre you path-finding every frame? Can you take a snapshot of the game state and run full-path finding on a background core just once every second?
- dirtyaura 10y agoChange your map generation to generate a higher level graph first with ensured paths between nodes and generate subareas so that they connect to higher-level graph?
- Kiro 10y agoMaybe I misunderstood you but the players can change the map during gameplay so I don't think that will work.
- Elrac 10y agoI'm assuming that changes to any given position X on the map happen much less frequently than pathfinding operations that touch on said position X. Is this the case? If so, then investing the pre-calculation effort (updating the precalc matrix, not re-generating the whole thing) at map update time, limited to only those areas potentially benefiting, might be an effective strategy.
- andrewstuart2 10y ago100x faster means improving the coefficients. A* is optimal in terms of asymptotic execution time, but that doesn't mean you can't improve the overall running time.
- semi-extrinsic 10y agoThe classic example is matrix multiplication, where we know of incresingly sophisticated algorithms with increasingly better asymptotic performance, but in practice most matrix multiplications are for sub-100x100 (IIRC) matrices where the naive algorithm we all learned as undergrads is fastest.
- derefr 10y ago> in practice most matrix multiplications are for sub-100x100 (IIRC) matrices I would say that you have the causation reversed: we just don't bother doing large matrix multiplications, because they're so expensive (and yet still don't usually cross the intercepts into making the "better" algorithms worth it, due to those algorithms having ridiculous constant coefficients.) I would love to run Floyd-Warshall on my 40-million point network graph—but it just ain't gonna happen.
- semi-extrinsic 10y ago> we just don't bother doing large matrix multiplications, because they're so expensive Sure, I agree. I'm not a specialist in numerical lin.alg., but I've heard it said that if you're spending a lot of time on large dense matrix multiplications, you're probably approaching the problem in the wrong way.
- raghavkhanna 10y agoA* is optimal in the sense that it is guaranteed to find the optimal solution (shortest path), there are no guarantees in terms of speed IIRC.
- y7 10y agoPaper: http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/download/5396/5212 http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/download... Previous HN thread: https://news.ycombinator.com/item?id=9714774 https://news.ycombinator.com/item?id=9714774
- _delirium 10y agoA somewhat more detailed paper (by the same authors): http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-g...
- sand500 10y agoI had an idea when I took my algo class to overlay a small graph of "highways" on a map and computer all pairs shortest path to that sub graph. Then when you do your search, you do BFS from both the start and goal till you reach a *highway node" and then you have a short but not optimal path between two points without too much computation.
- mcguire 10y agoSure, accepting a sub-optimal result often makes an infeasible problem easy. Extra credit if you can bound the sub-optimality.
- TillE 10y agoSomething like that is an essential optimization when pathfinding over long distances. You often need to answer the question can I go from A->B->C long before you need to say how exactly you do it.
- k2xl 10y agoJust watched the entire video - very interesting; however, there are two major caveats the speaker mentions that is worth noting. 1) This requires expensive precomputation. He mentioned it took 10 hours on one of the large starcraft maps. 2) (I may have misunderstood this point) This does not necessarily respond well to map changes - so in maps where you have the map changing structure (new walls, etc) you will have to run the precomputation again. With that said, very interesting stuff coming out of Digipen.
- vanderZwan 10y agoI think the Goal Bounding Gate optimisation he talks about could help with both: it's still O(N²), but if N is limited to those gateway nodes that would cut down on costs tremendously. But that all depends on whether it's cheap to find those gateway nodes automatically.
- botexpert 10y agoSounds similar to https://en.wikipedia.org/wiki/Contraction_hierarchies https://en.wikipedia.org/wiki/Contraction_hierarchies There was a paper by Microsoft Research where they find shortest path from one point to another in time equivalent to 5 memory reads + they sped up significantly the precomputation times and lowered memory requirements.
- vanderZwan 10y agoI had trouble watching the video on GDC (it kept breaking when changing chapters, for some reason), so for anyone else with the same problem, here's a Youtube Mirror: https://www.youtube.com/watch?v=KFwxqN_nASM https://www.youtube.com/watch?v=KFwxqN_nASM
- gens 10y agoAnd i just implemented A* yesterday... JPS is great. I remembered it from a former talk a while ago. From the little experience i have with pathfinding, it seems to be an interesting topic with many little details to be explored. Like smoothing a path, smoothing/tuning a path in regards to loss of "speed" when turning, avoiding dynamic obstacles like other "agents", "flocking" of groups, various different ways of representing a "map", and probably many more.
- Tloewald 10y agoIn a sense the JPS+ algorithm seems to be to be turning the grid into s kind of nav mesh and if you were to explicitly do this instead you might actually get a better and more general solution that's also easier to update in real time. The boundary checking improvement would be simplified by dividing the map into islands divided by gates (per his closing remarks) limiting the damage to precalculated data from changes to the map (assuming they occur in one island at a time)
- revelation 10y agoThis seems to be specifically for grids. Of course essentially no modern AAA game uses grids for navigation anyway, they use convex polys in a nav mesh.
- amitp 10y agoTitle's misleading. A* is also 100x faster than A* ;) It depends a lot on the graph you give it. JPS by itself (not JPS+ in this video) is notable for not requiring any precomputation to achieve some speedup. If you're willing to precompute some things, there are lots of other techniques available for unweighted grid maps. http://www.cs.du.edu/~sturtevant/papers/GPPC-2014.pdf http://www.cs.du.edu/~sturtevant/papers/GPPC-2014.pdf has an overview of techniques and some benchmarks that use real-world game maps (Baldur's Gate, Dragon Age). I believe the "goal bounding" from the video is called "arc flags" in the literature.
- jstimpfle 10y agoHannah Bast knows a lot about route planning. Here is one of her courses containing some important ideas: https://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012 https://ad-wiki.informatik.uni-freiburg.de/teaching/Efficien...
- krosaen 10y agoYes, was just about to post, "Exact Routing in Large Road Networks Using Contraction Hierarchies" which, after a one-time pre-processing step returns an optimal route on a continent-scale network in milliseconds. http://dl.acm.org/citation.cfm?id=2351896 http://dl.acm.org/citation.cfm?id=2351896
- nonsince 10y agoWhat's the memory usage there? Is it on the order of what can be used for games? Often memory is even more constrained than CPU time
- deleted 10y ago[deleted]
- 60654 10y agoIt's misleading indeed. This version of JPS+ is basically a preprocessing optimization - does graph compacting offline to compute a smaller representation that's faster to run guided search on. And of course there's a serious down-side: if the graph changes at runtime (eg. player builds a new door, or blows away a bridge) the preprocessing has to be redone, and it's not cheap.
- mcguire 10y agoWait. 100× faster than an algorithm?
- lngnmn 10y agoSo, basically, it is about a much better heuristics, not a general algorithm. Of course, with a specialized heuristics one could get a lot of pruning, but generally, if there is no way to come with a specialized heuristic when there is no way to have a jumping heuristic (one have to take one step at a time) and there is no way to look ahead for a specialized nodes, the A* is still the king. But in AI almost everything is about finding a good-enough heuristic.
- zamalek 10y agoJPS+ is also about skipping operations. It's a skip list expanded to grid format.
- nhaehnle 10y agoI wonder if any games use a landmark approach to bound their A* search. The basic idea of landmarks is that you choose a small number of landmarks (e.g. four corners of a map) and for every landmark, you pre-compute the distances to every node. You can then use this information to get a lower-bound for the distance to the target via the triangle inequality: d(p,t) >= |d(p,LM) - d(t,LM)|. This is obviously weaker than the goal bounding explained in the video, but the precomputing only takes O(n). We used it quite successfully in a global router (for EDA), where the heuristic lower-bound is often much better than a standard A-star heuristic based on geometric distances, because edges could have wildly different costs.
- karussell 10y agoI'm curious: what does "global router (for EDA)" mean? And yes, A* & landmarks is really nice :) !
- jononor 10y agoLikely an algorithm/tool that can automatically lay out the traces on a PCB for electronics production. EDA=electronics design automation
- nhaehnle 10y agoIn this particular case not a PCB but microprocessors. Global routing is a high-level routing approach: routing millions of nets (= connections usually between 1 output pin of a gate and N input pins of other gates) on a grid graph with potentially billions of nodes is an extremely difficult Steiner tree problem. To get good solutions, a common approach is to first solve the problem on a much coarser graph where edges have capacities. I.e. instead of having to place all connections disjointly, edges in the graph can accommodate a number of parallel connections. A later detailed routing step will produce the actual disjoint routes while following the outline that was obtained during global routing.
- rasz_pl 10y agoits something no remotely competent engineer uses, but tool providers love to dick wave around https://teespring.com/shop/autorouter https://teespring.com/shop/autorouter
- karussell 10y agoContraction Hierarchy (CH) is also at least 100x faster as A* . CH has nice properties of having good memory efficiency, optimality, any graph etc. And I am very sure JPS is not that generic applicable like CH. Still all 'fast' routing algorithms have their own drawbacks of engineering complexity, pre-processing time and memory requirements, potential lack for time dependent support etc. If you want to have the best summary of routing algorithms currently available then read 'Route Planning in Transportation Networks' (2014) https://arxiv.org/abs/1504.05140 https://arxiv.org/abs/1504.05140 And if you want fast implementations for routing algorithms like Dijkstra, A*, CH and Landmarks check out GraphHopper: https://github.com/graphhopper/graphhopper https://github.com/graphhopper/graphhopper (note: I'm one of the founders)