Print

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

[Granite26]

I'd rather see (Pie in the sky) the ability to write your own AI's, including pathfinding.

I'm just crazy though.

More practically,

I think the consensus is that any pathfinding optimization would need to reduce the total number of available nodes.  (Possibly by using doors to generate high level nodes and store those in memory while then using straightup pathfinding behind your door.)

[numerobis]

Oh, I see someone already mentioned path cacheing.

[Refar]

I think the consensus is that any pathfinding optimization would need to reduce the total number of available nodes.  (Possibly by using doors to generate high level nodes and store those in memory while then using straightup pathfinding behind your door.)

This seem to be the easiest thing - and can potentially have a lot of impact.

[sir monko]

boy, i'm drunk. i hope i did get all the answers.

my path caching idea ...

1)  ... has nothing to do with the ant approach of the thread starter. i probably should have started another thread, but ... whatever (i had the idea here as an anser/alternative (kind of "'ACO' is nice, but what about caching?")).

2) ... is nothing more than a simplyfied: if (a->b) was already computed, store it. if the same path needed again, reuse it. as soon as a dwarf runs into a block (because the map changed in between), recompute the graph or part of the graph. use some kind of age/rating based garbage collector

3) ... is pathfinding algorithm independed. i use a very simple flooding algorithm with no weighting, but the caching should work with weighted graphs too. my demo doesn't use z-levels, but there's almost not difference.

4) ... the demo is not optimized. there is no cache-size limitation, there is no reverse path recycling (a->b == b->a), there is no reuse of graphs in the neighborhood (a+-1 -> b+-1, should work for most a->b, because theres almost certainly no block between adjacent tiles), i don't do line-of-sight optimisations, ...

5) you could tweak the caching algorith a bit. e.g. instantly recompute the source path if the first dwarf runs into a block. then there would no dwarves running into walls (after the first one did). altough shortcuts would still be ignored until purging the aged paths.

6) there's no direct support for temporary blocks (other creatures that move, doors, drawbridges which change their state regulary). indirectly it does support it by rating the path (a path is purged only after a certain amount of dwarves running into blocks). optimizing pathfinding by communication between temporary blocks (moving creatures) is deadlock-prone (d1: "i'll move if you move!", d2: "me too")

7) path-finding wouldn't be "perfect" anymore (that is, dwarves wouldn't find the best path all the time). they'd make mistakes, as shown in my debug-output.

meh. waaaaay too drunk to think about all that. i love you all, man!

