Print

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

[MercuryP]

Okay, so here's a question.  It's obvious that you have to split the map up into nodes larger than a single space in order to improve the pathfinding.  You can't really improve upon A*, so you trade space for time.

So the map's split up using some elegant node-choosing algorithm.  This alone is going to speed up pathfinding considerably.  When I try to get out of a building when I'm on the third floor, I don't first try and go through the floor below me, then search for an alternate path.  I path to the door, then I path to the stairs, then I path down to the first floor, then I path to the exit.

So why do a tree, as opposed to just A* on the nodes?  It seems like A* on nodes would be fast enough in and of itself, and would be easier to implement.  I mean, I think the tree is a great idea and I don't see any problems with it, but does it have any advantages other than a little more speed?  Or would it really be that much faster?

[Draco18s]

So why do a tree, as opposed to just A* on the nodes?  It seems like A* on nodes would be fast enough in and of itself, and would be easier to implement.  I mean, I think the tree is a great idea and I don't see any problems with it, but does it have any advantages other than a little more speed?  Or would it really be that much faster?

That's what I've been thinking.

[NW_Kohaku]

You can smooth things out later by doing regular intranode pathfinding at each node along the way.  If the nodes make sense, this should be a larger quantity of very cheap calculations relative to what the game does now, and the cheapness should more than make up for the larger quantity.

Sorry to have not responded to this one earlier, but I wanted to focus in on speaking to Sunken at the time. 

Yes, this is exactly what I was suggesting doing - making a larger, looser set of nodes, and just allowing A* within the barriers of the current node to pathfind to the destination (possibly with a steering bias to help avoid collisions).

Okay, so here's a question.  It's obvious that you have to split the map up into nodes larger than a single space in order to improve the pathfinding.  You can't really improve upon A*, so you trade space for time.

So the map's split up using some elegant node-choosing algorithm.  This alone is going to speed up pathfinding considerably.  When I try to get out of a building when I'm on the third floor, I don't first try and go through the floor below me, then search for an alternate path.  I path to the door, then I path to the stairs, then I path down to the first floor, then I path to the exit.

So why do a tree, as opposed to just A* on the nodes?  It seems like A* on nodes would be fast enough in and of itself, and would be easier to implement.  I mean, I think the tree is a great idea and I don't see any problems with it, but does it have any advantages other than a little more speed?  Or would it really be that much faster?

I started thinking about the tree-based pathfinding idea when I was considering how to work multiple nested hierarchies and trying to get the game to recognize high-traffic hallways as compared to dead-end rooms.  My mind's image of the hierarchies led me to thinking about quad trees, and I realized that a tree-based search structure would allow us to pathfind without having to use some variation of A* at the more abstract hierarchies. 

To put it in terms of leaving a building, you don't think "I need to pathfind down 30 feet, north 25 feet and east 10 feet," you think, "to reach the exit, I need to get to the ground floor, and to get to the ground floor, I first have to go to the stairs."

The advantage of a tree-based search over some modified variation on A* is that you don't have to do the sorts of loopy heuristics that get complicated in a very abstract hierarchical search.  A* relies upon the heuristic to make its guesses, and when you don't have a way to make a general guess about what direction a given node lies down, it can become fairly problematic. 

A tree-based search is also not that hard to implement at all - it's a fairly rudimentary data type in very common use for finding data quickly.  There are degrees of complication that arise the more accurate you wish to make the search in exchange for greater use of memory, but these seem to be far more complex for me to explain to people than they actually would be to program.  A tree is simply a more abstract means of thinking about things (like "I need to go to the nearest stairwell") as opposed to the more direct A* ("I need to follow this wall until I find a passage that leads downward"). 

A tree-based search is faster than A* with a loopy heuristic that has to make a bunch of guesses on every connecting node, but it depends on how much you want to optimize for walking distance, and not just upon conserving processor power.  If you throw in too many trade-offs that trade memory for precision, then A* could potentially just be worth the memory you take back.  The exact crossover point on this is based largely upon the subjective relative value you are placing upon accuracy, processor consumption, and memory consumption at the time, however, so if you really want to argue for one over the other, there's a case for several different paths.  A* can potentially use up less memory, but use up more processor power.

