Bay 12 Games Forum

As for multi-creatures: the way you'd solve it with TCZs is that you make TCZs spanning different movement types (stopped from expanding by other movement types), store interfaces between them as usual, and simply take allowed zones into account when doing the path search - an A* node is not put on the open list if it is incompatible with the agent's movement.

The only extra cost is that you will need a whole new connectivity map for each movement type combination (not just each movement type). However, given that this map runs over zones, not tiles, it should be cheap enough that we can afford it.

And, yeah, fliers. I dunno about those. They're tricky.

Edit: I meant "multi-movement-type creatures" above, not "multi-tile creatures".

The reason I suggested standard convex shapes rather than TCZ in my last post was exactly for the reason that they won't span so many objects and so end up smaller. In this way we can ignore the fact that we get a suboptimal route because it will only be marginally suboptimal and vastly faster to calculate.

Because we don't need to calculate interface point to interface point, other than when we hit a zone and need to move to the next one, we don't have to worry that the interfaces will be larger stretches.

It is indeed a different ball game if you settle on suboptimal paths. I have a feeling that won't work well in practice, because the inefficiency is unbounded in principle - the cost of moving through B from A to C may be 1 and the cost of moving through B from D to E may be 100.
But I can't prove that it's impracticable, it's just a hunch.

If one does go for full accuracy, and plans with interface tiles, then a key issue is whether the zone subdivision "fits" the environment - whether it finds natural choke points and minimizes the sizes of interfaces. That's where I think the flexibility of TCZs are a strong point. They're not the final answer by any means, of course.

I don't think convex will help you as much as you think. It's easy to forget (as I did initially), when thinking about zone decomposition, about the critical importance of the size of the interfaces between the zones. If you do not want to produce paths that are wildly suboptimal, you have to consider not just "move from zone A to zone B" when searching for a path, but "move from zone A to zone B through interface tile x", for each interface tile.

The advantage of TCZs to convexes or rectangles is that they are larger (they will always be at least as large as a convex or a rectangle, since TCZs subsume those concepts). The idea is that they have a greater chance of filling up an entire room, leaving only the doorways or other choke points as interfaces to be considered in the search. A single obstacle in the middle of a room is enough for a convex or rectangular subdivision to split it into several zones, which will have potentially long open-space interfaces, making the branching factor of the search bigger. TCZs are designed to make that less common (though by no means eliminate it!).

Only extensive testing will verify whether this idea actually holds water - especially given the extra cost of creating and maintaining the TCZs (though I'm hoping that will amortize well over time).

EDIT: Forgot to answer to Sunken earlier (oops). What I meant by local checks is that, if you have a large TCZ, you want to limit your checking to the area near the point you're checking, to avoid exponentiality. So you might decide to check only a 24x24 area around the seed point (or around the newly added point, but that runs into heavy redudancy), for example.

If, despite that, you allow the TCZ to grow much larger than the size you limit the checks to, you open yourself to letting in shapes that don't comply with the silly-move requirement.

...I still don't get it  Checking for what? Are we still talking about incremental changes to the map? Or do you mean the initial TCZ creation? Either way there is no exponentiality involved even if you don't limit the area you process (especially with the simplified incremental update I suggested a post or two ago). Or do you mean some other check?

Quote from: Sunken on October 14, 2009, 09:16:53 am

I agree that TCZs should be 2D. They are adjacent to zones on other levels at the points where there are stairways, for purposes of path planning.
This leaves fliers basically unaddressed by the approach, sadly. They'll have to be considered specially.

You can have fliers using zones too, all zone needs to store is adjacent zones and in these cases every square would allow you to pass to an adjacent zone (vertically at least). Not the most efficent system but it would work.

You need to store more than adjacent zones in the general case. You can't path plan on the zone level without knowing the costs, and the costs depend on exactly which tiles you're entering and leaving the zone from. The hierarchical clearance-based approach accepted a suboptimality in this respect, but that can get pretty bad for large zones.
I suggest instead storing gateway tiles between TCZs and path planning between these instead. But that solution would be prohibitive for fliers.

Alternatively you could assume everything above a 'top level' zone is a trivial connection to critters passing through these can move freely, which although means a special case is probably a cleaner solution overall.

That's a possibility, although it's not trivial to carry out in practice.

I don't quite understand what you mean by "local checks".

How you'd deal with changing terrain is more or less like this:
When a tile changes, find the TCZ(s) it contacts (use an efficient bounding-box algorithm for quick lookup).
Resume TCZ processing for all neighbors of the changed tile (and itself, if it was cleared) and process from there as before.
Finally, check tiles from which TCZs have withdrawn. If any remain uncovered by a zone, re-seed them until coverage is reestablished.

This will (unmodified) not reclaim space as aggressively as restarting the TCZ from scratch, but that may be just as well - maybe that tile will close up again anyway.

Well, I'm not aware of anyone else having implemented it but that may not be because they haven't... I'm very bad at finding related works
As for my implementation, it is rather rough around the edges and I'm still working on it.
But basically, the idea is: Start with assuming all the world belongs to the TCZ. Move outwards from the seed tile, and whenever a tile conflicts (that is, it wouldn't be possible to silly-move from it toward some other tile in the TCZ), forbid either it or the other tile, depending on which is closest to the seed. Then backtrack to reprocess any neighbors of newly forbidden tiles.
Keep it up until the whole world has been processed.
That's the gist of it, though there are many obvious simplifications that can be made.