Print

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

[jeancallisti]

I'll be happy to do this, but I'm not entirely sure we even have to. In order to override the old pathfinding routine with a new one, we would simply check for every unit every tick whether unit.path.dest has changed, and if it has, change unit.path.path to whatever we want. This way, the default pathfinding algorithm will see that unit.path.path has already been set, and simply skip pathfinding for that unit. There might be some timing issues with trying to get to unit.path.path before the default pathfinder does, but other than that it should be pretty simple.

Yes, that was the plan from the beginning, plus or minus some small changes.

 But the latest test I suggested has moved on to testing something else: what is the weight of the native pathfinder on a game with a number of units close to the (practical) top limit? And does our bypassing method really silence the native computations, or does it have some unforeseen corner-case that causes the native pathfinder to run anyways at full cost?
The best way to measure that is to suppress the native pathfinder (in real conditions) and measure the difference.

[bloop_bleep]

OK. Working on it now.

[PatrikLundell]

- As far as I understand, DF selects destinations based on proximity as the dorf digs, i.e. the geometric distance, possibly with some Z level weighting (while ignoring burrows...). Once the target has been selected, the actual pathing to that destination takes place (respecting burrows so spam is generated when the target is detected to actually be invalid). This leads to stupid things like walking past the target location to the one beyond it, because the actual path arrives from the opposite direction (and it can probably be blamed for at least some cases of dorfs bricking themselves in when the only path is from the outside and the building material is on the outside as well).

- Based on observation, the pathing is done at the start with recalculation only happening when the path is obstructed, and that recalculation seems to be only to the next point in the path. This leads to stupidities such as units climbing when the floor/stair the path was pathed through gets removed while the unit was en route, even when there is a single tile safe detour on the side. Another silly case is setting up two single tile parallel corridors to a target. You can then have the pleasure of seeing two units approach each other from opposite directions along the shortest path, bump into each other, and have BOTH turn around to bump into each other in the other corridor, turn around.... Eventually something may cause the ping-pong to stop because one unit is interrupted, at which time the remaining unit paths either along the original corridor with no issues, or along the longer one, after which the bugger turns into the shorter one from the remote end, walks to the point the collision happened (or probably the adjacent tile), and then, happy at finding the path, turns around and continues along the remainder of the original path.

[jeancallisti]

I wrote a long message yesterday night but it seems to have disappeared??? Anyways. I'll type it again.

Thanks a lot for your post it provides invaluable information, especially the part about dwarfs anticipating obstacles only one block ahead, and the part about the pathfinder recalculating only one waypoint ahead.

About those weights:
- I'd like to be sure about the z-moving cost. Do dwarves understand that it's shorter  to walk around a mountain?
- what [/i]other[/I] kinds of node weights are there? Are we sure there are none? For example: do dwarves walk around thick forests? Do they rather find a bridge than swim to cross a river?

I didn't get the part about burrows, by the way. I don't know DF well enough and I don't know his they're different from regular corridors. How will there be extra spam because of them?

[bloop_bleep]

Burrows ('w' from main screen) restrict the movement of dwarves you assign to them to a certain area. It's important to note that a path within a burrow is considered if the start and end points are in the burrow; the waypoints don't all have to be in the burrow.

[PatrikLundell]

Unlike RL humans, dwarves do not care whether they're moving vertically or horizontally, so I think one tile is one tile, regardless of direction, but I believe diagonal movement is calculated as such, but without regard for whether that diagonal is vertical or horizontal. The path finder finds the "shortest" path, taking movement restrictions into considerations (you can set up those, but they default to normal cost everywhere, and DF does not set up any movement restrictions on its own).
Pathing does not allow climbing or swimming for normal critters, but pathing will set up paths through variable depth water if the water level at the time of pathing is 3 or below, and will likewise path through tiles onto which magma sloshes if there's no magma at the tile at the time of calculation, which can lead to dorf incineration when magma sloshes onto to tile when the dorf is on it (the dorf won't step into magma, though). Natural climbers are probably handled differently, and I'd suspect natural swimmers are as well. Path finding for fliers is buggy.

As bloop_bleep said, a burrow is an area (not necessarily contiguous) that says that assigned units (all civilians in the case of an active civilian alert) may only go to targets within the burrow, and not perform tasks that do not have their targets within the burrow. Path finding to that destination is completely oblivious of the burrow: it finds the shortest path. This also means non contiguous burrows usually won't work as intended, as dorfs readily pass from one area to the other through whatever you wanted them not to enter... Civilian alerts cause civilians to move inside the burrow, but ordinary burrows have no "pull", so units just stay rooted in place until they find a task that takes them inside the burrow when assigned to a burrow (with some exceptions: need fulfillment can violate burrows, for instance).
The burrow spamming comes from task assignment assigning tasks without checking that the target is at a legal location, so the task is accepted, but the path finding finds that the target is in a disallowed location, so the task is cancelled. The task assignment finds a task (quite possibly the same one)...

Movement restrictions (d-o, I think) specifies the cost of moving one tile (I think the default is 5), and so can be used to guide dorfs to move along certain paths and avoid others. However, the system doesn't work that well because there is no "DON'T EVER GO THERE" restriction. As an example, in an embark where water freezes periodically you don't want your dorfs on the ice when it melts, but ice is passable terrain. Painting the rivers and pools as restricted movement zones will increase the cost of crossing that terrain, but if the bridge is too far away it's still cheaper to cross over the ice. Also those restrictions are omni directional, so you can't specify that it's cheaper to move away from the river than moving towards it. This means wood cutters and the like will still drown. (And visitors, caravans, and invaders completely ignore movement restrictions anyway).

