Print

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

[Granite26]

I'll fall back on the fact that with the 3dwarf application (or whatever it is) we have access to any number of sample fortress maps to actually test these ideas on.  Anything else is just...  Fluff

[catpaw]

Granie26.... I'm not conviced, as I read some of Toadys posts, I don't know if its going really to be appreciated if we come up with the finished code (even without touching the original DF code at all). He seemed to be a little antagonistic when people came with very specific code things... But just my very humble impression that can easly be very wrong also. Just my impression as math-genius he wanted to figure out the details himself, not?

Also I guess coming up with a dwarven path learning algo in a static world is much easier than in a dynamic world... where the world just changes... we would have to simulate this changes as well (changing doors, digging new paths, cave-ins and the such)

[Granite26]

the impression I've always had is that giving up source code that you own and saying 'this is an example of what I think is a better way' is ok.  'Let me see your code', 'Allow me to write an API that I maintain' or 'let's work together' is not.

As far as the dynamic world issues, yeah... paths in DF change a LOT (compared to other algorithms)

[Draco18s]

As far as the dynamic world issues, yeah... paths in DF change a LOT (compared to other algorithms)

Calculating all the changes will take less CPU time than running paths for every dwarf and animal all the time.  Paths may change a lot, but they don't change at the same frequency that dwarves choose new jobs.

[Refar]

Also often multiple dwarfs will have similar - or the same/very similar path / destination - this is the case then hauling lots of stuff.

Anopther thing speaking in favour of a preashed data structure for pathfining is - the memoery usage of the game is not that bad now, as the frame rate drop on pathfining.

Something to concider is allowing the player to help out - be it by droping feromones or providing waypoints - if the player is allowed to do that, he can allwyas resolve really big problems (like lock ups or ridiculous-mass-bad-pathing) by hand.


BTW. Do the dwarfes ashe the path once coosen right now ? or do they run the pathfinding over again on each step...

Another related thing would be optimization of existing stuff without changing the basics... Like for example:
Why do caravans make the FPS drop ? These guys are not going no where, so why do they need to pathfind ?
Dwarfes working outside should not need pathfinding at all (which seem to have the worst impact right now) - they can just run towards the traget.

[Granite26]

I suppose the question then becomes how many paths will change when a dwarf does something, relative to the frequency of a dwarf pathfinding.

At the extreme answer, you could have the full fort staired out (every square is a stairs) except a wall up the center with one hole in the upper right hand side.  If you dig out a hole on the lower left, you will have to recalculate over half the map again.

The general case of digging is exploratory or new rooms, and in those cases, the pathfinding would stop at the closest choke point.  (Although digging a new 4x4 workshop room would still require 16 x 150*150*20 pathfinding operations.)

[sir monko]

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 shortcut
they 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

[Sukasa]

Pretty neat- Could you link us to the implementation or to the source so we can try as well?

At any rate, that's certainly a useful setup, 9:2 is an effective ratio.  Add into that the fact that you changed the path a couple times, and increase the lifetime limit a bit, plus factor in older fortresses which may not change their landscapes much at all once construction is finished, and you could probably get -much- higher efficiency ratios.

[sir monko]

i tweaked the cache-invalidating parameters (age, rating, in- and decrease of rating) not for good peformance, but for the demo. if you look at the output you'll see i don't do more hikes than needed for explaining a problem or the solution.

so, no parameter optimization. regarding the source code: please give me some time to fully comment the rest of the source code. i think i'll be done tomorrow.

[Sukasa]

Ah, okay.  Well, I see what you mean.  At any rate, my opinion stands, that's a very efficient system, at least on the 2D plane.

[Draco18s]

BTW. Do the dwarfes ashe the path once coosen right now ? or do they run the pathfinding over again on each step...

They don't call A* every step, that would be stupid.  From what I've gathered from postings by Toady in the past is that they calculate part of their path at a time.  The check to see if a path exists is a simple connectivity map (hash of what parts of the map are connected to each other by SOME path).  Then I assume some kind of function is called to find a block-path (i.e. the map is divided into blocks, if each one is consideredA* this) then the dwarf A*s inside his current block towards the next block.  He will re-path when he gets there or if he runs into an obstacle (such as another dwarf: he has to decided if laying down or taking another route is more efficient).  I assume that the algoritm doesn't path all the way to the edge of the block in this case, but rather attempts to and aborts when it cross back over the old path (such that it takes all of 2 or 3 steps of A* to get the dwarf to side step his pal going the other way).

