No, as I explained, it is you that does not understand that the game has a concept called 'floors', which is not present on the horizontal version as walls need a whole tile. Those 'floors' are everywhere under and over your workshops and rooms, and they are a serious impairment to pathfinding.
If floors did not exist, if dwarves could fly and if buildings could float, then your argument would be valid, but it is not so.
Floors/Z-levels are the primary pathfinding obstacle in the game. By far.
No, as I explained, this needs to be capable of handling flying and swimming creatures, and there is no real benefit to having a pathfinding structure that penalizes vertical travel and makes the game incapable of pathfinding for two modes of travel for a minor optimization under a certain set of circumstances that you are just assuming will be more common.
The gains you are making are trivial, and the costs are serious. It's just not worth it.
Must the game only use a single pathfinding algorithm for all creatures?
(That's a rhetorical question.)
This is the whole point around my argument. The current pathfinding algorithm has been broken to solve problems that it can't really solve. As you put it, serious costs for trivial gains.
The goal of fixing A* is not to fix the pathfinding problem (which it can't), the goal of fixing A* is to have a A* that does it's job, and then let other solutions take care of what A* can't handle.
A solution example that would improve things without breaking A* wouble be to have a different A* heuristics for creatures with different mode of travel.
This is not even some mind-blowing idea, that's just how heuristics are supposed to work.
It's also the reason why I proposed configurable A* settings options, because different fort design have different pathfinding expectancies. While those options will have minor benefits, they are also cheap to implement and have no actual costs as they are options.
That's basically saying your solution to the problem is not to solve the problem.
The reason (or at least one of the reasons) why we can't have multi-tile creatures and vehicles right now is because the pathfinding code doesn't support them. We need serious swimmer and flier pathfinding, because there's a reason why HFS will kill your framerate right now - the clowns are all fliers that use Breadth First Search.
Your tweak doesn't actually solve any problems, and creates larger ones. The way to solve these problems is to use a nodal structure that saves the breadth of passage and required travel mode through the nodes.
When creating a hierarchical data structure that supports storing its permitted travel types (including passage width for multi-tiles), then the hierarchical structure itself can easily handle all forms of travel, and standard A*, if it is necessary at all, assuming we don't use the "convex cube" route, is only used in intra-node travel. This allows every form of movement to easily use the same pathfinding system, doesn't require wheel-reinvention, and actually goes through the necessary step of allowing serious non-land-based travel.
I did a few tunnels with levers, I calculated the heuristic values that way.
One of my first test that left me puzzled was an obstacle course with tunnels.
Strangely enough, the dwarves usually prefer to move through the underground tunnels. The tunnels have exact same traffic settings as overground tiles.
Somehow the dwarves prefer the path that's moving away both horizontally and vertically from the destination.
That only made some kind of sense after I figured the path cost debt caused by the D = 1 heuristic vs. 2 cost normal traffic. Even then that behavior is, even if explainable, still somewhat abnormal as the overland cost should be traced first. It's possible the engine is actually pathfinding several times over the same time (if the second pass has equal or better heuristic estimate), or at least overwriting early tracebacks with later ones of equal travel cost.
Presuming that those ramps are just one z-level down, you actually ARE still returning an optimal path, because the costs of moving diagonally are the same as the costs of moving horizontally.
That far left miner would take 22 steps to reach either lever whether he went through those little tunnels or not.
What you are seeing is just a preference to move diagonally, even diagonally vertically, that is amusingly distracting, but that test doesn't demonstrate actually performing sub-optimal behavior, although it does demonstrate exploitable and somewhat illogical-looking behavior.
Those missed paths could be optimal, movement cost wise, if it managed to connect with a direct path of High traffic (1 cost) tiles to the destination. Very uncommon, and suboptimal step wise.
I'd also have to say that what you are really harping over - the traffic costs - is something that actually has a very simple fix. Either do what the system was meant for you to do, and set all your hallways to be high-traffic zones, which nobody really does, and hence proves this a broken system, or go into the init options, and set standard traffic weighting to be 1.
Do that, and standard traffic weight is now 1, and the heuristic assumes it to be 1, which means there's no problem. You can just use the restricted traffic settings when you really don't want dwarves pathing through a place, like in a bedroom, and maybe crank those traffic weights up while you're at it.
Yes, that's a problem, and it's frankly some real low-hanging fruit, but it's not a problem that anyone is arguing with, and it's not going to solve the real issues.
Author
Topic: Improving Pathfinding. (Computer sciency) (Read 65177 times)