Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Vengeful Donut]

Jump Point Search is a method for traversing less nodes when pathfinding.
It involves no memory overhead or preprocessing. It's only for pruning nodes that aren't worth examining.
It's especially well-suited suited to maps with large open areas of equal cost, in which it can improve performance by an order of magnitude or more.
The method does not interfere with most other speed-up techniques.


http://harablog.wordpress.com/2011/09/07/jump-point-search/
http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf

Pathfinding in uniform-cost grid environments is a problem
commonly found in application areas such as robotics and
video games. The state-of-the-art is dominated by hierar-
chical pathfinding algorithms which are fast and have small
memory overheads but usually return suboptimal paths. In
this paper we present a novel search strategy, specific to grids,
which is fast, optimal and requires no memory overhead. Our
algorithm can be described as a macro operator which iden-
tifies and selectively expands only certain nodes in a grid
map which we call jump points. Intermediate nodes on a
path connecting two jump points are never expanded. We
prove that this approach always computes optimal solutions
and then undertake a thorough empirical analysis, comparing
our method with related works from the literature. We find
that searching with jump points can speed up A* by an order
of magnitude and more and report significant improvement
over the current state of the art.

[thisisjimmy]

That looks really interesting, but as far as I can tell, it won't work in 3D.  Imagine the case where you have a staircase somewhere in the middle of a large room. Jump Point Search would skip most tiles in the room and would miss the staircase. 

However, it should be possible for a clever enough person to adapt the principles of Jump Point Search to Dwarf Fortress.

[Chobeat]

As i told you somewhere else, if it has been done this way, it means that it can't be improved.

[Soralin]

I like it, it's relatively simple, elegant and fast.

That looks really interesting, but as far as I can tell, it won't work in 3D.  Imagine the case where you have a staircase somewhere in the middle of a large room. Jump Point Search would skip most tiles in the room and would miss the staircase. 

However, it should be possible for a clever enough person to adapt the principles of Jump Point Search to Dwarf Fortress.

I don't think it would be too hard to adapt the principle to 3D, if you're taking into account walls above and below, it wouldn't miss a stairway in the middle of a large room for the same reason it wouldn't miss a hole in a long wall, because a stairway is just a hole in the wall of the ceiling.

Although it did note that a version that worked with weighted grids was still in the process of being developed, so that would cause problems with the low/high/restricted assignable travel costs thing.

As i told you somewhere else, if it has been done this way, it means that it can't be improved.

Err.. what?  If what has been done this way?  Dwarf fortress hasn't been done this way, because this is new.  And saying that something can't be improved is absurd.

[Chobeat]

I mean that if DF has been done as it has been done, it must be the best way to do such a thing, because Toady One never fails.

Anyway in the world of computer science, there are a lot of things that cannot be improved and there are mathematical theorems to prove it.

[Blade Master Model 42]

I mean that if DF has been done as it has been done, it must be the best way to do such a thing, because Toady One never fails.

Anyone remember the old medical bugs? Obviously, Toady actually harmed the game by fixing those, as he had coded them that way the first time, and Toady never fails.

/argument

[thisisjimmy]

Upon reading the paper, I'm not sure I understand where the speedup comes from.  They didn't have source code posted for the algorithm.  According to the paper, every time the algorithm steps diagonally, it has to examine every tile that's in the same row or column between the current tile and the first wall. From the images, it looks like it would have to examine about as many tiles as A*.  And in some cases it would have to examine a lot more.

Consider a large open field with a dwarf that wants to go from the bottom-left corner to the top-right corner. A* would go directly to the goal, while JPS would examine every single tile in the field before finding a path.

Could someone please explain what I'm missing here?

[Vengeful Donut]

Upon reading the paper, I'm not sure I understand where the speedup comes from.  They didn't have source code posted for the algorithm.  According to the paper, every time the algorithm steps diagonally, it has to examine every tile that's in the same row or column between the current tile and the first wall. From the images, it looks like it would have to examine about as many tiles as A*.  And in some cases it would have to examine a lot more.

Consider a large open field with a dwarf that wants to go from the bottom-left corner to the top-right corner. A* would go directly to the goal, while JPS would examine every single tile in the field before finding a path.

Could someone please explain what I'm missing here?

JPS is not an alternative to A*. It's something you can use along with A*.
The problem JPS solves is that in a map with a lot of symmetry (like a grid), A* expands many tiles that ultimately lead to a path no better than a path through alternative tiles.
JPS is a method for skipping over some tiles that we know aren't worth examining closely.

[thisisjimmy]

JPS is not an alternative to A*. It's something you can use along with A*.
The problem JPS solves is that in a map with a lot of symmetry (like a grid), A* expands many tiles that ultimately lead to a path no better than a path through alternative tiles.
JPS is a method for skipping over some tiles that we know aren't worth examining closely.

