Print

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

[Sunken]

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.

OK, amortized over the entire path you are correct, since silly-move has to either check the next step at each step, or precompute the entire path at cost O(N). A* has to do the latter.
A* will incur more overhead as you say.

The main point is not that silly-move is cheaper, but that it is part of the definition of a TCZ, which in turn guarantees that both movement strategies will find the path. Larger zones - you'll have to find another proof of linear complexity. And you have to come up with a way of creating those larger zones.

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.

Yes, that was the whole point of TCZs. They are strictly larger than convex zones or rectangles, while guaranteeing a constant-per-step complexity intra-zone. Again, even larger zones would be better, but not if that means losing intra-zone complexity guarantees.

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.

Rectangles will always be smaller than TCZs, that's what I've been trying to tell you. I'd still use rectangular bounding boxes to speed up TCZ lookup though.
And to my mind TCZs will be better at isolating chokepoints than rectangles. The biggest problem with TCZs is their tendency to overlap each other.

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.

Even assuming that computing that polynomial (leaving out the sqrt) is not too expensive, I think that would tend to make the algorithm try suboptimal paths first? Because that formula is not, in fact, the straight-line distance to the goal as the dwarf would walk in an open world. I'm not sure about that.
Anyway, it means adding computational complexity for an essentially cosmetic effect. It would work, though, and could be tried easily enough on top of any other approach AFAICS.

[Sunken]

Starver, I just skimmed over your description; it's too late in the evening to get deeply into it for me (spend much of my days reading and my brain gets tired...) but essentially, you're proposing a tree-like decomposition into convex zones, right? A non-overlapping, mutually exclusive decomposition?

Path-planning-wise this will have all the attributes of a convex subdivision, which has been part of the discussion for a bit now: trivial to path across, larger and thus potentially more efficient than rectangles; smaller and (or so I maintain) potentially less efficient than TCZs.
And you're suggesting a structure to create and maintain that convex subdivision, correct?

I'm doubtful as to the tree approach, though. Won't it be inefficient wherever the edges of the convex zone runs in the diagonal direction? This zone

Code: [Select]

#####   
####   #
###   ##
##   ###
#   ####is convex enough but would not benefit from the hierarchy you propose, I think? Correct me if I'm wrong.

[shadow_slicer]

...
Yes, that was the whole point of TCZs. They are strictly larger than convex zones or rectangles, while guaranteeing a constant-per-step complexity intra-zone. Again, even larger zones would be better, but not if that means losing intra-zone complexity guarantees.

*Edit: (forgot to comment here)
I'm not sure that I agree with you about the necessity of guaranteeing the intra-zone complexity be low. With hierarchical and cached pathing, the intra-zone stuff can be complex. It might be useful to constrain the zone such that the path from any tile in the zone to each of the zone edges have some maximum complexity* (or even just the nearest zone edge), since we're going to be pathing to and from edges a lot, but otherwise the intra-zone complexity doesn't seem such a big deal.

*I would define complexity of pathing as the ratio of number of tiles searched to path length.

...
Rectangles will always be smaller than TCZs, that's what I've been trying to tell you. I'd still use rectangular bounding boxes to speed up TCZ lookup though.
And to my mind TCZs will be better at isolating chokepoints than rectangles. The biggest problem with TCZs is their tendency to overlap each other.

.

I actually think that A* rectangles will be larger than TCZs. TCZs need a region of a) uniform cost and b) trivial complexity. How many TCZ regions (and purely A* regions) will be necessary to span the following design:

Code: [Select]

###########
a #   #   #
# # # # # #
# # # # # #
#   #   # b
###########


Spoiler (click to show/hide)

 The answer is 5 for TCZ and 1 for A*

