Print

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

[HenAi]

Basically, implement a cache for paths.
Kill the cache for a path when a new (blocking) object gets put in the path.

And on a similar note, limit path finding to find a path to the closest cached path first. And only if none exists, use the normal pathfinding.

Essentially, since multithreading is out for the foreseeable future, utilize RAM to take load off of the CPU where possible.

Edit:
For example, like (target tile)z->A->x+y->B+C => (origin tile)z->D->x+y->E+F | can_jump,can_fly => combination_exists ? use : normal_pathfinding

[King Mir]

Basically, implement a cache for paths.
Kill the cache for a path when a new (blocking) object gets put in the path.

And on a similar note, limit path finding to find a path to the closest cached path first. And only if none exists, use the normal pathfinding.

I don't think we want dwarves to ignore a new shortcut, nor to take the longer but more traveled path when a shorter path exists.

Essentially, since multithreading is out for the foreseeable future, utilize RAM to take load off of the CPU where possible.

This is the wrong motive. RAM latency is the bottleneck for DF. The CPU is about 100 times faster (depending on cache friendliness). Doing a bit more work on the CPU to avoid an extra random access into RAM is generally worthwhile.

[GavJ]

This is the wrong motive. RAM latency is the bottleneck for DF. The CPU is about 100 times faster (depending on cache friendliness). Doing a bit more work on the CPU to avoid an extra random access into RAM is generally worthwhile.

The CPU needs to wait on RAM of the current map tiles in order to calculate a path, though... Looking up a cache should be equal or likely lesser RAM access as well as lesser CPU.

I don't think we want dwarves to ignore a new shortcut, nor to take the longer but more traveled path when a shorter path exists.

Yes, this is true.

But there are tons of heuristics you could use here to notice when the things you mentioned might have changed. For example "Only clear or recheck the cache if and when a tile is dug or removed that is not a dead end (i.e. has more than one face exposed to open space after digging) or when a block is placed not in a dead end" <--- A very conservative rules, but even this would probably save a decent amount of FPS, since digging or placing walls in non dead ends is something that only usually happens once every few thousand ticks on average, probably.

Or more sophisticated version: "When one of the two above events occurs, do a quick, exploratory flood search. If, within 100-200 tiles or so, everything nearby is determined to be a dead end except one exit to the just-placed wall or just-dug tile, then don't clear or update the cache. If there still exist 2 or more posssible non-dead-ends after the maximum allowed search, though, then go update the cache." On the principle that a 200 tile search is much more likely to be efficient than redoing a ton of long paths.

Also, creatures should never be attempting to re-path after a failed pathing until/if tile changing events like those above happen (cough clowns cough cough) - not exactly related to OP, but still.

etc. etc.

[HenAi]

Basically, implement a cache for paths.
Kill the cache for a path when a new (blocking) object gets put in the path.

And on a similar note, limit path finding to find a path to the closest cached path first. And only if none exists, use the normal pathfinding.

I don't think we want dwarves to ignore a new shortcut, nor to take the longer but more traveled path when a shorter path exists.

Cache for any path would need to be killed if a blocking object (like a wall) was placed on a tile the path goes through. For opening up tiles, any that lead to a dead end could be ignored, i.e. if you mine out a wall, that could be ignored for all existing cached paths until it connects somewhere.
Like this (- open tile, + blocked tile):
-----
++++
++-++
++-++
-----
Only when the + above the - in the third row gets mined out would the cache need to be cleared.
Could be further optimized since not every new path that opens up is relevant to existing paths. If you mine out walls 200 z-levels below the surface, that can't matter to any existing path on the surface which doesn't go down any z-tiles. Doing that would of course be the most complicated part of this.
But even without that, caching would already help a lot.
Well, GavJ already summarized it nicely.

Essentially, since multithreading is out for the foreseeable future, utilize RAM to take load off of the CPU where possible.

This is the wrong motive. RAM latency is the bottleneck for DF. The CPU is about 100 times faster (depending on cache friendliness). Doing a bit more work on the CPU to avoid an extra random access into RAM is generally worthwhile.

There's no one single bottleneck, but even disregarding that, this would save on RAM accessing, too.
Also, if you have the option of either "get data to calculate path from RAM, then calculate" or "get the calculated path from RAM", the latter will always be faster, even if you needed to load the same amount of data for the latter as for the former, which you don't (since you only need the tiles on the path for the latter, but many more for the former).
In short, if you have, say, a butcher's shop and a stockpile and some dwarves regularly hauling stuff between them, it'd be much more effective if the path between the two was only calculated once, rather than every time a dwarf wants to path from one to the other.

[Putnam]

I think there already is path caching?