regarding path caching(...) but i will stop now, until i maybe got a demo implementation
so, here it is (the demo implementation/app) ... it's sluggy work, because it's done in java, and i haven't coded java for years.
the idea behind all this:
* dwarves will often use the same paths, so cache them and re-use them
* if a path becomes blocked or a shorter path becomes available, it takes them time to understand that
the cons:
* they'll find the perfect path (if there is one), if they're not using a cached one
* this is not a weighted graph (altought it wouldn't change the cache behaviour)
what i'm doing - in a nutshell - if a dwarf needs a path calculated:
1. find a cached path. if there is none, calculate a new one and put it in the cache
2. use that path. if its blocked, because the map changed in between, goto 1 (for the new position). also decrease the rating of that path
* if a path is too old or the rating is too low, purge it (so dwarfs discard blocked paths and learn new shortcuts)
here's a simple demo map
Demo-Map
################################
# # #
# O # X #
# #
# # #
# # #
# # #
# #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
... no, calculating a new path
################################
# # #
# ***********# * #
# ************ #
# # #
# # #
# # #
# #
################################
Block with a new wall, so the old path becomes unusable
################################
# # #
# O # X #
# # #
# # #
# # #
# # #
# #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 24.0/1.0, age 1
Path blocked, get new one
Searching for a cached path from 14|2 to 27|2
... no, calculating a new path
################################
# # #
# ***********# * #
# *# * #
# *# * #
# *# * #
# *# * #
# ******** #
################################
he bumps into a wall, so he gets a new path from his current position.
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 28.800001/0.8, age 2
Path blocked, get new one
Searching for a cached path from 14|2 to 27|2
Using a cached path with rating 18.0/1.0, age 1
################################
# # #
# ***********# * #
# *# * #
# *# * #
# *# * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 33.6/0.6, age 3
Path blocked, get new one
Searching for a cached path from 14|2 to 27|2
Using a cached path with rating 18.0/1.0, age 2
################################
# # #
# ***********# * #
# *# * #
# *# * #
# *# * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 38.399998/0.40000004, age 4
Path blocked, get new one
Searching for a cached path from 14|2 to 27|2
Using a cached path with rating 18.0/1.0, age 3
################################
# # #
# ***********# * #
# *# * #
# *# * #
# *# * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 43.199997/0.20000003, age 5
Path blocked, get new one
Searching for a cached path from 14|2 to 27|2
Using a cached path with rating 18.0/1.0, age 4
################################
# # #
# ***********# * #
# *# * #
# *# * #
# *# * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 48.0/2.9802322E-8, age 6
Path blocked, get new one
Searching for a cached path from 14|2 to 27|2
Using a cached path with rating 18.0/1.0, age 5
################################
# # #
# ***********# * #
# *# * #
# *# * #
# *# * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
... no, calculating a new path
################################
# # #
# ******* # * #
# * # * #
# * # * #
# * # * #
# *# * #
# ******** #
################################
wowzer, the blocked path's rating is too low (2.9E-8, so almost zero), so they now use the optimal new one!
the low-rated path will be purged as soon the garbage collector is called the next time (all 3 cache accesses)
Remove a wall, creating a shortcutthey won't use the shortcut for a time, because they have a valid one cached
################################
# #
# O # X #
# # #
# # #
# # #
# # #
# #
################################
==New hike==
GC: removing path 4|2->27|2 - rating too low
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 24.0/1.0, age 1
################################
# #
# ******* # * #
# * # * #
# * # * #
# * # * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 24.0/1.0, age 2
################################
# #
# ******* # * #
# * # * #
# * # * #
# * # * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 24.0/1.0, age 3
################################
# #
# ******* # * #
# * # * #
# * # * #
# * # * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 24.0/1.0, age 4
################################
# #
# ******* # * #
# * # * #
# * # * #
# * # * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 24.0/1.0, age 5
################################
# #
# ******* # * #
# * # * #
# * # * #
# * # * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 24.0/1.0, age 6
################################
# #
# ******* # * #
# * # * #
# * # * #
# * # * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 24.0/1.0, age 7
################################
# #
# ******* # * #
# * # * #
# * # * #
# * # * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 24.0/1.0, age 8
################################
# #
# ******* # * #
# * # * #
# * # * #
# * # * #
# *# * #
# ******** #
################################
==New hike==
Searching for a cached path from 4|2 to 27|2
Using a cached path with rating 24.0/1.0, age 9
################################
# #
# ******* # * #
# * # * #
# * # * #
# * # * #
# *# * #
# ******** #
################################
==New hike==
GC: removing path 4|2->27|2 - too old
Searching for a cached path from 4|2 to 27|2
... no, calculating a new path
################################
# ************ #
# ***********# * #
# # #
# # #
# # #
# # #
# #
################################
yay! the old path died of old age, so they're replacing it with a new one that uses the shortcut.
Total walks done: 18
Total paths calculated: 4
Bye
i hope you don't mind the printout of all the steps between the significant ones, but without them it wouldn't understandable.
if someone wants the source code, drop me a line (warning: ugly code!). also, it's not optimized.
edit:
in sum, 4 paths were cached.
their size depends on their length (simplyfied):
* rating and age per path (1 float, one int) + path length * 2 integers