Print

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

[zchris13]

Searching long branching hallways with a central stairwell has always been a major issue.  The zones could really help with this, because hallways are long zones with (usually) doors (fixed entrances and exits) to rooms. You would not have to have the walkers "walk" all the way down the hallway, if you knew the approximate pathcost to each of the doors.  You would only have to skip to the doors, add the pathcost, and go from there (with some sort of "oh look that's the totally wrong direction, don't need to check that broom closet") for each of the hallways.

[Sunken]

As far as the zones and branching goes, however, I'm not so much of a fan of the TCZ's that Sunken is proposing. I don't see the advantages of silly-move over A* for the scenarios silly-move is applicable for outweighing the flexibility of A*. Additionally I think we can do better if we allow for zones that do not satisfy TCZ (such as a windy passage that doubles back), but which are trivially pathable with A*. I also think that zones should be 3D since this allows for similar windy passages in the z-direction (and the sky could be one gigantic zone).

There's a trade-off: The more complex the intra-zone navigation is allowed to be, the larger the zones can be -

straight-line -> convex zones
silly-move -> TCZs
A* -> more convoluted zones (entire maps, in fact)

We simply have to experiment to see which trade-off  is most beneficial.
I'll say this, though: There has been no automatic cut-off criterion proposed for A* zones. As I just said, they can be as big as you want - but unlike the other two, the intra-zone pathing becomes more and more expensive for A* as the zones grow. Silly-move and straight-line are constant-time no matter how big the zone.

So, saying that we should use A* inside zones just begs the question - what zones to use? I thought up TCZs because they seemed a reasonable compromise.

[Draco18s]

I'm just popping in now to point out that in a tile based game, convex zones are rectangles.  Any other shape ceases to be convex.  Diagonals in a square area are an odd case, as the square the line passes through may or may not be traversable (eg. diagonal movement around a corner).  Currently such diagonals are allowed at normal cost (1.4), but this may change.

[Fieari]

Why would diagonal movement change?  Toady went to some lengths to enable diagonal movement in the first place...

[Sunken]

I'm just popping in now to point out that in a tile based game, convex zones are rectangles.  Any other shape ceases to be convex.  Diagonals in a square area are an odd case, as the square the line passes through may or may not be traversable (eg. diagonal movement around a corner).  Currently such diagonals are allowed at normal cost (1.4), but this may change.

Here's a convex zone to disprove your claim:

Code: [Select]

##
####
####
Edit: I suppose you mean that a tiled world superimposed on Rē only allows (axis-aligned) rectangles. But that's a useless definition of convexity in a tiled world. I, and I think most others, have been assuming convex to mean "the shortest path from two tiles in the set lies in the set", where "path" is something a dwarf might follow.

[Starver]

As for using bezier curves or other algorithms[...]

[Actually, the response of mine has been retro-ninjaed later, especially regarding the Bresenham function.   Which I admit I never knew the name of.]

[Sunken]

Though I agree the smooth line does look better, with the current path costs it is a purely cosmetic issue and must, I think, take a back seat to efficiency. In other words, if it should turn out TCZs or some other Bresenham-unfriendly zoning method is the more efficient choice, we'll have to go with the uglier diagonals.

Now, if costs were changed to make the staggered diagonal actually cheaper than the alternatives, then that would be a different story.

As for curves - a curve is never the shortest way (in Euclidean space) and so again I think aesthetics must give way to efficiency.

[Starver]

You got in there just before I decided to retract the post.

As for curves - a curve is never the shortest way (in Euclidean space) and so again I think aesthetics must give way to efficiency.

Although because of the non-Euclidean nature, a 'nice' curve can be no less efficient than a drastic non-curve.  (As can be a total zig-zag, of the kind we might actually use in Adventure mode while trying to sweep more of the field...)

[Starver]

1: You're working from an incorrect assumption. Diagonal movement and orthogonal movement cost the same in DF.
Edit: Scratch that, there's a sqrt(2) factor in there

