Print

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

[Thief^]

A side note that might be important:

Spoiler (click to show/hide)

The A* method on the linked webpage will (hopefully) differ from toadys method. The reason for this is that a real life diagonal step is longer than a dwarfs diagonal step.
Lets suppose you have marked a few tiles on the floor and are standing in the center of one, the center of the tiles directly adjacent to you is just one (1) step away. But diagonally adjacent tiles are (remember Pythagoras) square root of ( 1^2 + 1^2) steps away (about 1.41 steps). Dwarfes on the other hand (afaik) will just need one step in all directions. The A* method there will assume a stepping cost of one for directly adjacent tiles and 1.4 steps for diagonally adjacent tiles. This changes quite a lot when you have to find diagonal paths:


Select the greedy method in the program to get more df-like solutions (where all tiles are just 1 step away).
With simplified pathing costs quite a few less tiles have to be checked to find a diagonal path, the reason for this is that the sums for diagonally accessed tiles are lower, so they will be preferred if they bring us closer to the target, otherwise diagonal steps will be avoided a bit.

The webpage version is bugged, a real implementation of A* has no trouble with diagonals. Across open space A* and "greedy" should behave exactly the same.
My guess would be that it's using a straight-line distance for the A* heuristic, instead of an actual estimate of the remaining path cost (i.e. so many diagonal + so many straight).

But yes, to be dwarf friendly you want a very connected fort, with stairs everywhere. Otherwise, the pathfinder is going to search every floor over the place the dwarf actually wants to go to, finding that there's no direct route.

[Bronzebeard]

I think to improve "Dwarf intelligence", it would be useful to have some pathfinding numbers in the ini, like whether a Z-level is worth more.
Recalculating ideal paths between "accessibility areas" every season change would probably not take up much.
But wouldn't the best speed improvement be good multi-core support?^^
I think having pathfinding as a separate thread would speed stuff up.

Very, very, very true. 6-core processors are out now, and single-core computers are becoming a thing of the third world. Toady should get on that, foremost.

[Beeskee]

I wonder if a better pathfinding method would be to go from both points at the same time towards each other...

[DDR]

I'm satisfied with the current state of path-finding right now, tbh. I've had a few examples of times the pathfinding algorithm is invoked when it can't find a path, and - indeed, framerate goes down by about four fifths. All paths being calculated normally do find a way.

I'll have to give this some thought, but pathfinding sounds like it could be either very hard or easy to thread.

[infernalis]

Another addendum:  In large rooms with multiple small entrances and exits (like legendary dining halls) I have seen my FPS increase after designating high-traffic zones that connect all of the doors.  In dorms with lots of twisty zig-zags, it might be worthwhile designating a high-traffic path to a "common room" and then restricting the rest of the dorm.  Dorfs will still sleep there, but they won't path in looking for a way out of the tunnel complex.  If you think of a high-traffic zone as a rail or a notch in the floor that the dwarves tend to stay in (like lazy little marbles) it's easy to figure out where they'll need help.

Oi, what's a high-traffic path/zone?

Btw, there seems to be a difference in pathfinding for mining and channeling: for a set of 3 novice miners the former gets much more screwed up that the latter;

[beorn080]

I just skimmed, so I'm not sure if this has been mentioned yet. From what I recall, dwarves have two seperate pathing algorithms. One is a long range Point A to Point B that gets set when the job is assigned. The other is a short ranged check that looks for other dwarves and other obstacles. So wide hallways are a must so that each dwarf is able to follow its own path. Also, keep the halls clear of animals greatly improves it.

[Truean]

Wonderful paper. Question, how do I best apply it?

Might I request a follow up applications paper with fortress design blueprints set to achieve certain goals: living arrangements, dinning, work, etc.

This is seriously a wonderful paper; great job.

[HebaruSan]

How about a mix of the two? The dwarves stick to a learned path wherever they need to be but once every so often they calculate the surroundings to refresh and re-optimize their pathing (as opposed to doing that every single time, hundreds of dwarves doing it every single second).

That's better, but it could still be a lot of paths, I think. 200 bedrooms to and from the dining hall, plus the various workshops, plus stockpiles, plus mining sites. There's a lot of many-to-many here.

