Print

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

[NW_Kohaku]

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.

- 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))

I'm sorry, but what, exactly, is the reasoning behind this?

I can assure you that stairwells are anything but rare in many fortresses, and not all fortresses by any means use a "Central Stairway" approach to construction.

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.

Yes, well, that's sort of what's been said throughout the thread on everything but the first proposals sockless made, excepting the "engineered around vertical access points" part, since you can't assume that vertical access points mean anything.

[Phoebus]

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.

- 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))

I'm sorry, but what, exactly, is the reasoning behind this?

I can assure you that stairwells are anything but rare in many fortresses, and not all fortresses by any means use a "Central Stairway" approach to construction.

Every single fortress use the central stairway approach, it's just that some have more than others.
Why?
Because, literally, you can't build on vertical movement tiles, while even vertical movement tiles are horizontal movement tile, .
So, literally, all fortresses need to build their stuff next/away from vertical access tile, and the majority of that 'stuff' will not block horizontal movement.

Unless you want to build a fortress that specificaly designed to be a maze, your fortress will be much easier to navigate horizontally than it will be vertically.

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.

Yes, well, that's sort of what's been said throughout the thread on everything but the first proposals sockless made, excepting the "engineered around vertical access points" part, since you can't assume that vertical access points mean anything.

Because, I'm being pragmatic.
Any node system needs nodes.
There's no reason a node system would need to replace A*, supplementing it is far wiser.
If DF uses both a node system and a A*, it would be stupid to optimize the node system to solve the pathfinding problems that A* is already able to solve efficiently.
What A* can't handle efficiently are large/complex obstacles. 3D maps can increase both the size & complexity of obstacles exponentially.
Hence the worst case scenarios for A* will invariably involve Z levels, which requires vertical access points.
So by using vertical access points as nodes, you end up using the node system when and where you usually need it the most.

But sure, you can try to design an algorithm to find navigation nodes in a complex 3D maze of rooms, that could be more effective at pathfinding.
But see how designing that system goes for you and how much Toady cares about the 'solution'.

[NW_Kohaku]

Every single fortress use the central stairway approach, it's just that some have more than others.
Why?
Because, literally, you can't build on vertical movement tiles, while even vertical movement tiles are horizontal movement tile, .
So, literally, all fortresses need to build their stuff next/away from vertical access tile, and the majority of that 'stuff' will not block horizontal movement.

Unless you want to build a fortress that specificaly designed to be a maze, your fortress will be much easier to navigate horizontally than it will be vertically.

This is how I build workshops, so as to be efficient, and control what stones are selected for products.

Spoiler (click to show/hide)

Stockpile floor.

Workshop floor (below stockpile)  There are multiple floors of the same, stacked below.

No matter how much I dig downward, I am only moving my workshops 1 step further away from the stockpile per 6 workshops I build.

I also have a layer of pure soil between the stockpile layer and workshops because I want to preserve the chance to have underground trees, so you can generally assume that trip is more vertical than horizontal. 

Generally speaking, I just segregate my fortress horizontally, and then do my "sprawl" vertically, preferring narrow, yet deep fortresses.

That's just building for a particular form of optimization, however. I wasn't feeling artsy when I was doing that, except to make a hexagon instead of a square, and just made it compact and efficient.  If we want to go for a truly extreme version, we can go look at
Undergrotto once again.

Because, I'm being pragmatic.
Any node system needs nodes.
There's no reason a node system would need to replace A*, supplementing it is far wiser.
If DF uses both a node system and a A*, it would be stupid to optimize the node system to solve the pathfinding problems that A* is already able to solve efficiently.
What A* can't handle efficiently are large/complex obstacles. 3D maps can increase both the size & complexity of obstacles exponentially.
Hence the worst case scenarios for A* will invariably involve Z levels, which requires vertical access points.
So by using vertical access points as nodes, you end up using the node system when and where you usually need it the most.

But sure, you can try to design an algorithm to find navigation nodes in a complex 3D maze of rooms, that could be more effective at pathfinding.
But see how designing that system goes for you and how much Toady cares about the 'solution'.

Actually, there's little reason that a nodal system would really need to see a difference between a horizontal "hallway" and a vertical "hallway" made of stairs.  They theoretically cover the same distance, and dwarves move through them equally.  You're creating artificial barriers to how you generate nodes simply because of your mindset of how z-levels work. 

In fact, since any revised node system should be capable of including proper pathfinding for flying creatures and swimming creatures, the assumption that all creatures will be pathing to points along a flat surface is simply not one you can make - you need to build cubic nodes if you want to allow for a proper swimmer or flier pathing system.

