Print

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

[numerobis]

We're in agreement on A* v Dijkstra.

It is a waste to do:

Code: [Select]

for each destination, A*(src, dest)
Rather than:

Code: [Select]

A* (src, heuristic, success) where heuristic and success loop over the destinations.

The former will spend lots of time looking for the best path to the very far away destination, whereas the latter will prune the search and stop as soon as it's found the closest one.

[CobaltKobold]

I could think of one or two but they are fringe cases that are closer to a game mechanic than pathfinding.

EDIT: Here is a hint.

And yet...when it's doing that, it won't be looking for paths, so I think it can safely be ignored for groundlings?

I do wonder if there is any way for a [FLIER] to recover from projectile status more than others. but tht's off-topic.

[PencilinHand]

I could think of one or two but they are fringe cases that are closer to a game mechanic than pathfinding.

EDIT: Here is a hint.

And yet...when it's doing that, it won't be looking for paths, so I think it can safely be ignored for groundlings?

I do wonder if there is any way for a [FLIER] to recover from projectile status more than others. but tht's off-topic.

In response to your question, it is likely that Toady would handle all potential situations such as that(or something like a bird losing its wings while flying and fighting) with the physics engine.   That is why I said it was closer to a game mechanic than relevant to pathfinding but could give cause for a pathable subject to attempt to path from a position which it should not be able occupy(due to a bug, basically).

---------

My mind keep wandering back to how pathfinding through a hierarchy of zones would work and the most economical and useful methods for forming the hierarchy.  Toward that end, I do have a question for shadow_slicer.

1. Is it a necessity or a convenience there for the divisions in the example some pages back to be base 2 or a divisible of 2?

2.  How are zones ensured to be useful without potential misdirection?

Spoiler (click to show/hide)

Suppose a division of 4x4 were used in the following example.  Assume the lower left of one of the zones occurs at the small "x" near the lower left.

Code: [Select]

XXXXXXXX
 X   X   
 X X X X
AX X X X
   X   X 
  XXXXXXX B
 
 xXXXXXXX
Given that the shortest distance between A and B is 11 steps(w. 3 diagonal) without going through the maze.  How does the code keep from selecting the longer path through the maze with zones the size of a 4x4? 

What if the maze had longer halls than the zone size?  How does the code resolve bisected or otherwise impassable access from one side of the zone to the other?  Example, if "|" and "-" marked the outside of a 4x4 zone:

Code: [Select]


------
| XX |
| XX |
| XX |
| XX |
------

------
|XXXX|
|XXX |
| XXX|
|XXXX|
------
Since both example zones would be shown as accessible from the left and the right sides, might this confuse the code and lead to needing to repath?

I have tried to follow the whole thread but I think some of it went over my head due to jargon and I haven't looked into the specific code.  So, I am wondering how the more inconvenient cases are handled.

[shadow_slicer]

1. Is it a necessity or a convenience there for the divisions in the example some pages back to be base 2 or a divisible of 2?

Convenience. With everything evenly divisible things just work out nicely in my testing scripts. I could have used 3 instead of 2 just as easily.

2.  How are zones ensured to be useful without potential misdirection?

Spoiler (click to show/hide)

Suppose a division of 4x4 were used in the following example.  Assume the lower left of one of the zones occurs at the small "x" near the lower left.

Code: [Select]

XXXXXXXX
 X   X  
 X X X X
AX X X X
   X   X 
  XXXXXXX B
 
 xXXXXXXX
Given that the shortest distance between A and B is 11 steps(w. 3 diagonal) without going through the maze.  How does the code keep from selecting the longer path through the maze with zones the size of a 4x4? 

What if the maze had longer halls than the zone size?  How does the code resolve bisected or otherwise impassable access from one side of the zone to the other?  Example, if "|" and "-" marked the outside of a 4x4 zone:

Code: [Select]


------
| XX |
| XX |
| XX |
| XX |
------

------
|XXXX|
|XXX |
| XXX|
|XXXX|
------
Since both example zones would be shown as accessible from the left and the right sides, might this confuse the code and lead to needing to repath?

Zones, (at least in the current gridzone) just contain edge nodes (nodes on the edge of the zone that can lead to other zones). These edge nodes cache paths to all the edge nodes in their zone. The hierarchical A*, basically is just A* over these edge nodes. Of course we also need to add edge nodes for the source and destination temporarily. Since all the edge nodes are used and the path costs come directly from the original graph, this preserves optimality.

[Starver]

