Print

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

[Shades]

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

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.

If we limited the size of TCZ's as someone suggested earlier this would have a similar effect of course, but again we would end up with long interfaces as the TCZ's are stopped prematurely.

With most fortresses the interfaces locations at doors would probably result in small zone, but I wouldn't want to rely on it.

[dreiche2]

Concerning the wagons, I don't think you guys should try to solve all problems at once. A DF with an improved pathfinder that falls back to the default solution for wagons would still be better.

I myself also started implementing my pathfinder ideas quite some while ago, but then real life took over. What I want to mention though is two things:

1) It could be possible to utilize that the transitions in between z levels, i.e. stairs and ramps, are known beforehand and relatively sparse compared to how many tiles there are in total. That's basically what I tried to implement, but I didn't get very far.

2) :
Discussions about pathfinding ideas come up and die out regularly on this forum. I think for a PathFinder project to be actually fruitful it would be most beneficial if, for a start, someone sits down and implements a basic algorithm testing framework. That is, have a program or library that generates pathing jobs on DF-maps or simplified maps. Different pathfinder algorithms would have access to the map data and would retrieve the pathing jobs. Have some standardized benchmarks to compare the different algorithms' performance. Maybe even have some GUI for easy inspection of the maps, pathing jobs and generated paths.

Having such a testing framework would serve as starting point for people to try out their ideas. I think implementing this framework would be the most useful thing for a start.

[Sunken]

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.

[Shades]

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.

As long as we ensure a limit on size of zone, which I figured breaking on each object would do, then we should ensure the distance across a zone is small enough that it's only a small percentage of inefficiency. Technically we could get cases where we have 19 zones at an average of 20 squares each or 20 zones at an average of 1 square and so pick the wrong route but this should such a rare case we can probably ignore it.

I would recommend the weight of a zone is based on it's size (and so average cost to cross) as well though, just to help this kind of problem be avoided it.

Further, a common strategy would be to use the suboptimal route to give an initial movement for the critter and then let the perfect route be generated over a number of updates and splice the routes together. Although this is generally to allow user interaction to show an instant response so probably won't help in our case.

[Starver]

Maybe you guys could solve the animal pathfinding issue vs animal forbidden doors? Unless more than the pathfinding code is involved.

