Print

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

[Ogantai]

Consider the following:

1 dwarf with Item Hauling enabled at point A.
Pile of 10 objects to be stored at B.
Stockpile at C.

The dwarf with Store item in stockpile job starts out at location A, paths A->B, then B->C, then must recalculate routes C->B and B->C 9 more times to complete the hauling.

Considering that A* is O(nⁿ) in a worst-case scenario, the less pathfinding DF has to do the better. Instead, why not have the dwarf cache the precalculated B->C route, then instead of pathfinding C->B just reverse the route to arrive where he started, cache that, then repeat B->C and C->B from cache until done? That reduces the number of graph searches that must be done from 20 from 2. Perhaps store the last p routes in cache, let all dwarves share a common cache, and have then test if their prospective routes share endpoints within s squares (probably 1-2) of routes already in the cache. That reduces a potentially cpu-intensive 500 square long path calculation from the the armor stockpile to the xX(Pigtail Sock)Xx that Urist dropped to a much simpler calculation from the precached route's endpoint at xX(Pigtail Left Glove)Xx to the square adjacent to it.

Obviously the values of s and p will have to be tweaked (just let us set them in the init file) but this would really reduce the strain DF places on lower-end computers with high pop fortresses.

[Andir]

It's just a method of reducing CPU load by using memory.  He could just make each path an object array of points (from endpoint to endpoint) give it a lifetime to be deleted, a slightly lower travel cost and optimize the path finding algorithm to "jump" to the end of each route assigned to a tile. I think this would alleviate some of the overhead of path finding, promote "common" trails and overall complicate the poor thing.  He may already be doing some of this as well.

[Ogantai]

It's just a method of reducing CPU load by using memory. 

Yep, but it's easier (and cheaper) to add more memory than to upgrade the cpu (in most cases). 

Edit: Don't forget that running A* isn't exactly easy on memory either; compared to RBFS it's a pig. Given a sufficiently large fortress (both in area and in population) a route table would actually reduce average memory usage.

[scribbler]

I had suggested, while discussing something else, that DF run basic pathfinding for a set of locations based on use, landmarks (workshops, etc.) or arbitrary grid coordinates, such as every 16 squares. A dwarf would only have to path to and from this main route and updating it for traffic changes, tunnels etc, could be done in the background, like while giving orders or trading. Just assume any delay in using the new bridge is word getting around that it's done.
Once everything is caught up, extra CPU time (small forts, long trades, etc.) could be used to double check the route tables based on route usage/density or oldest calculated (just in case something was overlooked in calculating or updating).

[Footkerchief]

I had suggested, while discussing something else, that DF run basic pathfinding for a set of locations based on use, landmarks (workshops, etc.) or arbitrary grid coordinates, such as every 16 squares. A dwarf would only have to path to and from this main route and updating it for traffic changes, tunnels etc, could be done in the background, like while giving orders or trading. Just assume any delay in using the new bridge is word getting around that it's done.
Once everything is caught up, extra CPU time (small forts, long trades, etc.) could be used to double check the route tables based on route usage/density or oldest calculated (just in case something was overlooked in calculating or updating).

This would also have the cool side benefit of having dwarves follow habitual "trails," much like people do in real life.

[eerr]

what about wide open spaces?

[Mondark]

This would also have the cool side benefit of having dwarves follow habitual "trails," much like people do in real life.

Well, to some degree, they already do, as some paths are always the best way to go.  You can see this in an frequently traveled outdoor area, the grass turns reddish brown along the path, if it gets stepped on enough.

[Ogantai]

I had suggested, while discussing something else, that DF run basic pathfinding for a set of locations based on use, landmarks (workshops, etc.) or arbitrary grid coordinates, such as every 16 squares. A dwarf would only have to path to and from this main route and updating it for traffic changes, tunnels etc, could be done in the background, like while giving orders or trading. Just assume any delay in using the new bridge is word getting around that it's done.
Once everything is caught up, extra CPU time (small forts, long trades, etc.) could be used to double check the route tables based on route usage/density or oldest calculated (just in case something was overlooked in calculating or updating).

This would also have the cool side benefit of having dwarves follow habitual "trails," much like people do in real life.

It would be even better if we could designate those trails manually. Kind of a "Dwarves on Rails" idea, where I could specify a route from my crafter's workshop to my finished goods stockpile, and have DF keep in cache persistently.

[Footkerchief]

This would also have the cool side benefit of having dwarves follow habitual "trails," much like people do in real life.

Well, to some degree, they already do, as some paths are always the best way to go.  You can see this in an frequently traveled outdoor area, the grass turns reddish brown along the path, if it gets stepped on enough.

Yeah, I think that's more an artifact of the pathfinding though -- they seem to prefer long sections of diagonal and orthogonal travel to straight-line approximations, if that makes any sense.

[Warlord255]

Abstracting out a bit;

Due to the nature of fortress arrangement, a cached route would be harder to do because the route constantly changes.

[Ogantai]

Abstracting out a bit;

Due to the nature of fortress arrangement, a cached route would be harder to do because the route constantly changes.

That's why you store the last n used routes. If the route changes, the old route gets dropped from the table and the new one gets put in.

[sir monko]

path caching: http://www.bay12games.com/forum/index.php?topic=24790.0

[scribbler]

It would be even better if we could designate those trails manually. Kind of a "Dwarves on Rails" idea, where I could specify a route from my crafter's workshop to my finished goods stockpile, and have DF keep in cache persistently.

Well, you can designate high traffic areas, a route cache would make more use of them.

Yeah, I think that's more an artifact of the pathfinding though -- they seem to prefer long sections of diagonal and orthogonal travel to straight-line approximations, if that makes any sense.

Yeah, the way math works out moving diagonally 10 squares is half the steps without diagonals and covers 14.14 squares distance. So, most programs favor thew diagonals.

Abstracting out a bit;

Due to the nature of fortress arrangement, a cached route would be harder to do because the route constantly changes.

That's why you store the last n used routes. If the route changes, the old route gets dropped from the table and the new one gets put in.

I'm advocating sectioning the areas so that routes would be recalculated when there was some construction or traffic change in the areas they travelled.
There's probably some helpful math based on the fact that most of the map space isn't really used or at least relevant to most pathing and so on but I'm tired and I'd rather leave that discussion to those more interested in it. Maybe they can use my ideas and come up with some useful algorithms for Toady.

[Ogantai]

It would be even better if we could designate those trails manually. Kind of a "Dwarves on Rails" idea, where I could specify a route from my crafter's workshop to my finished goods stockpile, and have DF keep in cache persistently.

Well, you can designate high traffic areas, a route cache would make more use of them.

That wouldn't do anything to reduce CPU usage though. Designating traffic areas just weights the graph, it still calculates paths the same way.

[TrombonistAndrew]

There has been lots of research along these lines by professionals finding good algorithms to solve the travelling salesman problem.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

Particularly interesting solutions include the any colony optimization (usable in DF), and the TSP discussion toward the bottom of the page. There are also some genetically based algorithms not specifically listed on wiki. Granted, this isn't exactly the same problem, as the travelling salesman problem is with connecting multiple points via the shortest path, and pathfinding in DF is just connecting two points, but the tile-based structure of DF makes the problem fairly similar.