[korora]

A while back I was pondering pathfinding as relates to DF, and I found that there exist (let me get the jargon right) dynamic all-pairs shortest-path algorithms; that is, algorithms that find every shortest path and update when the graph changes.  I'm not sure what the time complexity is and I have no idea what the implementation looks like (I found abstracts but no full papers), but it might be worth looking into.  I would expect that a) updating is better than recomputing every time and b) people publishing papers on the topic have probably got it pretty well optimized.

A particular advantage would be that you're pushing most of the computation to when you load the map, which is a pretty nice time to have it crunch things, and the rest of the computation will happen when the graph changes, which is almost definitely not when the user is interacting.  It's probably a large memory cost though.  If I recall correctly, one of the abstracts I read had various parameters that could be tweaked to improve CPU at the expense of RAM and vice versa.

[Granite26]

A while back I was pondering pathfinding as relates to DF, and I found that there exist (let me get the jargon right) dynamic all-pairs shortest-path algorithms; that is, algorithms that find every shortest path and update when the graph changes.  I'm not sure what the time complexity is and I have no idea what the implementation looks like (I found abstracts but no full papers), but it might be worth looking into.  I would expect that a) updating is better than recomputing every time and b) people publishing papers on the topic have probably got it pretty well optimized.

A particular advantage would be that you're pushing most of the computation to when you load the map, which is a pretty nice time to have it crunch things, and the rest of the computation will happen when the graph changes, which is almost definitely not when the user is interacting.  It's probably a large memory cost though.  If I recall correctly, one of the abstracts I read had various parameters that could be tweaked to improve CPU at the expense of RAM and vice versa.

Draco's proposal is an all pairs solution with each pair only storing the bare minimum information and it's still upwards of a GIG of ram just for the pathing information.  (Now add the ram for calculating pathing, and calculating flows, and etc,etc,etc)  Any algorithm is going to have to beat that hurdle first.

[Idiom]

Ant fortress?

Playing as any race is planned anyway. Don't see why a second system can't be added with an on/off option in the init.txt for player experimentation. Or for people with poor CPUs but lots of RAM, and vice versa.

[numerobis]

A while back I was pondering pathfinding as relates to DF, and I found that there exist (let me get the jargon right) dynamic all-pairs shortest-path algorithms; that is, algorithms that find every shortest path and update when the graph changes.  I'm not sure what the time complexity is and I have no idea what the implementation looks like (I found abstracts but no full papers), but it might be worth looking into.

Dynamic APSP is not really practical for something like DF.  I remember Mikkel Thorup being pretty happy about getting n^2.something update times a couple years back (SODA'05 workshop in New Orleans, a few months before Katrina), and there were a few papers by Demetrescu and one coauthor or another before then that had pretty similarly awful numbers -- just breaking n^3 was a big deal.  I doubt it's been improved a huge amount since.  So, every time you lock a door or tear out a ramp, you'd halt the game to run a worst-than-quadratic-time operation.  Your n is going to be every excavated square in your connected component; easily in the tens or hundreds of thousands.  You can do better by approximating, but approximate APSP had a big constant in the stretch last I checked: your path will "only" be three times as long as necessary.  Also, the queries get expensive and might be no better than just computing the path you need from scratch.


More practically, and with precisely zero effect on the asymptotics (but perhaps still useful), one could cache paths in some LRU buffer: just store <x/y/z> source and <x/y/z> dest, and the corresponding path; maybe keyed also by the creature type (since animals can't go through certain doors, etc).  Currently, every creature carries around one path; we could likely spare a couple megabytes of additional paths on top of that, and the lookup would be cheap (hash seven integers and do a table lookup).  We'd have to deal with our dwarves setting out paths that they should have known aren't optimal or just plain don't work anymore, but that might be OK (just plain doesn't work could be dealt by scanning the path before heading out on it; optimality, well, maybe it's OK if dwarves take a while to find the best path, just like ants would -- maybe every 20th time they use a path, they recompute it from scratch just to be sure).

The pheromones idea is intriguing, but the number of destinations can be pretty large, so I fear it would turn out to be a memory hog as the fortress grows.