Print

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

[Starver]

Why not a SPZ(Single Path Zone) to complement the TCZ. It would cover any area with exactly two exits, and cache the fastest path between them. Pathing within it would use A*.

Two exits as in two exit-tiles, or two 'walls of exit'?

Sorry, probably a stupid question, but I've been looking at a problem related to travel over several (ostensibly linearly-connected) zones where the width and placement of the apertures reduces the triviality.  (Not merely the Z-bending situation.)

Although as long tunnels/causeways (and long straight tunnels being a nicer case, but not exclusively so) are one of the common features of a DF setup (alongside open countryside and rectangular rooms) and these have a single-tile aparture (and you can possibly also add long tunnel systems that are the sole entry/exit for rooms along their length), maybe it's not an issue.

[qwertyuiopas]

Single-tile.

Code: [Select]

############################
#     ######################
#     #####      ###########
#                 ##########
#######            #########
#######            #########
#######     #               
#######  #     #############
########   # #   ###########
#########       ############
############ ###############
############ ###############
Could be seen as a single SPZ containing many lesser zones, but as one(or more) node up the heiarchy(I think), it could reduce massive quantities of pathing, as long as neither endpoint is inside of it.

As the lowest level, it would take the place of multiple lesser zones in an arbitrarily shaped single tile corridor, or as in the example, a parent node to many other types to represent a more complex room.

It could be firther expanded to a Limited Exit Zone, that has N exits, and stores a path between each, but only exists if all exits are single tile.

[Starver]

Single-tile.
<snip>

Now, I think there's merit in something there.  (If not for the system being worked on, another one.)  Assuming your Zoning system likes differently 'headered' zones, they can be packed and optimised better, and (if push comers to shove) travel between points within such a convoluted zone can be left to ad-hoc calculation (assuming that there's not such a regular occurance that it deserves to be put upon and stay in any cache) as the load per-calculation would be trivial.

On a tree-of-meta^N-nodes model, no differentiation would be necessary, as it could be a single 'tile' in the first meta-organisation, and storing the popular entrance->exit route(s, i.e. bi-directional) probably as the main contents of any internal cache (followed by workshop or lever from/to each entry/exit, where applicable).

(Not that I think the meta-node would be exactly that area, but I know your diagram is an interesting example partially designed for expediency of drawing.  At a quick count, although I am not an algorithm and so might not be reading it the same, I can see three "TCZ-like" zones, not counting entry and exit corridors, which might be give themselves up to being part of a meta-zone roughly covering the area you give.  Unless "diggable routing" concerns arise, when at six 'underground traversal' ones (not counting the NW corner and a small number of tiles that might be technically a zone, or at least an overlap of zone) you may have a different number of non-underground ones to give edge-to-edge or one-tile-border connectivity, according to how you can arrange your B-Line joins.)

[Sunken]

This is interesting. The question is, how to create the clustering and when to cut off. Your illustration looks clear-cut, but what is the precise criterion that says we stop at this, and don't include parts of the corridors as well - say one of them has a bunch of single-entrance rooms along it, so that we can choose between a bigger 2-exit zone and a smaller one; how do we decide when we're satisfied?

[shadow_slicer]

In case anyone's wondering, I'm still playing around with the same code  from before. I've implemented hierarchical A* with a few of my own optimizations. I have implemented two zone algorithms: one where each tile is a zone (for debugging), and a grid based scheme that just blindly places NxNx1 zones based on location. So far the benefits have been somewhat limited (although that is probably due to the test cases I'm using.

For the curious, my code is available on my personal webspace, though it's still in-progress. There's some sort of bug in the hierarchy code that makes it return a suboptimal path (depending on grid size).

Spoiler (click to show/hide)

This shows two levels of the TestFort1 test case.
Green is start. Blue is destination.
Light blue shows where all paths are together.
Yellow is the optimal path (taken by most grid sizes).
Red shows the path taken with a grid size of 10 or 20.
Orange shows the path using a grid size of 19.

[zchris13]

That looks exactly like the patterns I tend to slap down for my hallways.

[SmileyMan]

Haven't had the time to read the whole thread, but has anyone mentioned "pheromone"  style caching for the pathfinding?  Could be useful for a colony-style game like DF.

