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?
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.Sign up to join this community
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:
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.
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.