Print

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

[czolus]

I've been assuming a diagonal weight of sqrt(2).  But its tune-able via constant.

[Footkerchief]

One open question I have, for Toady: what are the costs for cardinal (NESW), diagonal and vertical moves?

All are currently 1.

Good to know.  That can lead to some very interesting looking paths.

I just did some quick arena tests where I put identical creatures in pairs that were set apart by straight/diagonal paths of identical length, and then one-stepped until they reached each other.  The ones on the straight paths always reached the each other before the ones on the diagonal paths.

So moving diagonally is definitely slower than moving along a straight line.

Movement speed != the travel cost for the heuristic.

[astaldaran]

Maybe you have already considered this when thinking about multitile creatures but I just thought it might be important to mention that multitile creature support should probably be vertical as well as horizontal. True we have only had horizontal but Vertical would make since for things like Giants, etc.

It seems to me that it would have an added challenge because it would involve looking at multiple Z levels at once as opposed to simply pathing between Z levels.  I assume such creatures would be rare so perhaps the game wouldn't create the interesting points until such a creature actually entered the game.

[czolus]

Or, as multi-tile creatures are so rare, to allow them to A*.  Either way, what you do to calculate things for multi-tile critters is to use a moving mask of that critter---its quicker to retrofit into A*, and no information would have to be cached (like interesting points), since it is a very rare case at present.  If more critters (like, say, dragons) start to be multi-tile, then the effort-to-reward ratio means improving the algorithm becomes worthwhile.  The case of multi-z-level critters can be handled by the above "moving mask."

One open question I have, for Toady: what are the costs for cardinal (NESW), diagonal and vertical moves?

All are currently 1.

Good to know.  That can lead to some very interesting looking paths.

I just did some quick arena tests where I put identical creatures in pairs that were set apart by straight/diagonal paths of identical length, and then one-stepped until they reached each other.  The ones on the straight paths always reached the each other before the ones on the diagonal paths.

So moving diagonally is definitely slower than moving along a straight line.

Movement speed != the travel cost for the heuristic.

I'd expect the diagonal path (and I'm assuming that "identical length" means "identical number of tiles traversed") to take ~40% longer---or put another way, the actual distance traversed should be ~40% more than a cardinal (NESW) straight line. 

[klausw]

This thread reminds me of some experiments I was working on last year trying to make a fast "item finder" algorithm, where I was mainly focused on making trips between levels more efficient, or (where possible) avoid such trips if they are actually detours. I think this might potentially be useful to combine with other algorithms discussed here that mainly concentrate on making travel on 2D maps more efficient.

My goal was to help fix the old problem of dwarves choosing a target item that's below them on the next level, and then taking a huge detour to actually get there (and especially when walking past many other other items of the same type along the detour). It's based on a distance estimate heuristic intended as a replacement for the current 3D Manhattan distance that's apparently currently used for that purpose, while still being cheap enough to calculate when searching tens of thousands of candidates. That estimate can also be used as a distance heuristic for A* search.

The core idea is that the travel distance from point A to a point B on a different level has a lower bound of (distance from A to the closest stairs or ramp)+(levels between A and B)+(distance from B to the closest stairs or ramp), and that this number can be used as a cheap-to-calculate estimate when trying to choose a target among candidate items, without doing full pathfinding between them. It does this by saving a "distance to the closest level connection" lower bound value for each cell in the map, and updating that grid when the level connections change. These updates are fairly cheap to do, the changes don't need to propagate far to be useful as estimates.

Here's an interactive Javascript demo in case you want to experiment with it: http://pocketworkstation.org/ofinder/world.html

The demo's "Fortress" map has >10000 items, and it searches for the closest candidate(s) among them after each repositioning, intentionally done by a simple loop with no caching. You can select the heuristics used for target item selection and A* pathfinding separately:

• 3D distance: simple 3D distance between start and goal, ignoring stairs and walls, presumably as currently used by DF for target item selection.
• admissible stairs: check distance to stairs (ignoring stair direction) on the starting and ending level only. This is admissible for A* search.
• greedy stairs: sum level-to-level distance estimates for intermediate levels too, and check stair directions assuming a sequential start-to-goal level sequence. This isn't an admissible algorithm and can get confused for "express elevator" style maps, where the closest path going from A to a higher B might involve going down a level first to get to an otherwise-inaccessible direct staircase. But those should be rare for typical fortresses. The A* implementation I used tolerates an inadmissible algorithm, but it might not find the true shortest path in this case.

Let me know if you have questions or comments about this. I've tried to comment the "find.js" code to explain what it's doing, but please don't look too closely at the very hackish gui code ;-)

[Vattic]

Or, as multi-tile creatures are so rare, to allow them to A*.  Either way, what you do to calculate things for multi-tile critters is to use a moving mask of that critter---its quicker to retrofit into A*, and no information would have to be cached (like interesting points), since it is a very rare case at present.  If more critters (like, say, dragons) start to be multi-tile, then the effort-to-reward ratio means improving the algorithm becomes worthwhile.  The case of multi-z-level critters can be handled by the above "moving mask."

I brought them up because I've been lead to believe that Toady has shied away from them because they'd require too much pathfinding overhead. I wondered if this system could include them with less issues. Multi-tile entities should be becoming more common with things like siege engines.

[Forumite]

Iīm really liking where this thread is going. I just hope it will be implemented.

Quick question, when Traffic Designations are implemented, so that I can weigh each square and make dwarves avoid certain areas, would it be possible to add player-controlled points that are preferable to others, even if they take longer to walk to? This might be a way to control traffic without having to put weights on individual squares.

On that note, it might need a 5th set of important points, since traffic designations are generally ignored by invaders, they take the quick path, while my dwarves avoid areas I donīt want them to walk on, even though they all path using the set of land points. If players can designate points where they want dwarves to path to, then invaders could just ignore them, that might solve the problem.

[peskyninja]

Quick question, when Traffic Designations are implemented, so that I can weigh each square and make dwarves avoid certain areas, would it be possible to add player-controlled points that are preferable to others, even if they take longer to walk to?

They already are.