I am thinking though that pure rectangles may not be best. I was thinking that some sort of subtractive geometry might be efficient. We could define zones as "all of this rectangle except for those in the following rectangleszones". This could be represented as a "tree" (actually more of an acyclic graph -- since I would allow nodes to have multiple parents) where zones further down the "tree" have higher priority over the ones higher up. To determine what zone a node is, the algorithm goes down the path of the "tree" with zones containing the node until there are no zones further down containing the node. Pathing proceeds normally just using zones. This hierarchy is only used for determining a node's zone (though if we require zones to be completely contained in their parent zone: 1) we would have a multi-level hierarchy we could use to optimize pathing 2) the "tree" is a tree).

Even assuming that computing that polynomial (leaving out the sqrt) is not too expensive, I think that would tend to make the algorithm try suboptimal paths first? Because that formula is not, in fact, the straight-line distance to the goal as the dwarf would walk in an open world. I'm not sure about that.
Anyway, it means adding computational complexity for an essentially cosmetic effect. It would work, though, and could be tried easily enough on top of any other approach AFAICS.

The way I mean it, it shouldn't cause suboptimal paths to be tried first. I realize this formula isn't the distance as the dwarves see it (for them its actually max(dx,dy,dz)). It's actually more of a tie-breaking rule. We already have the cost (which in A* is equal to cost so far plus estimate of cost to go) for each candidate node. All I'm suggesting is if there is more than one node with the same cost, they can be sorted based on Euclidean distance (purely for aesthetic reasons).

[Sunken]

I actually think that A* rectangles will be larger than TCZs. TCZs need a region of a) uniform cost and b) trivial complexity. How many TCZ regions (and purely A* regions) will be necessary to span the following design:

Code: [Select]

###########
a #   #   #
# # # # # #
# # # # # #
#   #   # b
###########


Spoiler (click to show/hide)

 The answer is 5 for TCZ and 1 for A*

You obviously don't mean the same by rectangles as I do. I mean unoccupied rectangles - unoccupied being the prerequisite for search-less pathing such as the Bresenham algorithm. You allow obstacles in your rectangles. It would take 11 unoccupied rectangles.

To be clear:

axis-aligned obstacle-free rectangles
subset of
convex obstacle-free zones
subset of
TCZs

and

convex obstacle-free zones
subset of
arbitrary axis-aligned rectangles
subset of
arbitrary connected zones

The first three types of zone have a constant-per-tile complexity guarantee through their definition. The last two don't (I guess it's order-of-total-tiles, worst case), unless you add some further restriction (which is certainly possible).

I am thinking though that pure rectangles may not be best. I was thinking that some sort of subtractive geometry might be efficient. We could define zones as "all of this rectangle except for those in the following rectangleszones". This could be represented as a "tree" (actually more of an acyclic graph -- since I would allow nodes to have multiple parents) where zones further down the "tree" have higher priority over the ones higher up. To determine what zone a node is, the algorithm goes down the path of the "tree" with zones containing the node until there are no zones further down containing the node. Pathing proceeds normally just using zones. This hierarchy is only used for determining a node's zone (though if we require zones to be completely contained in their parent zone: 1) we would have a multi-level hierarchy we could use to optimize pathing 2) the "tree" is a tree).

Can't say if this would work or not. It seems like it might be sensitive to changes in the map, the way quadtrees et al. are, and the diagonal-tunnel example I put forth a couple of posts ago applies here too. But these are just hunches on my part. If you think it will work then you should try it out.

Even assuming that computing that polynomial (leaving out the sqrt) is not too expensive, I think that would tend to make the algorithm try suboptimal paths first? Because that formula is not, in fact, the straight-line distance to the goal as the dwarf would walk in an open world. I'm not sure about that.
Anyway, it means adding computational complexity for an essentially cosmetic effect. It would work, though, and could be tried easily enough on top of any other approach AFAICS.

The way I mean it, it shouldn't cause suboptimal paths to be tried first. I realize this formula isn't the distance as the dwarves see it (for them its actually max(dx,dy,dz)). It's actually more of a tie-breaking rule. We already have the cost (which in A* is equal to cost so far plus estimate of cost to go) for each candidate node. All I'm suggesting is if there is more than one node with the same cost, they can be sorted based on Euclidean distance (purely for aesthetic reasons).