26 directions though. When is it ever impermissible for a creature to move to where it already is?

My internal objection to the original figure was that "staying where one is" is never a viable movement option.

Although, I then wondered, could dynamic landscapes ever develop to the point where shifting tiles (elevators (especially paternosters), 'tramway tiles' and man(/dwarf)-rated conveyors, Thunderbird 1 entry styled bridges, even Hogwarts moving bridge/stairways) could reasonably be expected to introduce the "wait until safe to board/alight" movement.

Of course, then pathing would be far more complex.  We are already faced with the near impossibility of navigating "magma-curtain" features (how would the pathing feature know that travelling onto a dwarf-activated pressure pad mean that a viable path will open after within X cycles and close again within Y cycles[1], but otherwise be closed), but then that's a whole different future problem.


[1] Never mind complex interactions of other dwarfs/invaders/pets/cat-powered-RNG-pressure-plates upon any system.

[Sunken]

2.  How are zones ensured to be useful without potential misdirection?

Spoiler (click to show/hide)

Suppose a division of 4x4 were used in the following example.  Assume the lower left of one of the zones occurs at the small "x" near the lower left.

Code: [Select]

XXXXXXXX
 X   X   
 X X X X
AX X X X
   X   X 
  XXXXXXX B
 
 xXXXXXXX
Given that the shortest distance between A and B is 11 steps(w. 3 diagonal) without going through the maze.  How does the code keep from selecting the longer path through the maze with zones the size of a 4x4? 

What if the maze had longer halls than the zone size?  How does the code resolve bisected or otherwise impassable access from one side of the zone to the other?  Example, if "|" and "-" marked the outside of a 4x4 zone:

Code: [Select]


------
| XX |
| XX |
| XX |
| XX |
------

------
|XXXX|
|XXX |
| XXX|
|XXXX|
------
Since both example zones would be shown as accessible from the left and the right sides, might this confuse the code and lead to needing to repath?

Zones, (at least in the current gridzone) just contain edge nodes (nodes on the edge of the zone that can lead to other zones). These edge nodes cache paths to all the edge nodes in their zone. The hierarchical A*, basically is just A* over these edge nodes. Of course we also need to add edge nodes for the source and destination temporarily. Since all the edge nodes are used and the path costs come directly from the original graph, this preserves optimality.

Optimality is not preserved if there's only one node per edge, mind; indeed, hierarchical A* is not optimal.

[shadow_slicer]

Optimality is not preserved if there's only one node per edge, mind; indeed, hierarchical A* is not optimal.

In the current zoneManager implementation there are as many nodes per zone edge as there are tiles on the edge (eg. 1 node for each tile with at least one edge leaving the zone), so it is still optimal.

[PencilinHand]

Optimality is not preserved if there's only one node per edge, mind; indeed, hierarchical A* is not optimal.

In the current zoneManager implementation there are as many nodes per zone edge as there are tiles on the edge (eg. 1 node for each tile with at least one edge leaving the zone), so it is still optimal.

So then, for example, in a simple open(no obstructions, no z axis considerations) 4x4 there are 12 nodes/tiles around the edge and each node caches a path to every other node in the same zone.

11+10+9+8+7+6+5+4+3+2+1=66 cached paths with an average length of ~3 for a simple open 4x4 zone.  Is this right?

[shadow_slicer]

Optimality is not preserved if there's only one node per edge, mind; indeed, hierarchical A* is not optimal.

In the current zoneManager implementation there are as many nodes per zone edge as there are tiles on the edge (eg. 1 node for each tile with at least one edge leaving the zone), so it is still optimal.

So then, for example, in an open(no obstructions, no z axis considerations) 4x4 there are 12 nodes/tiles around the edge and each node caches a path to every other node in the same zone.

11+10+9+8+7+6+5+4+3+2+1=66 cached paths with an average length of ~3 for an open 4x4 zone.  Is this right?

The current version is both worse and better than that would imply. It's worse than that because the path cache is stored directionally (though only calculated once for each direction), so all nodes have their own copy. Additionally nodes have paths to their adjacent neighbors in other zones, so there would be a total of 168 cached paths, of average length ~2.14. 

It's actually better than it seems because 1) we don't usually deal with zones smaller than 8x8, and 2) the cache is actually calculated on demand, so paths that aren't ever considered won't be calculated or stored in cache. Since the cache is filled on demand, a zone in a completely open area will probably only have to calculate a single path (if not yet cached) each call. Further this path would simply be a portion of the path non-hierarchical A* would have needed to calculate anyway.