Why not combine the two approaches in this thread? Instead of memorizing specific paths, Toady could add an option to auto-populate the traffic designations based on real pathfinding (I know people have other reasons for designating traffic, so maybe "restricted" could remain as a separate, non-overrideable feature). For some sampling of real paths, ignore the current designations and calculate a "from scratch" path, then lower the cost of the tiles it contains. All other paths would use these generated traffic designations as an optimization. When your layout changes, the sampling would pick it up and gradually adjust (I don't know about you, but when they block a hallway at my job, it takes me a while to get used to it ). This should provide an automatic FPS boost over time, with no increase in memory consumption (same traffic data structure).

The sampling could be a percentage (e.g., 1% of all paths are randomly selected to be important), influenced by personality (more creative, independent-minded dwarves re-calculate more often). Or it could be something the manager or bookkeeper nobles take care of during their rounds.

[infernalis]

In my 31.03 version dorfs don't differentiate between z-lvls, so if there is a hostile on 1st floor which makes my farmers suspend harvest, my dorfs on the 2nd floor can't sleep, coz they take the zombie on the lower lvl into path-to-bed consideration. Or something.

[hjd_uk]

Thats a very in-depth explaination.

I assumed that A* was being used as the traffic zones would just change the path-cost of each painted tile to alter the A* route.

---

In other words; Keep it Simple.
Try to make a 3d grid system of stairs and cooridors.
I tend to have a few main stair-wells that join all my levels (as much as possible) and keep my resources near the places they are needed.
Remember that a stairwell is 1 'distance' so putting your wood stockpile directly above your carpenter-workshop and linking with a stairwell is better than putting it at the end of the cooridoor.

Technically the best architecture for pathfinding would be lots and lots of 3x3 rooms with single exits and 1-tile walkways all in a 3d grid-system.

Just plan out the fort in an effort to make your Dorf's journeys as short as possible.

[numerobis]

For path finding, Dwarf Fortress uses bog-standard A* with an L2 or similar heuristic.  First though, before a path is computed, it checks whether there exists a path -- whenever you lock doors, close bridges, build walls, or vice versa, the game recomputes the connected components on the map (this is pretty noticeable when you have a lot of connectivity-changing events).

For finding a material for e.g. a masonry job, it uses breadth-first search ignoring obstacles, with unit-cost diagonals, and ignoring Z; it stops at the first material it finds to which there's a path.  This is quite tragic: your dwarf will hike for *miles* over giant piles of rock to get the pebble on the other side of the wall.

Pretty much everything you say about how to exploit this knowledge is accurate.  One thing I frequently do is a big thick east-west corridor with workshops and rooms hanging off the north and south sides.  This is disastrous for a common case of a dwarf that enters on the east side, needs to walk all the way down the corridor to the west side, and then go either North or South from there: A* will search *every* room for a shortcut.  Traffic designations can help work around the bad design.  Knowledge can help fix the bad design (if A* is going to look for a shortcut, make one exist!)

[Hyperturtle]

I agree, you can fix an adhoc design with pathing costs. 

You can also increase the dwarfs safety.  For example, I dug a tunnel linking two parts of the map, and have reduced the path cost of that route to make most dwarfs prefer to go underground through the tunnel, than walk over the topside. The tunnel connects to fairly well defended areas and there is limited chaos during attacks.  Now they are usually quite secure from an outside ambush, as most dwarfs are indoors for most activities.

[einstein9073]

Only one problem... when should the paths be calculated?
...
The only practical possibility, I can think of, is only saving major traffic routes that are frequently used. The dwarves would still need to use regular pathing from their current location to the beginning of the main route (that goes wherever they need to go) and once they'd reach that route, they would just follow the predefined path until the end point from where the regular pathing would kick in again. It's still not easy to let them know, which main route is the best for their current purpose, but maybe it's a tiny bit more practical than saving everything.

Please correct me, if there's something fundamentally wrong with my negative thinking.

...The dwarves stick to a learned path wherever they need to be but once every so often they calculate the surroundings to refresh and re-optimize their pathing...

Your idea sounds a lot like what ants do. When they go off exploring, they lay down a "HAY I'M WANDERING THIS WAY" trail. When they come back to the nest with food, they lay "HAY GUISE FOOD THIS WAY KTHX". Yes, ant pheromones speak in LOLCAT.

Dwarves are not ants. (I don't think. If beak dogs can be velociraptors and kobolds can be lizardmen maybe dwarves are pheromone-laying insects. They are kinda hive creatures. Hmm.)

Besides, pheromones wouldn't help as much for DF. Dwarves are omniscient (sorta -- i mean that every dwarf knows about everything you can see on the map) so the kind of information stored in a pheromone trail isn't as useful as it is for an ant colony, whose workers are EVEN DUMBER THAN DWARVES.

I would expect more improvement from an implementation of the Hierarchical Path-Finding algorithm linked earlier.

[lookmeat]

Dammit that paper is awesome. The thing is, the dwarf fortress maps change a whole lot more than your average map. The algorithm might require too much changing, I'd have to play with it to see...

I though of a system where certain points where marked as "central points". Basically whenever a dwarf (or something) passes through a tile, it starts marking it, when it's been passed a certain amount of times it's considered a "key point". A couple other things that might influence if a tile (or area) is a key point is how many places it comunicates (say if it's an up-down stair) and how close it is to other keypoints (the farther the easier it is).
The craziest case would be building an up-down stair that makes a tile become a key-point and makes another keypoint stop existing.

The most inefficient moment is when a key point appears. Keypoints "precalculate" the optimal path distance of all tiles a certain distance from them, say until three other keypoints are reached. This is done with a flooding algorithm*, the nice thing is that this algorithm is a cell-automata based algorithm, so any change in the map doesn't trigger a full recalculation, but only recalculates the changed parts. It might take some time for the change to occur, but we aren't expecting optimal pathing and all knowing from the dwarves, let's give them some time to "learn" the new best path. A single tile could have the distances to many keypoints (though you should wonder why it isn't a keypoint itself if it's so centric).

Now we can calculate the optimal paths between keypoints. Because we extend the distances we calculate from a keypoint A until we have reached keypoints B, C and D (for example), we can do a map with diferent distances between the keypoints. We can use Dijkstra to find that the best path from A to E (which connects with B, C and F) is through C, for example. Hell, if the number of keypoints is small enought (and I mean something less than 50,000) floyd's algorithm could work, on the expectation that changing the optimal path between keypoints, or changing keypoints themselves is relatively rare (and it should). There could be cases where it actually finds a non-optimal solution by much, but if the number of keypoints that need to be found before stopping the flow algorithm.

When we want to find the optimal path between A (say a dwarf) and B (a barrel of dwarven rum), first A and B would find their closest "keypoint" (lets call them Ka for the dwarf and Kb for the rum). We find the optimal path between Ka and Kb. The dwarf then chooses a Keypoint Ks from all the Keypoints A has a measured distance to the Keypoint along the path that is closest to Kb. The dwarf then uses a greedy algorithm, reading the distance in each tile, to travel to Ks. From there he uses the same greedy algorithm to travel to Kb. Once the dwarf reaches Kb, the optimal path from B to Kb is found (again greedy method), and then the dwarf travels this path "backwards" to get to his precious alcohol. Now the dwarf if finally happy.

The biggest issue is how much the flooding would take in frames. If it happens separately, it might be reasonable. Another solution is to have a "step" in the flow to occur, but this might make a drastic map change take a couple hundred frames. None the less if the game runs at 100 FPS (not graphical, but logical step frames) this might not be that much of a problem.

Again I guess I'd have to do some math, and then experiment a bit (because algorithm efficiency only works when all steps take the same amount of time, which isn't so) and see what happens...

*The flooding algorithm works like this:
//Given that all tiles start with a distance "infinite" except the starting tile (which has 0)
flooding(tile):
    for adj in adjacent_tiles(tile):
        if adj.is_passable and tile.distance < (adj.distance + 1):
            adj.distance = tile.distance + 1
            flooding(adj)

[azmodean]

Actually I think the idea to use the existing dwarf paths to fill out where the high traffic zones are is a really good idea.

I think this is usually referred to as a breadcrumb approach.  As your entities move around the map, they drop virtual "breadcrumbs" at a certain rate.  In future calculations, these breadcrumbs are used to bias selection of a given tile for pathfinding.  In order to keep the paths optimal in the face of changing topology and tasks, you have the breadcrumbs age or decay (just periodically decrimenting the value of every tile would do it, then it's just a matter of determining how often to do it).  When a new path is opened up, pathing through that area will be temporarily mis-optomized because it will prefer the old path, but it should still detect the new path, and over time the more efficient path will become the preferred path.

As mentioned, this could replace the current high traffic areas, but it could also instead be used in addition to the high-traffic area interface.  So if you make major changes to your layout, or perform some movement-intensive task that screws up the breadcrumb distribution, you could manually adjust the breadcrumb distribution to return it to a good state, from where it would continue to optimize itself.

I think the behavior of such a system would be really good, since when a fortress starts, the pathing load is very low, so you have plenty of time to develop a breadcrumb network, and a side effect would be to provide the player with a heat map of dwarf movement, which would be extremely useful for evaluating fortress layout.