[Putnam]

DF sets up some restrictions on its own: minecart tracks are automatically set to low traffic.

Also, the default cost is 2; the default low is 5.

[PatrikLundell]

Thanks for correcting me, Putnam.

[jeancallisti]

By the way bleep bloop, any update on that performance test when the native pathfinder is forcibly disabled?

[lethosor]

Movement restrictions (d-o, I think) specifies the cost of moving one tile (I think the default is 5), and so can be used to guide dorfs to move along certain paths and avoid others. However, the system doesn't work that well because there is no "DON'T EVER GO THERE" restriction. As an example, in an embark where water freezes periodically you don't want your dorfs on the ice when it melts, but ice is passable terrain. Painting the rivers and pools as restricted movement zones will increase the cost of crossing that terrain, but if the bridge is too far away it's still cheaper to cross over the ice. Also those restrictions are omni directional, so you can't specify that it's cheaper to move away from the river than moving towards it. This means wood cutters and the like will still drown. (And visitors, caravans, and invaders completely ignore movement restrictions anyway).

Nitpick: you can adjust the 4 costs in the d-o menu. If you set restricted to ~10000 instead of 25, there's no map large enough that dwarves would go through a 1xN restricted area if there's another possible path.

[jeancallisti]

So the restrictions are painted by the player, not the game, uh? (apart from the minecarts).

Well I think I have a pretty good idea of how the current pathfinder works. If we make another one, then it does not matter if it works exactly like DF's one. The goal is to save lots of FPS in large fortresses. It can be improved overtime to mimic more and more DF's pathfinding refinements.

Because it's meant primarily for efficiency and for lifting the weight on the CPU, it would have these specs, that sparkled the whole idea :

- the alternative pathfinder needs to be mostly "offline". That means that it can update its knowledge of the world at some quite random times and not "too often" (which is still quite often, don't be worried, but not as often as a task hardwired directly in the native game loop). For example it will not be immediately aware that a tile is now filled with lava (which still doesn't mean that the dwarf will walk there, as they don't).
- the alternative pathfinder needs to provide an immediate (rather bad) first waypoint when being queried. That would be resolved with a lousy heuristics such as "start by walking one tile towards your final destination, I'll tell you what to do during next game loop". That's not too big of a problem since the game is so slow (less than 10fps) when there are many dwarves
- that lousy heuristics can be greatly improved by using a lot of RAM in replacement of CPU time. What we do, like every pathfinding algorithm ever, is trade computation cost for big indices that get built over time, as a background task, by another CPU core. Since DF's big problem is CPU and not RAM (it uses 1GB tops on coputers that have 16GB of RAM) then we steadily create big indices to create lightning past pathfinding over short distances in complex blocks of 16x16x1.
- because of what I wrote above, that's more than A*; that's any of its variations which index-building phase knows how to change a block without rebuilding everything, and does not hesitate to store a lot in memory -- even on the hard drive if needed, for long-distance path search. It should also not be (too) surprised i some tile data changes during its computations -- there would still be that process of getting the data from the game running in the background.
- the general algorithm, just like DF's native one, relies on connecting those 16x16 blocks as "abstract" network nodes.

Then, there could be some optimizations :
- the process crawling the map data focuses on tiles immediately around dwarves or creatures (they are th emost likely ones to alter the map)
- ...

As a summary, I'd say that there would be about 4 components in that system :
1) a small "core" component (That one would be the DFHack plugin) that knows: a) when to overwrite unit.path.dest at every game loop to fool the unit about its final destination, b) a quick heuristic to tell the dwarf when to go while the pathfinder has not returned yet (that would last only one game frame I think), and c) how to force the dwarf to go wherever the separate-thread algorithm tells it to go eventually.
2) a "crawler" component that steadily provides the separate "builder" and "searcher" threads with updated data from the world, primarily in interesting places (places that re likely to change often). That process knows when to read the world data without conflicting with /slowing down the game. It's strictly copy and paste. During its initialization phase it needs to read everything so it would be slow, but then it would update small amounts at a time (see the optimizations I mentionned above). We can decide that the first execution freezes the game, as one-time task.
3) a pathfinder "builder" component that builds all the indices to make the pathfinder "searcher" faster. That can be found in literature.
4) a pathfinder "searcher, that relies on the builder. That can be found in literature.

[jeancallisti]

EDIT: woops, I posted by mistake

[Putnam]

cache misses causing memory access is actually the thing that bottlenecks dwarf fortress more than anything else on the CPU, so adding yet more memory read times is not likely to improve performance much; making it access the hard drive would be even worse by orders of magnitude

not that this isn't worth trying; for what you're describing, you probably want to look into vector fields

[PatrikLundell]

As Putnam said, memory access may well be a worse bottleneck than CPU (do CPU usage measurements even consider the CPU to be "idle" when it's actually waiting for data from memory to arrive?). Also, fortresses can easily cause DF to use more than 1 GB RAM (or switching to a 64 bit capable implementation wouldn't have been needed). My current 3*3 embark fortress has DF weighting in at a bit over 2 GB, which wouldn't work with the 32 bit version (at least not without LAA patching). A 16 * 16 (incredibly slow) embark would use a lot of memory...

[jeancallisti]

It's not gonna hurt I promise.

Would you have suggestions regarding the most clever way to access memory (to read it) to minimize overhead required by concurrent access -- and therefore avoid adding to the bottleneck? Anyways as I said its all about scaling up. Once the world is mapped and we steadily update it, it doesn't matter if it slows down the game; what we're trying to achieve is a logarithmic increase in reources use, as opposed to the linear one.