Hacker News Reader

Comment by amitp | Hacker News Reader

Title'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 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.

View on HN

Yes, 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

What'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

Hannah 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/Efficien...

Use Floyd Warshall if you can pre-compute.

It pre-computes all the paths from all nodes to all nodes, and it's incredibly efficient.

Most awesome algorithm ever :D

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorit...

And if you need dynamic graph with variable weighting and nodes, that's a case for D*

Mostly used for drone/rover/robot navigation in open environments, with the graphs evolving as the robot discover the environment.

https://en.wikipedia.org/wiki/D*

Only if the area changing is near the start of the search, not near the goal. (i.e. near the sensors of a mobile robot, rather than near the destination far from the robot).

D* can be pathologically slower than repeated A* searches under such conditions.

I've been using a modified D*. It increases the grid size as the path moves out of the robot's observable area. This allows a fast search even when the goal is in a environment with known dynamic obstacles.

Ideally speaking, you need to plan in higher dimensions to get an optimal path in dynamic environments

Pearl, J. (1984), Heuristics, Addison-Wesley. In this text, Pearl proves that for a given heuristic, A* will perform computations on fewer (or the same number of) nodes than any other graph algorithm using the same heuristic.

The pre-computation JPS(+) does is cheating because it's essentially providing a quicker-to-evaluate heuristic than A* gets to use.

So yes, I agree - the title is misleading! However, it's still a pretty cool efficiency for situations where it's applicable.

It'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.

Oh man, Baldur's Gate pathing was abysmal, and not just because of moving obstacles (including the 6 members of your party interfering with each other while all moving greedily-not in formation-to the same general area).

With respect to the techniques that require precomputation, however, I wonder how they perform with such moving obstacles. Potentially quite terribly, I imagine.

A technique that is reportedly useful for dynamic situations is D*, since 90% of the world is static and most dynamic content is clustered, you could probably get away with using that in a radius and then devolve to the precomputed technique outside of that

Reply on news.ycombinator.com