JPS+ pathfinding – faster than A* [video](gdcvault.com)
gdcvault.com
JPS+ pathfinding – faster than A* [video]
http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than
14 comments
This isn't a heuristic search, it's guaranteed to find an optimal path the same as A*. More generally, this isn't a talk for theoreticians, this is another tool in the toolbox for game AI engineers, and personally I find it very clever. Whether you can afford the memory cost for the precomputed data is a question that must be answered in the specific context of your application.
Agree that everything must be contextualized. My point is, you saw this presentation and liked it because it seems like a good idea, and the performance is apparently good relative to something else. For an engineer (or a theoretician) to reason about that claim of improved performance there needs to be a systematic way to understand it. All I'm saying is that way this was done doesn't allow us to understand it very well - precomputation being a big part of that.
[deleted]
Precomputing 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.
Sure, 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?
I 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.
Implicit constraints kind of suck for the purposes of creating and sharing knowledge though, don't you think? Even constrained to the domain, there are a wide variety of devices people play games on, so I still think its misleading to say this is 1000x faster than an alternative without the huge caveat that benchmarking is multidimensional.
No, they do not suck. For example, "This technique helps you build a frobble faster." "No, you can build a frobble much faster if you have sentient nanobots!" "We don't have those. I am speaking of techniques that actually work in reality." "But implicit constraints suck for sharing knowledge!"
One of these two voices is saying something useful about how to do things better. To borrow a sports metaphor, it is moving the ball forward. That voice is not the voice that is complaining about the use of implicit constraints.
One of these two voices is saying something useful about how to do things better. To borrow a sports metaphor, it is moving the ball forward. That voice is not the voice that is complaining about the use of implicit constraints.
Thats an explicit constraint, not an implicit constraint: The first person has an explicit constraint of "Lets consider only proposals that use existing technology". Thats exactly my point! Except in this case the implicit constraint was "must fit in memory for gaming applications", and I'm saying it should be made explicit. Its not that constraints are bad, just that they need to be shared along with the idea for it to be actionable.
Implicit constraints are the enemy of doing things better, as they allow people to claim basically whatever they want with hidden caveats, which makes it harder for the non-expert to figure out what they need to actually get things done.
Implicit constraints are the enemy of doing things better, as they allow people to claim basically whatever they want with hidden caveats, which makes it harder for the non-expert to figure out what they need to actually get things done.
I doubt a single person at the Game Developer Conference, watching a talk constantly referring to StarCraft, was at all struggling to understand that the technique was for game development.
Even if they somehow managed to avoid that tidbit of knowledge, the memory and runtime costs were fully explained in the talk, so any reasoned developer would be able to consider the applicability to their situation.
Even if they somehow managed to avoid that tidbit of knowledge, the memory and runtime costs were fully explained in the talk, so any reasoned developer would be able to consider the applicability to their situation.
[deleted]
Precomputation is extremely common in realtime, high quality pathfinding scenarios like games - I wouldn't be shocked if realtime navigation (google maps, apple maps etc) uses it too. In that context something like this that leverages precomputation to be fast & accurate makes a ton of sense.
Most game level formats I'm aware of these days include some sort of precomputed navigation mesh that's used to guide intelligent pathfinding.
Most game level formats I'm aware of these days include some sort of precomputed navigation mesh that's used to guide intelligent pathfinding.
Oh for sure, precomputation is essential. Hell, on a 100-1000 node sparse graph you can store all pairs shortest path info in a really small amount of data (like, PC game feasible for sure). For a game situation I'd be willing to burn a lot of time to crunch down pathing times, but memory pressure is real - so there is a "pareto"/nondominated set of algorithms that explore the tradeoff between memory consumption and run time, and the question is not whether you are 100x faster than another algorithm, but whether you are improving that "efficient frontier" of algorithms by using the same memory as another algorithm but running faster, or running as fast as another but using less memory.
You're focussing a lot on whether they an algorithm can say that it "wins" and trying to find a way for them to say that fairly. I don't think that's important at all.
It seems like it's probably better for some problems and not others, like where some precomputation is both practical and helpful. So if you want to see if that's possible for a particular problem, try it and see.
It seems like it's probably better for some problems and not others, like where some precomputation is both practical and helpful. So if you want to see if that's possible for a particular problem, try it and see.
"Try it and see" will be pretty definitive (assuming you can implement it correctly, which is nontrivial), but it has scaling problems.
I'd argue thats exactly what this talk is about: the presenter claims to have a new method that "wins", i.e. beats something else (A* and some variants on it). So the presenter at least thinks its important, as does the competition he mentions in the talk. He thinks you should try it, because he is saying its better. I'm claiming that without more care, its hard for me to take action on that claim because "better" is not a single dimensional thing, its a rich trade off between at least run time, precomputation time, precomputation memory, and arguably implementation difficulty. It'd be nice to not have to try everything yourself for your particular problem, don't you think?
I'd argue thats exactly what this talk is about: the presenter claims to have a new method that "wins", i.e. beats something else (A* and some variants on it). So the presenter at least thinks its important, as does the competition he mentions in the talk. He thinks you should try it, because he is saying its better. I'm claiming that without more care, its hard for me to take action on that claim because "better" is not a single dimensional thing, its a rich trade off between at least run time, precomputation time, precomputation memory, and arguably implementation difficulty. It'd be nice to not have to try everything yourself for your particular problem, don't you think?
You're missing the point here: this is a practical application. He's saying in the context that most people currently use A* his approach is much faster (and he does explain it uses more memory) -- the title is completely justified. You're nitpicking, really.
On 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=1456...
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=1456...
It 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.
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.
Actually, the algorithms used are provably optimal in regard to whatever metric is plugged into them. This means that no matter which of these algorithms you use (including Dijkstra or A*), you will get the exact same result. The difference is in the time and space required for precomputation vs at query time. That includes Contraction Hierarchies, which Google Maps uses (or used?). But if they screw up the optimization metric, then the algorithm can't save them either.
I work on Google Maps and can confirm that it definitely takes the time required to turn left vs. right into account. If you send me an example of a bad route (you can use the web interface, which uses the same backend as Google Maps on your phone) I can take a look as to why it's routing you the way it is. My email address is in my profile.
Is 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.
Well, 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/route... (page is in German, but the literature is English of course)
It'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.
Very clever though, I like it.
It'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."
"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."
In 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-g...
The JPS paper from a few years ago explains in more detail: http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-g...
> 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.
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.
In that sense nothing is faster than Dijkstra's. There are problems for which A* heuristic fails completely, and Dijkstra's is better. JPS exploits a more specific structure of pathfinding just like A* exploits structure given by an heuristic. We have to be very careful to the setting when we say something is 'optimal'.
What 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.
But how does it compare to A* on a reduced[1] visibility graph?
[1] http://kovan.ceng.metu.edu.tr/~kadir/academia/courses/grad/c...
[1] http://kovan.ceng.metu.edu.tr/~kadir/academia/courses/grad/c...
That 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.)
That'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.
Precomputation 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.
Starcraft maps aren't static, as buildings and characters can block paths.
Maps themselves are static.
They do evaluate buildings though.
I wonder how OP solved this, if at all. There are too many of them to partially rebuild. Maybe they combine two systems.
As 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.
Same 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
I 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.
Indeed 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
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
Ah, and it seems to be connected to ray marching also, as demonstrated so well by the fractal lab guy: http://sub.blue/fractal-lab
How is it connected to ray marching?
I'm curious; my own playing with the area: http://williamedwardscoder.tumblr.com/post/26628848007/rod-m... http://williamedwardscoder.tumblr.com/post/28935319219/rod-m...
Would like to make it faster :)
I'm curious; my own playing with the area: http://williamedwardscoder.tumblr.com/post/26628848007/rod-m... http://williamedwardscoder.tumblr.com/post/28935319219/rod-m...
Would like to make it faster :)
I 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.
On 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.
Did you mean by leaving time rather than "by not leaving time"?
I believe JPS only works for unweighted graphs, so you can only compare it to A* for that particular case.
More 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.
> 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.
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.
Well, 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/
[1] http://ddg.cs.columbia.edu/
[deleted]
seems like optimizing something always involves precalculations.
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