Topic: Pathfinding is not a major cause of FPS death (Read 59771 times)

Putnam · « **on:** November 16, 2022, 01:32:54 am »

Source: I actually profiled the game, which is the only way to actually determine what is slow in a program.

Pathfinding is slow, yes. It's hilariously slow. The thing is, it doesn't happen often at all. When it does, fortresses drop to sub-single-digit FPS levels. This usually happens because you're using tightly closed doors. Don't do that.

Pathfinding happens so rarely that my profiling has shown it contributes to about 6% of an individual tick's processing time. This is compared to the largest cause, one whose contribution to total CPU usage actually grows faster than pathfinding and one that is still the slowest thing in early game: units checking other units for line-of-sight/proximity checks (running away from hostiles etc), which is more like 20%. The truth is that FPS death is not a matter of multithreading pathfinding or anything like that, it's a combination of just about everything in there.

Not to say there isn't some major high-level optimizations to be made. A lot of the CPU time in unit checks is wasted in branch misprediction due to the fact that it's checking the units vector and just skipping everything that happens to be inactive/caged/a ghost; if those units' indices (or pointers to them, as the case happens to be, unfortunately) were simply cached in a vector that contains only active/uncaged/non-ghostly units, that would be avoided and the game would probably run quite a bit faster.

In general, just, like. Trying to optimize a program without profiling is just... blind flailing at nothing of consequence. If you want to contribute to figuring out what is causing FPS issues, first you have to figure out how to actually use the tools that let you find out what's causing FPS issues. I don't know if this is a gatekeepy viewpoint, but I've seen people so hyperfocused on pathfinding, which does not cause FPS issues except in extreme edge cases and tightly-closed door mishaps, that they seem to be convinced that fixing the pathfinding will fix the FPS issues.

It won't. Pathfinding is not a major contributor to FPS issues. Sorry, people have just been wrong about this the whole time. You can get an FPS boost from fixing up pathfinding a bit--6% is 6%, reducing that helps!--but FPS death will set in just as it does now, even with magic oracle pathfinding that takes 0 time. It's not a pathfinding issue.

If I seem bothered by this, it's because I pondered the pathfinding a good deal too before I actually bothered to do the bare minimum work in actually figuring out why the game runs slowly and learned that, no, pathfinding has basically nothing to do with it. I literally had to be handed a save that had a pathfinding edge case (24 tightly-closed doors) before I even found the pathfinding function, since it's buried so deep due to its, again, not being a major use of CPU time.

A_Curious_Cat · « **Reply #1 on:** November 16, 2022, 03:45:15 am »

Quote from: Putnam on November 16, 2022, 01:32:54 am

Not to say there isn't some major high-level optimizations to be made. A lot of the CPU time in unit checks is wasted in branch misprediction due to the fact that it's checking the units vector and just skipping everything that happens to be inactive/caged/a ghost; if those units' indices (or pointers to them, as the case happens to be, unfortunately) were simply cached in a vector that contains only active/uncaged/non-ghostly units, that would be avoided and the game would probably run quite a bit faster.

(Emphasis added)

notquitethere · « **Reply #2 on:** November 16, 2022, 06:48:57 am »

So the last time I played (a while ago) the way to keep early game FPS at a reasonable level was to just have a very small embark space. Could you have a larger embark space, but keep # of units low and still keep it reasonable, if the major problem is units checking over units? Does this mean it would run quicker if you split up your dwarves into different warrens which rarely interacted (so less units seeing over units)?

Salmeuk · « **Reply #3 on:** November 16, 2022, 11:17:12 am »

good to read some firm words from Putnam on the issue. *pulls up a lawn chair*

Quote

units checking other units for line-of-sight/proximity checks (running away from hostiles etc), which is more like 20%.

so when people complain about fliers, does this also hold true? is it because large groups of flying kea are scouting many more units from their heavenly perspective?

disturbingly, it may be the case that a panopticon is the most efficient fortress design. what horrible reality have you created Tarn?!

Telgin · « **Reply #4 on:** November 16, 2022, 11:35:51 am »

I wonder what the performance impact might be to keep an index of only "active" units like that up to date would be. Naively I'd assume that it's something that doesn't change frequently and thus should be pretty low impact, but I don't remember exactly how C++ vectors handle things like deletion of elements in in the middle. Did that require copying / moving all elements after the deleted one? I guess shuffling even a few thousand pointers should have minimal impact if it only happens every few frames or however often it happens.

A_Curious_Cat · « **Reply #5 on:** November 16, 2022, 01:07:30 pm »