ps: (other replies been postet while i've been typing)

@draco18: the advantage of caching is: if there's memory for caching available, use it - if not, switch back to traditional atomic real time pathfinding. pre-computing every possinble path is too memory-intensive for DF.

@granite: don't pre-cache everything. cache the recently needed paths. there's a little look-up overhead, but nothing compared to recomputing the whole path all the time. if the cache is full, purge the least used.

pps: hangover now. never again dwarven ale!

[sir monko]

@granite 26: doors are build by humans. humans arrr unreliable.

line of sight is cheap. i mean, straight line of non-blocking walking path. so ... search for the points that cover most of the space by line of sight. those are the valuable nodes = the waypoints (aka "signs" other players request, though not set manually).

[korora]

Granite: That's what I get for not clicking on the links

benoit.hudson: That's what I get for not knowing the details

[Granite26]

@granite 26: doors are build by humans. humans arrr unreliable.

line of sight is cheap. i mean, straight line of non-blocking walking path. so ... search for the points that cover most of the space by line of sight. those are the valuable nodes = the waypoints (aka "signs" other players request, though not set manually).

I think you mean 'cover the most space' through line of sight, which isn't all that cheap.  Especially since, by your definition, all of the points in the grand hall would be 'waypoints', but the intersection of the two master hallways with the master staircase would only count if there aren't doors in the way or a crook in the path.

Separating zones by doors would take advantage of the fact that, by their very nature, doors exist to separate THIS SIDE from THAT SIDE, which is exactly what we're trying to do here.  (That is, separate the map into zones).

Could poorly placed doors cause problems?  Sure, of course they could.  OTOH, people already build their forts to minimize pathfinding difficulties.

[Granite26]

doors to separate zones, rough pseudo code.

Step 1:  Define initial zones.
 Start with a list of all points it is possible for a dwarf to stand on
 Start in the upper left hand side of the map. spot where the wagon embarked.  Find all points that connect to that point without going through a door.  This is zone 1.  (It is also 'outside', but that's another story)  Add every door you encounter to the door stack.
 Repeat this process until every outside point is covered.  (All of these points are 'outside' and any that don't link to doors are 'inaccessible')
 After all outside squares are covered:  For each door in the door stack, consider whether all sides (It's possible to have 4) have a zone #.  (one side is guaranteed to, or it wouldn't be in the stack).  If the side does not have a zone, create a new zone and calculate it, adding any doors to the door stack.
  When the door stack is cleared, any point without a zone is inaccessible to super-zone A.
  Repeat this process until every point is covered.  (Always start with outside points), creating new 'superzones' as need be.


Issues:
This could be sped up for dwarves and tame animals by only doing this for places dwarves can get to (calculate per dwarf rather than a random starting point.  Any points not considered after you finish the dwarves are 'inaccessible')  Make gobbos, etc, use brute force pathfinding (Or never spawn them in inaccessible places...)

When a map change is made, recalculate by assigning a zone to the new place based on whether more than one zone can be reached in less than 1 square (for digging), recalculating the entire zone (for trenches and other 'breaks'), or recalculating for a door.  This should be cheap to keep up.

Pathfinding:
Each door is now a node.  Store the pathfinding costs to each other door connected by a single node, and use a stored system to navigate.  When you need to pathfind, you'll A* path to your destination, only beyond your current zone and destination zone, you'll use the chart costs.  (This also means you'll ignore traffic in the hall until you get to it.)

[sir monko]

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

so, heres the code i used to create my sample output for path caching:

http://crew.tapirpirates.net/upload/PathFinder.rar

[Impaler[WrG]]

Though I don't really like the 'pheromone' concept as described by the original poster, I do like the idea that dwarfs would have 'knowledge' of the locations and paths between them and this knowledge would be fallible and learned.  The knowledge should be held IN THE DWARF, not only because its vastly more intuitive but its far more memory efficient. 

Each individual dwarf would maintain a list of stockpiles/workshops and map zones (not zones the player makes in game but the heuristic map zones described in the above posts) ware they 'think' things are located.  For example Urist thinks their is wood in Wood Stockpile #1 and #3 but he thinks theirs none in #2,  Pointers to stockpiles #1 and #3 are at the top of a Wood linked-list in his memory, #2 is at the bottom of list, he is unaware of the new #4 stockpile and it dose not appear on any of his lists.  As he moves around he might physically pass buy some wood thats not in a stockpile and their locations will get pushed onto a second wood list that holds temporary items, these get a time stamp which stockpiles also get along with the quality in the stockpile at that time   If he passes a stockpile that will also be inserted into his stockpile list, the more material in the stockpile the higher in the list its placed thus the largest stockpile will be at the top.  When ever he wants/needs a piece of wood he will check his memory and check paths to the top X number of items in the stockpile list (3 sounds descent) and run through the temporary list, old items get purged from the temp list but if some are fresh they get path checks too and weighed against the stockpiles.   He go's to the nearest source and  If he finds he was wrong and theirs nothing their he re-arranges the stockpile list or temp list (depending on which type it was) and tries again until he's either found the item or run completely out of locations to find it.

Now comes the fun part, if Urist is stumped and all the places he though would have items in fact don't then he will start 'Asking for Directions' from random dwarfs.  When dwarfs do this the Item lists of the two dwarfs sync-up.  Their lists are essentially merged with duplicate entries resolved based on who's time stamp was most recent, the merged list is now given to each dwarf, they each now knows what the other knows.  When dwarfs 'talk' in the meeting hall theirs a small chance that a 'ask for Directions' exchange happens and they will occasionally ask for Directions while in the process of following a path or before making a pathing search.  If after several attempts at asking Directions the dwarf will try the last resort which is to go to the Record Keepers office, any dwarf that speaks to the Record keeper or 'reads' his the table in his office (possibly a book once thats implemented) gets a perfect (maybe less perfect depending of the precision settings for the RK) list of the holds items.  Thus the Record Keeper helps to prevent things from becoming completely lost or disorganized a very appropriate function.  Other types of nobles might also have more narrow knowledge like the Captain of the Guard knowing all weapon and armor locations, if Guild masters come back they could know about craft specific materials.

One last things, I used wood in my example but their would of course be lists for a variety of materials like stone, blocks, armor, food and drink.  Some materials need more differentiation such as when a mason goes to get a block for a wall, he must bring back the correct kind.  In such instances the dwarf remembers a list for each kind of object.  To keep the memory footprint down a dwarf will only remember specific kinds of materials for their dominant profession, so a Mason will know ware the limestone and obsidian blocks are but non-masons will just remember them all as generic blocks and will have to check the location to see if it has what they really want.  Thus their will be an efficiency advantage for dwarfs skilled in a profession as they spend less time looking for stuff (seems logical enough).  The maximum memorable locations for a dwarf might also be determined by an Intelligence attribute if thats added to the game.

[Granite26]

The knowledge should be held IN THE DWARF, not only because its vastly more intuitive but its far more memory efficient. 

bwaaah?

[Refar]

doors to separate zones, rough pseudo code.

I think this is to simple - there are many possible worst case scenarios here - a fortress with no doors beeing just one of them.

"Zoning" in general is a good approach, but perhaps using just doors for it is not enought.

How about "Rectangle Cover" zoning:

- Cover all fortress with rectangles (As large as possible, but not habing obstracles in them) - this should be easy enought - start in one corner, graw rectangle as large ar possible, repeat for not covered areas.
- Create a adjacency graph on these rectangles (these directly connected are adjacent).
- Pathfind on that adjacency graph, to the nearest rectangle to your target (the one the target is in)
- Inside one rechtangle allways move straight towards target (be it the destination, or the next rectangle on th path) - since the rectangle is free of obstracles, this is safe
(+possible alterations to avoid traffic)

- If a new solid (potentially bloking) object is placed, only the rechtables it is in need to be updated (probably subdivided).
- On digging out new zones, try to extend existing rechtangles first, if impossible, cover with new ones.

Edit: Hi Impaler 

[catpaw]

Though I don't really like the 'pheromone' concept as described by the original poster, I do like the idea that dwarfs would have 'knowledge' of the locations and paths between them and this knowledge would be fallible and learned.  The knowledge should be held IN THE DWARF, not only because its vastly more intuitive but its far more memory efficient.

It maybe intuitive, and in maybe more CPU efficient, but tracking the spatial memory of every dwarf is sure everything but memory efficient.

[Draco18s]

The knowledge should be held IN THE DWARF, not only because its vastly more intuitive but its far more memory efficient. 

Because holding 200 different copies of known locations is less memory intensive than having a single Master List of all of them....

[Refar]

The knowledge should be held IN THE DWARF, not only because its vastly more intuitive but its far more memory efficient. 

Because holding 200 different copies of known locations is less memory intensive than having a single Master List of all of them...

I think the idea there was, that every dwarf would only hold memory on the locations he "needs" for his job. So say a farmer does not need to remember where these stone stockpiles are etc. If a dwarf need to go to a unexpected place he need to ask to direction (and will probably purge the memory soon after).

I am still not really convinced it would use less memory.
But it might be fun.

There are possible issues however - i am thinking mass hauling... It's no ones job, so no one does really know wher eto go...
Everyone is running around like mad...
Everyones nerves are tense, because everyone hates hauling anyway...
While asking for directions Ugdalf drops a bin with 6000 pounds of lead bars on Alrigs foot...
Alrig throws tantrum... Misses Ugdalf with his pick, but hits the Sherif instead...
A mass brawl breaks out...