Print

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

[sir monko]

I think the caching tradional complete path searches is a problem, since everytime you dig through a tile, or lock/unlock a door, raise/lower a bridge the complete cache would have to be deleted... which happens almost constantly at a DF:.. unless you life with the fact that a dwarf starts running a known path, altough it is blocked now, and only stop to recalculate a new path when hindered. Or if a new shortened way is opened up, the dwarves will continue to run the long cached patch, until it times out after a quite long time...

you're part right. but there the rating comes into play: a blocked path would loose rating fast and if it's low enough, it is purged. say the rating is 1, every blocked dwarf decreses it by .1, it is purged when 0. it would take 10 dwarfs running into the block before the path is completely purged. if the block is a door and it's reopening (while the rating is > 0), the paths rating would go up again (up to a max of, say, 2). also, if the rating is 0.1, the chance of a dwarf choosing a different path with a better rating in the first place is high enough.

also, a patch to point 1 (picking a path) - the cached path mustn't exactly be starting and stopping exactly where you are and want to go, but must be a superset of the path you wanted. this introduces another problem, but i will stop now, until i maybe got a demo implementation

[catpaw]

Draco, had already mentioned that algorithmn in OP Note the explicitl word of "most" not all "all". When entering a maze It might not get you to the target, but it will always get you at least out again (as long there arent super evil things inside, like teleporters or moving walls)

How could this alternatively work, without having dwarf run around like crazy lost roboters (like the old follow the left wall algorithmn that will get you out of almost every maze)

Yes, this simple algorithm can fail on mazes with braidiness.

There are however ones that will also go through your maze, however it requires a chalk you can draw lines on the floor with

This Maze solving method is designed to be able to be used by a human inside of the Maze. It's similar to the recursive backtracker and will find a solution for all Mazes: As you walk down a passage, draw a line behind you to mark your path. When you hit a dead end turn around and go back the way you came. When you encounter a junction you haven't visited before, pick a new passage at random. If you're walking down a new passage and encounter a junction you have visited before, treat it like a dead end and go back the way you came. (That last step is the key which prevents you from going around in circles or missing passages in braid Mazes.) If walking down a passage you have visited before (i.e. marked once) and you encounter a junction, take any new passage if one is available, otherwise take an old passage (i.e. one you've marked once). All passages will either be empty, meaning you haven't visited it yet, marked once, meaning you've gone down it exactly once, or marked twice, meaning you've gone down it and were forced to backtrack in the opposite direction. When you finally reach the solution, paths marked exactly once will indicate a direct way back to the start. If the Maze has no solution, you'll find yourself back at the start with all passages marked twice.

http://www.astrolog.org/labyrnth/algrithm.htm is a great ressource regarding mazes... However it would make every dwarf run around like crazy, and theyd never get anything done!

[Star Weaver]

I've been thinking about this too, since I'm trying to figure out how to work with a lot more tiles / cubes per area than DF uses.

Right now I'm thinking a loose graph of Unreal-like pathnodes to represent roads / hallways / corridors of civlilzed areas. Just keep them in the halls and junctions.

Every once in a while, tag each major resource (workshop, stockpile, zone) with it's nearest graph node.

Dwarf thinks he wants to go to his current position X to building Y, so he finds his nearest graph node A, does normal pathfinding to it, looks up Y's nearest node, graph-finds to it, and does normal pathfinding to the end. X -> A -> B -> Y.

Like highways.