Is there?  Oooh, I assumed it was equal in all eight basic directions.

Might put the scuppers on any assumptions I've made, if this is true.  Of course, if anyone was going to make this matter, Toady would.

(Not that it would matter if a route was 10E,5NE or 5NE,10E or 5x(2E,NE), but it would mean that 20E would be quicker than 10x(NE,SE) or 5x(2NE,2SE) or other versions.  Now, how does one test.  Actually, never mind, for now I'm not too bothered.  Just speculating.)

[Starver]

I'm just popping in now to point out that in a tile based game, convex zones are rectangles.  Any other shape ceases to be convex.  Diagonals in a square area are an odd case, as the square the line passes through may or may not be traversable (eg. diagonal movement around a corner).  Currently such diagonals are allowed at normal cost (1.4), but this may change.

If you enforce wossisnames[1] algorithm, then a diagonal in a zone might preclude a 'convexity', as the 'ideal stagger' hits the wall, but otherwise shouldn't matter.

For example:

Code: [Select]

            ########
       ######b    a#
########c          #
#d                 #
#                  #

a->d 17W,2S which would be a sum of 15W,2SW, or "ideally" 5W,SW,5W,SW,5W, which would hit the wall next to 'c'. (This was quickly rendered in ASCII, I may not have made the wall stagger B-algorithmically correct!  It might more correctly miss the wall.)  But it could be made to sidestep SW earlier and delay one of the W-steps.  To equal weight (with or without the root-2 cost l;evied against a diagonal).

b->d and c->d would be required to start with the SW movement (and the route from b may need to premeturely enact a second SW, compared to the B-algorithm's idealisation), but to the same equality.  That shape would still be topologically convex in all respects.  Treat the 'inconvenient' corners on the diagonal wall much the same as inconvenient single-square 'step-around' blocking elements in the middle a zone.

Ironically, if the 1.4 weighting exists, then a straight orthagonal path that has to make a diagonal-and-back 'jink' around an obstruction on the path will cause more problems to (strict) convexity than otherwise.  Although minimal in the grand scheme of things.

[1] Begins with a 'B', forgotten it already.  Sorry.

[Shades]

Might be able to achieve some of the 'nice' curves, the ones that are the same total length at least, by when performing the A* search you prioritise the squares in the current direction of movement.

As there is only 8 squares in the plane of movement the combinations for order of testing are few and can probably be handled cheaply with a lookup against the links (rather than processing links in order).

I have no idea if it would get the effect you desired, or how much extra processing it would really be but it would be a very minor change to any of the A* implementations (or any graph based search) and so easy to test.

[Starver]

For example:

Code: [Select]

            ########
       ######b    a#
########c          #
#d                 #
#                  #

a->d 17W,2S which would be a sum of 15W,2SW, or "ideally" 5W,SW,5W,SW,5W, which would hit the wall next to 'c'. (This was quickly rendered in ASCII, I may not have made the wall stagger B-algorithmically correct!  It might more correctly miss the wall.)[...]

Actually, re-reading my own item, the whole point is that corner-to-corner of the region should have been a 'regular' stagger, the wall that bounds it is beyond the limit.  However consider the zone bounded by...

Code: [Select]

                    ###
#####################a#
#b         c          #
#                     #
#             d       #
#######################...that would be as much convex as the rectangle minus the alcove, given that no shorter route exists between all points within than the shortest route that must avoid the boundary.  The route a->b would have to be SW, then a number of Ws, but would not be longer than the stagger that travelled 'through' the wall then emerged at or around 'c'.

Of course, if 'c' was an obstacle, then the 1.4 weighting would cause minor problems (without, one might even stretch the definition to still be convex), and ditto if there was a further alcove in the wall at 'c'.  But (at least in the latter case) it would be a trivial matter of making the 'a' or 'c'-adjacent alcove a separate 1x1 zone attached to the main zone.  For a "'c' is an obstacle block", then if your algorithm bothered about the weighting disadvantage you might be forced to split the zone.  Either straight down (shortest distance) or across to hypothetical obstacle 'd' should that also spring into existence.

But that's all... well, a different solution/direction-of-solution to what is being worked on with the A* algorithm stuff, as far as I can tell, so this is just waffle on my part.

[Sunken]

Sounds like you're on your way to inventing the TCZ ;-)

[Starver]

Sounds like you're on your way to inventing the TCZ ;-)

Well, to be honest I had invented something prior to hearing of the TCZ that was very TCZ-ish, but then came in after the weekend/night-off to see almost all of my considerations[1] mentioned.  (Straight off, I must have skimmed over what TCZ was, and thought the "C" was for "Convex", but rewound after a while when I decided I really needed to know the title.)

But even back then I had assumed it was to be a Bresenham line on all sides (albeit that there were several possible B-lines, or rather that various possible B-line segments could be adopted as the zone border, where it wasn't a fully constrained border, just a path between corners as defined by other constraints.  And I'd also never considered the possibility of single blocking cells in the centre not (necessarily) preventing a zone's trivial connections.  To my eye, it would have forced the bissection of a potential zone.

[1] Tell you what, here's something of what I'd composed.  This was not a finalised version (appears to have a few BBCode-inaccuracies, being composed off-line), but contained the basis of the "from the ground up" conglomeration of tiles into zones, which would have been maintained but in turn grouped as sub-zones, and included the stipulation that zone borders overlap (by one tile) with relevant adjacent zone borders, and that zone-group edge-zones overlap with all relevent adjacent zone-groups' edge-zones (i.e. copying) which I felt was an inefficiency of storage that could be made up for by the possibility of giving better routings between zones/meta-zones/meta-meta-zones/etc.:

Spoiler (click to show/hide)

At this point, I'm going to be totally off the wall, because:

• A - I've not actually studied the theory behind this, so I can't draw upon great reserves of prior knowledge,
• B - Those that have have probably spent a lot of time fine-tuning the known methods using a lot of effort that I couldn't even hope to equal,
• C - I've had this idea for a while (back at least to original Doom days), meaning to apply it to a vectorised 'Levels Of Detail' environment of my own conceit, and a rasterised one can always be boiled down into a particularly limited (and ragged) vector environment, so there should be some crossover available.

Of course, combine A, B and C (especially the time-scale of the latter) and I'm probably not innovative at all.  Apologies if it's a tried and tested and possiby rejected method.  From what I've already read in this thread, I recognise some of the features, or at least related ideas.




Ultimately every cell (a.k. tile) is a box (or square, in 2D) with access or not to each of its neighbours.  Multiple modes of travel mean multiple types of access to neighbours or not (ground-only, water-only, amphibian, aerial and (especially for DF) additional magma-tolerent, pet-passable, climbing/jumping access and 'tunellable' options), but for now we'll ignore that.  A cell has access or not to its neighbours, and not necessarily bi-directionally if so.

The idea is to group cells together into hierarchies of "free travel zones" that at each level act like cells in and of themselves, and that a 'travel request' is passed up to the first 'uber-zone' level containing both source and destination, and thus able to coarsely guide the travel between its subzones.

A binary tree would seem to be the obvious (or at least grouping in 2^n squares/cubes of cells) but, including diagonal transits, there are eight potential 2D and twenty-six potential 3D exits to a cell, which is 3^d - 1, so consider reflecting this structure.  The first-level zoning is a trinary grouping of cells.

Code: [Select]

...
...
...

The possibility of transit (and prefered routing, if so) between any two cells in this grid would be simply maintained based upon the relevent border-passing information.

Then group first-level trinaries into second-level trinaries:

Code: [Select]

+-+-+-+                           :::::::
|.|.|.|                           :.:.:.:
+-+-+-+                           :::::::
|.|.|.| or alternately notated as :.:.:.:
+-+-+-+                           :::::::
|.|.|.|                           :.:.:.:
+-+-+-+                           :::::::

Note, for later, that in the second notation (where ":" indicates a shared border, and thus representation in multiple sub-trinaries), 7² cells have 105 'records' (83 if the external borders of that particular grouping don't actually go anywhere, and if I've added it up right), so obviously a large data overhead at this stage, and greater and greater the more levels we go up...  So, how do we sort that out?

By merging these most basic of zones into their parents, insofar as we can create "convex" zones of arbitrary size.  i.e. where all routes across a zone can be simplified to simple staggered 'across-by-N, sideways-by-1' line steps (at least at the level where a zone encompasses individual tiles).  Absorb multipe leaf zones (tiles) into their parents first-level zone (to become a 'leaf' in their own right) such that the entity remains convex (remember that this was originally for a vector-based environment).  In this case, convex means that from any particular tile to any other tile within the boundaries of the zone is a staggered line (actually a straight then a diagonal side-step, rather than a straight then a perpendicularly-straight sidestep) that does not cross the border, e.g.:

Code: [Select]

............
......----+.
.+----....|.
.|........|.
.+........|.
..\......|..
...+--...|..
......---+..
O...........
Where the "+" parts are limiting features that contain the zone (are not, in themselves, passable), and the straight lines (of whatever kind) are representative of the line-of-appropriate-stagger between the limiting features that forms the boundary to the zone.  Which are, as with the second-level trinary diagram, shared (at least theoretically) with neighbouring zones.  To maintain the validity of being totally convex, wholely contained paths from not-offically-a-corner tiles, like that border tile at (6,7) relative to the marked 'O'rigin, are allowed to start their stagger on a diagonal before continuing in the required pattern cycle.  If (5,6) was also a limiting obstacle, then it could not be convex, and the absorbtion of sub-zones would have stopped at the point where two different convex sub-zones could not be merged into a single 'convexity', e.g.

Code: [Select]

............
........--+.
.+---+--..|.
.|....\...|.
.+.....|..|.
..\....|.|..
...+--..\|..
......---+..
O...........


(BTW, current pathing doesn't tend to use nice 'staggered' straight-line across a field of play, from my observations, but will use orthagonals and diagonals in such a way as to have a long 45-degree diagonal for part of the leg with an orthagonal for the other, for any journey across open ground that cannot be purely by one or the other.  This is no longer than a 'proper' diagonal on a grid, but looks more unnatural.  I'd prefer the engine to take a necessary displacement of 20 east and 5 north and turn it into (3e,1ne)*5 rather than (15e,5ne).  Obviously this can be changed variations like 2e,1ne,(3e,1ne)*4,1e or (1ne,3e)*5 if obstacles along the way require such fudging to avoid individual obstacles and yet maintain such a stagger, or just randomly where all paths are as likely, meaning an almost anti-aliased look to the line, when superpositioning all possibilities, looking at relative 'footstep-frequency' along the way.


So, how to apply this....  One of DFs flat plains (or at least one that is undulating but ramp-enabled, if we introduce that fudge for surface travel) with no obstacles would find itself defined as a simple leaf-zone, constrained by only by such things as the edges of river gorges, the intrusion of a constructed defensive wall or certain key trees along the the edge of a forested area.  From a few key locations, travel across that plain would be a matter of "Am I within the bounds of this free-travel area?  Yes?  Then let's plot an appropriate stagger across it!"  Simple routing at very little cost.

If an orthagonal channel was dug across the plain, leaving a gap (of arbitrary size), then this would be two adjoining leaf-zones, sharing up to three 'borders', as defined by two channel terminations (between them is a passable border) and the two points on the edge extermities of the channel serving as limiting features (between which and the inner channel termination is a non-passable border).  The channelling may perversely 'open up' an expanse of plain that could not have been included in the original convex area, for whatever reason, but is a valid inclusion to increases the size of one or both of the spliced-off areas, while maintaining a convex nature.  But when it comes to travel across the plain, requiring navigation through the gap that was left, the superzone that might-have-been the result of the smaller zones merged into it understands that routing from anywhere within the first leaf-zone to anywhere within the second leaf-zone means traversing the border.  As such, a stagger-path needs to be plotted from A (within the first leaf-zone) towards 'B' (upon the passable border between the two leaf-zones) and then a new stagger onwards to C (within the second leaf-zone).  If there is only one tile of channel-gap forming the border, then B is obvious.  If the border is wider (whether that be two, ten or thirty eight tiles in width) then some intelligent guesswork can be used to work out where to aim at.  e.g. calculating the intersection of the line defines the passable border with the one that defines the direct trip from A to C, and chose the point nearest that intersection, or the end nearest it if the boundary forces a dog-leg.

If a series of channels are dug across the plain (or any other obstacle, such as arbitrarily placed pillars), then the leaf-zones could find themselves sharing a number of passable-borders.  Again, calculate the intersection of A->C with each passable border.  Whichever border has the best 'bid' (cuts across A->C, or has the closest border-end to the point beyond the segment where it would have done) gets to have 'B' upon it.


Scale that up accordingly.  In an area with trees, the convex leaf-zones would be more numerous, giving the increased number of limiting features (OTOH, there more of the borders would be fully passable, unless significantly numbers of limiting features sat side-by-side).  Travel between A and C would probably require passage across not only multiple leaf-zones, but multiple zones of the level above (being formed of convex groups of convex groups of tiles, BTW), perhaps more levels above that.  But once the level of overview increases so that A and C are contained within a single zone of that level, routing can begin.  This level knows which borders are open, and which are not, between immediate sub-level zones it commands, and performs an A->B->C calculation accordingly.  Then the A->B calculation is passed to the zone containing A and (on the border), B.  If this is a leaf-zone, all very well, otherwise the A->B is treated as A->C_B and a new B_A->B worked out to sit between them.  Ditto any A_B->B_B->C->C that is necessary.  And down the tree of zones we go, as far as necessary.










Definite issues:

• - I'm not sure travel weighting could be reinforced well enough.  A path between adjacent leaf zones that has a heavy expense that's still light enough for travel between near-adjacent cells could propogate it's 'usefulness' up through the zone hierarchy.  At some point, though, there could be a source and destination where the appropriate zone level to contain them both brings up this choke-point as a 'win', where the two termini are both near the edges and actual best path involes a trip outside of that zone (as a simple example, imagine a large "R"estricted travel designation, where corner-to-corner travel (including opposing corners, but especially when not) would be best taken by exiting the zone at adjacent exits and wandering along a path outside the perimiter and then entering again).  A fact that the next zone level up might or might not 'know', if interrogated, given that it contains the source/destination zone and those adjacent zones that allow the detour.  But it would never be consulted about this without some sort of additional notation propogated down.
• - There's a 'parity'or displacement of zoning that must be addressed.  Why is a certain initial level of zoning
  Code: [Select]
  [/li][/list]
+-+-+-+                  -+-+-+-    |.|.|.|         .|.|.|.
|.|.|.|                  .|.|.|.    +-+-+-+         -+-+-+-
+-+-+-+                  -+-+-+-    |.|.|.|         .|.|.|.
|.|.|.| when it could be .|.|.|. or +-+-+-+ or even -+-+-+-
+-+-+-+                  -+-+-+-    |.|.|.|         .|.|.|.
|.|.|.|                  .|.|.|.    +-+-+-+         -+-+-+-
+-+-+-+                  -+-+-+-    |.|.|.|         .|.|.|.
, when laid out over any particular grouping of 7x7 cells?  Similarly, there is no 'one' way to place convex spaces upon a feature-limited area, though undoubtedly there are better ways than others.  (If having to split an existing convex space due to the introduction of a limiting feature within it, then I would aim at selecting the option where the additional border length is as minimal as possible, to avoid creating long and thin parallel zones that are far less likely to require purely internal pathing than inter-zone pathing.  The same philosophy when merging suitable leafs into larger ones (or creating cumulative zones out of 'optimised' ones of the level below) would probably be how I would go.)
  
• - For multiple modes of travel, the choice appears to be: 1) give each border a passability flag according to the different (ground, water, amphibious, etc) modes of travel, but put up with some limiting features (e.g. ponds and rivers) not actually needing to limiting features for a whole skein of possible travellers, or 2) build up totally separate zone-trees for each situation.

I rather think the latter would be best.   Aerial creatures, innate swimmers in multi-Z water-bodies and diggers who can tunnel through rock (at some small expense of effort?) would not actually need different zoning algorithms from one that can handle Z-travel by surface-routers through treating the 'open borders' between levels that are ramps and stairs (and even climbing/plummeting opportunities, if forced to) as mere 'pinch-points' in a 3D-convex definition, but considering how much open air, ocean or unmined rock could be a convex routing container for the appropriate creatures, it would seem rather less efficient to constrain them to 'traditional' layers of 2D convex boundaries and have to calculate 3D stagger intersections with the Z-boundaries as well.

• - None of this addresses transient open/closed border situations.  e.g. the bridge that might be raised/lowered though is currently lowered/raised, the door that is or is not pet-passable but could be inadvertently left open or the freezable river survace, but allowing boundaries to maintain boundary information between upper levels of zones to contain "boundary open if[/if] <some season/bridge/door-status>" information and maintain one (or more) alternate route would probably mean
  

[shadow_slicer]

There's a trade-off: The more complex the intra-zone navigation is allowed to be, the larger the zones can be -

straight-line -> convex zones
silly-move -> TCZs
A* -> more convoluted zones (entire maps, in fact)

We simply have to experiment to see which trade-off  is most beneficial.
I'll say this, though: There has been no automatic cut-off criterion proposed for A* zones. As I just said, they can be as big as you want - but unlike the other two, the intra-zone pathing becomes more and more expensive for A* as the zones grow. Silly-move and straight-line are constant-time no matter how big the zone.

So, saying that we should use A* inside zones just begs the question - what zones to use? I thought up TCZs because they seemed a reasonable compromise.

I'm not sure that intra-zone pathing is difficult for A* than it is for silly-move for the cases where the two are applicable. If your silly-move algorithm is simply "move to the tile that is closest to the destination," then A* will have similar complexity since the only tiles A* would consider are the same ones the silly-move algorithm would (So both are algorithmic on the order of the zone size). A* has some additional overhead since it handles non-uniform costs, but this does not affect the algorithmic complexity.

Having smaller zones can actually decrease performance as well. As zone size decreases, the ratio "surface area" (number of external links) to the enclosed volume increases linearly (or is it even superlinearly?). In order to perform A* routing over the set of zones, the source link must know the cost to each of the other links in the zone. This means that the required calculation and storage grows as O(n^2) in terms of the number of links, resulting in the total algorithmic complexity increasing as O(n^3) in terms of the "smallness" of the zone. Note that this will be true regardless of what method of pathing is chosen inside the zones.

I'm not saying that the zones should be too large. A large zone with lots of chokepoints or doubling back or something like that would perform horribly, regardless of the pathing algorithm chosen. There definitely needs to be a tradeoff between zone size and complexity. I still haven't found a good algorithm to define the zones. All I really have so far is that the edges should follow chokepoints as much as possible to reduce external links. And I would probably use rectangular prisms as zones since this makes it easier to determine which zone a tile belongs to.

Edit: (instead of posting again)
Also, A* can be modified to produce the diagonal pattern that several posters have suggested seems more natural. If A* was adjusted to order (ascending) candidate nodes with equal heuristic cost by "sqrt(dx^2+dy^2+dz^2)", where dx, dy, and dz are the differences between that node's x,y, z and z positions to that of the destination, the paths found by A* would look like those "straight" lines.