[MercuryP]

I don't really see why A* itself would get complicated, though.  You find nodes, find direct paths between adjacent nodes, then do A* with the standard distance-from-destination heuristic using the points where the nodes connect to each other as your search graph.  Admittedly, the heuristic is not conducive to picking out the proper path without a significant level of failure, but if the nodes are few enough does it really matter?

I do see your point though.  If you have a hallway of bedrooms, it makes a lot of sense not to try and go through the other bedrooms when you're pathing out.  With most of the things that get built in DF, trees make a whole lot of sense.  Buildings with rooms and hallways and exits and such.

I'm curious about what would happen with wide-open spaces, though.  What about outside the fort?  Is the whole exterior going to be one node, or will it be sliced up into smaller blocks?  If you slice it up, then you have a lot of pieces connecting to each other, and that doesn't much fit into a tree.  You can arbitrarily assign a top node and then file things away, sure, but you'll end up in situations where the paths are extremely suboptimal.

In terms of the US map, you're going from AZ to WY, and the root node is OK, so you pick out a path AZ->NM->OK->KS->NE->WY.  That's six steps from something you could do in two.  You can't find a shortcut since there's no direct path between any of the nodes you're going through.  I know the goal isn't to find an optimal path, but take this a few steps further out (Florida to Maine?) and you end up with paths that aren't even good.  A slightly meandering path is one thing, but your dwarves could easily end up prioritizing a point in the middle of nowhere that has no real significance to your fort.

It seems like the best thing to do here would just be to make the entire outside area one single node, or a few very very large nodes.  That way the high-level nodes would be a lot more likely to end up in the right places, and you wouldn't have a faux-tree of nodes that are all really connected to each other.  But doing that makes it hard for me to wrap my head around how you would go about splitting up the map into nodes in the first place.

You've probably considered/discussed this already, so apologies if I'm rehashing things you've already been over.

[NW_Kohaku]

I'm curious about what would happen with wide-open spaces, though.  What about outside the fort?  Is the whole exterior going to be one node, or will it be sliced up into smaller blocks?  If you slice it up, then you have a lot of pieces connecting to each other, and that doesn't much fit into a tree.  You can arbitrarily assign a top node and then file things away, sure, but you'll end up in situations where the paths are extremely suboptimal.

In terms of the US map, you're going from AZ to WY, and the root node is OK, so you pick out a path AZ->NM->OK->KS->NE->WY.  That's six steps from something you could do in two.  You can't find a shortcut since there's no direct path between any of the nodes you're going through.  I know the goal isn't to find an optimal path, but take this a few steps further out (Florida to Maine?) and you end up with paths that aren't even good.  A slightly meandering path is one thing, but your dwarves could easily end up prioritizing a point in the middle of nowhere that has no real significance to your fort.

It seems like the best thing to do here would just be to make the entire outside area one single node, or a few very very large nodes.  That way the high-level nodes would be a lot more likely to end up in the right places, and you wouldn't have a faux-tree of nodes that are all really connected to each other.  But doing that makes it hard for me to wrap my head around how you would go about splitting up the map into nodes in the first place.

You've probably considered/discussed this already, so apologies if I'm rehashing things you've already been over.

Yes, this is exactly the thing that Sunken has been talking about, and I don't particularly feel like rehashing right now.

Suffice it to say, there are ways to overcome this deficiency, and it involves consuming more memory by storing duplicate paths.  Basically, you could consider Wyoming "up the tree" from both Colorado and Nebraska.  In that case, you go from AZ->NM->CO->WY.  It's not the fact that it's "three steps" that matters, though, it's the total distance you traveled, and whether or not it was the most direct route - a trip that passes through Nevada and Utah is going to be longer than a trip through New Hampshire, Massachusetts, and Connecticut, even if it's only passing through two states, rather than three.

[MercuryP]

Yeah, I see what you mean.  A tree just doesn't seem to be a particularly good model for open areas, though, even if it can be made to work.

So let me attempt to contribute an idea on top of the tree.  I was trying to think along the lines of networking, but what I came up with was a little different.  The entire map is a tree-ish sort of thing where each node is either:

a) a single map node
or
b) a graph consisting of exactly one cycle of nodes