Yes, as a tie-breaking rule it would do the trick, though I'm not sure how you'd make sure the modification doesn't go beyond pure tie-breaking. But it's probably not a hard problem to solve.

And the cost isn't max(dx,dy,dz) (or max(abs(dx), abs(dy), abs(dz)), if one is to nitpick), but actually:
max(abs(dx), abs(dy))-min(abs(dx),abs(dy)) + sqrt(2)*min(abs(dx), abs(dy)) + abs(dz)
"straight bit plus diagonal bit plus vertical". Or at least I think so - I think movements in the "vertical diagonal" aren't possible.

[Draco18s]

You obviously don't mean the same by rectangles as I do. I mean unoccupied rectangles - unoccupied being the prerequisite for search-less pathing such as the Bresenham algorithm. You allow obstacles in your rectangles. It would take 11 unoccupied rectangles.

Which solution has more overhead in terms of memory cost:

11 rectangles
5 regions

?

[numerobis]

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.

It's not hard to define a discrete version of convexity that would obviate your worry (straight-line obstacle-free path from the center of each tile to the center of all other tiles, for example).

But all we seem to be using of convexity is that there is a closed-form solution for the cost from one tile in the region to another, looking just at their coordinates -- this is a larger class than what you'd normally call convex.  For example, TCZs have this property when diagonals are the same cost as the other directions (which is not the case here, but it might still form a good approximation).

[numerobis]

A question not yet raised in this thread: what heuristic to use.  One issue with traffic designations is that if you're actually using them heavily, the standard heuristic (euclidean distance) can make you sad: it assumes it costs 1 to cross each unit distance, when in fact it probably costs 2 or maybe 25.

It's not clear to me how to improve on that, but maybe someone has an idea.

[Cloaked]

This whole problem scope seems set up to be a total pathfinding nightmare.

Both vastly and rapidly changing terrain, hundreds of agents constantly demanding paths, multiple movement types and nearly completely user controlled/designed terrain. You can't assume anything! Terrifying.

The stuff laid out in the thread so far makes sense to me though, especially how it makes sense to divide the world into zones to simplify the graphs involved. TCZ's sort of remind me of navigation meshes, only squashed into this 2D grid-world. The basic idea is the same, they define interconnected trivially walkable areas with local agent steering filling in to walk around unexpected obstacles. (Here's a easy to digest article about em: http://www.ai-blog.net/archives/000152.html Obviously, nothing from that is really directly applicable, but having more buzzwords to google is always good.)

It seems like no matter how you define your zones though, there are going to be situations that will be less than optimal. It'd be nice if there was a way to intelligently recognize those cases and reduce them appropriately. (That winding passageway posted previously, for example, has only one possible path through it, so it'd be nice if it was able to merge those into a neat single black box path from a to b instead of a long chain of TCZs.)

On the logistics side, though, are you guys going to go full-steam open source project on this thing? It'd be nice if people outside of a handpicked team could download and fiddle with the source, with any changes still going through an approval process controlled by the team. It might be a little early for that, though, if you're still designing a framework. But I know that's what I'd be doing right now (fiddling with stuff, either framework-wise or algorithm-wise) if I could.

[Sunken]

But all we seem to be using of convexity is that there is a closed-form solution for the cost from one tile in the region to another, looking just at their coordinates -- this is a larger class than what you'd normally call convex.  For example, TCZs have this property when diagonals are the same cost as the other directions (which is not the case here, but it might still form a good approximation).

Exactly. "Convex" doesn't have an unambiguous definition on discrete sets, AFAICS, but if one can define a closed-form next-step algorithm (math people would probably use "ordering" here somehow), then a convex region is one where that algorithm takes you on a path that never leaves the region to your goal.
TCZs are just a special case, more general than more natural algorithms that just step in a straight line for the goal, doing no obstacle avoidance at all (such as Bresenham).