Quote from: Telgin on November 16, 2022, 11:35:51 am

I wonder what the performance impact might be to keep an index of only "active" units like that up to date would be. Naively I'd assume that it's something that doesn't change frequently and thus should be pretty low impact, but I don't remember exactly how C++ vectors handle things like deletion of elements in in the middle. Did that require copying / moving all elements after the deleted one? I guess shuffling even a few thousand pointers should have minimal impact if it only happens every few frames or however often it happens.

What about using a linked list instead?

Thisfox · « **Reply #6 on:** November 16, 2022, 02:10:54 pm »

Playing on a Mac, and I've thought for a while this was a Windows OS issue. Back before the issue with travellers from outside the map (currently I don't get migrants, caravans, etc, because of a machine upgrade) my Mac had no FPS issues, even with an in-game decades old game. Even now, with the game only just not working, no FPS issues. I am aware that I'm basically running the thing on WINE or whatever, but still, seems odd that it's not an issue for me. Is there something different about your OS handling the game?

LuuBluum · « **Reply #7 on:** November 16, 2022, 02:13:22 pm »

That's good to know, at least. My fortress design tends to be a bit antagonistic towards optimizing for pathfinding, so good to know that won't kill FPS.

Telgin · « **Reply #8 on:** November 16, 2022, 03:11:21 pm »

Quote from: A_Curious_Cat on November 16, 2022, 01:07:30 pm

Quote from: Telgin on November 16, 2022, 11:35:51 am
I wonder what the performance impact might be to keep an index of only "active" units like that up to date would be. Naively I'd assume that it's something that doesn't change frequently and thus should be pretty low impact, but I don't remember exactly how C++ vectors handle things like deletion of elements in in the middle. Did that require copying / moving all elements after the deleted one? I guess shuffling even a few thousand pointers should have minimal impact if it only happens every few frames or however often it happens.

What about using a linked list instead?

Linked list traversal is very slow compared to iterating over a vector so I'd expect it to be a bad trade, but it depends on the typical size of the collection and how often it changes. I haven't profiled any of it myself of course, so I'm not sure what typical numbers would be.

A funny thought would be just sorting the unit vector by active / inactive status, but sorting it may not have a trivial time component and isn't particularly useful if there are multiple flags or fields it checks for this purpose. I suspect there are multiple unrelated fields.

On this topic, I'm wondering what the implications would be on cache misses if a separate index were used that stored pointers to the units. If their status changed and they were removed and added back then the index would get out of order and lead to poor cache coherency, unless efforts were taken to prevent that. No idea how much that would compare to branch prediction misses on a modern desktop CPU but I'm guessing it's not trivial. Then again, my guess is that DF probably has a lot of cache problems because of how much it keeps track of.

anewaname · « **Reply #9 on:** November 16, 2022, 04:53:13 pm »

That example of 6% and 20% gives no example of the scale of the fort's population and layout. If Observation checks were using 20% CPU, is this because there are 300 dwarfs in a 20x20 room?

I'm thinking of how I often set up a single room with a temple, tavern, library, and barracks in it, and dwarfs gain in observation skills because of this.

A_Curious_Cat · « **Reply #10 on:** November 16, 2022, 05:29:37 pm »

Quote from: anewaname on November 16, 2022, 04:53:13 pm

That example of 6% and 20% gives no example of the scale of the fort's population and layout. If Observation checks were using 20% CPU, is this because there are 300 dwarfs in a 20x20 room?

I'm thinking of how I often set up a single room with a temple, tavern, library, and barracks in it, and dwarfs gain in observation skills because of this.

So… dwarves only ever check to see if they have line of sight of each other if they have line of sight of each other?

Putnam · « **Reply #11 on:** November 16, 2022, 08:04:56 pm »

Quote from: Salmeuk on November 16, 2022, 11:17:12 am

good to read some firm words from Putnam on the issue. *pulls up a lawn chair*

Quote
units checking other units for line-of-sight/proximity checks (running away from hostiles etc), which is more like 20%.

so when people complain about fliers, does this also hold true? is it because large groups of flying kea are scouting many more units from their heavenly perspective?

disturbingly, it may be the case that a panopticon is the most efficient fortress design. what horrible reality have you created Tarn?!

Every unit must check every other unit to see if they're in line-of-sight; this is actually basically unavoidable. It's not the line-of-sight checks that are the problem, it's the checking for line-of-sight. Skipping over units that literally cannot be seen by anyone even in principle takes up more CPU time than pathing.

Quote from: Telgin on November 16, 2022, 11:35:51 am

