Print

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

[Putnam]

We know that basically every fort a player plays that doesn't immediately die will succumb to FPS death, we know virtually every modern CPU can do about 8x more work than the game can currently utilize. Why not try and unlock that at all

1. We don't know that first thing at all, actually. BlindIRL's longdeath ran for something like 1000 years(?) and never suffered "FPS death", just the entropy of the game's hard cap of 3000 units before it stops bringing in migrants. It's not an inevitability as described, especially since the optimization in 50.05 was apparently way stronger than I thought because I didn't test it on a >=200 citizen fortress.
2. 8x the CPU time but not nearly so much gain in performance. Synchronization overhead is pretty dang onerous, actually.

Two things, one I don't see why finding a path necessitates modifying globally shared state at all let alone concurrently, and two having a bunch of different threads doing pathfinding at the same time isn't what I suggested anyway; if pathfinding is a relatively rare but slow task, just have one thread for pathfinding while the main thread does the rest of the tick. Since pathfinding apparently doesn't happen very often, I'm assuming it probably isn't the case that normally you need two paths calculated in the same tick anyway. Maybe pathfinding takes so much longer than the rest of the tick that you don't see much difference, maybe it does, impossible to say without knowing how long pathfinding calls actually take.

1. It doesn't and having separate pathfinders for each thread would be possible, yes.
2. One thread for pathfinding while the main thread does the rest is not possible because whatever the game needs a path for it uses immediately. You can't just foist it off onto another thread, the original ones needs that.
3. Pathfinding does in fact tend to take up a huge chunk of whatever tick it happens in and synchronizing it would remove a lot of the benefit.

I do think it's not unlikely that multithreading a lot of map block operations would be possible, which would have the benefit of making larger embarks much faster (!), but it would take such a major rewrite that it's still much better to go for smaller, "incremental" improvements. 50.05's optimization was commenting out 3 lines.

[Thorfinn]

50.05's optimization was commenting out 3 lines.

Wow! So you are saying you could improve on THAT by 33% by simply commenting out one more line? 

[Bumber]

Comment out the pathfinder -> No FPS loss due to pathfinding.

[ayy1337]

We know that basically every fort a player plays that doesn't immediately die will succumb to FPS death [..]

1. We don't know that first thing at all, actually. BlindIRL's longdeath ran for something like 1000 years(?) and never suffered "FPS death", just the entropy of the game's hard cap of 3000 units before it stops bringing in migrants. It's not an inevitability as described, especially since the optimization in 50.05 was apparently way stronger than I thought because I didn't test it on a >=200 citizen fortress.

That's actually pretty neat, but did he have to limit the population really low and avoid the cavern layers etc? I've never had a fort of decent length not have FPS be terribly low eventually, and apparently others are concerned with this too as the most popular (by far) item in the DF suggestions poll thread is performance related, as is #5.

2. 8x the CPU time but not nearly so much gain in performance. Synchronization overhead is pretty dang onerous, actually.

That's true certainly, you can never perfectly parallelize everything so you won't get 100% utilization of all cores all the time, but even getting 2x instead of 8x would be a huge boost. Soon the average desktop CPU will have 16 cores, eventually maybe 32. There's definitely something useful those cores could be doing in parallel I'm sure of it.

1. It doesn't and having separate pathfinders for each thread would be possible, yes.
2. One thread for pathfinding while the main thread does the rest is not possible because whatever the game needs a path for it uses immediately. You can't just foist it off onto another thread, the original ones needs that.
3. Pathfinding does in fact tend to take up a huge chunk of whatever tick it happens in and synchronizing it would remove a lot of the benefit.

I do think it's not unlikely that multithreading a lot of map block operations would be possible, which would have the benefit of making larger embarks much faster (!), but it would take such a major rewrite that it's still much better to go for smaller, "incremental" improvements. 50.05's optimization was commenting out 3 lines.

Two pathfinders on the odd occasion where you do have to do it twice in the same tick would be great seeing how long it can take so that's good I guess.
To your point two, how much does the game actually need the paths right then though? Seems like there's a lot that could be done in a tick that doesn't depend on knowing whether Urist wants to walk up down left or right.

