Print

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

[Sunken]

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.

[Shades]

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.

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.

[Sunken]

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.

[Draco18s]

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.

Keep in mind guys that we do need to be able to maintain a functional set of traffic rules, such that we can restrict traffic from some areas.  Entering a zone on a normal traffic tile, but having to path over a stripe of "restricted" to get to the other side gives you a valid path, but doesn't take into account the restricted nature of a portion of the zone.

[Sunken]

That's pretty easily taken into account (in principle): only allow a zone to spread along equal traffic cost tiles.

Obviously, this makes for trouble if the traffic zones are changed a lot or are badly shaped (dots spread out in the middle of rooms and so on).
An interface change could help remedy this: If the player can see TCZs when setting traffic zones, he can elect to paint entire TCZ with the same cost, which means no TCZ reshuffling is necessary.

[DeathOfRats]

Considering that traffic designations are done while paused (unless Toady intends to change that in the future), couldn't we take advantage of that to calculate the affected areas before the player unpauses the game? It's just a one-shot calculation, and that way it won't affect FPS.

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.

[Impaler[WrG]]

The problem I'm foreseeing with TCZ as currently envisioned is that their agent size dependent.  A 1x1 agent can go through a forest easily because all the obstacles are 1x1 and it can continually home-in on its destination and just take the diagonals when it runs into an obstacle.  But what about larger agents like wagons, two close trees can form an impenetrable barrier.  Their would need to be a TCZ for each agent size which will probably be prohibitive.

Thus I'm in favor of rectilinear areas, the shortest side of the rectangle can be used to determine the size limit for agents passing through it and one area will be adequate for all agents without knowing what sizes to expect.  Like wise the connection between two rects would itself be a rectangle overlapping the two connected zones, the footprint on each side being at least as deep as it is wide.  This would avoid the situation ware two zones that can accommodate large agents have a small connection like a 1x1 door.  The connection size would be 1 and large agents would not try to path through the area.

[Puzzlemaker]

As soon as I get off my lazy ass I'll program in a simple A* algorithm for starters.  Lazy being the keyword here.

My MSN is death_spear684@hotmail.com
My AIM is Aiko12349

Just, ya know, in case you want to bug me/motivate me.

[Sunken]

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?

[Sunken]

The problem I'm foreseeing with TCZ as currently envisioned is that their agent size dependent.  A 1x1 agent can go through a forest easily because all the obstacles are 1x1 and it can continually home-in on its destination and just take the diagonals when it runs into an obstacle.  But what about larger agents like wagons, two close trees can form an impenetrable barrier.  Their would need to be a TCZ for each agent size which will probably be prohibitive.

True, I never even thought about multi-tile agents when I thought up the TCZ approach.
But really, won't multi-tile creatures/wagons be rare enough that we could use brute force pathing for them? If a colossus should show up, we just perform a single, specific clearance-based flood fill starting at his current position and then brute A* over this - just like wagons (seem to) work right now?
Remember that the bigger the creature, the fewer its movement options. A four-tile creature can't even move through doors - A* inside a typical fortress should be a reasonably shallow search!

Simply put, I don't really feel multi-tile creatures/wagons are enough of a performance problem in practice to worry about. Especially since there's already a special clearance based system in place.

[Shades]

Maybe we are going about this the wrong way, simiple 'brute force' A* works well enough on outside areas because paths are almost always direct (rivers and chasms excepted) so homing in on the fastest is route from A to B should be fast despite the large grid.

If we combined this with a special case for underground routing system that used the standard convex (without sliding) area generation then we will end up with a, most likely, very small graph to traverse that knew where it connected to the outside.

This would also have the benefit of a simple way to make dwarves prefer inside to outside routes by weighting the outside connections highly (should someone wish to do that).

[zwei]

The problem I'm foreseeing with TCZ as currently envisioned is that their agent size dependent.  A 1x1 agent can go through a forest easily because all the obstacles are 1x1 and it can continually home-in on its destination and just take the diagonals when it runs into an obstacle.  But what about larger agents like wagons, two close trees can form an impenetrable barrier.  Their would need to be a TCZ for each agent size which will probably be prohibitive.

True, I never even thought about multi-tile agents when I thought up the TCZ approach.
But really, won't multi-tile creatures/wagons be rare enough that we could use brute force pathing for them? If a colossus should show up, we just perform a single, specific clearance-based flood fill starting at his current position and then brute A* over this - just like wagons (seem to) work right now?
Remember that the bigger the creature, the fewer its movement options. A four-tile creature can't even move through doors - A* inside a typical fortress should be a reasonably shallow search!

Simply put, I don't really feel multi-tile creatures/wagons are enough of a performance problem in practice to worry about. Especially since there's already a special clearance based system in place.

Three wagons on larger map are framerate killers (along with some ten extra critters.), for me it literally means drop of about 20% in fps anytime they appear.

---

However, you can easily create map for any odd-sized (1, 3, 5 ...) creature by expanding all obstacles: you can path them as one tile wide creature (see 'wagon access' map - all trees there count as 3x3 obstacles with tree in center)

Similar apporach can also work for even sized creatures - just grid transformation so that you path it as one-tile item.

This can even work for rectangle shaped creatures. (you create two maps - one for 90 degree rotation) and add then together with OR operator to get basic map of possible creature placement, then add them together with AND to get locations where you want to be able to turn - AND this map with map of access for square or longer side to get map where you need to turn and can, then  .... well, it can take some work to figure out fully, but i think it can be done with bit operations.

[Sunken]

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).

[Sunken]

Three wagons on larger map are framerate killers (along with some ten extra critters.), for me it literally means drop of about 20% in fps anytime they appear.

Are you sure it's mostly the wagons and not the critters?
But anyway, I would guess that not much optimizing has gone into the current wagon navigation system yet. With only small improvements it could probably handle most practical cases. Or so I'd think. Again - tests will tell...

[zwei]

Three wagons on larger map are framerate killers (along with some ten extra critters.), for me it literally means drop of about 20% in fps anytime they appear.

Are you sure it's mostly the wagons and not the critters?
But anyway, I would guess that not much optimizing has gone into the current wagon navigation system yet. With only small improvements it could probably handle most practical cases. Or so I'd think. Again - tests will tell...

Sure? No, but strong enough suspicion because lagging stops once they all reach trade depot.