Print

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

[worldspawn]

I have a question for any programmers out there regarding pathfinding. Using A* I've made my own programs with pathfinding before, but they were always on flat 2d plains. How do you get it to work with multiple Z axis, like in DF? Example: if there's 5 stairways one can use to go up a level how does it calculate things like the heuristic etc to determine which stairway is the best one?

[Armok]

I actualy HAVNT made anything whit A* yet, but even I know the answere to this one (unless, of coarse, i got it backwards); just the same way as betwen adjustent squares on the plain, A* dosn't differ betwen a 2d surface (your implementation might do that, thou) or a completly arbitary something else, you can use A* for decition trees or 5d grids, or theoreticaly linking those togeter.
If I remember corectly then when that flood-fill-like thing A* is made up of reaches a stair, spill it over to the stair on the other level that it's conected to... ugh I'm up far to late and is tirred I'm not bothering to check my speeling even, sorry if I'm hard to understand.

[Nahno]

Assuming the nature of traversing the z-axis is the same as the x- or y-axes (not necessarily the xy-plane), or can be reduced to a problem where that is the case, it doesn't matter. To the algorithm it'll be just another path.

The algorithm will choose one of the 5 stairways. Which one depends on the layout of the world and the heuristic, just like paths in 2D worlds.

[Ampersand]

It's also important to note that Dwarf Fortress does not differentiate between z levels for certain things. Suppose a dwarf is surrounded by rocks, and three z levels down, there is a rock directly below it. The Dwarf will assume that the rock 3 z levels below is closer because they have the same x,y value, completely disregarding the z.

Besides all this, the z levels can still be treated as 2D planes with the staircases acting as 'teleportation points' between them, when it comes to path finding

[Veroule]

An efficient way to do it is to calculate the heuristic for many different places.  Lets say you are at 37,12,6 and your destination is at 27,12,18.  The H formula I use would come out to 198 between start and destination, and moving in the general direction of 'west' would be what A* wants to do.

Before I consider the move I also calculate the H for all the stairs on the current level.  Let's say the nearest stair is at 29,13.  Since it produces a lower H the path expands that way first.  When it encounters the stair it immediately traverses it, recording the additional F cost, but skipping the H calculation for that step.  H calculations resume with the perspective of the new level.

That repeats as usual with A*, the main modification is to calculate the H based on desitination and all stairs on the current level then use the lowest.  If you just use destination then A* will move directly under/above the destination and flood until it finds a stair; and then it would repeat that process even with a stair stack.