And to point three, how much of a tick do pathfinding calls usually take exactly? If it's 50% that's actually basically ideal for punting it into its own thread, could cut the tick time in half. If it's more like 90% then probably you're better off looking for some other optimization like precalculating paths (incidentally precalculating paths is something that would be perfect for its own thread, since by definition the paths aren't needed right now).

Other expensive things like temperature and weather, item checks and whatnot could be other promising candidates.

In any case I'm extremely happy to hear optimizations are being made.

[Putnam]

Moving pathfinding to another thread would not make the tick faster because the main thread would have to wait until the pathfinder is done to continue doing what it was doing before, is what I was saying there.

[ayy1337]

I get what you're saying but I'm asking why, basically, does the rest of the tick depend on knowing where Urist is going? The only thing that seems to obviously depend on a creature having a path is updating its position, which could be deferred until the end of the tick. If it's really really hard to update his state in a consistent way because of the deferment the creature could spend 1 tick not moving to the destination (considering the best path) and just start moving on the next frame.

The why is somewhat rhetorical as I know you probably can't go into specifics too deeply.

[Thorfinn]

It's not quite that simple, @ayy1337, because to update a dwarf's position, you need to know at least roughly what direction he needs to head. And ideally, have the entire path already mapped out at least to the next choke point, because there's a huge difference between taking a straight path down a 100 long, 3 wide corridor and heading more or less that direction, zigzagging as you go. Worst case going more or less the right direction might turn the 100 long trek into 141.

Seems to me the simplest solution is to just let dwarves pass through one another on a path 1 wide that has already been charted for typical moves between points A and B. It would only need to be updated if doors get locked or bridges flip up or a forgotten beast is traipsing through, specifically NOT every time some dwarf is assigned a task that takes him down the same corridor. But self-evidently, that was not the vision for the game or that's how it would have been coded.

[Putnam]

Seems to me the simplest solution is to just let dwarves pass through one another on a path 1 wide that has already been charted for typical moves between points A and B.

they already do this

It would only need to be updated if doors get locked or bridges flip up or a forgotten beast is traipsing through, specifically NOT every time some dwarf is assigned a task that takes him down the same corridor.

caching such things is a bit of a computational nightmare in and of itself. A default embark is 36864 tiles per Z. Storing the weights between two tiles for just one Z level is thus 679,495,680 stored paths.

Caching common paths is slightly less nightmarish.

The game does in fact have accessibility stuff that it recalculates all the time. Calculating that is what causes water to kill your FPS. It would take much longer if it were O(n^2) instead.

But self-evidently, that was not the vision for the game or that's how it would have been coded.

sometimes things really are harder than you think, actually

[Thorfinn]

Seems to me the simplest solution is to just let dwarves pass through one another on a path 1 wide that has already been charted for typical moves between points A and B.

they already do this

Really? I've always run into issues with dwarves colliding with each other. Or I'm pretty sure that's what I saw. I never single-stepped through to watch, but I thought for sure going to 2 and 3 wide corridors and stairs fixed a lot of problems. Is that unnecessary, too? I'm seeing a lot of things that seem different since I last played.

It would only need to be updated if doors get locked or bridges flip up or a forgotten beast is traipsing through, specifically NOT every time some dwarf is assigned a task that takes him down the same corridor.

caching such things is a bit of a computational nightmare in and of itself. A default embark is 36864 tiles per Z. Storing the weights between two tiles for just one Z level is thus 679,495,680 stored paths.

Caching common paths is slightly less nightmarish.

The game does in fact have accessibility stuff that it recalculates all the time. Calculating that is what causes water to kill your FPS. It would take much longer if it were O(n^2) instead.

Gotcha. More or less what I meant. Once he has a path to go install the bed, that path remains the quickest path from beginning to end unless a door gets locked between here and there, or a bridge toggles, or an intervening wall constructed, or a new shortcut dug, or a handful of other circumstances.

Caching is another matter because the game would have to constantly update its list of optimal paths as new corridors are dug, or doors locked, etc. In my forts, it would not take very long before the cached path was obsolete.

[Putnam]

Once he has a path to go install the bed, that path remains the quickest path from beginning to end unless a door gets locked between here and there, or a bridge toggles, or an intervening wall constructed, or a new shortcut dug, or a handful of other circumstances.

This is also how the game already works. They cache their entire path as soon as they make it and they just follow it until it's done unless they're explicitly stopped along the way.

People have a tendency to severely underestimate how optimized the pathing is in this game. It is unironically about as optimal as it can get right now. It's just that pathfinding on a graph this big is inherently slow and there is nothing that can be done about it besides reducing the amount of pathing actually being done, which is already done a lot in the game.

[ayy1337]

Speaking of path caching I actually had an idea about this that I think could reduce the cost of pathing through very spread out forts a ton. Basically treat staircases as nodes and index them by region and z-level. Cache pre-calculated paths between staircases on the same z-level and region, and from each of them to nearby destinations on the same z-level, so you have a weighted graph connecting the fort.
Then all a dwarf has to do to navigate a huge labyrinthine fort is find the nearest staircase and then search the graph for his destination.

Alternatively, if you don't want to precalculate the paths you could actually just record the paths when a dwarf makes a journey that connects two staircases or between a staircase and his destination. I think this option has some nice properties like not needing to do any extra work because the dwarf was already going to generate that path, and the most commonly used paths are the ones it's going to generate.

I know you're probably sick of hearing about pathfinding by now Putnam but if you had any thoughts on this I'd appreciate them

[Magnus]

I have an idea:

Graph database (such as NebulaGraph) with quadtree space partitioning. Basically, on generating the map you partition the tiles according to passable or not, then store the partitions in a graph database. Then it's a matter of:

Urist wants tile X to tile Y.
Tile X is in Partition A.
Tile Y is in Partition Z.

Query Partition A's shortest path to Partition Z (graph databases are really good at this, and you can store info in the links between partitions such as "can walk here: yes", "can fly here: no"). So we can have dragons flying over walls. The actual path between tiles in a partition is just a straight beeline, because we know partitions are always made up entirely of passable tiles.

Cache query so Nith and Rith can follow Urist with no overhead.

The only time you have to recalculate is when a tile changes accessibility (drawbridge raising, magma flowing, Urist doing some mining etc), and then all you do is tell the tile's parent partition to do a repartitioning (possibly merging partition A B C and D into partition A if the last unpassable tile was cleared).

EDIT: I see other dogs are on the same bone here, and apparently pathfinding is as good as it gets already.

[ayy1337]

EDIT: I see other dogs are on the same bone here, and apparently pathfinding is as good as it gets already.

Pathfinding definitely isn't as good as it gets already haha, but I think the partition graph is definitely another possible solution. I think rimworld uses that. They don't have to go across z-levels but they do have a pretty large map.

[Thorfinn]

This is also how the game already works. They cache their entire path as soon as they make it and they just follow it until it's done unless they're explicitly stopped along the way.

That's what I just said. It wasn't a suggestion. I figured that was how it was coded based on watching their movement.

But I am intrigued. Did I understand you correctly that there is no advantage in terms of pathing to having corridors wider than 1 tile? Is that new, or did I really flub the testing in (I think) .34?

@ayy1337, I've run forts where that would not work well at all. Maybe a couple short stairs in the whole fort, everything else ramps. I assume you can still gain a lot of efficiency with ramps over using stairs and hallways, though I have not bothered to confirm since .42 or so. But obviously I'd go back to stairs if the advantage to ramps disappeared.

[Putnam]

I thought about implementing a sort of hierarchal pathfinding thing where each map block has 6 bits (one for each orthogonally adjacent map block), pathfinding starts by pathfinding backwards to the origin map block, storing the distance in map blocks for each block as it does, then adding the map block distance to the heuristic (multiplied by some generic constant, probably 4096 for same-Z distance and 256 for cross-Z distance, to keep it admissible hopefully), which would make things quite a lot faster... but still pretty slow, ha. Wouldn't make much of a difference, I think.

This is also how the game already works. They cache their entire path as soon as they make it and they just follow it until it's done unless they're explicitly stopped along the way.

That's what I just said. It wasn't a suggestion. I figured that was how it was coded based on watching their movement.

But I am intrigued. Did I understand you correctly that there is no advantage in terms of pathing to having corridors wider than 1 tile? Is that new, or did I really flub the testing in (I think) .34?

@ayy1337, I've run forts where that would not work well at all. Maybe a couple short stairs in the whole fort, everything else ramps. I assume you can still gain a lot of efficiency with ramps over using stairs and hallways, though I have not bothered to confirm since .42 or so. But obviously I'd go back to stairs if the advantage to ramps disappeared.

They started swapping instead of dropping to the ground in v50