Everyone is allowed one wall of text in this thread, right?
Seriously, this is a bit dense to explain(there may be one or more MAJOR logical errors I am not seeing as well) so I am warning you to get comfortable before you start reading.
Suppose we have a 3x3 grid of tiles.
-----
|...|
|...|
|...|
-----
Continuity is guaranteed(that is that all pathable tiles are connected) within this grid if and only if the center tile is not blocked. This should be easy to check for.
-----
|...|
|.X.|
|...|
-----
If the center tile is blocked, and if any two of the four cardinal points are blocked then there may be a pathable tile that is not connected within the grid. This too should not be difficult to check for.
-----
|.X.|
|.XX|
|...|
-----
If this 3x3 grid were then split along the division to form an L and a 2x2 cube then they would be pathable within themselves. If the geometry ever changes(suppose the center becomes unblocked) then the whole grid could be checked and merged back together. A check for this should be relatively simple(knowing that 3x3 should start at xyz coordinates).
Of note: At most, a 3x3 grid could be divided into 4 2x2 cube(a sub-zone) with shared walls. So sub-zones would either need to share unpathable tiles or only include pathable ones.
-----
|.X.|
|XXX|
|.X.|
-----
As for connected zones and subzones(preferentially). It only be necessary to note if a zone or sub-zone is connected to its neighboring zones without having to calculate every possible connection. All that is important is that it is or isn't connected. So in the following example, 2 is only connected to 1 and 3 but the number of shared tiles doesn't matter.
1|2|3
-----
4|5|6
-----
7|8|9
-------------
|...|...|...|
|...|...|...|
|...|XXX|...|
-------------
|..X|.X.|X..|
|XXX|XXX|...|
|...|.X.|X..|
-------------
|...|XX.|XXX|
|...|...|...|
|...|...|...|
-------------
Although 4 is connected to 1, 5, and 7, only 4a(the upper sub-zone) is connected to 1 and 4b(the lower subzone) is connected to 5, and 7.
All of this allows for the following assumption. Any given path through one zone or sub-zone to a neighboring zone or sub-zone on the same z-level will cost approximately the same**. So, each zone and subzone can be treated as a if it were an extra large tile itself. With this A* should be able to be run at any level of the hierarchy without resolving down to the explicit per-tile path. Resolve the path to the nearest desired zone size(suppose a 3x3 resolution) then path within each known zone that must be visit and reevaluate the overall meta-path periodically.
I haven't included stairs and ramps in this example specifically as it would confuse the attempted explanation, but they would be treated simply as more neighboring zones though the cost of moving through different z-levels would be scaled.
Under ideal circumstances, this should be able to resolve to perfect optimality. Under less ideal circumstances I think(I haven't proven this to myself) the Delta from perfect optimality should be bound and not deviate frequently nor significantly.
A further advantage that this offers is you can then cache whatever resolution meta-path is desired. Be it on the 3x3 or the 81x81 level.
This is, of course, assuming that the method described in this post is not only possible to implement but more CPU and memory efficient than current methods. Admittedly, I haven't fully thought out all possibilities and shortfalls so this there is probably a major hole in this proposal.
**This isn't necessarily true. The exception(weighing a single tile sub-zone as equal to a 3x3 zone), by my reckoning, should be relatively rare and the difference should be relatively minor on the macro scale.
------------
I hope somebody smarter than me actually reads all of this and gets the idea I am trying to communicate.
Here is some thoughts on zones and subzones.
This:
.........
.......X.
.......X.
.......X.
.b.....X.
.......X.
.......X.
.XXXXXXX.
.Xa......
Can, for the purpose of pathing, be thought of roughly as follows.
.........
.......X._Diagonal not possible here
.......X.......
.......XX .
.b.....XX .
.......XX .
.......XX .
.XXXXXXXX .
.XXXXXXXX a
A way to explain it would be to say that the physical 9x9 zone(that is itself a 3x3 of 3x3s) is thought of as two sets of sub-zones connected but with different 'logical' zones and sharing the same 'physical' zone (or space*).
*Kind of like hard drive partitions, a logically segmented 'physical' medium. There can be many logical drives on one physical drive.
A potentially important question would be to know how many potential sub-zones are possible within a given sized zone. Of those finding out how many are meaningful would also be important.
a...X...a
XXX.X.XXX
....X....
aX.....Xa
XXX.b.XXX
aX.....Xa
....X....
XXX.X.XXX
a...X...a
The above example assumes that for a zone to be a sub-zone it must pass through another 'tile'(at this scale that would be a neighboring 3x3). I was only able to trivially find 8 meaningful(?) subzones. I need to do an analysis at the 27x27 scale before I can draw any conclusions about scalability.
I am not even sure what meaningful really is in this circumstance. I would really need to sit down and hack out code until I ran into a problem I didn't anticipate to find a proper definition(and repeat until it fits). Then pass off the "refined" idea to someone who can code better.
In actual practice, with real forts(anecdotally based on my forts), the number of sub-zones a 9x9 zone is likely to form is generally maybe two or three. Much the same as how a 3x3 zone is likely to form only one or two sub-zones.