Also, when it comes to dividing zones, why not leverage user brainpower and divide zones based on door placement?  Any one door has zone a on one side and zone b on the other (zone a and b may of course be the same).  A bit of smart map searching could look for known door-like construction patterns as well.

[zchris13]

Yeah. Start indexing common fort designs from the archives, and analyze them.  Start with doors.  If I could get more technical than that to help, I would, but sorry.  Just... patterns. You know.

[Silverionmox]

Haven't had the time to read the whole thread, but has anyone mentioned "pheromone"  style caching for the pathfinding?  Could be useful for a colony-style game like DF.

In eternal voting as: "Automatically adjust pathfinding for traffic".

Also, when it comes to dividing zones, why not leverage user brainpower and divide zones based on door placement?  Any one door has zone a on one side and zone b on the other (zone a and b may of course be the same).  A bit of smart map searching could look for known door-like construction patterns as well.

I agree that we should use the player's brain cycles whenever we can, especially since doors, zones etc. are likely concentrated in areas where the most dwarves and hence the most pathfinding requests are.

[Shades]

Haven't had the time to read the whole thread, but has anyone mentioned "pheromone"  style caching for the pathfinding?  Could be useful for a colony-style game like DF.

The only way this really works is a combination of allowing full pathfinding some of the time (even as low as 1 in every hundred times) to force capture of new pathways and to store a pheromone map rated for each game task (or at least each related set of tasks).

No reason it can't be tested the same way as other methods though

[SmileyMan]

Was thinking some more, and while the traditional "pheromone per task" design would seem obvious, the massive number of tasks would likely make this pointless.

But, if we re-imagine the map as a series of subdivisions, then we could make the pheromone data universally applicable, based on subdivision heirarchy.

A Small 2D example

First, a standard Cartesian coordinate map

Code: [Select]

11 12 13 14 15 16 17 18
21 22 23 24 25 26 27 28
31 32 33 34 35 36 37 38
41 42 43 44 45 46 47 48
51 52 53 54 55 56 57 58
61 62 63 64 65 66 67 68
71 72 73 74 75 76 77 78
81 82 83 84 85 86 87 88

And here it is, as a binary subdivision map, divided xyxyxy

Code: [Select]

000000 000010 001000 001010 100000 100010 101000 101010
000001 000011 001001 001011 100001 100011 101001 101011
000100 000110 001100 001110 100100 100110 101100 101110
000101 000111 001101 001111 100101 100111 101101 101111
010000 010010 011000 011010 110000 110010 111000 111010
010001 010011 011001 011011 110001 110011 111001 111011
010100 010110 011100 011110 110100 110110 111100 111110
010101 010111 011101 011111 110101 110111 111101 111111

Critter 1, starting at (7,7) wants to move to (2,2).  There are no pheromones
stored at (7,7), so it gets a path from the standard pathfinder, which will
trivially be 77->66->55->44->33->22

At each of those tiles, it places a marker, containing the final destination,
and the direction of travel.  The destination is stored as the most significant
different bit pair from the current coordinate:

Code: [Select]

(7,7) -> 111100
(2,2) -> 000011
Stored:  110000 = (-1,-1)

(6,6) -> 110011
Stored:  110000 = (-1,-1)

(5,5) -> 110000
Stored:  110000 = (-1,-1)

(4,4) -> 001111
Stored:  001100 = (-1,-1)

(3,3) -> 001100
Stored:  001100 = (-1,-1)

(2,2) = Destination

Critter 2, starting at (6,6) wants to move to (3,1).  The subdivision coordinate
for (3,1) is 001000, and therefore the most significant bit pair from (6,6) is
110000.  There is already a marker on (6,6) telling us how to move to 110000, so
we don't need to go to our expensive pathfinder.  The movement goes as follows:

Code: [Select]

(6,6) -> 110011
(3,1) -> 001000
Search:  110000
Found:   110000 = (-1,-1)

(5,5) -> 110000
(3,1) -> 001000
Search:  110000
Found:   110000 = (-1,-1)

(4,4) -> 001111
(3,1) -> 001000
Search:  000100
Not found!