The H calculation is quite often overly complex, when it can be simple.  I use 9*abs((z1-z2)+9*(abs(x1-x2)+abs(y1-y2))+7*abs(abs(x1-x2)-abs(y1-y2)).  16 is the number I used for the F cost of a base movement, 9 and 7 make a split such that 1 cardinal movement calculates to 16 for the H, while 1 diagonal movement calulates to 18.

For flying units what you really have to do is make the 'can step that direction' check able to handle 26 directions, and have the movement using directions like northeastUp.  You can shortcut the map or use 26 bits per location.

I was working on writing an entire library with a number of other modifications to A*.  I may get back to it soon.

[worldspawn]

That's what I thought Veroule, but when I posted this in another forum I was told by a number of people "no you don't have to do it like that, the nature of A* should let you use multiple z levels the same as though it were a plain" without giving any explanation as to HOW. I'll stick with what you said since that is what I had originally assumed. thx

edit: unless anyone is aware of some source code or something that is open source that would make a good example

[Calculus]

It seems like DF does the really simple thing - it just adds the Z difference to the heuristic cost of the squares.

[Armok]

If you give a sample of your code helping you whit specifics might be easier?

[SolarShado]

It's also important to note that Dwarf Fortress does not differentiate between z levels for certain things. Suppose a dwarf is surrounded by rocks, and three z levels down, there is a rock directly below it. The Dwarf will assume that the rock 3 z levels below is closer because they have the same x,y value, completely disregarding the z.

I knew dwarfs were did stupid stuff like that, but i thought it was because the distance-to-stone was calculated with a simple 3D distance formula (the one derived from the pythagorean theorem)...

Talk about a relic from the 2D version...

[FunnyMan]

The thing to rememer about A* is that it simply does not care how your world is connected.  It's happy searching through a square grid, a hex grid, or even something totally bizarre, like a square grid with teleporters.

Essentially, to run A*, you need three pieces:

• A distance heuristic.  This is a function that tells you approximately how far you are from the goal, and the one restriction on it is that for A* to work correctly, it can never *over*estimate the distance  (this one is the reason that teleporters would be a pain, since you need to factor them in to avoid surprise shortcuts).
• A way to tell which nodes you've already visited. Lookups need to be fast, because you'll be using this a lot.
• A way to get the possible next steps from a given node, including weights.

Since A* doesn't care how the world is connected, you can feed it a 3D world just by adjusting those three key pieces:

• Pretty easy.  Instead of 2D distance, calculate 3D distance.  If there are fairly few connections between levels, you might want to factor them in to this part.
• This works pretty similar to before.  Since you only need one for the entire algorithm, you were probably using a 2D array before, so just add the third dimension.  Memory usage will go up a lot, but not horrendously.
• Again, pretty easy.  Just check for and add any valid cross-Z-level moves to the list.

Or you can do a multi-phase search, like Veroule suggested.  The advantage here is that once you reach all the stairs on a level, you can stop thinking about that level.  The disadvantage is that you *have to* reach all the stairs on each level before you can continue.  A single, hard-to-reach stair on one level will make your running time spike, because you have to follow the path its entire distance before you can continue, as opposed to the direct A* where if it's longer than the correct path, it will never be followed.

A hybrid solution would be to run standard 3D A*, but whenever you hit a stair, check to see if all the stairs on that level have been reached.  If so, mark it as done, and whenever you pop a node on that level, just discard it and continue onwards.  For bonus points, also mark any levels further from the goal as done, since you'd still have to go through the completed level, and you already know the best paths for its stairs.

[Veroule]

FunnyMan, standard A* breaks down when a unit is dimensionally challenged.  Meaning only limited ability to move on an entire dimension that is considered.  You said it yourself the H factor can not be over estimated, which means it has to be a shortest distance calculation, and has to relate to the F values you will use.

You can even see this on a very simple 2d map, there are many tools that will graph the standard A* for you.  Set up the map with the start point in the top left corner, the destination in top right, a north-south wall next to the desitination, and a single opening in the wall at the bottom.  A* will run straight to the wall then flood until it finds the opening.

The stair modification breaks down when there are many level change points to be considered.  For example open terrain in DF with thousands of ramps on each level will cause this modification to be much slower then A*.  Such terrain removes the dimensional challenge, and is better done without the modification.

The most common solution to do it is multi-staging, using connection nodes.  You prerun pathing between node points to determine the cost of travel between them.  Actual unit movement paths on the node table to generate an overview path, then paths on the terrain map 2 nodes ahead.  As movement reaches a node pathing for the next node is done.  That method breaks down when the terrain is variable.  Recalculating the node information can be expensive.

There is no single method that is efficient for all circumstances.  You have to select from many methods for the combination that will be most efficient with your particular needs.

[dreiche2]

I actually started my own A* implementation that respects stairs, but since my PhD went into the coding phase, I lost motivation to code even more in my spare time ...

The idea was to counter the problem with many stairs on a level by having stairs grouped according to a grid on the current level, so that their heuristic can be quickly estimated according to which grid block they are in. The pathing algorithm would thus not have to consider all stairs on the current level, but only those with a lower heuristic compared to the ones currently considered, adding more stairs when the total cost of the current path increases.

The second problem is that it can in principle happen that you consider stairs on the current level which are not accessible from where you are (without changing levels in the first place). This is something that wouldn't happen with plain A* and should thus be avoided. AFAIK Toady already tracks which tiles are accessible from each other to avoid A* pathing all over the place when tiles aren't connected. To solve the stair problem, one would have to extend this to tracking which areas are connected on a per level basis as well.

Finally, having the area connectivity graph, one could also perform search there first so that A* doesn't have to consider stairs which don't actually lead to the goal. This additional search might not always be worth it though and could be optional.

Well so much for the ideas, maybe I'll get back to them in the future...