Bay 12 Games Forum

Quote from: Sunken on November 02, 2009, 05:08:53 pm

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.

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.

Quote from: Sunken on November 02, 2009, 02:05:50 pm

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.

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.

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.

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.

Planning movement within a rectangle is not a problem, no matter which algorithm you select. Nor is it within TCZs, using silly-move. The computational costs for these are all absolutely negligible, I think.

The problem is the search. What is needed is a reduction in branching factor and search tree depth (and a good heuristic). And it's my belief that TCZs will have a better impact on these key factors than rectangles will.

But it's true that in principle it would be possible to mix zones of different types. It would require more programming work, and a disciplined, modular structure, but it's not infeasible.

Made an edit, but too late. Pasting my rebuttal here:

Still, Bresenham will require the storage of the d parameter, and the final path will not actually cost any less than the silly-move one; it will just distribute the diagonal movements differently. Plus, it disallows TCZs (as presented by me, as opposed to rectangles or other strictly convex regions) and, as you say, isn't optimal with moving targets.