Print

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

[MDFification]

Brief idea- make dwarves choose to walk those extra tiles to avoid walking up a z-level.
Essentially, I want dwarves to reach a realistic laziness. We wouldn't climb when a flat surface was available unless traveling longer distances, and I think it'd be neat if dwarves had the same cost/benefit analysis going on.

[GavJ]

What would this accomplish for gameplay? In a generic sense, higher but not infinite costs for any tile in pathing = more lag, since arbitrary pre-decided weights like this have no reason to line up with the optimal path, thus usually encouraging certain paths for no particular benefit most of the time.

That cost should come with a pretty tangible gameplay benefit to be worth it. (For example, the default higher cost on tracks carries the tangible benefit of dwarves being less often maimed by high speed boxes full of rocks, as a tradeoff for the higher lag it introduces)

[Bumber]

Multi-Z level pathing isn't done properly yet. They calculate distances based on the assumption that they can float right through any floor or ceiling. Increased costs for z-level pathing might become a thing later since tiles are canonically taller than they are wide (by a 3:2 ratio, IIRC.)

[GavJ]

Multi-Z level pathing isn't done properly yet. They calculate distances based on the assumption that they can float right through any floor or ceiling. Increased costs for z-level pathing might become a thing later since tiles are canonically taller than they are wide (by a 3:2 ratio, IIRC.)

There is not really any notion of "proper" or "improper" to the way it is done now, as far as I can see. In the case of multiple possible goals, you can't use actual paths to determine the goal of the pathfinding operation prior to finding the path: that's circular. Thus, your only two options are:
1) Choose the goal by some shortcut method that inherently cannot take into account exact paths by the very nature of it being the STARTING point for a pathing algorithm. This is the current model. OR
2) Just do a blind flood algorithm until you hit one of the valid goals. This would make everything based on natural paths, but it would also be way the hell slower.

Which one is "proper" depends entirely on the value you place on speed versus weirdness, which is subjective.

[Bumber]

There's got to be some kind of way to cache room data in an efficient and effective way.

Other than that, you can start with the current method and attempt to path from the 'nearest' goals to the job owner. You can then also eliminate some goals if they intersect a cheaper path while you're iterating. Probably still slow, but it might be viable in the near future (i.e. before the game's done.)

I'd count on the room method.

[GavJ]

There's got to be some kind of way to cache room data in an efficient and effective way.

That is merely a different flavor of shortcut. In the exact same way that sometimes dwarves will take ridiculous paths to get to get a reagent that was near them but on the other side of a wall, they would also occasionally take ridiculous paths to get a reagent that used to be next to them but has since been moved since the last data cache update.

Might be more or less to your liking, but it's the same category of logical solution.

[Bumber]

That is merely a different flavor of shortcut. In the exact same way that sometimes dwarves will take ridiculous paths to get to get a reagent that was near them but on the other side of a wall, they would also occasionally take ridiculous paths to get a reagent that used to be next to them but has since been moved since the last data cache update.

It would add the item to the room as soon as it was dropped (or as it is passing through, if future features require intercepting an item in transit.)

[GavJ]

And what is a "room"?

[Bumber]

And what is a "room"?

That's probably the most important part.

Obviously we've got some precedent with the in-game room system (a general size, blocked by doors.) Might not be optimal for pathfinding to involve doors, but maybe stop at narrow passages of sufficient length. Perhaps let the player define them? You could use fixed size squares/cubes (a grid) across the map and break them into sub-rooms by flooding (or just use actual octrees?) Obviously there are better ways of doing it than I alone can think of.

[GavJ]

Okay. It might strike a better balance than right now, but I'm fairly skeptical. Worth pondering.

Something like octree would be totally unworkable if used on actual game tiles, since you'd have like, 10,000 rooms most of the time, and you'd need to cache millions of paths between all of them, and it'd almost certainly be slower than simply using a flood algorithm each time in the first place.

Octree used on a forced bigger grid is maybe not combinatorically explosive anymore, but it's unclear how it would work, because paths have to be between literal tiles, and which tile do you pick for a path to a grid that is composed of 27 actual game tiles??? The one you pick might be a solid wall, etc.  All kinds of problems arise from treating many tiles like one for any purpose. An analogous situation is even when intelligent humans trying to figure out if/when there are land connections on the embark screen, the abstraction across tiles is problematic. If humans have issues, algorithms will.

