Print

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

[Starver]

how are you going to optimize pathfinding based on room definitions in Adventure mode?

• Actually have useful-to-the-Adventurer room definitions
• ? ? ?
• PROFIT!

[Shades]

I'm of the opinion we just pass room defines and any square low / normal / high / avoid traffic settings as flags along with everything else. Algorithms that want to use them can and others can ignore them. Adventure mode can deal with that when the concept of rooms is more ingrained into DF.

This probably means we will end up with separate routing algorithms for dwarfs in fortress / other things in fortress / adventure mode as the latter two won't need traffic designations.

[Sunken]

I think we must keep all channels open when it comes to the number of movement types we can deal with. We don't just have to cope with walkers, fliers, swimmers, jumpers, water walkers and lava-resistant creatures, but actually with a potentially infinite set. Pathing doesn't care whether a space is untraversable because it is impassable to the creature, or because it is passable but otherwise forbidden by the AI.

For example, we have the pets-and-doors issue, but in general this may be much more complex: different castes of creature may be allowed through different sets of doors (guards, workers, guests, nobles, the owner of a given room).
Then there's the issue of knowledge of spaces - an invader might not be allowed to path through spaces he doesn't know about.
Then there's traffic limitations - "dwarfs don't go outdoors", "absolutely forbidden zones" and other player-imposed restrictions, possibly applying differently to different agents.
Also, you might envision situation-dependent limitations - disallowing civilian dwarfs from moving through "enemy held territory", automatically maintained (rather than user-specified in detail).

What all this adds up to, I think, is that each path search is in principle unique, and we should have a system that permits arbitrary limitations to be placed on any individual path search. A path request could be as general as:
"Find a way from tile A to any tile with a limestone block; staying indoors at all times; going through no restricted doors except my personal room; walking, or jumping down no more than 1 z-level at a time; staying out of dangerous areas"

It's not as hard as it sounds, in principle: as has been stated already, A* can do all this - we just place custom limitations on which search nodes we are allowed to open. Whatever zone types we choose need to be annotated with the data we use for the limitations, naturally, but that will be obvious once we get there.

The tricky bit is that A* needs a connectivity map to be efficient. We can't maintain a connectivity map for each such custom request so we must find some way of cache the most commonly used ones, and compute an exact or approximate variation of the connectivity map when a special path request needs it. Requests for unusual restrictions are just that - unusual, so maybe we can get by with a flood fill every time for them. The more common ones ("general indoor worker dwarf walking through any unlocked door") will stay cached and updated constantly.
It's not a trivial problem but should be possible to solve, and with big dividends.

Finding good heuristics will be another challenge.

[Shades]

Paths allowance and goal states can easily be a function of what calls the path finder rather than the path finder itself, assuming we can reduce the map to a set of restrictions.