Something like this:

1) Split the map into nodes.
2) Make a node graph.
3) Look for cycles, starting with the smallest available cycle (measured according to game distance).  Treat these as singular nodes in the remaining graph, and repeat until there are no more cycles.
4) The remaining graph will of course be a tree.

Without cycles, this is the same as a regular tree.

What about large rings?

Code: [Select]

o........o........o........o........o........o
.                                            .
.                                            .
.                                            .
o                                            o
.                                            .
.                                            .
.                                            .
o                                            o
.                                            .
.                                            .
.                                            .
o........o........o........o........o........o
When pathing to the opposite corner, you can end up going the wrong way pretty easily.  But we know it's a cycle, so that can be used to advantage by storing a clockwise distance index (to distance to the centers of the nodes relative to an arbitrary starting position) and a full cycle length.  Since there are only two options for directions to go in, it's pretty easy to pick the right way.

So that covers halls of bedrooms (no cycles), and covers two-dimensionally ringed hallways.

What about double rings?

Code: [Select]

o........o........o........o........o........o........o........o........o........o........o
.                                            .                                            .
.                                            .                                            .
.                                            .                                            .
o                                            o                                            o
.                                            .                                            .
.                                            .                                            .
.                                            .                                            .
o                                            o                                            o
.                                            .                                            .
.                                            .                                            .
.                                            .                                            .
o........o........o........o........o........o........o........o........o........o........o
First you condense, say, the left ring into a single node, and then you're left with a single ring, wherein one of those nodes is abstracted.  So how do you store the clockwise distance index for the abstracted node?  The same way as before, using the "center" (the midpoint between the two end connecting nodes).  Since it's counting actual game spaces, it should still work correctly.

Okay.  How about two adjacent floors of ringed hallways with stairs in the four corners?

Code: [Select]

2D simulation
...,................................................................................................
.                                                                                                  .
o........o........o........o........o........o........o........o........o........o........o........o
.                                            .        .                                            .
.                                            .        .                                            .
.                                            .        .                                            .
o                                            o        o                                            o
.                                            .        .                                            .
.                                            .        .                                            .
.                                            .        .                                            .
o                                            o        o                                            o
.                                            .        .                                            .
.                                            .        .                                            .
.                                            .        .                                            .
o........o........o........o........o........o........o........o........o........o........o........o
.                                                                                                  .
...,................................................................................................

It gets a little confusing here, but it still works as far as I can tell, and as long as the smallest cycles are the most internal, the chosen paths are still good.

And now what about the wide-open exterior of the fort?

I was hoping to come up with a way to consolidate the entire exterior into one network-esque node and just do regular pathfinding on that, but I think a huge nested graph of 3-node cycles actually works pretty well, again provided that the smallest cycles are furthest down the tree.  That way, pathing basically goes to smaller and smaller regions until it pinpoints the target location.

There are some calculations to be done with the centerpoints of the nested cycles, but I don't think it would be a huge problem.    It's not overly memory friendly, but probably wouldn't be too terrible.  The advantage it has over the regular tree, provided that I'm not missing some obvious counterexample, is that you won't need the "find a shortcut" algorithm or to store alternate paths at all, the paths that do get found are very reasonable, and since routing through a cycle is "intra-node routing" as far as the overall tree is concerned, the main algorithm is no slower.  And with the clockwise node indexing, routing through the cycles should be fast as well.  Going in and out of and passing through the sub-cycles does get a little complicated, though.

I feel like I'm missing something that makes this idea entirely worthless, but it's not readily obvious to me.

[Aquillion]

You can't really improve upon A*

You totally can if you use more specific heuristics.  A* is a very good general-case solution for a totally random graph, but if you know some general features of the graph beforehand, you can use heuristics customized to the case you're dealing with to speed up pathfinding, sometimes immensely.

