11 ms·
JPS+ pathfinding – faster than A* [video]
- ingenter 11y agohttp://mikolalysenko.github.io/l1-path-finder/www/ http://mikolalysenko.github.io/l1-path-finder/www/
- jessaustin 11y agohttps://github.com/SteveRabin/JPSPlusWithGoalBounding https://github.com/SteveRabin/JPSPlusWithGoalBounding
- opcvx 11y agoPrecomputation takes O(n^2) complexity so this is great for static environments like Starcraft maps where the units don't evaluate units in their path finding.
- Udo 11y agoThey do evaluate buildings though.
- opcvx 11y agoI wonder how OP solved this, if at all. There are too many of them to partially rebuild. Maybe they combine two systems.
- imaginenore 11y agoStarcraft maps aren't static, as buildings and characters can block paths.
- opcvx 11y agoMaps themselves are static.
- lorenzhs 11y agoOn road networks (Google Maps style routing) much much bigger gains have been achieved. Taking things to an extreme, Hub Labelling achieves sub-microsecond query times on continental-scale road networks [1]. More flexible algorithms (e.g. Multi-Layer Dijkstra aka Customizable Route Planning, which Bing Maps supposedly uses) achieve sub-millisecond query times, with preprocessing times for new metrics less than a few minutes. This allows full timely integration of traffic information etc. On a 2D grid, there are a few differences, but even modeling it as a graph and applying road network algorithms (even simple ones like Landmark Routing) sounds like it would yield similar, if not better speedups. [1] http://research.microsoft.com/apps/pubs/default.aspx?id=145689 http://research.microsoft.com/apps/pubs/default.aspx?id=1456...
- AnonymousPlanet 11y agoIs there any kind of proper formal definition for the algorithm? The linked paper is a bit unstructured in this regard and seems a bit implementation focussed.
- lorenzhs 11y agoWell, it's a paper from the Symposium on Experimental Algorithms ;) You can find a good list of interesting route planning papers, including hub labeling, at http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/routenplanung/index#literatur http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/route... (page is in German, but the literature is English of course)
- lnanek2 11y agoIt would be nice if Google Maps started doing a decent job, though. I lived for years in NJ and I would typically require 3 roads and 20 minutes to get anywhere I needed to go shopping because I would drive to the highway, hop on, get off on the road to my destination, then be there. Even if I avoided the highway I would get there in 30 minutes with smaller roads, taking the minimum needed to go the right direction toward the destination. Google Maps? It was a disaster. It would take the small roads since it couldn't bear to drive 2 blocks the wrong direction to get on the highway, then every small road it would alternate taking a left and a right and end up with dozens of turns when a human only needed 3 or 4. I actually met the ex-Googler who bragged about writing that algorithm that alternates left and right, I think he must be responsible for millions of hours of lost time for drivers just because he didn't realize turning has a cost and was trying to draw a diagonal as best he could. Does it really make sense to brag about fast calculation speed when the calculation is a disaster? I'd rather wait a minute for a calculation and get the right one, than have the wrong one back in 3 seconds. I think the Google Maps engineers don't understand this.
- mathgenius 11y agoI love the connections to the continuum case where these problems show up looking like ways of solving path integrals, Huygens principle, etc. In particular, some of these jump point rules look alot like diffraction (of a wave) around a boundary.
- mathgenius 11y agoAh, and it seems to be connected to ray marching also, as demonstrated so well by the fractal lab guy: http://sub.blue/fractal-lab http://sub.blue/fractal-lab
- willvarfar 11y agoHow is it connected to ray marching? I'm curious; my own playing with the area: http://williamedwardscoder.tumblr.com/post/26628848007/rod-marching http://williamedwardscoder.tumblr.com/post/26628848007/rod-m... http://williamedwardscoder.tumblr.com/post/28935319219/rod-marching-on-the-gpu http://williamedwardscoder.tumblr.com/post/28935319219/rod-m... Would like to make it faster :)
- mathgenius 11y agoI just think it is interesting to consider all these path finding algorithms, and compare/contrast them. So with ray marching, we already have access to a "distance" function. And it's not one but many targets we are looking for. It does seem to me like JPS tries to do something similar, the cacheing of jump points looks alot like the distance function, and now we are going to cast rays out looking for the target point, and let rays "bend" around corners, etc.
- darkmighty 11y agoIndeed light simply just uses a Dijkstra-like flood [1] fill :) This isotropic propagation is the reason Fermat's principle [2] works. [1] The flood pattern, or Huygens principle, in turns follow from the local (fundamental) and isotropic (for most media) nature of Maxwell's equations for electromagnetic propagation. [2] https://en.wikipedia.org/wiki/Fermat's_principle https://en.wikipedia.org/wiki/Fermat's_principle
- justinhj 11y agoIt's a bit misleading to call this faster than A* since it is still using A* under the hood. Most optimizations to path finding with A* involve changing the world representation somehow. Most do not use a simple grid, with navigation meshes being more common. Very clever though, I like it.
- andor 11y agoIt's also misleading because nothing optimal is faster than A* . Quote from AIMA: "A∗ is optimally efficient for any given consistent heuristic. That is, no other optimal algorithm is guaranteed to expand fewer nodes than A∗ (except possibly through tie-breaking among nodes with f(n) = C∗). This is because any algorithm that does not expand all nodes with f(n) < C∗ runs the risk of missing the optimal solution."
- bnegreve 11y ago> nothing optimal is faster than A* . For what task? The speaker seems to be concerned with the problem of answering repeated path-finding queries for a single static map. With that problem in mind A* is indeed sub-optimal since it redoes all the computations for each query.
- _delirium 11y agoIn the general setting A-star is optimal. JPS (and JPS+) can speed it up if you have additional information about the topology of the search space: 1) search is on a rectangular grid, and 2) movement between adjacent grid squares has uniform cost. In that case, you can take advantage of certain properties/symmetries of a rectangular grid to safely "skip" parts of the expansion that A-star would normally do, while still being guaranteed to find the optimal solution. The JPS paper from a few years ago explains in more detail: http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-g...
- JulianMorrison 11y agoWhat probably fudges around this, is that all the nodes get looked at before any routing code starts running. A* is coming to the graph cold.
- idunning 11y agoAllowing precomputation seems a little suspect, or at least difficult to incorporate into a comparison. I could offline precompute all pairs shortest path, then I'll be 10^6 faster than Astar, for example. Where do you draw the line? In the Q&A someone asks this, and points out that the precomputation in the video has a lot/all of the shortest paths stored. The speaker says that requires too much memory to store - so basically, arbitrary line here (what is too much?) Another problem is with heuristics in general: if you are not guaranteed to find an optimal path (which is possible with Astar variants), then you have a two-dimensional way to understand heuristics: run time, and solution quality. e.g. I can give you a bad path very fast. Finally, implementation data structures and language. Two people implementing the same algorithm in different languages are going to have different performance. Here is a preprint that addresses these questions for heuristics for two NP-hard problems (MAXCUT and QUBO): http://www.optimization-online.org/DB_FILE/2015/05/4895.pdf http://www.optimization-online.org/DB_FILE/2015/05/4895.pdf
- Symmetry 11y agoPrecomputing all shortest routes uses O(n^2) memory with the size of the map, though as opposed to the O(n) memory that this uses. For a Starcraft map that's the difference between a MB and a TB.
- idunning 11y agoSure, but thats exactly my point. Given a set of well-stated limitations (like, cannot use more than N^x bytes of storage for an instance of size N, using the same standard library of data structures etc) we can make meaningful comparisons. I could come along with a method that uses O(n log n) memory and crushes this (maybe) - how do we declare a winner now, without some sort of context?
- Symmetry 11y agoI think the constraints are implicit in the forum the talk was given at. This is Game Developers Conference so the constraint is that the algorithm has to run on the computers that the game buying public possess. If you think you've got an algorithm that can blow the presenter's out of the water on a typical PC then I encourage you to test it and show it to the presenter if you succeed.
- striking 11y ago> uniform cost grids There are very many grids that do not fit this in real (not theoretical) applications. I honestly can't think of when I'd use this algorithm.
- mathgenius 11y agoWell, yeah, but the whole question of extending this algorithm to arbitrary (weighted) graphs is still very interesting: it seems to rely on some kind of discrete [1] version of parallel transport. [1] http://ddg.cs.columbia.edu/ http://ddg.cs.columbia.edu/
- andrepd 11y agoAs a side note, I love the index on the left hand side of the player, that lets me quickly jump to any section of talk, instead of having to fish for the part when he starts talking about the algorithm, for instance. An awesome feature I wish other websites had too.
- h1fra 11y agoSame note, at first I was like "another video I won't watch watch because I'm only curious about one point of the talking" then I saw the menu. Very cool feature, greatly optimize user experience in a simple way
- deleted 11y ago[deleted]
- bsdetector 11y agoOn a side note, you can increase performance of presentations by 25% by not leaving time for questions. I find Q&A is often the best part and I wish the conferences left more time for it.
- wesleyy 11y agoDid you mean by leaving time rather than "by not leaving time"?
- jokoon 11y agoseems like optimizing something always involves precalculations.
- kbwt 11y agoBut how does it compare to A* on a reduced[1] visibility graph? [1] http://kovan.ceng.metu.edu.tr/~kadir/academia/courses/grad/cs548/hmws/hw3/vg/node3.html http://kovan.ceng.metu.edu.tr/~kadir/academia/courses/grad/c...
- obstinate 11y agoThat page claims it's about 40% faster than A*. Multiply through the ratios and you'll have your answer. (1000x faster is a lot more than .4x faster, so I guess it compares quite favorably.)
- kbwt 11y agoThat's for A* on a complete visibility graph, which is much faster than on a uniform grid. I only added the link so that the reduced terminology is clear to everyone.
- beefsack 11y agoI believe JPS only works for unweighted graphs, so you can only compare it to A* for that particular case.
- _delirium 11y agoMore specifically, JPS works on unweighted grids (not arbitrary graphs). That allows it to use properties of a grid topology to figure out where it can safely "jump" without sacrificing optimality.