I'm trying to speed up my pathfinding and discovered A* with JPS. It basically prunes tiles before adding them to the OPEN set.

Can I use that technique with my grid that only allows straight directions?


If you read the article, you'll see that they list this as an open problem in the "Conclusions" section:

"One interesting direction for further work is to extend jump points to other types of grids, such as hexagons or texes (Yap 2002). We propose to achieve this by developing a series of pruning rules analogous to those given for square grids."

So, to apply Jump Point Search to your orthogonal grid, you'd need to decide which points should count as jump points on that grid. After thinking about this for a moment, I think — but have not proven! — that the following rules (based on Definitions 1 and 2 in the paper, somewhat rephrased for readability) may work:

A node y is the jump point from node x, heading in direction d, if y is reachable from x by moving straight in direction d, and is the closest such node to x to satisfy at least one of the following conditions:

  1. node y is the goal node,
  2. d is a horizontal move, and either of the cells vertically adjacent to the cell y − d (that is, the cell one step before y when moving in the direction d) is blocked, or
  3. d is a vertical move, and there exists a node z which is a jump point from y (by condition 1 or 2) in some horizontal direction d'.

Of course, the words "vertical" and "horizontal" can be exchanged in the definition above. The point is that we need to pick some way of breaking the symmetry so that only one of the possible paths for traversing an open rectangular region is considered. Harabor and Grastien do that by preferring "diagonal-first" paths, but since we can't do that, we have to make do by preferring vertical-first (or horizontal-first) paths instead.

It might also be possible to develop alternative pruning rules that produce more "natural-looking" paths, such as preferring the current heading over turning, or perhaps even preferring constantly turning staircase paths. The rule I gave above is simply the most straightforward translation of the Harabor & Grastien rule to an orthogonal grid I could think of.

  • \$\begingroup\$ +1 This is exactly what I was going to answer. It is possible to prove that this will still be optimal. \$\endgroup\$ Jun 19 '13 at 10:43

Actually, if you look at the definition of 45-degree route, it is always possible to transform a path with 45-degree route into a path without 45-degree turn. And it's also optimal (you can easily prove it by contradiction).

So, the simplest way is to run the jump point search and then transform it into orthogonal route.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .