Print

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

[Slogo]

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

Because the idea of sectioning off a large enough % world with designations is something pretty unique to dwarf fortress. A lot of other tile based games, including adventure mode of DF, don't have the luxury of these designations. It's something that would require a fair bit of coding for vague benefits at this point. Since we need to support the 'no hints' case anyways (even in DF) the whole idea is basically committing to a lot of work for unclear at best gains.

Even within DF there are plenty of cases where player hints may be less than ideal or just not workable. What about a general 'barracks' bed room design where you have an open room with many bedroom designations in it? What about a stockpile room that's really 8 different stockpiles? What about non-continuous stockpiles or overlapping rooms? The divisions based on the player hints in these cases are going to be less than ideal or outright ambiguous.

[numerobis]

Back in March I put up the following testbed for path-finding:
http://idefix.uchicago.edu/~bhudson/src/astar_test.tgz

It reads a file (look at test-input for an example), stores it as a grid, then does 500 random A* searches.  It's easy to do 500 random searches using a different algorithm.  Ideally we'd have a library of input files, and a library of paths to find in those files.

It is in C++, which is of course very slightly slower than C except when it's much faster.

User annotations are not my idea of a good time: users will get them wrong, and they've (we've) got more fun things to do than help the pathfinder.

A convex subdivision of above-ground space would be a fairly big boon for flyers.  I'm not sure it would be for below-ground space, where much less is convex.  We have to make sure our subdivisions are enough bigger than mere grid squares.

We don't have to decompose geometrically though.  We have the whole field of graph partitioning to draw on.  For example, one subdivision commonly used for clustering in multi-commodity flow problems and the like (i.e. network routing -- which is pretty much what we're doing here, if you think of dwarves as packets): start a seed at a random spot somewhere in the graph.  Build a cluster by taking in neighbours of nodes in the cluster until the ratio (number of neighbours) / (number of nodes in the cluster) is some small value.  Intuitively, this means you repeat until you hit a chokepoint.  Repeat until all nodes have been put into some cluster.  Now, create a new graph by saying that clusters are nodes now, and there's an edge between two clusters if in the original graph, there was an edge between a node in one cluster and a node in the other.  Repeat until you have a small number of clusters, and you've created a clustering hierarchy.  Under various assumptions that I'm fairly sure we satisfy (but which I don't remember so I can't check -- however, grids usually satisfy most of what you'd want to satisfy), clustering is linear or so time and yields a log n depth structure.  The size is linear, but depending on how you set the constants, particularly on the lowest-level clustering, is basically tiny.  Edge weights (e.g. restricted zones) are easy to include and don't change anything fundamental: instead of number of neighbours / number in cluster, it's sum of edge weights to neighbours / sum of edge weights in cluster.

Given the hierarchy, it's relatively cheap to find an approximately shortest path from s to t: find the least common ancestor of s and t in the hierarchy, and path in that graph.  Then, you recursively find a path from s to the next "node" (actually, itself a cluster) and so on.  Each cluster is approximately round, so whatever path you find is pretty much a straight-line path through the graph -- that's why it's approximately a shortest path.  The path-finding time is near-linear in the length of the path.

It seems non-hard to run this dynamically (maintain the clustering as you add or remove edges and nodes), but we never did work out the details.

There are two types of pathfinding we should be interested in: (1) going from s to t, where s is the dwarf and t is the dwarf's unique bed.  (2) going from s to T, where s is the dwarf and T is the set of all booze barrels, of which there are many, strewn about all over the place.  What I mentioned above handles (1), but I'm not clear on whether it handles (2) nicely.  Note that A* also only handles (1).

[numerobis]

Oh, I forgot about how the graph changes depending on who's walking.  If the number of categories is small, we can just have several different clusterings (assuming each one really is small).  If there are many categories, but only a small number are common, we can have the uncommon ones fall back onto A*.  If there are many categories, all of them commonly used, we need to do More Thinking (TM).

[Jifodus]

Even within DF there are plenty of cases where player hints may be less than ideal or just not workable. What about a general 'barracks' bed room design where you have an open room with many bedroom designations in it? What about a stockpile room that's really 8 different stockpiles? What about non-continuous stockpiles or overlapping rooms? The divisions based on the player hints in these cases are going to be less than ideal or outright ambiguous.

I was thinking more of global scale.  What you're thinking of is localized conditions, in a localized situation like you describe path-finding is already near optimal.  The path-finding that really slows DF down is at a large scale, when it pointlessly explores winding tunnels.

When you consider small scale areas like path-finding within a room, or even neighboring rooms the cost of pointless exploration is fairly minor.  But if you were to attempt to find a path from deep within the fortress to the map edge, it'll take many tries and dead-ends before it makes it to the surface.  After it makes it to the surface, the complexity usually goes down so it's more or less a straight path to the edge.

The goal of the waypoint suggestion is to make it so the player just has to put about 10 waypoints down in the main hallways and have path-finding costs decrease substantially.  The player shouldn't have to figure out the optimum path between the waypoints or even which waypoints should have a precomputed path to another waypoint.  The main goal is to keep the number of hints low and act as highway to different parts of the fortress.

While it's already possible to do something similar with the current traffic designations, it's high maintenance and would require manipulating the weights since the difference between normal traffic and high traffic is only 1.

[Slogo]

My responses are in reference to people suggesting that room definitions are used to determine the hierarchy. Having players place specific waypoints is bad for a whole set of different reasons, mostly that placing waypoints isn't fun. Why have the player perform tasks simply to increase the performance of their pathfinding? There's nothing fun about that. Traffic designations are different as they're meant to guide the dwarves away/towards specific areas or tiles such as carp infested rivers. You're also relying on the player to be able to determine which waypoints will provide the best paths and performance, also very much not fun.

Even with waypoints the issue still stands: It's DF specific. It has no application outside of a manager type role. You couldn't even use the waypoints in adventure mode for example.

[Jifodus]

Even with waypoints the issue still stands: It's DF specific. It has no application outside of a manager type role. You couldn't even use the waypoints in adventure mode for example.

Waypoints are a general method for taking a complex topography and creating a simple representative graph.  In no way is it limited to a manager type role.

Even if waypoints aren't optimally placed, having even having parts of precomputed paths that will go through major hallways can help with travel between distant parts of the fortress.  This is helpful even in adventure mode, the game engine could place waypoints inside each of the buildings in an above ground village.  For a fortress/cave that is player/computer generated, several random waypoints may be placed with the same results.  If a player wants to place several waypoints to act as more accurate hints to where primary paths should be it is left as an option, but not a requirement.

If you run into one of the precomputed paths during normal path discovery, you can switch to a bidirectional method where you start at the endpoint trying to find a path to the starting point. If the backwards path finding also hits a precomputed path, it's now possible to skip detailed searching between the start and end and use the precomputed paths.  After finding a path, it can potentially be used as a new precomputed path or, depending on how much of the path used existing precomputed paths, can be used to determine if a new detailed path is required.

[Slogo]

If they're automatically placed then why use them at all? Regioning and a Hierarchical algorithm accomplish the same goals with better performance and more flexibility.

A Hierarchy with caching of movement between regions is essentially the same as a pre-computed path. Instead of A* ing over 100s of tiles you simply A* to the first border of your region, follow the computed paths between regions, then A* to the destination. Even without the precomputed route cached you can at least distribute the pathing work over time using the hierarchy.

Also with a dynamic map regions are easier to maintain than waypoints. It's a lot harder to tell if a waypoint is out of date compared to a region. With regions you know exactly what region needs to be updated based on a map change. With waypoints it's a lot more difficult to tell if a new opening creates a better path or blocks a set path.

[JanusTwoface]

A Hierarchy with caching of movement between regions is essentially the same as a pre-computed path. Instead of A* ing over 100s of tiles you simply A* to the first border of your region, follow the computed paths between regions, then A* to the destination. Even without the precomputed route cached you can at least distribute the pathing work over time using the hierarchy.

One potential problem with this is that heavily trafficked paths (specifically in DF, but possible in other games) impose a penalty to movement when there are multiple agents in the same square.

It's not a horrible problem in the case of larger hallways because the agents can have a secondary routine that automatically routes them around each other in problems like that.  Like staying to the right when passing (or left as the case may be).

The bigger problem comes from narrow/twisty paths that have similar costs.  IMO, a good path finding algorithm should be able to randomly choose the worse path proportionately to how much worse and the average traffic through both to help balance the load along precomputed paths.

On another note, has anyone looked around for any open source projects that do the same kind of thing?  It seems unlikely (albeit possible) that the DF community would be the first to come up with such an idea.  It's entirely possible that someone else has already done the original work and we can build from there.

[Slogo]

Well, I think some of that is the responsibility of traffic designations and part of it is just dynamic obstacle avoidance. Basically just checking out along the next few tiles for a new obstacle that you may have to avoid, I don't know if we can get around that any other way without too much overhead.

If you did want something to handle traffic flow in a more sophisticated way then I'd say that you could store something like a baseCost and trafficCost for tiles (short ints). The base would be static while the trafficCost could respond to traffic dynamically. When a creature travels over the tile the cost of the tile could go up incrementally. Conversely over time, and to keep it simple I'd say every x game time regardless of when the tile was last stepped on, the trafficCost could be decremented. Then during pathfinding actualCost = baseCost + trafficCost * weight where weight < 1 (likely much less).

The other simple and more pronounced way to handle traffic is going to be in how the A* algorithm expands out + any smoothing operations we perform. If you favor an algorithm or smoothing that will expand out to generally run down the middle of a hallway or one side of a hallway then that'll help a lot.

Overall I'm wary to do any system like that because of the overhead it would add to pathfinding. There are probably some better algorithms for dense populations out there but I'd have to research it more.

I also don't think it's any worse than what you see now as the current system will generally route dwarves along the same paths constantly.

[Footkerchief]

On another note, has anyone looked around for any open source projects that do the same kind of thing?  It seems unlikely (albeit possible) that the DF community would be the first to come up with such an idea.  It's entirely possible that someone else has already done the original work and we can build from there.