Yes, I understand that.  I worded my question poorly. When I said JPS, I meant A* + JPS.  If I understood the paper correctly, you use the graph of jump points to run A* on.

That doesn't answer my question though.  It seems that to find the jump points, you need to examine a lot of tiles.  It looks like in some cases you'd have to examine a lot more tiles than you would if you ran A* without JPS.  So why is A* + JPS faster than A* alone?

[czolus]

Because you can cache tiles as "worth searching" and "not worth searching."  Open squares adjacent to a corner are interesting, as are z-level crossings (stairs).  The rest of the open tiles are uninteresting, and a stepped-line algorithm will suffice to find an optimal path from jump-point to jump-point.  I'm not seeing the author's assertion of less work (as it appears to me too that they test squares opportunistically rather than as-needed), but there's a definite opportunity for a solid speedup (if you search over the cache of interesting tiles, rather than the whole field).

[thisisjimmy]

Because you can cache tiles as "worth searching" and "not worth searching."  Open squares adjacent to a corner are interesting, as are z-level crossings (stairs).  The rest of the open tiles are uninteresting, and a stepped-line algorithm will suffice to find an optimal path from jump-point to jump-point.  I'm not seeing the author's assertion of less work (as it appears to me too that they test squares opportunistically rather than as-needed), but there's a definite opportunity for a solid speedup (if you search over the cache of interesting tiles, rather than the whole field).

The author says there's no preprocessing, so I don't think he's caching the jump points over multiple searches. The set of jump points depends on your starting location, so they would change between searches. 

If you meant that it's quicker to check if a tile is a jump point than to do full A* pathfinding on it, then that's true. However, the difference shouldn't be that big. Examining a node in A* involves removing it from a priority queue (O(1) amortized with Fibonacci heaps), adding its neighbours to the queue (also O(1)), and calculating the heuristic (very fast for Manhattan distance).  Both methods are at least asymptotically the same.  Checking a tile in JPS would also involve checking its neighbours to see if one is a wall.  It would save a few cycles on adding and removing stuff from the priority queue.

It does seem like the jump points could be cached though, which would be interesting.  I'd expect a huge speedup on the Baldur's Gate map (more than 1000x) if the jump points could be cached.  You'd have to work around the problem that different start points make different jump points, but it may be doable.

Anyway, it seems as it's described now, building the cache of interesting tiles would take nearly as long as doing A*.  The slow part of A* comes from the huge number of tiles it needs to examine, not because examining each one is slow.  JPS still needs to check all those tiles when finding the jump points.

[drilltooth]

Interesting.. but, looking at it, seems it'd only really affect surfaces and caverns. (uness I'm in the minority of making the majority of the settlement a labyrinthine mass of corridors..)

[thisisjimmy]

Interesting.. but, looking at it, seems it'd only really affect surfaces and caverns. (uness I'm in the minority of making the majority of the settlement a labyrinthine mass of corridors..)

That's true, but it's usually the large open areas that takes the majority of the time to search.  Searching through narrow corridors is very fast because there are so few tiles to check. To search a 200x200 tile surface on the other hand, you'd have to check up to 40,000 tiles.

[Uristocrat]

That doesn't answer my question though.  It seems that to find the jump points, you need to examine a lot of tiles.  It looks like in some cases you'd have to examine a lot more tiles than you would if you ran A* without JPS.  So why is A* + JPS faster than A* alone?

Reading this article is the first I've heard of JPS, but it seems simple enough and it's the opposite of what you said.  Instead of examining more tiles, you exclude more tiles immediately.  In the example of moving diagonally across a large, square room, JPS would never examine any tiles *except* the diagonals unless it hit an obstacle.  It would go straight to the goal.

[thisisjimmy]

Reading this article is the first I've heard of JPS, but it seems simple enough and it's the opposite of what you said.  Instead of examining more tiles, you exclude more tiles immediately.  In the example of moving diagonally across a large, square room, JPS would never examine any tiles *except* the diagonals unless it hit an obstacle.  It would go straight to the goal.

That's exactly what regular A* would do, but that's not what's described in the paper. Algorithm 2, function "jump", in the paper is essentially this:
Jump:
1. Step one square in the current direction
2. If the square is a wall, there's no jump point. Return null.
3. If the square is the goal, or is next to a wall, return this point as a jump point.
4. If we're moving diagonally:
       Recursively call Jump, moving horizontally.
       Recursively call Jump, moving vertically.
5. Recursively call jump moving the same direction.

So after each diagonal step, it scans an entire horizontal row, then an entire vertical row, then steps diagonally again, and so forth. It needs to scan the horizontal and vertical lines first, because if they contain any jump points, the square on the diagonal also becomes a jump point.

Here's an image from the paper. The dashed lines are the horizontal and vertical lines that are checked while checking the diagonal.