More importantly, though, the slowdown in DF's pathing probably doesn't have anything to do with the abstract speed of the algorithm; it probably has to do with how it interacts with the limitations of architecture.  On a really really huge graph, like the ones DF works with, the slowdown isn't going to directly be from the processing itself, but from the cost of accessing that huge graph in memory.  Specifically, because access is so unpredictable, and because the graph is too big to fit into your cache, you have to go to RAM constantly.  While RAM is fast, sure, when you're doing a huge series of calculations, you want to be able to keep as much as possible in your cache -- as a result, simply applying A* mindlessly to a huge graph is going to end up being much less efficient than you would think, because most of your time is wasted fetching stuff from RAM to the processor.  Even those few milliseconds add up when you're forced to fetch from RAM for every step in the graph that you take.

Eg. see the abstract for this paper, which touches on the problem.  A* and Dijkstra's algorithm in general was set up to minimize computation time, not to reduce access; but nowadays, access is the real bottleneck, at least when dealing with graphs that are too huge for caching to eliminate the issue.

(There are other issues, but this should give you the general idea.  It's a very common mistake to fall into the trap of saying 'oh, I have a beautiful, perfect-looking algorithm, I'll just use that!' without considering the actual constraints placed by your hardware.)

[tps12]

More specific heuristics?

[Starver]

More specific heuristics?

I must say that I remain a bit wary about "Well, we know there'll be corridors and rooms..." coming into discussions about how to make a better A*, or why to swap to a 'better'-than-A*-when-it-comes-to-corridors-and-rooms system.

Not to say that I don't like the various solutions being brought forward, but just because one player uses a basic 3x3-grid-and-doorways[1] doesn't mean that another player doesn't do 3x3-grid-with-columns[2] or 3x3-grid-with-nothing![3], among others (I didn't even bother to draw diagonal doorways, but I know they're popular) not even taking into account stairwell placement issues.  And there are players who do more aesthetic (less grid-like) layouts with diagonals, even approximations of curves, or are almost entirely open-plan or opportunistic within dug-out veins and other deposit minings.  Some will go for closed-path systems[6] that should be a pathing algorithm's dream.  Certain pathing algorithms, anyway, but others might struggle.

 
Personally, I tend to go for a variety of "filled 11-blocks"[4] within a corridor framework, according to need, and even my corridors might be simple or fancy[5].

Combined with the (near-)open nature of the surface topology and the different ways the various cavern setups might appear, I can only suggest that anyone suggesting a solution optimised for a typical playing-style/fort-layout should look at least at the 'natural' environment, and probably into other layout designs being used (even intermingled in the same fort!) and do a sanity check to see if they're in danger of de-optimising those areas.

Which is not to say that A* is the best-all-rounder, even, I hesitate to add.  And I know people already design their forts according to the vagaries of A* (e.g. walling off unused areas of the fort as a nod towards helping the A* from not investigating that easily-taken dead-end), even while others just ignore it all.  Under a different scheme the former can change styles again, if necessary, while the latter keeps on ignoring the issue (for better or worse).