Indeed, the silly-move strategy is not guaranteed to produce the shortest path within a TCZ with obstacles - it can be a factor sqrt(2) inefficient in really contrived cases.

But note - even if we form our zones as TCZs, we don't have to use silly-move to actually path-plan within them. We can use A*, and we'll know the search will not run into the usual traps with doubling-back. That will give us an optimal path with the benefits of a more or less intelligent zone decomposition.

[Sunken]

You obviously don't mean the same by rectangles as I do. I mean unoccupied rectangles - unoccupied being the prerequisite for search-less pathing such as the Bresenham algorithm. You allow obstacles in your rectangles. It would take 11 unoccupied rectangles.

Which solution has more overhead in terms of memory cost:

11 rectangles
5 regions

?

5 TCZs have more overhead than 11 rectangles, obviously. But I will stick my neck out and claim most fortresses don't look much like the example. Only testing in the wild will tell which is the more practical.

[Sunken]

A question not yet raised in this thread: what heuristic to use.  One issue with traffic designations is that if you're actually using them heavily, the standard heuristic (euclidean distance) can make you sad: it assumes it costs 1 to cross each unit distance, when in fact it probably costs 2 or maybe 25.

It's not clear to me how to improve on that, but maybe someone has an idea.

It's a tough one. I think it will be extremely hard to come up with a heuristic that is more efficient than the obvious one - not Euclidean, but
max(abs(dx), abs(dy))-min(abs(dx),abs(dy)) + sqrt(2)*min(abs(dx), abs(dy)) + abs(dz)

...and still remain both admissible and monotonic.
I think we're probably stuck with this heuristic. We'll have to concentrate on making the tree itself more efficient, through using good segmentation of the map. And maybe using caching, though I'd go for that only as a secondary.

[Sunken]

Both vastly and rapidly changing terrain, hundreds of agents constantly demanding paths, multiple movement types and nearly completely user controlled/designed terrain. You can't assume anything! Terrifying.

At least our world will always be a grid of discrete squares! That's a great strength compared to pathfinding in, say, reality.

The stuff laid out in the thread so far makes sense to me though, especially how it makes sense to divide the world into zones to simplify the graphs involved. TCZ's sort of remind me of navigation meshes, only squashed into this 2D grid-world. The basic idea is the same, they define interconnected trivially walkable areas with local agent steering filling in to walk around unexpected obstacles. (Here's a easy to digest article about em: http://www.ai-blog.net/archives/000152.html Obviously, nothing from that is really directly applicable, but having more buzzwords to google is always good.)

Interesting, even though it's mostly a comparison of two systems none of which is on a discrete grid. Doesn't mean one cannot take inspiration from it, though. Convex polygons do have their interpretation in discrete space, as we've found.

It seems like no matter how you define your zones though, there are going to be situations that will be less than optimal. It'd be nice if there was a way to intelligently recognize those cases and reduce them appropriately. (That winding passageway posted previously, for example, has only one possible path through it, so it'd be nice if it was able to merge those into a neat single black box path from a to b instead of a long chain of TCZs.)

Indeed! I have no idea how to adjudicate that automatically, nor whether the overhead would mean it wasn't worth it, but a system that could pick its zone types optimally would be golden.
To encourage attemts at this, as well as to make it easier to compare different types of zones and their performance, any framework should make "zone" a generic module that could be instantiated as a TCZ, rectangle, convex zone or A* block, transparently.

[Starver]

Starver, I just skimmed over your description;[...]

Just bear in mind that was a v0.1 (Alpha) thing that I wrote before I integrated and evolved what everyone else was talking about, if you're talking about the Spoilered bit.  (I just thought "I spent at least 3/4 hour writing it, way back when, maybe I should give it a belated airing...

but essentially, you're proposing a tree-like decomposition into convex zones, right? A non-overlapping, mutually exclusive decomposition?