So we go to the pathfinder for a path from (4,4) to (3,1), which will be something
like twice as fast as finding a full path from (6,6) to (3,1).  The path returned will be
44->33->32->31, so we place markers as before:

Code: [Select]

(4,4) -> 001111
(3,1) -> 001000
Stored:  000100 = (-1,-1)

(3,3) -> 001100
Stored:  000100 = (0,-1)

(3,2) -> 001001
Stored:  000010 = (0,-1)

(3,1) = Destination.

Critter 3, wanting to travel from (7,7) to (3,1) will now follow markers all the way, and will make no pathfinder calls at all.

For each tile, it makes sense to store a limited number of markers in a cache,
depending on memory usage.

The nice thing about this is that while there is a chance of a sub-optimal path,
it will create quite naturalistic behaviour in that dwarves follow the paths other
dwarves make.

I hope the above makes sense.  Given that it's obviously optimal in square areas
of power-of-two edge length, it might be best as a sub-routine for final delivery
within the (existing?) 64x64 regions, and then a macro path-finder can find routes
for the inter-region transport.

I'm sorry I don't have the time to stick some code behind this.

PS - I never did formal Computer Science, but if any compscis out there can tell me if this has been done before, that would be nice!  If not, I henceforth name it the SmileyMan Algorithm!!!!!! 

[Sunken]

The Department for Unwanted Enlightenment would like to inform the readers of this thread about the word Stigmergy.
That is all.

[Silverionmox]

The Department for Unwanted Enlightenment would like to inform the readers of this thread about the word Stigmergy.
That is all.

That just closed my browser.

[Starver]

The Department for Unwanted Enlightenment would like to inform the readers of this thread about the word Stigmergy.
That is all.

Of course, we're dealing with globally-omniscient agents.  Given that we have these[1] and not limited-knowledge agents with[2] or without[3] communicative learning, Stigmergy isn't relevent to the current situation, though I know it would be an interesting thing to put into the world simulation.  With associated change of game balance.


[1] "Oh, I feel sad.  I need to speak to the Mayor.  He's deep in the caverns and I will now calculate how to get to him, and recalculate arbitrarily to his new position he moves around, despite being way beyond my vision or hearing."

[2] "Hoi!  Freind McMiner, I have been tasked to cut some fine amethyst, and I understand that you can tell me down which long tunnel they may be found...  Pray tell me, good sir, which way hither?"

[3] "Where is that log?  Where is that log?  I've been asked to get a log, and I don't know where it is.  It wasn't to the east of this wall last time I looked, but is it there now....  No, first I'll check the northern forests.  It may be there..."


[edit@Silverionmox: Didn't close mine, F.Y.I.  Try again, reboot machine, check browser... Probably not Wiki's fault, unless it's a Compatability Mode issue.]

[shadow_slicer]

In case anyone's wondering, I'm *still* playing around with the same code  from before. I've implemented multi-level hierarchical A* with a few of my own optimizations. Currently the only real Zone/Hierarchy method implemented places square zones in a grid so that they are 1 z-level high and length long and wide. For the curious, my code is available on my personal webspace, though it's still in-progress.

I am running three test cases and measuring the time it takes to calculate 100,000 random paths with different hierarchies. A plot of the initial results is shown in the spoiler below.

Spoiler (click to show/hide)

The hierarchies were defined in terms of the Maximum Zone Size (at the highest level), the ratio of the current zone size to the zone size of the next zone down, and the Minimum Zone Size allowed. In the plot they are listed in Max-Ratio-Min notation.
For example, 128-2-8 corresponds to a hierarchy with zones lengths as follows: 128, 64, 32, 16, 8. Similarly 64,8,2 should be: 64, 8. Note that the minimum zone size is not necessarily the size of the smallest zone.

Plotted on the left of the figure is the A* performance. The TCZ test case consisted of a wide open region that was trivially connected. The TestFort test case consisted of a small fort. The Maze test case consisted of a maze. Note that for both the TestFort and the Maze the hierarchical method has a configuration that is around twice as fast as simple A*. For the TCZ case, the hierarchal implementation offers similar performance.


This scenario is similar to the previous, except that after every 100th path, a tile was marked as having changed. This tests how the pathing algorithm performs on changing topologies.