Print

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

[KaelGotDwarves]

See here: http://www.reddit.com/r/dwarffortress/comments/k7x79/jump_point_search_could_it_speed_up_df/ - where the general consensus is that "it might help for certain things, but not by much- but we honestly have no idea because only Toady knows how the code works there".

[thisisjimmy]

See here: http://www.reddit.com/r/dwarffortress/comments/k7x79/jump_point_search_could_it_speed_up_df/ - where the general consensus is that "it might help for certain things, but not by much- but we honestly have no idea because only Toady knows how the code works there".

Okay, thanks, I get now.  The speedup comes from not having to bother with the priority queue and hash set for most of the tiles.  Even though those operations are O(1), they're relatively slow. That's a nice optimization.

I still wonder if my previous example of searching diagonally on an open field might be slower with JPS though.  I might run some benchmarks and see when I have time.

Edit: Oops, just remembered that deleting from a Fibonacci heap is still O(log(n)).  So there's another reason why A* would be slower.

[Ari Rahikkala]

In case anyone wants to play with this I wrote a simple C implementation: https://github.com/arirahikkala/astar-jps

(that's in addition to the one by the author that's based on HOG, you can find that at http://code.google.com/p/ddh/)

[agrastie]

Hi guys,

I'm one of the co-authors of the paper on jump points, and I also have a strong understanding of the rectangle-based methods.  It seems you are interested in applying such methods to your game.  That's pretty cool. We would be happy to contribute although we don't have much time.  Our goal at NICTA is to apply our research to real problems, so using DF as a real world benchmark would be really great.  Even if performance is not that great, the feedback from DF would be invaluable. 

At the moment, the approach is a bit limited in the sense that it is only applicable to uniform-cost grid maps.  IIUC, your domain is a 2.5D, i.e., a bunch of grids connected through a (small) number of stairs.  I don't see any particular difficulty for that.  The jump-point detection algorithm should simply flag any node that is (the entrance of a flight of) stairs as a JP.  If there are 3D units (flight creatures), it could be adapted I guess. 

We've been looking at the pre-processing based enhancement.  There are a few subtleties around the corner, but it's pretty much the same thing as JP.  There is limited overhead and it seems to be faster by quite a lot.  The only potential issue is in case the environment changes (if a hole appears in a wall, for instance).  Then again, that's an interesting research problem we would be happy to investigate, and we already have some ideas for that.

Another interesting problem for us: weighted grids.  If you think this is relevant for your game, please mention it.  In particular, if you have regions with different weight, our method should be applicable (to some extend). 

Now, regarding some of the comments I saw on the forum.  I agree with the last comments from thisisjimmy.  Our method allows to get pass some nodes (i.e., not insert them in the priority queue but immediately process them).  Not only do we save by not inserting them (i.e., many O(log(n)) operations avoided, either when inserting, moving, or deleting nodes) but we also reduce the size of the queue which makes faster each operation that we could not avoid. 

[sockless]

http://www.bay12forums.com/smf/index.php?topic=76278.0

That's a good thread to read about pathfinding, it gets better later in the thread. I'm not sure if what you've suggested is in there, but I thought that you'd probably find it interesting.

[Ari Rahikkala]

Hi guys,

I'm one of the co-authors of the paper on jump points, and I also have a strong understanding of the rectangle-based methods.  It seems you are interested in applying such methods to your game.  That's pretty cool. We would be happy to contribute although we don't have much time.  Our goal at NICTA is to apply our research to real problems, so using DF as a real world benchmark would be really great.  Even if performance is not that great, the feedback from DF would be invaluable. 

I don't know if that's actually the case. Dwarf Fortress is unfortunately not open source, and Toady One (the game's author) is basically constantly flooded by the suggestions posted on this forum and only has time to implement a fraction of them. I'm hoping he'll get around to this one, but he hasn't posted in this thread to indicate it yet.

In any case, good to have you here. I thought Daniel was the only one of you who was advertising your work, after he posted about it it on reddit and HN :p

Another interesting problem for us: weighted grids.  If you think this is relevant for your game, please mention it.  In particular, if you have regions with different weight, our method should be applicable (to some extend).

As I'm not the game's author I don't know if there actually are any other sources of non-uniformness, but it's possible we might be lucky in this regard: As far as I know, the only way in which any pathfinding grids in DF are weighted is traffic designations, which are player-assigned regions with a specified cost-to-enter-a-tile. They're usually even rectangular since the designation interface works by drawing rectangles.

[thisisjimmy]

Hi agrastie,

IIUC, your domain is a 2.5D, i.e., a bunch of grids connected through a (small) number of stairs.

For the 2.5D, I'm curious if ramps would be a problem. The game can have lots of rolling hills and mountains that span many z-levels. In addition, you couldn't directly treat the surface as a 2D grid, because there can be caves and overhangs.  So you could follow two different paths on the same surface and end up at the same (x,y) coordinate but on two different z-levels.  Would this be a problem for JPS?

[Uristocrat]

I'm one of the co-authors of the paper on jump points, and I also have a strong understanding of the rectangle-based methods.  It seems you are interested in applying such methods to your game.  That's pretty cool. We would be happy to contribute although we don't have much time.  Our goal at NICTA is to apply our research to real problems, so using DF as a real world benchmark would be really great.  Even if performance is not that great, the feedback from DF would be invaluable. 

ToadyOne is the only coder here and the game is closed-source, but lots of us are interested in helping him and we try to gather whatever research he might be able to use (for example, I personally gathered the densities of tons of different stones to help improve the materials system).  I can at least tell you some of the challenges DF faces, though.  If you want map data, there's the DF Map Archive which should give you lots of interesting things to work with.  We frequently have challenging maps with lots of dead-ends (bedrooms, etc.) and the like.  We also tend to design central staircases, so algorithms that don't head straight for the stairs can waste a lot of time.

At the moment, the approach is a bit limited in the sense that it is only applicable to uniform-cost grid maps.  IIUC, your domain is a 2.5D, i.e., a bunch of grids connected through a (small) number of stairs.  I don't see any particular difficulty for that.  The jump-point detection algorithm should simply flag any node that is (the entrance of a flight of) stairs as a JP.  If there are 3D units (flight creatures), it could be adapted I guess. 

Player-made stairs are usually small in number, but natural ramps (which allow an almost diagonal movement across z-levels, given that a unit on them effectively is on both the level above and below) can be high in number.  Mountains tend to contain natural ridges composed of lines of ramps.  Also, yes, there are flying units and large numbers of them slow things down a *LOT* right now.  There's a certain (spoiler) event that can release tons of flying creatures, so people tend to suffer FPS death before they suffer actual death.  For them, the airspace really is 3D.

We've been looking at the pre-processing based enhancement.  There are a few subtleties around the corner, but it's pretty much the same thing as JP.  There is limited overhead and it seems to be faster by quite a lot.  The only potential issue is in case the environment changes (if a hole appears in a wall, for instance).  Then again, that's an interesting research problem we would be happy to investigate, and we already have some ideas for that.

We have quite a few different environment change possibilities.  Water can flow (which itself is slow), not to mention magma, and that can cause tiles to become impassible (oh, except for the creatures that can swim... yes, some swim in magma, too).  There are also drawbridges and the like.  Not to mention cave-ins, deliberate and otherwise.  In short, the map can suddenly change, though these updates are usually infrequent, except in certain cases (e.g. someone starts pumping magma).

Another interesting problem for us: weighted grids.  If you think this is relevant for your game, please mention it.  In particular, if you have regions with different weight, our method should be applicable (to some extend). 

Right now, one way of controlling movement (i.e. speeding things up) is player-made traffic designations which apply weights to grids.  The basic way to use them is to mark all your hallways as low-cost and block off all the dead-ends with high-cost designations.  You might also mark dangerous areas and traps as high-cost to get dwarves to avoid them.  Movement itself doesn't really cost more.

Now, regarding some of the comments I saw on the forum.  I agree with the last comments from thisisjimmy.  Our method allows to get pass some nodes (i.e., not insert them in the priority queue but immediately process them).  Not only do we save by not inserting them (i.e., many O(log(n)) operations avoided, either when inserting, moving, or deleting nodes) but we also reduce the size of the queue which makes faster each operation that we could not avoid.

Interesting.  Oh, and there's one other complication which is currently disabled:  multi-tile creatures.  We used to have 3x3 tile wagons.  I think that Toady made that problem simpler, because they would only ever attempt to path to one location (from edge of map to the player-built depot) and the player was required to clear a path for them before they would even arrive.  But you can still check whether or not they have a path to your depot in-game, even though they're disabled in current versions.

[czolus]

Really, the weakness in any search algorithm is in the quantity of nodes in your search space.  Most of your effort involves (finding and) searching around barriers: The result of an optimal search is really a straight line from edge-of-barrier to edge-of-barrier---minimizing the deflection from the optimal path.  I sat down & wrote up an algorithm that does better than raw A* w/ minimal caching.  It works by processing the map for "interesting" points---areas where ideally paths must deflect through to obey impassable areas.  Then a mapping of line-of-sight connected interesting points is constructed.  From this, no further processing is required (but is useful, as pathing maps in DF are read far more often than modified).  Paths are generated by first locating all line-of-sight attached interesting points from the start, all line-of-sight interesting points attached to the destination, and then A* from that initial set to destination set.  Finally, connect everything by lines.  Empirically, I found that ~7-10% of tiles are interesting for my style of architecture.

Picking interesting nodes:
A node is interesting if any one of three things is true:

• It has a diagonal, planar-passable neighbor with which 2 common, planar-impassable neighbors are shared.
• It has a cardinal (NSWE) neighbor which adjoins no more than 1 common, planar-impassable neighbor.
• It has a vertical connection.
• The tile contains a sock.

In essence: A diagonal-only connection between two tiles makes both interesting; tiles at a cardinal (NSWE) of an outer corner (not an inner corner) are interesting; Stairwells are interesting; Socks are important.

This list allows you to determine if a node is interesting simply by looking at its local neighbors, without concern for where those neighbors might connect.

Strictly, the third can be constrained further in the case of NxM staircases where N, M > 2 by not considering anything but the edge staircases to be interesting.  That requires more pre-processing effort, however, as now you become concerned with the connection characteristics of your neighbors.

You can then calculate which interesting nodes have line-of-sight to each other, storing that mapping.

Line-of-sight:
A node has line-of-sight to another node if you have some stepped-line algorithm that can route from the start to the end without passing over some impassable tile. (Bresenham's, for example.  But note that this line algorithm is sensitive to which tile is "first" and which is "second".  hasLOS(a, b) does not imply hasLOS(b, a))

The algorithm for searching:

• From start location, calculate all interesting nodes that are in line-of-sight (hasLOS(start, interesting_x) == true).  This is the starting open set for A*.
  
• Calculate all interesting nodes that are in line-of-sight of the end (hasLOS(interesting_y, end) == true.  Note: order of arguments is often important).  This is the destination set for A*.
  
• Run a standard A* across the interesting nodes (until you hit one in the destination set).  Remember: the hasLOS(interesting_j, interesting_k) mapping was calculated in advance for all interesting nodes.
  
• Connect the chain of interesting nodes, as well as the start & end (in their correct spots).  Use the line-of-sight algorithm to fill in any missing steps (which is simple step-calculations, as opposed to searching.  And in the case of interesting node connections, will be cached).

Caching:
Any call to hasLOS(a,b) can be cached.  Such a function should calculate the path & distance if there exists a line-of-sight.  Line-of-sight information between interesting nodes must be stored (and updated if mutations occur, as below).  Line-of-sight info for normal nodes may be cached, and said cache may be dropped in the face of nearby mutation (as opposed to updating)--in addition--if the language supports soft-references, I recommend the cache be setup with that in mind to aid with memory consumption.

Mutation:
If the map needs to be mutated (and this is DF, after all), you can modify the caches without requiring a full re-processing.  Consider the set of modified tiles and their immediate neighbors as the "changed set."  Recalculate the interesting status for each of those tiles.  If any tile becomes not-interesting, make note, and remove any mappings from other interesting nodes to it.  For any interesting node that has a path crossing the changed set and if that path is now invalid, remove the path.  If a tile becomes interesting, calculate the paths to-and-from it as in the pre-processing step.

For the above interesting nodes that lost paths but were not themselves in the changed set, they get their new paths when the new interesting tiles in the changed set calculate their own paths.  And as a characteristic of the algorithm, if there are paths deleted due to a blocked line-of-sight (but there is still some total path around the obstruction), new interesting points (and their connections) that are made will ensure the "pathing hole" is filled.

For non-interesting nodes that are not in the changed set, but are in line-of-sight with it, you have 2 options: drop their cached hasLOS() information, or attempt to drop any invalid entries.  I recommend the former.

Empirical:
Feeding one of my forts in---I use a consistent architecture, so they all look alike---and time-to-path was decreased by ~10x over raw A*.  Substantially more if there was no path from start to end.  Much of my time seems to being eaten by I/O concerns, and the time-to-cache for hasLOS(non-interesting, interesting).  Both are a characteristic of the testing, as I'm choosing random start and end pairs that do not share line-of-sight, and thus for almost every path there is no cached hasLOS(start, interesting) or hasLOS(interesting, end) information.  Both of which are O(nm), where n is the number of interesting points, and m is the average distance from either or end to an interesting point.  In short, if I had ~7 dwarves standing in my dining hall, all the non-interesting tiles would know which interesting tiles they're connected to within a few dozen frames, and that information won't be changing, especially once the map stops changing nearby.  I'd expect ~20-30x improvement over raw A* by then.

[agrastie]

Plenty of interesting comments.  (BTW, we have long discussions with Daniel and he pointed me to your forum so, as long as he does not register to contradict me, you can assume you are talking to him as well.)
(And I haven't totally caught up with the 26pages thread linked above.)

I really like the points about different types of unit mobility and different sizes.  Daniel worked on that : <http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-botea-cig08.pdf>.

For the 2.5D, I'm curious if ramps would be a problem. The game can have lots of rolling hills and mountains that span many z-levels. In addition, you couldn't directly treat the surface as a 2D grid, because there can be caves and overhangs.  So you could follow two different paths on the same surface and end up at the same (x,y) coordinate but on two different z-levels.  Would this be a problem for JPS?

I was more suggesting to have a collection of grids, one for each z level (the z values are discrete, right?,  not continuous).  When you search on the z level, you run your search on the zth grid as if there was only one level.  However, when you reached a point where you can change level, you put this point as a JP.  (Technically, you might even continue.  The point of the approach is that you stop only when you have more than one successor.)

Thanks for the maps, by the way.  We will have a look. 

Also, yes, there are flying units and large numbers of them slow things down a *LOT* right now.  There's a certain (spoiler) event that can release tons of flying creatures, so people tend to suffer FPS death before they suffer actual death.  For them, the airspace really is 3D.

OK.  Question about the flying creatures.  How do they move exactly?  If they can move all their (x,y,z) coordinates by 1 at every move, there are 3*3*3=27 potential moves (including the case where the creature actually does not move).  Is that correct?  Or is it the case that when z changes, x and y cannot change (vertical take-off and landing).  If this is the case, I believe the JP method can easily be extended.  If not, then I fear there will be too many successors and it will be hard to reduce them to only one. 

Right now, one way of controlling movement (i.e. speeding things up) is player-made traffic designations which apply weights to grids.  The basic way to use them is to mark all your hallways as low-cost and block off all the dead-ends with high-cost designations.  You might also mark dangerous areas and traps as high-cost to get dwarves to avoid them.  Movement itself doesn't really cost more.

Do I understand well that these designations are only used for the dwarves pathfinding algo, but that practically, the creatures are unaffected?  Anyway, we started investigating weighted grids and the type of maps you describe should not be a problem. 

czolus, the approach you propose looks like the "visibility points" approach.  It can be pretty efficient, but the problem is that, in certain environment, the set of successors of a node can be quite large, for instance in a forest-like environment.  The problem is that you have to store these pairs of points, and this can lead to a prohibitive overhead. 

Just to finish (for now), if you start implementing the JP approach, you might want to limit the jump length (so that, if you reach a desert, the search doesn't cross the desert.  I would limit the jump to (K+h) where K is a constant (say, 10) and h is the distance to goal given by the heuristic or (K+g). 

Also, if you want to look at Daniel's implementation on google sources, you'd better download the revision 31.  Whatever was committed after is unstable.  Daniel is polishing it; soon, it should be properly commented. 

[thisisjimmy]

czolus, your algorithm sounds like a great match for dwarf fortress.

If I may make a suggestion, why not ignore single, isolated impassable tiles when looking for interesting nodes?  That is, any impassable tile that has passable tiles north, south, east and west of it should be treated as if it were passable.  The rationale is that you can always path around these tiles easily, and it could greatly reduce the number of nodes in forested areas.

You could even extend this idea to also ignore impassable clusters of up to 2x2 tiles or 3x3 tiles.  This would further reduce the number of interesting nodes in forested areas, but at the cost of have somewhat more complex pathfinding between interesting nodes.  Of course, those slightly-more-complex paths could be precomputed and cached.

[Uristocrat]

OK.  Question about the flying creatures.  How do they move exactly?  If they can move all their (x,y,z) coordinates by 1 at every move, there are 3*3*3=27 potential moves (including the case where the creature actually does not move).  Is that correct?  Or is it the case that when z changes, x and y cannot change (vertical take-off and landing).  If this is the case, I believe the JP method can easily be extended.  If not, then I fear there will be too many successors and it will be hard to reduce them to only one. 

I believe they move in true 3D.  At least, I know of no special rules for moving up and down.  Quietust might know for sure.  Ramps are also weird and I think they allow diagonal movement across z-levels.  At least, that's what I remember reading on the wiki.  So Quietust probably knows, because he tries to verify all the stuff that people write on the wiki.

Do I understand well that these designations are only used for the dwarves pathfinding algo, but that practically, the creatures are unaffected?  Anyway, we started investigating weighted grids and the type of maps you describe should not be a problem. 

Yes.  Actually, I guess there may be an energy cost for diagonal movement, according to some half-remembered comment in some thread by the Toady One, but it was based on some integer approximation of sqrt(2) or something like that.  I don't know that the pathfinding algorithm cares about that, though, I think it only affects movement speed.  Diagonal movement is still faster than moving through two tiles, so I don't think that part really matters.

czolus, the approach you propose looks like the "visibility points" approach.  It can be pretty efficient, but the problem is that, in certain environment, the set of successors of a node can be quite large, for instance in a forest-like environment.  The problem is that you have to store these pairs of points, and this can lead to a prohibitive overhead. 

Interesting, because we do have forests (though players tend to clear-cut them... and then get invaded by elves).  There are also caverns and the like.  Actually, DF maps tend to have a lot of dead space where no one needs to go along with an active core in the fortress where there are lots of different destinations.

And that reminds me of some other things.  For example, Dwarves seem to cache their path and, when the terrain changes, they walk all the way up to the drawbridge (or whatever) and then get confused and find a new path (if they can... they will cancel whatever job they were assigned if it's impossible).  So they only recalculate their path when they actually hit an obstacle, even if the environment changed a long time before they got there.

There are also special rules for doors.  You can make them so that dwarves can pass (but pets cannot) and also lock them so that nobody can pass (though certain enemies can *destroy* them...).  They also stay open for a short time after someone goes through.  So animals, especially fast ones, may slip through while a slow dwarf carrying something walks through the door.  Creatures can path through each other, but it slows them down and they prefer not to.  You will see dwarves tend to walk around each other.  Sometimes, one dwarf will even walk backwards a bit to let another dwarf through.  It's anyone's guess how Toady manages some of this.

There's even talk of adding digging units someday.  That ought to be interesting.  I guess they'd have to assume that they can path through unknown areas... only to find out that maybe they can't, because there could be underground caverns, magma, underground rivers and whatever else in their way.  And maybe the diggers will be able to swim or survive magma... so who knows?  If not, someone would add one like that, I'm sure.

There are also traps.  These are harmless to the dwarves that build them.  Not so much to hostiles.  Except that enemies who discover them spread the word so that future ambushes will *avoid* the traps they know about... if they can.  If there's no other route to your fortress, they'll brave even known traps.  So maybe there's some invisible path weighting going on in there.

[czolus]

czolus, your algorithm sounds like a great match for dwarf fortress.

If I may make a suggestion, why not ignore single, isolated impassable tiles when looking for interesting nodes?  That is, any impassable tile that has passable tiles north, south, east and west of it should be treated as if it were passable.  The rationale is that you can always path around these tiles easily, and it could greatly reduce the number of nodes in forested areas.

You could even extend this idea to also ignore impassable clusters of up to 2x2 tiles or 3x3 tiles.  This would further reduce the number of interesting nodes in forested areas, but at the cost of have somewhat more complex pathfinding between interesting nodes.  Of course, those slightly-more-complex paths could be precomputed and cached.

I could see this being very useful, especially since a single impassable in an otherwise open room would have an interesting node at each of its cardinals (NSWE).  The complication would come during path reconstruction, because we couldn't use our stepped-line algorithm to just connect the dots---we'd have to have something to route us around the obstruction.  Trivial in the case of a lone tile, less-so as the size of the impassable block increases.  I'll see if I can weave something in, as my test-case has several 3-wide hallways with a central pillar at the ends (where I normally hang the doors)

[thisisjimmy]

The complication would come during path reconstruction, because we couldn't use our stepped-line algorithm to just connect the dots---we'd have to have something to route us around the obstruction.

One possible solution is to replace the stepped-line algorithm with A*.  A* is usually pretty efficient when it only has to path around a few small objects. Especially if you use the Manhattan distance as your heuristic.

I guess the other question is up to what cluster size should we ignore for maximum efficiency? It's a trade-off of the number of nodes to search vs how hard it is to path to a node.  My guess is that just ignoring single tiles would make the biggest difference, because there's a lot of single trees. But I haven't tested it so who knows?

[czolus]

Mind you, the stepped-line algorithm is O(n), and A* is at best O(n) if we're explicitly moving on a non-obstructed path---decays toward O(n²) as the amount of deviation increases.  In addition, A* has the memory overhead of tracking where it needs to search (open set), where it has searched (closed set)---both of which a stepped-line algorithm lacks.

Specifically, routing around a tree will typically only add 2 nodes per tree to the open set when searching over the interesting set.  Both nodes are diagonal neighbors, so pathing between them is effectively a no-op.