I don't think anyone really gets your 'highway' concept (though I do think it would be useful). How exactly is the computer supposed to figure out where those traffic patterns go, anyway?
The game has to store a "path width" (which would be necessary for vehicles, anyway) for the nodes, and prefer to travel down the far right side. If you have a three-tile-wide rectangular hallway, the dwarves would prefer to stay on the right hand side of that hallway, given their current direction of movement, hence making opposing traffic stay on either side of the hallway, the way that cars stay on the right (or left in certain countries) when driving down a road to prevent traffic collisions.
Putting a traffic jam-solving method into the pathfinding would be a relatively minor burden on pathfinding time, provided it is set up correctly, and would give a performance boost in actual navigation when dwarves stop bumping into one another all the time, and having to pathfind around one another.
For comparison, worst-case for unaided A* is a wide, contiguous up/down stair column, so YMMV.
Isn't a giant field of up/down stairs the
best case for A*? You'd have a direct line of sight to wherever your destination is, meaning just picking the first tile that the heuristic will lead you to choose will always be the best choice, meaning you'd never have to do a double-back.
Technically, A*'s worst case is pathing to a completely blocked path or the like, where it functionally flood-fills, aborts, and tries again next frame, but the sort of thing that others were posting a couple posts ago is the next-worst, I.E. this:
##################
#s+++++++#d++++++#
#+##############+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++++++++++#
#++++++++++++++++#
##################
This is the worst case because every time, the heuristic will trick the program into trying to go down each and every one of those dead-ends, thinking that it is a possible path to the exit.
Regarding those hell maps, they are still better than unaided A*. The worst case scenario for the convex polygon method is still half as intensive as unaided A* (it does gain that at the cost of greater memory overhead), and looks like this:
##################
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
##################
Also, I have a diagonal version of the notched corridor that I'm puzzling over. Ideal packing is one large node in the bottom corner, and successively smaller nodes adjacent to it, with 1x1 nodes only between larger nodes (think Sierpinski triangle). I don't know how to get that, though. On the other hand, I don't think ideal packing is ideal for pathing (at least via the funnel algorithm), so it may not matter.
##################
################.#
###############..#
##############...#
#############....#
############.....#
###########......#
##########.......#
#########........#
########.........#
#######..........#
######...........#
#####............#
####.............#
###..............#
##...............#
##################
And kaenneth, try to keep convex nodes, otherwise intra-node navigation needs A* to work.
Now, a giant triangle is the exact sort of convex node shape that works very well for this sort of thing.
The thing I'm asking is,
is it really worth it to remove A* if we build node maps that are horribly complex because we're all using rectangles?
Yes, A* uses up cycle time, but if we make a map that has 80,000 nodes in it because we have so many one-tile nodes, you're probably going to need to use A* or something to even navigate the node map in the first place, completely nullifying the point of the whole operation.
Rather, if we are going to have hierarchical node structures, we need to make the hierarchical nodes fast to search paths through, as well, and that means that it can be worth some inefficiencies in building the nodes in the first place to be able to make less 1-tile-nodes or fractured nodes like having the entire triangular room split into horizontal rectangles, where every step is pathing into the next node, anyway.
Now, for the statue hallway, ignore the fact that they are statues for a moment, in fact, ignore the alcoves, as well.
Let's just imagine a big square room with one tile of natural wall in the middle.
Should we divide this room up into four separate nodes? Or should it just be one big node where we give the dwarves the ability to path around the obstacle if they happen to go towards it?
Again, the problem with A* is not finding its way through mostly open areas, it's preventing A* from going down dead ends. If you just find the dead ends and mark them off, A* works perfectly well. That's all the hierarchical/nodal structure needs to do - zoom out to an abstract model, and find the zones that are the "leaf nodes" that are dead ends, the "branch nodes" that provide access to some local areas, and the "trunk nodes" that are the main throughfares that serve as the access points to all the other portions of the fortress.
Now, the complexity of the system that divides up the rooms is a major sticking point - it needs to be fast enough that the computer doesn't spend more time dicking around looking for a "perfect" set of nodes than it does pathfinding in the first place, and it also needs to conserve on memory as much as it can, but these are all tradeoffs that should be balanced, rather than going for maximizing any one to the exclusion of all others.
Or you could limit it to only 45 degree angle lines. That would get you some non-grid convex shapes without having to go into complex math.
This is probably the simplest, fastest method of merging larger nodes. Just make sure that there is a pathway to and from any given point in a grid using no more than a single "turn" of 45 or maybe 90 degrees. Yeah, it means something like A* would have to be used, but as long as you have a very simple pathway from one end of a node to the other, that will never be much of a problem.
Of course, there's also a way to try and make the sort of stored pathways of a certain width, which may help with making that "highway" method of trafficking. That means purposefully storing the width of specific nodes that you expect to get high traffic.