(Coming late to this (comparitively), and not yet having read all that is discussed so far, so excuse me if I'm a little behind.)

If you look at the complexity involved in maintaining (frexample) region-connectivity across a whole map for one route-finding algorithm (e.g. the one for non-amphibious land-based creatures), it seems relatively trivial to maintain parallel route-maps for such as aerial, aquatic, magma-surviving, etc, as well as a "pet map" that handles pet-forbidden doors as non-routable[1] (but includes knowledge of transient 'openness' if a non-pet wanders through...).

The above possibilities means multiplication 5-fold of the map (or, rather, 5 maps if better optimisation of each map can be made), In a worst-case !N problem of every-tile-to-every-tile routes being stored it would be an insifnificant increase.  For better logN-type situations it would not be as good, of course.


Now, I spent a while last night writing in an idea I was adapting from a vector-based environment that I'd had a long time in
planning (started thinking about it circa the time of original Doom, which dates it), but reading this thread further it looks like some of the key features (e.g. convex zones, built up from merging the leafs of a trinary tree structure where shared border cells can be optimised away inbetween "limiting features", letting each higher level zone governing a convex mass of connectable sub-zones) are really not that innovative, so I'll go back to the drawing board before saying anything about that.

[Shades]

it seems relatively trivial to maintain parallel route-maps for such as aerial, aquatic, magma-surviving, etc, as well as a "pet map" that handles pet-forbidden doors as non-routable

Trivial yes, but memory hungry if a trivial method is used. As you mention they might be better ways to store the 5 (or more) fold data.

A possibility would be that each zone was either passable or not (ie: no zone could have both a passable and a shorter but non-passable route) so zone calculations would have to generate two zones where there was two adjacent routes, one with was all open, one which was not passable by a subgroup. Then the path finding could just treat non-passable as inf cost if that critter cannot pass that way. Not perfect, but fairly simple.

[Impaler[WrG]]

Discussions about pathfinding ideas come up and die out regularly on this forum. I think for a PathFinder project to be actually fruitful it would be most beneficial if, for a start, someone sits down and implements a basic algorithm testing framework. That is, have a program or library that generates pathing jobs on DF-maps or simplified maps. Different pathfinder algorithms would have access to the map data and would retrieve the pathing jobs. Have some standardized benchmarks to compare the different algorithms' performance. Maybe even have some GUI for easy inspection of the maps, pathing jobs and generated paths.

Having such a testing framework would serve as starting point for people to try out their ideas. I think implementing this framework would be the most useful thing for a start.

Excellent point dreiche, a system for benchmarking the whole thing is going to be key, real performance numbers put an end to debates like nothing else can.  I suspect we will see multiple versions of the zone creation routines and will need to pick amongst them based on performance testing.

I'd like to speculate on the API, it should be as neutral towards the actual game design as possible, the only thing that should be assumed is a grid system in 2 or 3 dimensions with multiple movement types.

Grid coordinates should be in 3 Signed ints and movement types expressed as bit fields (thus allowing for the combination of multiple types), that gives us something like

void loadMapData(int x, int y, int z, int Movement)

void changeMapData(int x, int y, int z, int Movement)

void buildZones()

loadMapData is used to inject the map data and just stores it without processing it, buildZones would do a full scan an the map and build the initial zones, changeMapData would update a tile with new data and trigger what ever zone changes are appropriate.

The pathfinding work would be done with

Path getPath(int x, int y, int z, int x, int y, int z, int Movement, int size)

int getEstimate(int x, int y, int z, int x, int y, int z, int Movement, int size)

getPath returns some kind of Pathway description object the format of which is still not determined, multiple type could be possible such as a zone level path and a per tile path.  getEstimate is the quick heuristic I spoke of earlier, it doesn't do as much work as a full path but it needs to be a LOT faster and be within about 10% of the true path length.

[Starver]

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.

I'm probably reading this wrong (still progressing through the thread) or it is commented on later, but, a rectilinear area that is 2x5 would not be a limiter/untravelable area for a wagon wishing to travel across it between the twi 5-wide borders.

The 2-wide borders would be considered non-passable, of course.  Though that would be wrong if the corners were not passage-limiting features, and instead just arbitrary points chosen to create a rectangle.  Two adjacent but side-slipped 2x5 rectangles (so that they cannot be represented as a single 4x5 rectangular area or larger, due to limiting features carving out 'corners') might allow free passage to a wagon-sized agent along their shared borderline and thus partially across one or other of the 2-wide border.

My homegrown method (which looks like it has been long-presaged, I need to sit down and read up on what's actually been done by others on this) working around convex areas relies upon all corners being limiting features, and thus the borders can be similarly reliably sampled for passage or otherwise for arbitrary-sized units, and the truth table of passage for the convex-area-of-convex-areas (one, or more, levels up) can account for the intricracies of inter-zone travel accordingly.

(Until I get to the end of this thread, I am of course postulating into the wind, I think the above is probably already known, and possibly rejected for some reason that hasn't occured to me.)

[DeathOfRats]

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?

I was talking about creation, but the incremental changes suffer from the same problem, too. Wouldn't you have to check your addition against all other tiles in the TCZ? Or could you just settle with checking against certain key points, or points close (i.e., local) to the point where you are making the change?

[Impaler[WrG]]

I'm probably reading this wrong (still progressing through the thread) or it is commented on later, but, a rectilinear area that is 2x5 would not be a limiter/untravelable area for a wagon wishing to travel across it between the twi 5-wide borders.

Yep hadn't considered the possibility of zones abutting each other in ways that create movable areas still larger then the zones.  It's a tricky problem all right.

[Starver]

it seems relatively trivial to maintain parallel route-maps for such as aerial, aquatic, magma-surviving, etc, as well as a "pet map" that handles pet-forbidden doors as non-routable

Trivial yes, but memory hungry if a trivial method is used. As you mention they might be better ways to store the 5 (or more) fold data.

What I also meant to mention is that a bit-wise "passable/not-passable" flag was made, that had not been given any form of compressive optimisation (by programmer or compiler) and was inhabiting an entire byte regardless of only being true/false, then a number of different flags could be loaded into the same byte of storage to no extra memory usage (and trivial logic applied to the setting/retrieval of the state).  But I still err towards zone-trees optimised towards differing requirements.

A possibility would be that each zone was either passable or not (ie: no zone could have both a passable and a shorter but non-passable route) so zone calculations would have to generate two zones where there was two adjacent routes, one with was all open, one which was not passable by a subgroup. Then the path finding could just treat non-passable as inf cost if that critter cannot pass that way. Not perfect, but fairly simple.

This reminds me of the vectorised world I have breifly aluded to.  Surface-to-surface convex polyhedra, the sides being indexed (at the simplest level) towards the polyhedra and subsequent side of that polyhedra to which it abuts (if any, and not a complete boundary, i.e. a wall), but while normally it would be a 1:1 matching for all phenomena (or with outright exceptions, such as "invisible forcewall" preventing physical movement but allowing vision, and "energy barrier" allowing everything through but certain classes of weapon discharge, "glass" being like the invisible forcewall but able to be "smashed" and revoked by any physical weapon discharge of sufficient power) there were possibilities of making physical transit and optical transit progress into alternate 'target' polyhedra (with equivalent 'receptive' surface), which I suppose one could liken to a "stargate, without the rippling pool effect" (though you could have given it a rippling pool effect as well, remember how old this idea was...  I can't remember when Stargate first popped into my consciousness).  Alongside other interesting possibilities[1], this meant that the environment could involve 'overlaid' polyhedra where the physical and optical aspects could pass through alternate 'overlaid' dimensions in the same logical space. 

So...  if we could not establish every zone to be 'one-size fits all' and be able to pack all necessary border-to-border passagability information into each, it would not be too difficult to have transit from one zone (say an internal zone, entirely constrained by the bedrock, and thus pretty much the same to any creature that hadn't a tunelling capability to fall back on) guided by the zone-boundary definition to split so that surface travellers make use of a 'surface friendly' target zone, one of many overlaying the landscape that are interupted by trees and channels and other impassables, while aerial creatures are free to fly into the 'atmospheric'-styled zone, which may still have trees as obstacles at the surface (either zone limiters in Z-spanning convex polyhedra, or singular features to avoid within that) but treats channels as vertical borders into 'deep ditch' zones with aerial access possibilities, or can be ignored and passed over.  The 'logical' positions of ground-dwellers in the surface-zoning would be known within the aerial-zoning hierarchy through passing the absolute cartesian coordinates between the two, so allowing appropriate pathing and 'hunting' of ground dwellers by aerial ones (despite inhabitting a different 'zone-space') and a ground-based archer would have no problem targetting a flyer.  If the surface-pather was amphibious and passed into an aquatic-styled zone to swim below the surface, this would put them beyond a non-transitable boundary as far as any particicular aerial agent was concerned, if it was hunting and not an aquatic-capable creature (e.g. gannet) able to undertake that transit.


[1] Scaled travel: i.e. transit between polyhedra surfaces of differing areas, essentially altered the avatar's relative size in the environment if he looped back to origin via a different route ('Distorted' travel, also, where the avatar changes relative width and height).
  Mono-directionality in some/all of the physical/optical/sonic/etc propogations.
  "Movable holes" in the environment, that could be slide around one one or both sides.
  Simple implementation of mirrors (back then Duke Nukem 3D hadn't popped up, so I'd not seen it done) by linking the optical 'outward' transit to the same facet of the polygon
  Rooms with a rotational symmetry of 0.5, where you have to walk around the central pillar 'twice' to get back to your original position.
Some of the above was inspired by "Toonyverse" physics, I'm sure you can imagine.[/1]

[kurokikaze]

Whoa, great project. Too bad i'm not into C anymore.

[Sunken]

I was talking about creation, but the incremental changes suffer from the same problem, too. Wouldn't you have to check your addition against all other tiles in the TCZ? Or could you just settle with checking against certain key points, or points close (i.e., local) to the point where you are making the change?

As I already said, you only need to check a tile against the closest other tile in the TCZ that is in conflict with it. You do this by finding conflicting directions, and processing just those tiles that are closer to the seed and in this direction. It is on the order of the size of the TCZ, but with a very small factor on it.

[Sunken]

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

[Ampersand]

I'm going to go ahead and divulge what I've figured out about how path-finding and job assignment works in Dwarf Fortress after some experimentation.

The Dwarf Fortress map is not 2 dimensional, or 3 dimensional. It is 5 dimensional. Allow me to explain.

The fifth dimension is the most obvious; the Z-level dimension, the first four are not so obvious.

First we have the recognizable 2D grid that makes up the visible map, but there is an invisible, second 2D grid overlaid on top of that, each square of this consisting of 16X16 squares of the visible grid. I'm not sure how important this grid is in terms of path finding to a particular point, but I do know how tasks are assigned in this grid. With the top left most 16x16 square being square 1, the one below it being square 2, and so on, tasks are ordered first by where in this super grid they are, with a preference for the lower numbers, and then by their position within the subgrid of points within that square, starting from the top left within the subgrid.

So we're dealing with coordinates that look more like (X, Y,{A, B}), Z. The order is important, as the Z coordinate is not relevant in terms of calculating distance, as we all know far too well, Everything with the parentheses is used to determine how far away something is, then the Z is added on afterward to do actual path finding to that point. This is obviously something that needs fixing.

I'm not entirely sure if the A, B coordinates are used in the pathfinding, as opposed to only task ordering, though exploiting their existence may make pathfinding more efficient.