Something like the existing bedroom fill might be better, but that requires a specified center point. Where does that come from? And how often is one re-chosen for all rooms? Etc.

I suspect most of these would quite possibly add more weirdness than is being solved.



Also, all of these or any other room solution suffers from the problem that it would need to be adjusted based on how expansionistic a given player is. Too few rooms is wasteful and will lead to even weirder pathing than we have now, if you don't dig much.  But too many rooms made too aggressively could grind your game to a halt or crash it if you dig a lot, and it ends up making thousands of rooms with millions of paths again.

[breadman]

Multi-Z level pathing isn't done properly yet. They calculate distances based on the assumption that they can float right through any floor or ceiling. Increased costs for z-level pathing might become a thing later since tiles are canonically taller than they are wide (by a 3:2 ratio, IIRC.)

Adding an extra cost to Z-level movement could be done in any of three places: The initial goal choice, the cost function, or the heuristic function.  The cost function is the one that already handles each tile's traffic value; adding 1 when the Z-level changes should be simple, but on its own would slow down pathfinding.  Switching the heuristic function to assume a movement cost of the normal traffic designation per tile would speed up pathfinding, particularly if it also assumed extra for Z-level differences.  Switching the initial goal choice might also speed things up, and would definitely trim down weirdness, but might not be as important given my next idea:

There is not really any notion of "proper" or "improper" to the way it is done now, as far as I can see. In the case of multiple possible goals, you can't use actual paths to determine the goal of the pathfinding operation prior to finding the path: that's circular. Thus, your only two options are:
1) Choose the goal by some shortcut method that inherently cannot take into account exact paths by the very nature of it being the STARTING point for a pathing algorithm. This is the current model. OR
2) Just do a blind flood algorithm until you hit one of the valid goals. This would make everything based on natural paths, but it would also be way the hell slower.

Which one is "proper" depends entirely on the value you place on speed versus weirdness, which is subjective.

It seems like there could be a hybrid option, though, which might even be faster in the general case.

Step 1) Find a set of goal spaces.
Step 2) Choose the closest one, as the ghost flies.
Step 3) Path using the heuristic for the chosen one, but stop as soon as any goal space is found.

Checking whether each node is a goal space would slow down pathfinding, except that the shortcut would speed it up, sometimes dramatically.  For example, I once watched one dwarf carry another halfway down the map, through one hospital, up and down dozens of ramps, and through two cavern layers to get to another hospital that just happened to be directly below where the wounded dwarf was lying.  I have since learned to build similar things directly underneath each other, but still wish I hadn't needed to.

There are still cases where this algorithm will choose a sub-optimal path, but they should be rare and far less obvious.  I have considered a multi-destination heuristic to handle these cases, but that gets complicated, potentially slow, and possibly less effective than the blind flood fill.

[GavJ]

With careful consideration that might be good. It's great for finding a hospital. Potentially catastrophically horrible for every goblin checking every tile to see if it is one of any of 200 dwarves, though. So it should pick the algorithm based on # of goal items, at least. Otherwise sounds quality.

[breadman]

With careful consideration that might be good. It's great for finding a hospital. Potentially catastrophically horrible for every goblin checking every tile to see if it is one of any of 200 dwarves, though. So it should pick the algorithm based on # of goal items, at least. Otherwise sounds quality.

Fair point.  It might be possible to reduce the node check to a single flag, but that requires more initial setup time and storage space.  The case you describe iterates over the list of potential goals for each node, which is convenient for a generic pathfinding implementation.  An alternative implementation could use a function pointer to call for each node, which (for example) might be able to ask whether a dwarf is here instead of whether this space is one of the dwarves.  Only profiling can tell whether that's faster in practice.

Are there other cases that could go pathological?  I can see multi-destination pathfinding useful when selecting:

• A job
• An item for a task in progress
• A hospital bed
• An empty table for eating
• A dump zone
• A destination for an animal out of its pasture
• A meeting zone or other break room
• A depot (should more than one actually be available)
• Where in the stockpile to place an item
• Where to stand for constructing a wall
• Potentially much more...