A long, long time ago, though, in a completely different thread, I mentioned one improvement to pathing that might help (and might easily help immediately, with a suitably annotated A* scheme).  When going to dig out a tile (or otherwise make passable one that's currently impassible), give that destination tile an "honorary passable" status for the purpose of that particular path-finding search and then cut the found path short by one tile to find the actual work-spot.  This way you don't get dwarves standing directly SE of this block, now seeking to cut it out, finding that the westerly tile is a viable dig-spot and then seeking the long path around a mountain to make that dig.  Nor do you get dwarves checking the westerly-tile path, then various other paths to any other access points until they finally get to checking the path to the SE tile, which trumps it and throws all the other pathing effort in the bin, which would be the other solution (saving on dwarf-time, but wasteful of pathing-time).

Instead: Let pathing algorithm know that dig-block is valid destination for this journey; Pathing algorithm (of most sensible types) almost immediately determines that the best path to dig block would be to go NW, and no further; Because it's a dig-job, pop the NW off of the stack; Travel instructions = stop here; Commence to dig to NW.

(If relevant to instances where only orthogonal working is actually legal, would need slight modification to prevent 'illegal' last-steps, but minimally so.)

Should an alternate method be implemented, I'd very much like the above to become a realistic possibility, in some form that does not require a complete tree-graph overhaul, of course, or risks sending other nearby dwarves towards the not-yet-passable tile in advance of its removal. (If they're far enough away, already, they could anticipate, but I think keeping the passability-in-potentia local to the specific miner's path-search data would be wiser and might be simpler.)

Spoiler: Feetnete 1..5 with a lot of ASCII diagrams (click to show/hide)

Code: [Select]

[1]              [2]              [3]
##.###.###.##    #...#...#...#    .............
#+++#+++#+++#    .+++.+++.+++.    .+++.+++.+++.
.+++.+++.+++.    .+++.+++.+++.    .+++.+++.+++.
#+++#+++#+++#    .+++.+++.+++.    .+++.+++.+++.
##.###.###.##    #...#...#...#    .............
#+++#+++#+++#    .+++.+++.+++.    .+++.+++.+++.
.+++.+++.+++.    .+++.+++.+++.    .+++.+++.+++.
#+++#+++#+++#    .+++.+++.+++.    .+++.+++.+++.
##.###.###.##    #...#...#...#    .............
#+++#+++#+++#    .+++.+++.+++.    .+++.+++.+++.
.+++.+++.+++.    .+++.+++.+++.    .+++.+++.+++.
#+++#+++#+++#    .+++.+++.+++.    .+++.+++.+++.
##.###.###.##    #...#...#...#    .............

[4] Open 3x3      Open 5x5     Opener 5x5     Closed 5x5   Closed 3x5     Maximal (wall styles vary!)
#.#############.#############.#############.#############.#############.#############.#
.X.............X.............X.............X.............X.............X.............X.
#.##.###.###.##.###.#####.###.##...###...##.###.#########.##.###.###.##.##.#.#.#.#.##.#
#.#+++#+++#+++#.#+++++#+++++#.#+++++#+++++#.#+++++#+++++#.#+++#+++#+++#.#+++++++++++#.#
#..+++.+++.+++..#+++++#+++++#..+++++.+++++..#+++++#+++++#.#+++#+++#+++#..+++++++++++..#
#.#+++#+++#+++#..+++++.+++++...+++++.+++++..#+++++#+++++..#+++#+++#+++#.#+++++++++++#.#
#.##.###.###.##.#+++++#+++++#..+++++.+++++..#+++++#+++++#.#+++#+++#+++#..+++++++++++..#
#.#+++#+++#+++#.#+++++#+++++#.#+++++#+++++#.#+++++#+++++#.#+++#+++#+++#.#+++++++++++#.#
#..+++.+++.+++..###.#####.###.##...###...##.#############.#############..+++++++++++..#
#.#+++#+++#+++#.#+++++#+++++#.#+++++#+++++#.#+++++#+++++#.#+++#+++#+++#.#+++++++++++#.#
#.##.###.###.##.#+++++#+++++#..+++++.+++++..#+++++#+++++#.#+++#+++#+++#..+++++++++++..#
#.#+++#+++#+++#..+++++.+++++...+++++.+++++...+++++#+++++#.#+++#+++#+++#.#+++++++++++#.#
#..+++.+++.+++..#+++++#+++++#..+++++.+++++..#+++++#+++++#.#+++#+++#+++#..+++++++++++..#
#.#+++#+++#+++#.#+++++#+++++#.#+++++#+++++#.#+++++#+++++#.#+++#+++#+++#.#+++++++++++#.#
#.##.###.###.##.###.#####.###.##...###...##.#########.###.##.###.###.##.##.#.#.#.#.##.#
.X.............X.............X.............X.............X.............X.............X.
#.#############.#############.#############.#############.#############.#############.#

[5]
Limited top view of one slice:
#...#         #...#         #...#
#...#         #.#.#         #...#
#.v.#         #.^.#         #.v.#
#...###########...###########...####
....................................
..X..v......#^..X..^#......v..X..v..
....................................
#...###########...###########...####
#.v.#         #.^.#         #.v.#
#...#         #.#.#         #...#
#...#         #...#         #...#


Side cross-section through the main gubbins:
__X__ ______#\ _X_ /#______ __X__ __
__X_#\ ______#\_X_/#______ /#_X_#\ _
__X__#\ ________X________ /#__X__#\
__X___#\ _______X_______ /#___X___#\
__X____#\ ______X______ /#____X____#
__X_____#\ _____X_____ /#_____X_____
__X______#\ ____X____ /#______X_____
__X_______#\ ___X___ /#_______X_____
__X________#\ __X__ /#________X_____
__X__ ______#\ _X_ /#______ __X__ __
__X_#\ ______#\_X_/#______ /#_X_#\ _
__X__#\ ________X________ /#__X__#\

Continued (in X and Y) through a whole fort layout,
this give both long-distance and local travel advantages
(I sometimes add strategic "diagonal access" blocks with
 diagonal ramps running through open areas.)
((Needless to say, this is not a design easily
  defended, once an enemy gets inside, so instead I do
  my utmost to not /let/ them get inside!))


[6] Main marble rock-race opens only into stone workshop opens only onto various stockpiles clumped together opens onto Trade Depot, tree-farm only leads to wood stockpile only leads to carpenter only leads into various furniture stockpiles leads to central stairwell for distribution, ore-vein is mediated by ore stockpile, smelter, metal stockpile (maybe others along those lines) and forge then metal goods/weapons/armour/etc stockpiles, etc, and I won't even describe such a farming layout, although I've got a nice one planned that one day I'll actually establish properly!)

[Draco18s]

Need I remind you that we want a pathing algorithm that is "fast" not "110% dead spot on finds the shortest route."*

Organizing the map into room/corridor nodes and A*ing that will return sub-optimal paths on occasion.  This is OK.  Finding the absolute shortest path every time is why pathing is so CPU intensive.

*Doing the pathcheck to the impassible-to-dig tile does save CPU, yes, but the point remains: we're not trying to find the best path we're trying to find a reasonably short route quickly.

[NW_Kohaku]

Yes, that's basically been what I've been saying with the tree structure this whole time.  It's meant to be fast, not accurate.

As for the problem of large, open areas, I think the best solution I can come up with would actually be to just make the whole surface before you start carving it up one giant node, unbounded by size limitations.  Then you just A* across the giant node.  As long as all you have is an open field where slopes don't matter and only occasional trees as obstacles, A* is perfectly fine. 

It's only in areas where you have something like a river bisecting the map, or sheer cliff faces, that you need to split that up into nodes that a tree would handle. 

That, alone, would be enough to clean up the big weakness in the tree method for handling large open areas.

Still, after a certain point, I'm just plain getting tired of defending the tree method, and am willing to just go back a few steps in its evolution, and talk more about building a pathfinding tree solely as a means of identifying what are rooms and what are hallways, and then using A* through the resulting structure.  (This seems to be what Draco18s favors.) 

Multiple hierarchical levels of node structure, again, make the whole thing more efficient, especially since the top levels of the hierarchical structure can just store "best routes" for long-range pathfinding.

[Setharnas]

What Draco said. I would even go so far as to suggest that simply splitting each z-level into 8x8 squares annotated with portal information and running HPA* over that first could have additional usage - as in, introducing additional annotations that say "this square has wood resources. this square has metal resources. this square has building-grade rocks." and changing the 'where do I get the next block of stone for this wall?' search to a hierarchical breadth-first search. Best effect if the squares also hold z-connectivity annotations - a rock that's located just one z below on the same x/y would only be found if the area BFS actually got that far. Why only resource classes (rock/metal/wood) as annotations? Because that is what the game is interested in the most usually. If actual materials are needed, an extra search can be executed that builds lists the old fashioned way.

The whole point of hierarchical path finding is to first work on a simplified abstraction of the map, ideally with a set of nodes that completely fits into cache (as much of a pipe dream that may be for DF). It basically returns a burrow that actually limits all pathing for that particular path request. The whole path caching idea is just icing on the cake - I would much rather attempt to tackle that in combination with a user-set waypoint system.

I consider the room-node identification method as achievable (I know it has been used in continuous space environment games before, and grid based is just a special case of continuous based environments), but computationally too risky for the stuff DF players come up with.

[Starver]

*Doing the pathcheck to the impassible-to-dig tile does save CPU, yes, but the point remains: we're not trying to find the best path we're trying to find a reasonably short route quickly.

You missed the point I was making with that bit, it seems.  The best path-checking in the world (being somehow fastest and best and the least CPU intensive, if such a chimeric beast could even exist) returning the round-the-mountain solution is as much in error as the current system.  Even if it did it with a fraction of the effort.

Even a "reasonable route, quick-processing, low-memory footprint" version that still ends up tracing a route hundreds of tiles long (or through however many zones/nodes/whatever) not only wastes dwarf-time, but also impacts the FPS compared to the one that says "Hmm, I can dig that from here" and needs to go no further.  This applies to "walk three steps and I can mine that square from there" cases as well, or any arbitrary distance that's still a fraction of the illogically long distance round to the other side, so while a preliminary "check to see if diggable tile is next to (or nearly next to, or nearly nearly next to) dwarf seeking to work that tile" is a viable option in the extreme example, you'd still end up making the long-distance route-checking if it was just one step beyond your threshold for checking this fact.  Unless you grant the target temporary accessible status of some kind, when it's all done as part of the necessary pathing check in the first place, no extra fuss.

That was the point.


I'm actually not as bothered about massive amounts of speed improvement at the expense of 'accuracy', where some speed improvement might still be had for a totally accurate version. To compare with image formats, I'd go with PNG over JPEG, but both are better than BMP or 'Portable[Bit|Gray|Pix|]Map' representations (especially P1, P2 or P3, in the latter case).  However, I'd live with whichever, if that happened[1], and I just thought I'd take the opportunity to mention a small consideration that all algorithms should at least consider (even though it might not be practical[2]) before someone ends up getting a system implemented (of whatever quality) that doesn't even consider this... well...  consideration.

But having made this point, I shall go back to either lurking or being constructive (or otherwise) regarding the other general issues, depending on how the discussion goes.


[1] The main problem is that as well as 'absolutists' insisting on the "one and only best route, whatever the cost (albeit as low as can be had!)", there will be people who think that one system is 'good enough' but that another is 'not quite good enough, even if faster', and a third is 'much better than it should be, and too expensive for all that'.  At least among the "one and only best" people there's no shifting grey line to be argued over.

[2] I think it should be for most systems, given it's a temporary allocation anyway, I could see certain zone-based algorithms actually adding the "target tile" as a zone of its own (or extension of other zones) for up to 5[3] different neighbouring zones, in a manner that would technically be an illegal duplication/overlap under the more strict systems.  And each of those connecting 'diggable-froms' could be at the end of indeterminately long corridors winding around who-knows where.  And the first four/five choice to access the dig site could be lead anywhere, through all kinds of terrain (external, cavernous, dwarf-dug into either easily-navigable layouts or labyrinthine messes, etc) horrendously difficult to path and time-wasting to cycle through each of them, and possibly the absolute worst-case scenario to attempt to go by the current priority scheme.

[3] i.e. if it was a stairwell tile being dug with a pre-existing stairwells dig/constructed into existence above and below and up to three different neighbouring incursions[4] on the same level, e.g. W, NE and SE.  Hmm, actually, there's possible arguments for six different neighbouring digging-points if it's a ramp to be dug with pre-existing W, NE, SE access on lower level and E, SW, NW on the upper, if I'm not wrong about ramps being able to be dug diagonally from Z+1.

[4] With four, there'd be diagonal passage between them, invalidating the example.

[Niseg]

I just skimmed through the recent responses:
- suboptimal paths can be smoothed using a simple line drawing algorithm try this maze , click on "find path using waypoints", then click on "smooth Path (LOS search)". You'll see my loop chopper (nlog(n) ) and then line smoother (currently bounded by  n^2/2 ) turning a suboptimal path into an optimal one. The example path smoother generates a  lines with total length of 650 nodes  on 131 length path  which is less than nlog(n) ( i got a debug value called ntracker in smoother and i put a breakpoint in Chrome). I still need to optimize those smoothers they aren't that bad comparing to path finding complexity.

- I didn't look at the tree stuff yet (seems complicated)

-I've tried experimenting with heuristics if you got a suggestion for a good one ( I still need to add one I saw somewhere on forum but i lost it  ).

- the caching problem can be solved by a few bit vectors who represent the entire map . it would take about 56KB per 200 height embark square. or 900KB for a 4X4 map . holding 1 vector for walkers,flyers,swimer,magma walkers would take about 3.6MB. due to the locality most of the data fetches would be local. As far as I think Toady might be doing something similar to that  because I've seen linear improvement in FPS while keeping memory speed constant while raising CPU speed

I'm going with my waypoint room implementation you can enable the checkbox and click redraw to see my simple arbitrary room selector ( might change it).

I thought about creating a direct LOS heuristic which would be high complexity but would probably give better accuracy at leading to the target.  The idea is if you try to go toward your destination with a straight line and hit an obstacle you'll have to at least go around it which is about 2 moves.

here is an example

Spoiler (click to show/hide)

###########
#++#+++#++#
#++#+++#++#
#++#+++#+D#
#++++++#+*#
#+++*++#*+#
#++*#*a#*+#
#++*#++*++#
#+S+#+++++#
#+++#+++#+#
###########

* is the A* path (   just found a bug I manually fixed)   .


if the penalty for hitting an obstacle is 3 and you are at point a . The closest point is North with simple heuristic  but if you draw a straight line you hit 1 obstacle so instead of  score of   about 2.5 you get a score of about 5.5 due to the penalty.  the point SE is about 4 away but because there is a clear line (somewhat need to sort out the ends  ) to the destination there is no penalty.

Well I need to implement it to see how well it works this example is hand drawn so I don't know the true path.



EDIT: if you check my WP room example you can see the paths between them - I thought I could avoid diagonals but now I have to add them back in. The paths are found by doing a limited heuristic A* which is limited to 16. I'll add back the diagonals and update.
EDIT2: added diagonals made, a single recursion with double the search limit on dead ends nodes.
EDIT3: I hammered out the bugs in room based waypoint path finding it's still not full proof and I doubt It would work when there is no path to the destination(that's the next stage).  I also need to add more freedom in wp room selection.
EDIT4:traffic zones added to the simulation as separated A* search.
EDIT5: changed links