I wonder what the performance impact might be to keep an index of only "active" units like that up to date would be. Naively I'd assume that it's something that doesn't change frequently and thus should be pretty low impact, but I don't remember exactly how C++ vectors handle things like deletion of elements in in the middle. Did that require copying / moving all elements after the deleted one? I guess shuffling even a few thousand pointers should have minimal impact if it only happens every few frames or however often it happens.

It's O(n) to remove from the middle. This would only happen when units die, become caged or leave the map, though, which is rather rare. "Every few frames" is a massive overestimation, orders of magnitude more often than it's likely to actually happen.

Quote from: A_Curious_Cat on November 16, 2022, 01:07:30 pm

Quote from: Telgin on November 16, 2022, 11:35:51 am
I wonder what the performance impact might be to keep an index of only "active" units like that up to date would be. Naively I'd assume that it's something that doesn't change frequently and thus should be pretty low impact, but I don't remember exactly how C++ vectors handle things like deletion of elements in in the middle. Did that require copying / moving all elements after the deleted one? I guess shuffling even a few thousand pointers should have minimal impact if it only happens every few frames or however often it happens.

What about using a linked list instead?

Since we're talking about something you iterate over, you want a vector, no other choice. Linked list iteration is pretty bad, as mentioned earlier. The fact that removal from the vector is rare (only when units leave/die) means that its worse asymptotic performance isn't terribly relevant.

Quote from: anewaname on November 16, 2022, 04:53:13 pm

That example of 6% and 20% gives no example of the scale of the fort's population and layout. If Observation checks were using 20% CPU, is this because there are 300 dwarfs in a 20x20 room?

I'm thinking of how I often set up a single room with a temple, tavern, library, and barracks in it, and dwarfs gain in observation skills because of this.

The checks have little to do with actually being able to see other units. It has to check every unit regardless. Literally half of the CPU time spent in there was skipping over dead/caged units due to branch misprediction. IIRC this fort was something like 100 citizens, where they were doesn't really matter due to the previous. It also has nothing to do with the observation skill, not sure where that comes from. This is the basic checks that e.g. make dwarves run away and cancel jobs.

delphonso · « **Reply #12 on:** November 16, 2022, 11:29:45 pm »

Hmm - so the solution is still the same, right? Atom-smashing corpses and occasionally, your own dwarves.

Does this new-found knowledge help us understand how to optimize our own games a bit more? Maybe...blinding dwarves?

bloop_bleep · « **Reply #13 on:** November 17, 2022, 12:51:33 am »

Guys, the ideal data structure would be a hash table, e.g. std::unordered_set, no? O(1) insertion, deletion, iteration, at least in theory. At most there could be some data locality issues with jumping between different buckets.

EDIT: Also there is probably something clever you might do for line-of-sight checks. Creatures can only see so far, right? Assign each creature to a set of rectangular blocks which they might potentially be able to see in, then only check line-of-sight in those blocks.

Salmeuk · « **Reply #14 on:** November 17, 2022, 01:14:40 am »

Quote

Every unit must check every other unit to see if they're in line-of-sight; this is actually basically unavoidable. It's not the line-of-sight checks that are the problem, it's the checking for line-of-sight. Skipping over units that literally cannot be seen by anyone even in principle takes up more CPU time than pathing.

thanks for the clarification. this truly is something us players cannot avoid.

I love the idea that you drop this info less than a month away from the new release - after years and years of (what ultimately appears to be) superstitious rituals in the name of saving FPS.

News:

Author Topic: Pathfinding is not a major cause of FPS death (Read 59771 times)

Putnam

Pathfinding is not a major cause of FPS death

A_Curious_Cat

Re: Pathfinding is not a major cause of FPS death

notquitethere

Re: Pathfinding is not a major cause of FPS death

Salmeuk

Re: Pathfinding is not a major cause of FPS death

Telgin

Re: Pathfinding is not a major cause of FPS death

A_Curious_Cat

Re: Pathfinding is not a major cause of FPS death

Thisfox

Re: Pathfinding is not a major cause of FPS death

LuuBluum

Re: Pathfinding is not a major cause of FPS death

Telgin

Re: Pathfinding is not a major cause of FPS death

anewaname

Re: Pathfinding is not a major cause of FPS death

A_Curious_Cat

Re: Pathfinding is not a major cause of FPS death

Putnam

Re: Pathfinding is not a major cause of FPS death

delphonso

Re: Pathfinding is not a major cause of FPS death

bloop_bleep

Re: Pathfinding is not a major cause of FPS death

Salmeuk

Re: Pathfinding is not a major cause of FPS death