Faster pathfinding using Jump Point Search

http://harablog.wordpress.com/2011/09/07/jump-point-search/

by harada • 15 years ago

110 16 15 years ago

harablog.wordpress.com

wingerlang• 15 years ago

Is it just me or does the Vanilla-A* algorithms look too bad? I mean especailly in the second image [(d) A* (Adaptive Depth)], why does it search behind itself?

harada4• 15 years ago

This behaviour exists because A*'s heuristic function assumes there are no obstacles when estimating the remaining distance to reach the goal. As the difference between the heuristic estimate to the goal and the actual distance increases, some nodes "behind" the start location will appear more promising than other nodes which are eventually proven to be on the optimal path.

shasta• 15 years ago

Because that's how A star works :)

It's a graph search. Imagine adding an out-of-plane edge that travels from behind the starting point to the goal. Since taming that path could be optimal it has to check - it doesn't attempt to reason that such a path would necessarily be obstructed by what's been explored thus far. It's just a graph search.

nelhage• 15 years ago

Suppose there was a wall or other obstacle between you and the destination. Then you might have to go "back" to find a way around. Vanilla A* can't "know" whether this is the case, so it searches outwards in all directions, using the heuristic to weight the search towards paths that are getting us closer to the destination.

GoGlobal• 15 years ago

Any speed ranking against alternatives?

harada4• 15 years ago

In the paper we make an apples-to-apples comparison with a recent optimality-preserving state-space reduction method called Swamps and an apples-to-oranges comparison with an approximate pathfinding algorithm, HPA*.

Swamps is a nice technique for narrowing the scope of the current search; it achieves ~5x maximum speedup and could be combined with Jump Point Search to go faster still.

The comparison to HPA is summarised in the article. Additional evaluations are the subject of further work :)

pixcavator3• 15 years ago

What a strange use of the word "symmetric": "Two grid paths are symmetric if they share the same start and end point and one can be derived from the other by swapping the order of the constituent vectors."

harada4• 15 years ago

I can see how defining symmetry for a pathfinding domain might be non-intuitive. What the quoted definition is trying to communicate is that paths sharing such a relation are permutations of one another and thus, symmetric.

pixcavator3• 15 years ago

I understand that they are "equivalent" in a certain sense, but "symmetric"?

demallien• 15 years ago

How so? That would be a 2-fold rotational symmetry, wouldn't it?

http://en.wikipedia.org/wiki/Rotational_symmetry

pixcavator3• 15 years ago

Two pieces are rotated, that doesn't make the whole thing symmetric.

praeclarum• 15 years ago

"speeds up pathfinding on uniform-cost grid maps"

How useful are uniform-cost grids? Every implementation of A* I've ever used has been applied to varying-cost grids.

jemfinch• 15 years ago

Any game vaguely resembling Wolfenstein uses a uniform-cost grid.

sonar_un• 15 years ago

Quick, someone send this to Toady One!

malu• 15 years ago

Problem is, the traffic designations make the grid non-uniform-cost. Edit: But you could probably remove the possibility of traffic zones if this was implemented.

Faster pathfinding using Jump Point Search

Related Stories