[Phoebus]

I just did a bunch of pathfinding test.

I rate DF's pathfinding engine with an F-.

Literally, even within the mindset of only using a A* search algorithm, everything about the pathfinding engine has been done wrong.
EVERYTHING.

1. The heuristic estimate is of 1 per tile, not 2 per tile as it should be. That incurs an ridiculously huge performance penalty (1000x the cost or more in common otherwise optimal A* scenarios) for the sake of naive traffic cost agendas.
2. The algorithm values the Z axis less than the horizontal axis. Optimized for ramp seeking greed, the A* algorithm searches every Z levels (between the origin and the target) in hope of finding a ramp. Incredibly stupid 'optimization' for the sake of trivial outdoor pathfinding. Sane DF heuristic should value underground Z levels as a top priority. Stairs/Ramps are relatively rare, and should be highly valued when they are found.
3. The system uses taxicab heuristics, but non-taxicab movement costs. Wtf really.

- DF A* pathfinding algorithm should use non-taxicab heuristic horizontally, but not vertically. Ex.: max(abs(x1-x2), abs(y1-y2)) + abs(z1-z2)
- Optionally, outdoor heuristics should also have an option (on by default) to also use non-taxicab vertically, for the sake of the outdoor ramp layout. Ex.: max(abs(x1-x2), abs(y1-y2), abs(z1-z2))
- The basic heuristic estimate per tile should equal or greater than the cost for 'Normal Traffic' by default, and it's also very important for it to be customizable, as tweaking the traffic cost values is pointless unless we can also change the heuristic estimate. An heuristic estimate smaller than normal traffic cost invariably results in A* bombs.
- There should be an independent heuristic estimate value 'bonus' for Z-levels, preferably configurable too.

No matter how much you tweak the A* algorithm, it is NOT going to be less than disastrous in it's worst case scenarios, which are common in DF.
A* well configured as listed above is VERY efficient at pathfinding to a reachable target on the same z-level, tweaking it away from that will make it much worse at what it's good at, and barely any better at what it's bad at. Don't do it.
A* well configured as listed above is also much more efficient at pathfinding through non-maze forts, for example using access shafts.

Fixing A* worse case scenarios will require a solution like implementing a node system engineered around vertical access points. I repeat, tweaking A* will not fix anything.

The worst case pathfinding scenarios for DF are:
- Not being able to reach the target.
- Needing to move to a Z-level further away from the target to reach the target.
- Maze like architecture.