The much-linked article on HAA* includes the code that guy used for testing and a link to what looks like a more generalized library.

[JanusTwoface]

On another note, has anyone looked around for any open source projects that do the same kind of thing?  It seems unlikely (albeit possible) that the DF community would be the first to come up with such an idea.  It's entirely possible that someone else has already done the original work and we can build from there.

The much-linked article on HAA* includes the code that guy used for testing and a link to what looks like a more generalized library.

Shiny.  That gives me even more reason to read the article (it's open in one of my tabs already, but I'm a little behind on going through them).

[Silverionmox]

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

Because the idea of sectioning off a large enough % world with designations is something pretty unique to dwarf fortress. A lot of other tile based games, including adventure mode of DF, don't have the luxury of these designations. It's something that would require a fair bit of coding for vague benefits at this point. Since we need to support the 'no hints' case anyways (even in DF) the whole idea is basically committing to a lot of work for unclear at best gains.

Well, then design the library for other games... but then I wonder what it's doing here? Trying to to serve many masters will end up satisfying none. Both approaches are complementary rather than mutually exclusive anyway.
Just use any present designations as a starting point. Let the algorithm determine the rest of the terrain sections automatically.. which would have to happen anyway without using the designations. The result will be a little different than full automation, but the sections will resemble the vision of the player more closely.

Even within DF there are plenty of cases where player hints may be less than ideal or just not workable. What about a general 'barracks' bed room design where you have an open room with many bedroom designations in it? What about a stockpile room that's really 8 different stockpiles? What about non-continuous stockpiles or overlapping rooms? The divisions based on the player hints in these cases are going to be less than ideal or outright ambiguous.

A barracks/communal bedroom can be defined as a single room.. If the player wants to do the work to make a barracks-like bedroom setup (because of space constraints, roleplaying goals, etc.), why shouldn't the dwarves think that way and try to avoid the personal space of as many dwarves as possible? The same for the 8 different stockpiles in the same room. If the player considers them separate spaces, then the dwarves will too. Non-continuous rooms are invalid as section and should be considered as two parts - trivial to check and split. The overlapping part of the rooms can be considered a separate space, and merged with a nearby one if it happens to be to small to be meaningful. Alternatively, room overlap could be cut out since it doesn't serve a useful function anyway - introducing shared rooms instead, if and when that's necessary. Otherwise ignore them if they don't give clear information on cells. But how is that going to be any worse than making the computer guess what the player wants to happen?

[zchris13]

A Hierarchy with caching of movement between regions is essentially the same as a pre-computed path. Instead of A* ing over 100s of tiles you simply A* to the first border of your region, follow the computed paths between regions, then A* to the destination. Even without the precomputed route cached you can at least distribute the pathing work over time using the hierarchy.

One potential problem with this is that heavily trafficked paths (specifically in DF, but possible in other games) impose a penalty to movement when there are multiple agents in the same square.

It's not a horrible problem in the case of larger hallways because the agents can have a secondary routine that automatically routes them around each other in problems like that.  Like staying to the right when passing (or left as the case may be).

The bigger problem comes from narrow/twisty paths that have similar costs.  IMO, a good path finding algorithm should be able to randomly choose the worse path proportionately to how much worse and the average traffic through both to help balance the load along precomputed paths.

On another note, has anyone looked around for any open source projects that do the same kind of thing?  It seems unlikely (albeit possible) that the DF community would be the first to come up with such an idea.  It's entirely possible that someone else has already done the original work and we can build from there.

Let it be able to draw on parameters for each creature.  Let you be able to draw on predetermined factors. (such as sociability), or the ratio of the times the dwarf has traveled a path to the number of times it has had to walk around another dwarf.

[Slogo]

Well, then design the library for other games... but then I wonder what it's doing here? Trying to to serve many masters will end up satisfying none. Both approaches are complementary rather than mutually exclusive anyway.
Just use any present designations as a starting point. Let the algorithm determine the rest of the terrain sections automatically.. which would have to happen anyway without using the designations. The result will be a little different than full automation, but the sections will resemble the vision of the player more closely.

It was written clear as day on the very first post...

Create a flexible BSD licensed C++ path-finding library specialized for grid based systems like that of Dwarf Fortress and able to efficiently handle rapidly changing map geometry and other challenges such as but not limited too multiple travel domains, multi-tile creatures, variable movement cost terrain and path caching.

That is our goal. Nothing more nothing less. Considering that using designations both backs us into a corner and creates more headaches than performance gains I don't see the value in it.

[Jifodus]

Create a flexible BSD licensed C++ path-finding library specialized for grid based systems like that of Dwarf Fortress and able to efficiently handle rapidly changing map geometry and other challenges such as but not limited too multiple travel domains, multi-tile creatures, variable movement cost terrain and path caching.

That is our goal. Nothing more nothing less. Considering that using designations both backs us into a corner and creates more headaches than performance gains I don't see the value in it.

Now I remember why I was mentally averse to this thread.  Good luck with your general library, because you will need it for certain.