Off-the-beaten path stuff (like draco's ore) and misplaced items wouldn't be stored, they would just be normal-pathfound or have their nearest node grabbed when requested.

How to cacluate the grid for this in DF automatically I have no idea; it probably requires at least user tweaking.

This may equate to something someone's said already, but I wanted to get it out of my brane right away .

[Vicomt]

Urist McNewbyMason cancels Construct Rock Blocks - asking for directions
Urist McGreeter suspends Whatever He's Doing - giving directions to Urist McNewbyMason
Urist McGreeter resumes Whatever He's Doing

I actually dislike dorfs having a full inbuilt knowledge of where everything is, I'd really like the pathfinding to be some kind of learnt behaviour, like using one of the above mentioned maze algorithms to find a path for the first time, then being able to pass that path information on to other dorfs, and having to adapt and relearn whenever things change.

Now that's a project I'd love to get my teeth into....

[Draco18s]

Draco, had already mentioned that algorithmn in OP Note the explicitl word of "most" not all "all". When entering a maze It might not get you to the target, but it will always get you at least out again (as long there arent super evil things inside, like teleporters or moving walls)

I was being somewhat silly.

[catpaw]

But I wanted to get it out of my brane right away .

I like that attitute. Well after all, it just depends what might fancy the one dev with the code to look/develop into it. We can just dump out our ideas to be picked up or dumped. And I think we are doing quite well

[Granite26]

Going to be a little silly here:

IIRC, each tile is 48x48, and each area has about 20 z levels.  That's 150x150x40* int(s)** to determine a normal map.  25 megs of memory to store the entire (pathfinding) map at 32byte integers.***

At most, on any given turn, 600**** squares are going to change their state, so it's easier to track state CHANGES than the path.

We've already got an application that reads the layout of the map and converts it.  (AKA we can get that 25 meg pathmap out.)  If anyone wants to design something that converts the whole map into the object described and feed it into an API that takes the map, takes updates, and responds to path requests, we could change out the Pathfinding API and actually check the speed of some of these pathfinding suggestions on real maps.

Personally, I think that the A* is going to be the best non-learning algorithm we can get, although cacheing paths between common choke points (similar to Star Weaver's method) would be a cheap learning algorithm.

I was also thinking that the outside is usually very different from the inside, and pathing to the closest door might save a lot of costs for gobbos and woodcutters.

*Need to track Ceilings vs Open vs Stairs between z-levels.
** Need to track Open vs Closed vs Increased Costs (discouraged areas)
*** REALLY rough numbers, don't bother to correct me if that's all you're going to do.  It doesn't matter.
**** Digs, builds, doors changing state, player value changes (forbids).  I'm assuming that the player isn't flipping all the doors in the fort or laying down massive new discouraged areas on a regular basis.  Ignoring player actions, 200 Up/Down Stairs would affect 600 tiles

[Draco18s]

There might be a better option, but I've forgotten what it's called, it's supposed to be good for non-dynamic maps because it precalculates every possible path before hand.  It might work here, because even though we're doing a lot of state changing, we're effecting mostly individual nodes at a time and typically once changed, don't change again (there might be as many as 4 changes in some places on certain fort maps, but for the most part most forts settle down and don't see a whole lot of change).

Ah ha!  Found it again:
http://www.electrotank.com/junk/mike/ai/precomputedPathTutorial.html
Here's a thread:
http://board.flashkit.com/board/showthread.php?threadid=525292
And here's some kind of page that I dug up looking that looks related to how he implemented it, even goes into dynamic worlds:
http://www.gamedev.net/reference/programming/features/precalcpath/

[Granite26]

Path table for a 150*150*20 map would be...  202 Billion entries, Assuming you dug out the whole map as a floor.

Still, if you take out the sky and digging tiles, it's going to be something like a gig of memory for the whole map...

[Draco18s]

it's going to be something like a gig of memory for the whole map...

Heh.  Always has been CPU or RAM...

[Nadaka]

I think signposts are the way to go.

Signposts can be placed  by hand for custom path-finding or they can be placed by the AI in best guess locations.

To find a path between two distant locations, the path to the nearest signpost is calculated, the path from that signpost to the the signpost nearest the destination is calculated, and finally the path from that signpost to the destination is calculated. Each signpost can pre-calculate and store the best paths between it and several adjacent signposts (possibly even all signposts).

This would not give the best path under all situations, but it would very often give a very good path while also using a very small amount of CPU and memory.

[Granite26]

I think you're right, but the signposts themselves are just a physical artifact representing chokepoints. 

No reason to physically make them if you've got a good heuristic function for deciding where they would be.

[The-Moon]

Did anyone read what i said.

Or was i so tired at the time i didn't get out what i was trying to say?

I just explained how to make path finding as fast as possible and no one responds...

[Granite26]

Did anyone read what i said.

Or was i so tired at the time i didn't get out what i was trying to say?

I just explained how to make path finding as fast as possible and no one responds...

tl/dr...

(Seriously, it's a poorly formatted wall of text that makes it difficult to focus on what you're actually trying to say.  I don't think you're wrong, though)

[Yourself]

I think you're right, but the signposts themselves are just a physical artifact representing chokepoints. 

That is the tiles that all dwarves pass over the most.  That might be a suitable metric for having the machine decide the placement of these waypoints.

@The-Moon:

Just to add on. The current path finding system would stay in place with myidea. But however, the current path finding system would be the last resort for a dwarf trying to get some wheres. The dwarf would first check the set traffic zones, before it trys to get to its destination with the current pathfinding system.

And therein lies your problem.  You have not described how one would determine if one of these pre-defined paths is actually valid.  It sounds like you'd have to use the old method of pathfinding to determine whether or not to fall back on the old method of pathfinding.  Needless to say, that'd be dumb.

Your entire idea is far too vague to be useful, let alone practical.  You only waved your hands over the concept of traffic zones and stated nothing about the actual data structures and algorithms which would be necessary for such an implementation.

It seems one of the general ideas here is a kind of hierarchical pathfinding where the fortress is abstracted into a more general graph with paths between nodes cached for efficiency.  Then the same A* algorithm can be applied to that graph and since it has fewer nodes and is less complex than your fortress alone less time is spent computing the path.  The difficult part is getting this abstract representation.  It's possibly an idea worth pursuing since it may not require too huge of a change to DF.