Some restrictions are obviously more complicated than others, or at least require more game world knowledge. Enemy held territory is open to interpretation for example, further more how would a dwarf starting on a path even know that the last few squares where held by the enemy. (Of course you could argue it's the same way they know a sock is laying there waiting for an owner )

We could use a simplistic decorator like pattern to allow fairly arbitrary comparissions, as long as it's all inline and templated it will be a minimal although possibly significant overhead.

I would recommend sticking to the basic bit array for things like magma and water and looking into expanding it if and when it's required. As long as the check functions are isolated and well tested its easy to refactor and the basic system should allow duplication of the DF system without overly complicating the problem.

[Slogo]

I agree, some designations like Burrow are beyond the scope of path finding. It's the goal selection process that's going to determine if something is in the right burrow to be worked on.

Designations like Indoor/Outdoor could also be solved easily if we use a Type->Subtype allowance flag system like I described earlier. If a creature is designated to only be allowed indoors then they can check the sub tile of any tiles during A* to see if its of a valid type much like they might with water or magma.

[Sunken]

I would recommend sticking to the basic bit array for things like magma and water and looking into expanding it if and when it's required. As long as the check functions are isolated and well tested its easy to refactor and the basic system should allow duplication of the DF system without overly complicating the problem.

Quite, but it's important to remember not to circumscribe ourselves while coding. No optimizations based on the knowledge that capabilities will be bitmasks of a certain size! No optimizations based on the knowledge that the goal is a single tile!

[Shades]

Designations like Indoor/Outdoor could also be solved easily if we use a Type->Subtype allowance flag system like I described earlier.

To be honest you only need a single flag for indoor/outdoor as it's one or the other, but I agree it should be in the list of flags.

Blocked - Non Construction (tree/wall etc), Construction (for building destroyers), Indoor, Water, Magma, Pet Passable, Room (of any kind, probably don't need to specify), Restricted Traffic, Low Traffic, High Traffic, Open (for fliers)

Nothing else springs to mind, but it's getting on in the day and my brain is shutting down.

Traffic could be combined but the list I put is all single flags as it is.

Quite, but it's important to remember not to circumscribe ourselves while coding. No optimizations based on the knowledge that capabilities will be bitmasks of a certain size! No optimizations based on the knowledge that the goal is a single tile!

Agreed, I would say that the only 'flags' requirement is that it supports the array operator and the goal is based on some goal state comparison passed into the function (probably a comparator that can be in-lined away during compile)

[Sunken]

Designations like Indoor/Outdoor could also be solved easily if we use a Type->Subtype allowance flag system like I described earlier. If a creature is designated to only be allowed indoors then they can check the sub tile of any tiles during A* to see if its of a valid type much like they might with water or magma.

More importantly, subtyping can make for efficient representation of the connectivity map. For example, a dwarf with access to a certain room is also a dwarf with general dwarf access; thus, if a goal is reachable in the general-access connectivity map he doesn't need to check (or create) a connectivity map that uses his special room.

[Shades]

I may have misunderstood what you meant by type->subtype then. I was assuming flags on squares to generate zones of the same flag set (which might mean some single square zones like a door) which is then used in path finding

[Jifodus]

I remembered something, that may point to an obvious inefficiency in the current code. The normal traffic weight for an open space is two. Experiments have demonstrated that reducing the normal weight on the entire map down to one produces a marked benefit in terms of frames per second, as dwarfs manage to determine paths faster.

This only happened if you manually overrode the weights in your fortress because it would tell DF to ignore the exterior of the fortress until you've fully explored the interior of the fortress.  Since for the most part, the interior of the fortress is smaller than the exterior.

By extension, you can influence path finding by placing walls of restricted areas based on if a section of the fortress or for a single room rarely needs to be accessed.  In addition, by using low traffic along major hallways will also help.

These optimizations unfortunately don't help when building something, because it appears that it explores the entire map regardless.

Relying on player hints for zones is a bad road to go down. It means that the library we write isn't a 3d tile based path finding algorithm but instead a pathfinding algorithm specifically for dwarf fortress. You can't expect every use of the path finding library to be Dwarf Fortress, even if its requirements are the driving force behind the design.
Objects like doors should naturally be along any hierarchy divisions. Not because there's a door there but because it's a narrow chokepoint giving us a well defined region with limited routes to neighboring regions.

How would adding player hints make it specifically for Dwarf Fortress?

It's just a point of interest, the path finding algorithm can use it or ignore it.  Most games use waypoint navigation, however, players don't usually see it.  I would've suggested using area navigation (which is essentially the same concept as TCZ's), but it would've been pointless since DF uses discreet areas and it would only useful for hallways larger than 3 tiles wide.

The tricky bit is that A* needs a connectivity map to be efficient. We can't maintain a connectivity map for each such custom request so we must find some way of cache the most commonly used ones, and compute an exact or approximate variation of the connectivity map when a special path request needs it. Requests for unusual restrictions are just that - unusual, so maybe we can get by with a flood fill every time for them. The more common ones ("general indoor worker dwarf walking through any unlocked door") will stay cached and updated constantly.
It's not a trivial problem but should be possible to solve, and with big dividends.

Thank you for the clarification.  Most of what I could got from all the previous posts was that "We'll optimize the algorithm," which didn't make any sense since A* is already optimal assuming that the heuristic is >= actual cost.  I still would like to know though, what is the algorithm are you planning on using to discover areas, since an idea is one thing, but an implementation is something else.

[Shades]

Thank you for the clarification.  Most of what I could got from all the previous posts was that "We'll optimize the algorithm," which didn't make any sense since A* is already optimal assuming that the heuristic is >= actual cost.  I still would like to know though, what is the algorithm are you planning on using to discover areas, since an idea is one thing, but an implementation is something else.

I was assuming something that acted like a flood fill to find the zones and something that used an A* walker to find the route. However part of the point is to abstract out the algorithms so people can drop in custom ones that might work better for our specialised situation (grid based map for example). If you prefer to think of it as way point navigation then each zone is a way-point and it is connected to all adjacent zones.

[Silverionmox]

Relying on player hints for zones is a bad road to go down. It means that the library we write isn't a 3d tile based path finding algorithm but instead a pathfinding algorithm specifically for dwarf fortress. You can't expect every use of the path finding library to be Dwarf Fortress, even if its requirements are the driving force behind the design.

Designing the Universal 3d Based Path Finding Algorithm might be a little too ambitious. If that's the goal, a lot more factors will have to be taken into account and as a result the project will become larger and less focused. That requires more work, more persons involved, more coordination and all that for less tangible and slower improvement in DF. If recruiting happens elsewhere too, fine. If it doesn't, the project will flounder due to overextension. I think it's better to develop a library primarily useful for DF, that's also useful for other projects, rather than a universal library that might also be useful for DF.

Well obviously that's why we're keeping it focused on Dwarf Fortress, I just don't think we should rely on things ultimately DF specific so the game can keep a broader application to other tile based rogue-ish games.

For example doors, or more generally dynamic open/shut tiles (in DF's case this would also mean floodgates, bridges and hatches) are a good criteria for breaking up regions. It's something that would likely apply to other games. Something like stockpiles, room definitions, zones, or burrows on the other hand are very DF specific and would likely pose problems for applying the game to other applications. Even with DF these are a bad idea, how are you going to optimize pathfinding based on room definitions in Adventure mode?

Marking an area as especially relevant for certain actions is something that comes up in a lot of games, I imagine. It's certainly useful.

AI settlements will need to be generated with their own set of room definitions, traffic designations, etc.. That will break save compatibility again, so it's not trivial - but something like that has to happen if the townsfolk ever are not to act like they all suffer from terrible amnesia, don't really know what they're doing there, and just amble around wondering whether they are just a randomly generated npc in a big simulation.

There certainly are improvements to be made in the more general area, but can you knock 80% off A* or another algorithm that is about the best that so many others (computer scientists, roboticians, game designers, mathematicians, etc.) have done so far? It's comparatively easy to optimize the pathfinding of the 90% of the fortress inhabitants that spend their lives mostly crafting, hauling and sleeping so their 90% of cpu usage can be reduced to 10%.

If it works well, other game designers might start to use areas more often in pathfinding.

[Sunken]

Thank you for the clarification.  Most of what I could got from all the previous posts was that "We'll optimize the algorithm," which didn't make any sense since A* is already optimal assuming that the heuristic is >= actual cost.  I still would like to know though, what is the algorithm are you planning on using to discover areas, since an idea is one thing, but an implementation is something else.

Well... "A* is optimal" means that A* finds the optimal path - not that it does it in the least possible time!

The time taken is given by the shape of the search space we give to A* (which in our case comes from the zones we use, the limitations imposed by movement types, and the use of a connectivity map), and the heuristic function we use (absolutely crucial), and also by the low-level programmatical implementation (such as which language to use). I'm just claiming the two former are vastly superior targets for optimization efforts than the latter.

[Starver]

So... If we had the equivalent of a "Lossy" path-finder (generally fast, efficient, just not always the best path, and very occasionally an 'artefact' strangeness) what would you think about that?
A: Good for the running of the programming, as well as speed-up/resource improvements it add's 'character' to the routes taken (perhaps reflects a little "artificial stupidity" on behalf of the agents)
B: Bad for the player, because she can no longer meta-game the situation (normally she'd expect a particular behaviour and thus account for it, suddenly it's unknowingly complex what might happen)
C: Both/neither/something else?

(An idle bit of postulating, not a call for a formal vote or show of hands...  Just thinking out loud.  Besides, some people consider the current "route around the mountain to finish the tunnel" situation as an 'artefeact glitch' of the current system, and one which could be solved by methods <foo> or <bar> or <baz>...)

[Sunken]

It depends. Mostly A, I think, at least if the errors are "human" in nature. People don't do optimal pathfinding, after all.
I'm counting on that with my TCZ suggestion, because "silly-move" navigation inside TCZs is not optimal. In extremely contrived circumstances it can be as much as 50% inefficient.

That's on the small scale, however. On that scale, one could even get by with having dwarfs use different pathfinding locally depending on whether the player is looking at them or not... if it is visually displeasing. Large-scale pathing should be acceptable.