Anyway, I'm thinking in the long run, we'll probably have to sacrifice optimality. The current implementation uses too much memory and is only twice as fast as A* for a typical load. We really need to use less memory and calculate paths faster, which is not really possible if we want to maintain optimality.

[PencilinHand]

The current version is both worse and better than that would imply. It's worse than that because the path cache is stored directionally (though only calculated once for each direction), so all nodes have their own copy. Additionally nodes have paths to their adjacent neighbors in other zones, so there would be a total of 168 cached paths, of average length ~2.14. 

It's actually better than it seems because 1) we don't usually deal with zones smaller than 8x8, and 2) the cache is actually calculated on demand, so paths that aren't ever considered won't be calculated or stored in cache. Since the cache is filled on demand, a zone in a completely open area will probably only have to calculate a single path (if not yet cached) each call. Further this path would simply be a portion of the path non-hierarchical A* would have needed to calculate anyway.

Anyway, I'm thinking in the long run, we'll probably have to sacrifice optimality. The current implementation uses too much memory and is only twice as fast as A* for a typical load. We really need to use less memory and calculate paths faster, which is not really possible if we want to maintain optimality.

I had a feeling it was going to be something like that.

I do have an idea that might keep perfect to near perfect optimality by carefully managing and taking advantage of zone definitions.  Assuming the idea can work at all and isn't completely baseless with regards to CPU and memory considerations. 

Let us set that aside for the moment, though.

------

Aside from the inter/intra zone node caching, how are the paths cached?  What I mean is, are zone meta-paths cached or are the semi-explicit tile paths cached?

-------

I am sorry for these odd questions.  I have coded in C++, Java, and different flavors of Basic before but don't have the time(read as the willpower to learn more about C++) to really dig into and wrap my head around code someone else wrote.

[shadow_slicer]

Aside from the inter/intra zone node caching, how are the paths cached?  What I mean is, are zone meta-paths cached or are the semi-explicit tile paths cached?

The only path caching currently implemented is between the border nodes on the edge.

I am sorry for these odd questions.  I have coded in C++, Java, and different flavors of Basic before but don't have the time(read as the willpower to learn more about C++) to really dig into and wrap my head around code someone else wrote.

It's fine, really. This is a really hard problem, and I had to think carefully to come up with even the imperfect prototype we have now. The more we talk about it, and the more we think about it, and the closer we come to a good solution.

[atomfullerene]

When is it ever impermissible for a creature to move to where it already is?

I could think of one or two but they are fringe cases that are closer to a game mechanic than pathfinding.

Here's a good one:  If you use a hatch to drop a dwarf on top of a tree, he'll just stand there 1 z-level above it, not climbing down or anything.  But if you build a floor next to him on the same z-level, he'll walk right off onto it.  But he won't ever walk onto a tree.

[PencilinHand]

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.

Spoiler (click to show/hide)

Code: [Select]

-----
|...|
|...|
|...|
-----

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.

Spoiler (click to show/hide)

Code: [Select]

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

Spoiler (click to show/hide)

Code: [Select]

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

Spoiler (click to show/hide)

Code: [Select]

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

Spoiler (click to show/hide)

Code: [Select]

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.

Spoiler (click to show/hide)

This:

Code: [Select]

.........
.......X.
.......X.
.......X.
.b.....X.
.......X.
.......X.
.XXXXXXX.
.Xa......
Can, for the purpose of pathing, be thought of roughly as follows.

Code: [Select]

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

Code: [Select]

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.

[shadow_slicer]

That's certainly an interesting idea. The subzone portion sound similar to the "Memory Efficient Pathfinding" paper Impaler linked to earlier.

I do have a few criticisms of your method:

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 **.

This isn't really true. The path length through one of your 3x3 zones could be as little as 1, or as much as 5. This means that the path found can be more than twice the optimal path length. Additionally, I don't think your method supports non-uniform path costs.

Also, you're only reducing the graph by a factor of 3. The overhead from keeping track of the new abstract graph (and its subgraphs) is likely to be larger than any gains you have from abstraction. I don't see a way to easily increase the amount of abstraction, so I'm not sure we can solve this without significant changes.

[Impaler[WrG]]

Were getting close to doing our first real searches on DF map data which will be a big accomplishment (a DF map is many hundreds of times larger then the test maps Shadow_slicers code uses).  Were going to allow manually placed start and goal locations and provide an output of the speed and efficiency of the search.  From their we can iterate and get progressively better performance.