The difference between building a "square" and a "cube" based nodal system is trivial, as has been discussed at length in this thread.

Further, using a node-based system, as I already said, is something everyone agrees to immediately.  The point of contention is how to form and adjust and split those nodes, and how best to organize those nodes.

[Setharnas]

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.

Unless you meant using FP instead of integer values and sqrt(2) for diagonal travel, I really don't see your point here. If you stay with integers, the only possible penalty is a (slightly) higher chance of reaching the point of sign overflow - with higher edge traversal costs nonetheless, not smaller.

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.

I don't think you can really solve that problem with heuristics alone, even though I agree that your suggestion might help a little.

3. The system uses taxicab heuristics, but non-taxicab movement costs. Wtf really.

I assume you mean Manhattan heuristic? That's the term I'm most familiar with, but I think it's the same.

- 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))

But how do you propose to decide when to use which heuristic? I's doable, but you're likely to burn up any computational savings in having to make that decision on each new tile.

Any node system needs nodes.
There's no reason a node system would need to replace A*, supplementing it is far wiser.
If DF uses both a node system and a A*, it would be stupid to optimize the node system to solve the pathfinding problems that A* is already able to solve efficiently.
What A* can't handle efficiently are large/complex obstacles. 3D maps can increase both the size & complexity of obstacles exponentially.
Hence the worst case scenarios for A* will invariably involve Z levels, which requires vertical access points.
So by using vertical access points as nodes, you end up using the node system when and where you usually need it the most.

A node system cannot replace A* - they are two different things.

Node system = representation of an abstract graph structure.
A* = one type of search algorithm across a graph structure.

DF already has a node system built-in - the tile grid. There is actually no way around this, as long as DF keeps using a non-continuous space. A* is just one way to search across that, but it is a provable good choice, because pretty much any other way has a much worse ratio of "good in some cases / bad in other cases". It hasn't been the de facto general search algorithm of choice for four decades for no reason.

You are correct that optimizing the parts of the graph representation that A* already deals well with would be stupid. That's why large parts of this thread focus on A*'s weaknesses:

• high search space complexity
• high amount and randomness of memory access
• heuristic being the only way to provide guidance to the search

The focus has been on introducing a hierarchical or tree structure to the graph representation:

• partitioning the search space (by separating it into areas that can be searched across individually)
• simplifying the graph for better cache locality (by compressing the low level grid that's already present into a smaller higher level graph, where individual nodes may represent / expand to multiple nodes or whole areas on the low level graph)
• 'directing' and 'culling' the search (by first running a search across the high level graph and using the result to sort out low level nodes that don't have to be looked at)
• 'smartifying' the graph (by making dead ends on the low level graph stand out as single or at least few nodes on the high level one, so the high level A* pass won't have to expand as many nodes)

And optimizing the z-level connectivity is trivial in a node system, because it is abstract by nature - A* doesn't care if the search graph has edges representing 2, 3 or 42 dimensions; that's just a question of how much time and memory you can afford to throw at it.

But see how designing that system goes for you and how much Toady cares about the 'solution'.

Actually, the whole PF problem isn't even what I would guess to be the main problem of the game. Nor the single threadedness, or the exclusive 32bit compiling. All of these are nothing against the sheer amount of memory shuffling going on - optimizing that is where I put my money.

[Phoebus]

Every single fortress use the central stairway approach, it's just that some have more than others.
Why?
Because, literally, you can't build on vertical movement tiles, while even vertical movement tiles are horizontal movement tile, .
So, literally, all fortresses need to build their stuff next/away from vertical access tile, and the majority of that 'stuff' will not block horizontal movement.

Unless you want to build a fortress that specificaly designed to be a maze, your fortress will be much easier to navigate horizontally than it will be vertically.

This is how I build workshops, so as to be efficient, and control what stones are selected for products.

Spoiler (click to show/hide)

Stockpile floor.

Workshop floor (below stockpile)  There are multiple floors of the same, stacked below.

No matter how much I dig downward, I am only moving my workshops 1 step further away from the stockpile per 6 workshops I build.

I also have a layer of pure soil between the stockpile layer and workshops because I want to preserve the chance to have underground trees, so you can generally assume that trip is more vertical than horizontal. 

Generally speaking, I just segregate my fortress horizontally, and then do my "sprawl" vertically, preferring narrow, yet deep fortresses.

That's just building for a particular form of optimization, however. I wasn't feeling artsy when I was doing that, except to make a hexagon instead of a square, and just made it compact and efficient.  If we want to go for a truly extreme version, we can go look at
Undergrotto once again.

Your workshop example are perfect example of completely trivial pathfinding that can be handled by A* with absolutely no problem.
They are short & well structured pathways between destination.
Even as extreme as they are, they are all predominantly horizontal. On average your workers walk 6 tiles horizontally, and even if there's a layer of soil/mud in-between, only 2 tiles vertically.
And in your workshop example, you are using central shafts that are the logical and optimal location to build node points on.

Because, I'm being pragmatic.
Any node system needs nodes.
There's no reason a node system would need to replace A*, supplementing it is far wiser.
If DF uses both a node system and a A*, it would be stupid to optimize the node system to solve the pathfinding problems that A* is already able to solve efficiently.
What A* can't handle efficiently are large/complex obstacles. 3D maps can increase both the size & complexity of obstacles exponentially.
Hence the worst case scenarios for A* will invariably involve Z levels, which requires vertical access points.
So by using vertical access points as nodes, you end up using the node system when and where you usually need it the most.

But sure, you can try to design an algorithm to find navigation nodes in a complex 3D maze of rooms, that could be more effective at pathfinding.
But see how designing that system goes for you and how much Toady cares about the 'solution'.

Actually, there's little reason that a nodal system would really need to see a difference between a horizontal "hallway" and a vertical "hallway" made of stairs.  They theoretically cover the same distance, and dwarves move through them equally.  You're creating artificial barriers to how you generate nodes simply because of your mindset of how z-levels work. 

In fact, since any revised node system should be capable of including proper pathfinding for flying creatures and swimming creatures, the assumption that all creatures will be pathing to points along a flat surface is simply not one you can make - you need to build cubic nodes if you want to allow for a proper swimmer or flier pathing system.

The difference between building a "square" and a "cube" based nodal system is trivial, as has been discussed at length in this thread.

Further, using a node-based system, as I already said, is something everyone agrees to immediately.  The point of contention is how to form and adjust and split those nodes, and how best to organize those nodes.

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.

[Phoebus]

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.

Unless you meant using FP instead of integer values and sqrt(2) for diagonal travel, I really don't see your point here. If you stay with integers, the only possible penalty is a (slightly) higher chance of reaching the point of sign overflow - with higher edge traversal costs nonetheless, not smaller.

That has nothing to do with Manhattan vs Diagonal heuristic.
I'm talking about what heuristic are supposed to do: predict as accurately as possible the movement cost from point A to point B.
If the actual default movement cost is 2, but the heuristic calculates (as it currently) that the expected cost per tile of distance is 1, the heuristic is actually ridiculously off-chart and will result with something like this.

Top version uses the natural Diagonal heuristics with a D value of 2. (48 tiles explored.)
Bottom version uses DF's current Manhattan heuristics with a D value of 1. (233 tiles explored.)


Legend: Black = Start. White = Destination. Grey = Viewed but not walked.

Traveling through a tile with a cost value above the heuristic's expected value makes the A* pathfinding algorithm try to find a path around said tile.
The game is currently using the bottom version, and mind you, that's only in 2D. If I could show you in 3D the damage in done by the bad heuristic, it is even more ridiculous. Think a needle vs a top.

[Niseg]

welcome to the endless thread,Phoebus.

using a tablet atm so typing is limited...

if you want I can fix my simulator to double the hueristic but I don't think it would help much. A*  likes getting lost and it easily get confused by hueristic. my approach for solving the complexity is by reducing the distance, and saving common pathes.

this is done by grouping nodes into rooms. all you have to do is to keep track of which room is connected to which and. then A* on rooms. my simulator can do a limitted form of room pathing but it gives up easily because it won't look at rooms 2 blocks away. in decent conditions it reduce a long distance A* to a few short distance A*. Afterwards the path can be smoothed but it's generally pretty good.

the z axis doesn't exist in my program,I can add it but it won't contribute much. a room system can help more and that's what I'm working on. the size and shape of the grid doesn't matter.

I noticed that even with a few user placed fully path cached to eachother you can get a performance boost when a path exists. when it doesn't... you go through worst case of A*....

[Phoebus]

I don't think you can really solve that problem with heuristics alone, even though I agree that your suggestion might help a little.

if you want I can fix my simulator to double the hueristic but I don't think it would help much. A*  likes getting lost and it easily get confused by hueristic. my approach for solving the complexity is by reducing the distance, and saving common pathes.

Combined reply.
This is exactly my point. No amount of A* tweaking is ever going come even close to solve DF's pathfinding problems.
But that's the problem, A* is already heavily tweaked in attempt to solve DF's pathfinding problems.
It's tweaked so bad that even if a good node system is implemented in DF, the cost of using current A* to pathfind between nodes is still going to make the whole pathfinding process cost 2 to 5 time more processing power than it should.

I'm proposing to un-tweak the A* engine back to the actual standard way in which it's supposed to work.

[Setharnas]

...[beautiful Phoebus-diagrams ]...

You are talking about admissible vs. inadmissible heuristics. General rule: having the heuristic overshootunderestimate the cost = admissible, meaning guaranteed shortest path. UnderOverestimation = inadmissible, meaning you get a path, but not a guaranteed shortest, and possibly with an open list like your example. OK; I see what you mean. Just... How did you come to the conclusion that DF uses inadmissible h(x)?

*EDIT* Oops - I messed up badly, switched around the over- and underestimating for admissibility. Estimating less than actual cost keeps heuristic admissible.

This is exactly my point. No amount of A* tweaking is ever going come even close to solve DF's pathfinding problems.
But that's the problem, A* is already heavily tweaked in attempt to solve DF's pathfinding problems.
It's tweaked so bad that even if a good node system is implemented in DF, the cost of using current A* to pathfind between nodes is still going to make the whole pathfinding process cost 2 to 5 time more processing power than it should.

I'm proposing to un-tweak the A* engine back to the actual standard way in which it's supposed to work.

I'm still heavily convinced that PF isn't the real problem in DF, and that a hierarchic search would even pretty much solve the worst case of 'no path exists' - because it would come to the same conclusion in a fraction of the effort it needs in a flat structure. It would be equivalent to having a cut-off depth in the current version equivalent to the number of nodes in the current strongly connected component of the high level graph.


Oh, and Niseg: kudos to you for being the only one in this thread (to my knowledge) who has actually coded up an example. Talk about putting your money where your mouth is.

[Phoebus]

...[beautiful Phoebus-diagrams ]...

You are talking about admissible vs. inadmissible heuristics. General rule: having the heuristic overshoot the cost = admissible, meaning guaranteed shortest path. Underestimation = inadmissible, meaning you get a path, but not a guaranteed shortest, and possibly with an open list like your example. OK; I see what you mean. Just... How did you come to the conclusion that DF uses inadmissible h(x)?

I don't think I was ever arguing admissible (optimal final result) heuristics.
But the current heuristics can potentially be 'inadmissible' when you consider the misuses of Manhattan heuristics in a game with diagonal movement. Optimal paths can be missed by the engine due to that.
Heuristics for diagonals and ramps = 2. Heuristics for diagonal ramps = 3. Movement cost (High Traffic) for those is 1.
But, are optimal paths really that necessary?

Edit: Pure Diagonal heuristic with D = 1 and movement cost = 2:

Definitively not worth the extra cost.

This is exactly my point. No amount of A* tweaking is ever going come even close to solve DF's pathfinding problems.
But that's the problem, A* is already heavily tweaked in attempt to solve DF's pathfinding problems.
It's tweaked so bad that even if a good node system is implemented in DF, the cost of using current A* to pathfind between nodes is still going to make the whole pathfinding process cost 2 to 5 time more processing power than it should.

I'm proposing to un-tweak the A* engine back to the actual standard way in which it's supposed to work.

I'm still heavily convinced that PF isn't the real problem in DF, and that a hierarchic search would even pretty much solve the worst case of 'no path exists' - because it would come to the same conclusion in a fraction of the effort it needs in a flat structure. It would be equivalent to having a cut-off depth in the current version equivalent to the number of nodes in the current strongly connected component of the high level graph.

I can only agree with DF needing search algorithms that scale better.

[Setharnas]

But the game can currently be inadmissible when you consider the misuses of Manhattan heuristics in a game with diagonal movement. Optimal paths can be missed by the engine due to that.

True, diagonal movement needs both cost and heuristic of ~sqrt(2) (can be simplified to 1.4, or even lateral 5 / diagonal 7 if you want to keep integer math), else your diagram happens.

Thinking out loud though... Is that missed path even a non-optimal one, if movement costs the same in every direction? Sure, it may look idiotic if the dwarf walks straight-line NE first, then straight SE, only to arrive on the same y-coordinate as he started from. But if it takes him the same time and number of steps... ? (The path, not the search!)

Heuristics for diagonals and ramps = 2. Heuristics for diagonal ramps = 3. Movement cost (High Traffic) for those is 1.

Did you experiment with the traffic costs? I'd be interested in the !science!.

But, are optimal paths really that necessary?

Not in my humble opinion...

I can only agree with DF needing search algorithms that scale better.

Especially for history, material and item lists.

[NW_Kohaku]

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.

[Phoebus]

But the game can currently be inadmissible when you consider the misuses of Manhattan heuristics in a game with diagonal movement. Optimal paths can be missed by the engine due to that.

True, diagonal movement needs both cost and heuristic of ~sqrt(2) (can be simplified to 1.4, or even lateral 5 / diagonal 7 if you want to keep integer math), else your diagram happens.

Thinking out loud though... Is that missed path even a non-optimal one, if movement costs the same in every direction? Sure, it may look idiotic if the dwarf walks straight-line NE first, then straight SE, only to arrive on the same y-coordinate as he started from. But if it takes him the same time and number of steps... ? (The path, not the search!)

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.

The colors represent time in the pathfinding algorithm. The tiles in the back have an heuristic value of 27-29, if they manage to find a path of high traffic to the destination they will keep that heuristic value up to the destination and beat the direct normal cost paths (which will end with a cost of 30).

Heuristics for diagonals and ramps = 2. Heuristics for diagonal ramps = 3. Movement cost (High Traffic) for those is 1.

Did you experiment with the traffic costs? I'd be interested in the !science!.

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.

But, are optimal paths really that necessary?

Not in my humble opinion...

I agree with the sentiment about dwarves needing to think.
But delayed pathfinding (unless there's some techniques I do not know) will incur large memory penalties and will most likely lower performance even further due to cache hits.

I can only agree with DF needing search algorithms that scale better.

Especially for history, material and item lists.

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.

[Niseg]

Combined reply.
This is exactly my point. No amount of A* tweaking is ever going come even close to solve DF's pathfinding problems.
But that's the problem, A* is already heavily tweaked in attempt to solve DF's pathfinding problems.
It's tweaked so bad that even if a good node system is implemented in DF, the cost of using current A* to pathfind between nodes is still going to make the whole pathfinding process cost 2 to 5 time more processing power than it should.

I'm proposing to un-tweak the A* engine back to the actual standard way in which it's supposed to work.

I'm not sure what simulator you are using , mine is JS and I can change it to serve dinner but it doesn't show the nodes it adds to the queue (I can change a* function to keep track of that). All it does is count the visited nodes. And on a trivial straight line path with a good vector heuristic and no obstacle it always visit the number of nodes the length of the path. Sure it does have major penalty - O(n) find minimum cost.  This is why the node grouping approach is the leading solution to the complexity reduction.

here is one example(link to this maze in my simulator):

Spoiler (click to show/hide)

-  top left pure A* ( no traffic ) is   - 812 node visits is too much
- top right is room based navigation - 13 node visits  which is a lot  less complex. R has the gray paths to eachother and A* between the closest node to start  and closest node to destination. It first find paths to an R1 and from an R2  , and then find path between them if there is no path it gives up. having a 4X4 grid reduce the penalty for no path to something more acceptable.
- bottom left is waypoint pathfinding - 'w's have a full cache - better but zigzags much like room navigation but more because of less wps.
- bottom right is the same as the one on the left but it's smoothed using a line of sight algorithm.

edit:updated link to backup site

[warman45]

obviously creating two different algorithms (vertically locked, and flying/swimming) would help (also remove the unnecessary vertical components for most animals and dwarfs at a negligible increase in program space.)

one thing i have noticed about the A* approach (and probably most others) is the exponential increase in calculations over greater distance (due to the exponential increase in path options, most of which are redundant and unnecessary)

there are two suggestions i have. one would help a lot for pathing in a fortress. by breaking the fortress down into rooms separated by doors, you could simplify the code by using a macroscopic version to calculate what rooms you need to go to, and a microscopic one for pathing through each room. even if it needs to preform the same amount of pathing checks it won't have to do them all at once, only once every time the object enters the room, spreading the lag more evenly. this also means numerous shorter distances instead of one long one minimizing the exponential growth in possibilities ( i know it is better then exponential but the algorithm hates distance. you could even use memory to store the path from one end of the room to the other (though this would have to be compiled and called on when needed because RAM is taxed as it is (i think))

the other method is a modified A* (don't kill me) i have a Wikipedia understanding of A* (meaning i looked at the Wikipedia animation) using the animation as an example, the program traces a line towards it's target. the line hits the wall, and instead of expanding from there, it follows the wall in both directions until one becomes free to move again. the program then begins to trace between these points, and if it collides again it repeats this task. then, after it arrives, it begins to continue it's course. i might create an example when im not exhausted and can think.