Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  

Author Topic: Add LRU caching to pathfinding.  (Read 1150 times)

BoboJack

  • Bay Watcher
    • View Profile
Add LRU caching to pathfinding.
« on: February 08, 2020, 06:35:38 am »
You could try remembering the most used 100 MB or so of distances and paths between pairs of tiles in a LRU cache https://www.geeksforgeeks.org/lru-cache-implementation/.
Maybe even 1GB. The most used of these would be in the cpu cache then, which would be fast.

I would probably recompute the paths, when a dwarf needed much longer/less for the path than expected.

The Cataclysm DDA dude apparently had a similar idea. https://github.com/CleverRaven/Cataclysm-DDA/issues/9914 but didn't act on it.

Storing only distances you'd maybe be able to use the distance information for faster pathfinding, but I'm not sure how exactly.
Pruning too long paths could be wrong as the original path need not exist anymore. But maybe that doesn't happen so often.
If you only store distances between tiles, you should store a moving average https://en.wikipedia.org/wiki/Moving_average of the time it actually took the dwarves to walk the paths which's distanced you've cached.
« Last Edit: February 08, 2020, 08:28:39 am by BoboJack »
Logged

Bumber

  • Bay Watcher
  • REMOVE KOBOLD
    • View Profile
Re: Add LRU caching to pathfinding.
« Reply #1 on: February 09, 2020, 05:12:02 am »
The time it takes to walk a path would be affected by the individual dwarf's move speed. Might not want to use that.
Logged
Quote from: Ispil on August 30, 2018, 01:17:08 pm
Reading his name would trigger it. Thinking of him would trigger it. No other circumstances would trigger it- it was strictly related to the concept of Bill Clinton entering the conscious mind.

THE xTROLL FUR SOCKx RUSE WAS A........... DISTACTION        the carp HAVE the wagon

A wizard has turned you into a wagon. This was inevitable (Y/y)?

BoboJack

  • Bay Watcher
    • View Profile
Re: Add LRU caching to pathfinding.
« Reply #2 on: February 10, 2020, 10:11:40 am »
Quote from: Bumber on February 09, 2020, 05:12:02 am
The time it takes to walk a path would be affected by the individual dwarf's move speed. Might not want to use that.

You can probably relate the time it took a dwarf to walk a path to the inherent length/weight of the path.
If you have a car going 100km/h at max speed along a 100km highway and it ends up needing 2 hours you'd unterstand something to be off.
« Last Edit: February 10, 2020, 10:27:03 am by BoboJack »
Logged

darkhog

  • Bay Watcher
  • JAGIELSKI is PERFECTION
    • View Profile
    • Jagielski Gaming YT channel
Re: Add LRU caching to pathfinding.
« Reply #3 on: February 11, 2020, 09:17:36 pm »
I can see how that would help, but how would you solve the problem of stuff getting in the way (e.g. tree that happened to grow in the path that is cached, or buildings that were ordered to be constructed)?
Logged
I am a dwarf and I'm digging a hole. Diggy Diggy hole, diggy diggy hole.

If I say something funny, don't ask if you can sig it. Just do it (though credit me).

BoboJack

  • Bay Watcher
    • View Profile
Re: Add LRU caching to pathfinding.
« Reply #4 on: February 12, 2020, 08:39:55 am »
Quote from: darkhog on February 11, 2020, 09:17:36 pm
I can see how that would help, but how would you solve the problem of stuff getting in the way (e.g. tree that happened to grow in the path that is cached, or buildings that were ordered to be constructed)?

You don't solve it. When a dwarf tries to walk a path and that doesn't work, you remove the path from the cache.
Then you search for a new path from wherever the dwarf is, to his goal.

The way it is now I think, is to let the dwarf search for a path, try it, if it doesn't work, try a new one. That's the same basically, just without a cache.
What I'm trying to say is that the same problem already exists, as the world can change while a dwarf walks.
« Last Edit: February 12, 2020, 08:45:17 am by BoboJack »
Logged