1) you sounded pretty condescending.
Thanks:)
I have finished implementing a version of a* pathfinder that can find a single path from opposite corner of a 300^3 cube in about 5ms - on one thread. 5 threads(my rig has 6 cores) running simultaneously reduce the speed to 6-7ms, so the worst case scenario with this map size(6x6 embark) is about ~ 1.2 ms per path.
I know that it's not great, but it's a first time I've done path finding of any kind and there is still some room for optimisation:
a) I don't have a very efficient implementation of a double-linked list for maintaining sort order of F in A* open list at the moment and seek times in closed/open lists are not great.
b) still testing the appropriate heuristic functions for calculating the H value. Manhattan is ok. Diagonal a bit better, but I haven't turned on the area restrictions yet (variable G for a step) - this will change H - G balance and will need to rerun all the tests with these on. Also need to implement that Quake fast sqrt for Euclidian and see if it fares any better.
c) I have some problems maintaining a very large map in the memory, I have implemented a partitioned sparse vector (index = x + y<<10 + z<<20, partition = index/((maxindex/partitionCount +1))) for holding the data, but it will need more improvements before I can realistically maintain the maximum size local area map ( (48*16)^3). Good thing is that random and neighbouring cell access is very fast.
Now its time to do the caching. There is no reason to recalculate paths all the time. I will reuse as much of the pre-calculated paths as possible. Path calculation will also use the cache, so if its gets to a point where the path can be completed with a pre-cached one it will do so.
Next steps
caching
a) Cache full path and all its subcomponents. Idea is that entities will reuse cached paths. Paths will be cached with the usability flags (flier, walker, jumper, climber) so a dwarf wouldn't try take the same one an eagle does.
b) Invalidate cached paths when a set amount of ticks have elapsed (f(path length) - longer paths decay faster). Probably read repair consistency check, unless memory or seek times prove problematic.
c) Invalidate paths on node and adjacent node update. Path should be invalidated when a node on it becomes unpassable/passable. It won't account for a shorter route suddenly becoming available, but those will be taken care by tick based invalidation unless I think of something better. Async repair.
d) Entity movement feedback - should entity find that path can't be followed any more, the path will be cleared from cache. Write/Async repair.
visualiser/simulator
Simple visualiser for simulating movement of entities on a map.
df hookup step 1 - live map data from df
a) Will likely expose the map from dfhack via a memory mapped file for start.
b) map block update events tied into the path cache to invalidate calculated paths where appropriate.
df hookup step 2
h2xor DF to
a) change the pathfinding loop to wait for paths from the external pathfinder <-Will need help with this one.
b) give feedback on the path (entity can't use path/completed the path, etc.)
future
local avoidance
fast checks for a 3-step path bypassing the node blocked by another entity.
right-of-way
nobles newer give way to others
dwarf might elect to wait a tick or 2 if way is blocked
pets might be kicked aside
climbing
nimble dwarves who don't carry stuff might climb a zlevel
jumping
nimble dwarves not carrying crap might jump down a zlevel
swimming
swimmers will go through deep water