Essentially, although crucially I was going on the premise of the boundaries actually overlapping by exactly one unit (at whatever level of [meta-^n]zoning we're at).
Thus

Code: [Select]

<--Zone 1-->
......01234567890......
           <--Zone 2-->...in a 1D example.  In 2D that boundary would be a B-line (consistently defined for both zones) which would allow a calculation of where the segment "[point-in-Zone1] to [point-in-Zone2]" intersected the "boundary between Zone1 and Zone2" segment (or, indeed, if it did not intersect, and thus had to be doglegged around the end of the "bbZ1&Z2" segment closest to the off-segment intersection point.  The [piZ1] and [piZ2] coordinates possibly being the entry point to the Z1 or Z2 from/to Z0 or Z3, as guided by the meta-zone path-finding.  However, I later saw problems with that.

Path-planning-wise this will have all the attributes of a convex subdivision, which has been part of the discussion for a bit now: trivial to path across, larger and thus potentially more efficient than rectangles; smaller and (or so I maintain) potentially less efficient than TCZs.
And you're suggesting a structure to create and maintain that convex subdivision, correct?

Again, that's historic.  But you've got the essential flavour of what was proposed, with a couple of minor differences that don't bear going into.

I'm doubtful as to the tree approach, though. Won't it be inefficient wherever the edges of the convex zone runs in the diagonal direction? This zone

Code: [Select]

#####c                                                                             d
####   #
###   ##
##   ###
#a  ####                                                                         bis convex enough but would not benefit from the hierarchy you propose, I think? Correct me if I'm wrong.

With travel between the (inserted) "a" to "b" locations may (with the 1.4 multiple penalty for diagonality) be less quick to travel between than the (equivalent in crow-flies) "c" to "d" route.  My original concept would have split the constrained diagonal containing a and c into one convex area and the large one leading to b and d into another, with a shared boundary somewhere a couple of cells to the right of "c" (and however far off-diagram you needed to go).  Which would have meant a path dog-legging around the top of that "/|" shape from either a or c, and then straight to d or stagger to b.  An a->b journey would actually be longer than a vector-based approach, of course, due to the disproportionate acumulation of 4x(root(2)-1) additions to the pure horizontal distance compared with the proper trigonometric adjustment for the angling across.

(If I understand your query (and diagram) correctly, of course.)

[Sunken]

I'm afraid you misunderstood my diagram... I meant an indefinitely long diagonal corridor surrounded by rock. I'll make it clearer:

Code: [Select]

###############
###########   #
##########   ##
#########   ###
########   ####
#######   #####
######   ######
#####   #######
####   ########
###   #########
##   ##########
#   ###########
###############I was afraid the tree structure wouldn't be able to efficiently represent that as one unit. A quadtree wouldn't, but if you can then that's cool.

[Starver]

(Here's a easy to digest article about em: http://www.ai-blog.net/archives/000152.html Obviously, nothing from that is really directly applicable, but having more buzzwords to google is always good.)

Interesting.  That's very close to the approach I never-quite-implemented back when I was so impressed by Doom, but thought it needed a proper third dimension (and the rest of the funny tweaks, like rotational symmetries of 1/2)...  Looks like another thing I could have gotten rich from but didn't.

(That winding passageway posted previously, for example, has only one possible path through it[...]

Yes/No (*delete as inapplicable).  There's only one shortest path, but there are others.  c.f:

Code: [Select]

#####       #####
#+++#       ##+##
#+#+#  and  #+#+#
#+#+#       #+#+#
++#++       +###+
#####       #####
7.2 to 11   only 7.2
steps        steps
(based on 1.4 for diagonal)

And if you're splitting those into rectangles (minimum of 5, in either case), how do you ensure the former only takes the 7.2 step route?

(But, drawing in my prior mentioned 1-cell overlap system, it'd be 2 convex shapes, which would optimise the travel into the overlapped cell.  However, there are other problems with that.)