Print

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

[Fieari]

Hm.  Those categories do seem to be pretty good, although they aren't as customizable... but you do also need movement for dragons, who should be able to fly, swim, walk, magmaswim, and even destroy stuff.

I read the powerpoint version of the HAA* paper above.  I didn't see anything about multitile creatures though...

[Shades]

Thus, to fit current DF movement types into categories, you'd have:
walker ("floor", "ramp", "stairs", "unlocked door" tiles with no water or magma)
flyer (walker tiles + "open space" tiles -- this maps to giant eagles)
swimmer (any tile with water level > 4 -- this maps to carp)
amphibious ( walker + swimmer -- this maps to snakemen/lungfish)
dwarf( walker + tiles with water level <= 4 + "pet-impassible doors")
magmaphibian(walker tiles (+ any magma) + "open space" tiles with magma > 4 -- this is imps, etc.)
destroyer(walker + "locked doors" + "buildings" -- this maps to trolls, dragons, etc.)
digger( walker + "wall" tiles)

This list is not 8, you even list how some of the flags combine to make others (amphibious would just have both walker and swimmer set for example) seems excessive to record them as well. Also I wouldn't worry so much about how many we have as long as a sensible structure is used to store the information.

I'd use:
walker (as above but should water < 4 be included here too?)
flyer (open space)
swimmer
magmaswimmer
pet passable / door opener
destroyer ("buildings" what is the difference between destroyer 1 and 2)

Not sure if we need digger? Adding a new movement type is cheap so we can when we need. Note that my swimmer groups include climbing out of water/magma if walker is enabled so adjacent zones would only need to mark which they are.

As we only have one critter larger than a tile I'd suggest just doing the current pathfinding for it as needed, if we come up with a clever system great but otherwise just ignore it for now.

[Idles]

This list is not 8, you even list how some of the flags combine to make others (amphibious would just have both walker and swimmer set for example) seems excessive to record them as well.

....

As we only have one critter larger than a tile I'd suggest just doing the current pathfinding for it as needed, if we come up with a clever system great but otherwise just ignore it for now.

About your first point: if you read the HAA* paper, the important thing to take away from it is that each creature is able to move over only a part of the map. A "movement type", as I defined it, is a set of rules from which you can figure out whether or not a creature can move through a tile (given that you have all the information that DF currently stores about tiles). By using these "movement types", you construct the abstract "high level" path graph, where the annotations of edges include information defining which one (and only one) of the "movement types" is valid for that edge. That information could take the form of a byte which stores flags (1 flag for each of the 8 movement types I defined).

For the low-level tile-map (which already exists inside DF), you obviously wouldn't store that flag annotation byte, since you would be duplicating information already present in the tile map. Instead, you'd just rely on the information that DF already provides, and have a function that takes a tile and spits out a byte (or word or whatever) with the flags for which "movement types" are valid for that tile.

About your second point: The HAA* paper already has a clearly defined method for handling multiple tile creatures. Perhaps you should read it? That said, we could always special-case them, by just letting them use regular old A* without any enhancements. However, since the point of this project is to improve the current pathfinder, we might as well use the HAA* method for multiple-tile creatures.

About dragons, and other creatures that don't clearly fall into a single "movement type": we can just let them use regular A*, because having to store an abstract path graph for each possible permutation of tiles that a creature can move through would quickly eat up all of our memory. My list of movement types was an attempt to shoehorn all the common creatures into as few categories as possible.

Here's a link to the HAA* website with accompanying paper that I'm referring to: here.

[CobaltKobold]

I still do dispute the need for a seperate BUILDINGDESTROYER:1 or 2.  I would really prefer just weighting the cost of going through different types of constructions and materials.  Moving it from a "is it possible" question to a "is it really worth the effort" question.  If you're the sort of creature that will bust through stuff to get places, the only question is how difficult busting through that stuff is.

I'd agree if it were actually attacking and stuff, but DESTROYER1 can only destroy doors and a few other similarly flimsy things, while 2 can get through any nonconstruction.

Why do people suggest weighting paths that cannot be traversed?

[Idles]

Why do people suggest weighting paths that cannot be traversed?

Probably lack of understanding about how path finding algorithms work.

[Shades]

Here's a link to the HAA* website with accompanying paper that I'm referring to: here.

The last HHA* (well technically HPA*) differed from that in that routes across zones where stored by type and not grouped so a critter would pick whichever route worked for it, combining them would be faster but at the cost of memory. Probably a cheap enough trade off mind you.

I still think the zoned A* will probably be more efficient though (although again at the cost of memory as you don't have regular cluster sizes)

Edit: of course trying different methods is the point of this

[qwertyuiopas]

If the system only supports weighting, make the last bit set if it CAN be pathed at all. No silly mucking around in infinites, especially infinite improbability(Though with that, dwarves wouldn't have problems...)

[Sunken]

8 movement types will never cut it, even if we don't try to solve problems that are not currently solved (and we want to, don't we?). Soldiers, pets, invaders and ordinary dwarfs are all different walker subtypes, and we'll want more if certain doors are going to be accessible only to certain people, for example. It's a challenge we have to deal with in any solution we come up with.

[Shades]

If the system only supports weighting, make the last bit set if it CAN be pathed at all. No silly mucking around in infinites, especially infinite improbability(Though with that, dwarves wouldn't have problems...)

In most pathing systems I've used/written hitting an infinite weighted value for a link for a given movement type meant it couldn't be taken and so wasn't added to the list of solutions. Don't worry overly about terminology I think, basically blocked is blocked however the under laying algorithm handles it.

8 movement types will never cut it, even if we don't try to solve problems that are not currently solved (and we want to, don't we?). Soldiers, pets, invaders and ordinary dwarfs are all different walker subtypes, and we'll want more if certain doors are going to be accessible only to certain people, for example. It's a challenge we have to deal with in any solution we come up with.

I don't think the number is relevant as long as we know what they are at some point. However it depends what you meant by movement types, the HAA* suggested wanted combinations of movement styles which means we'd need more types and more memory used but saves us calculations in real time and so increases performance. Other methods might only need a flag of what movement styles are possible in which case I have a hard time thinking of even eight.

[shadow_slicer]

Why bother with movement types at all? Why can't we just use a callback function to determine the cost/if pathable of some opaque movement class? There's really no reason to store all the path costs (27 of them per each tile!) since they're easy to calculate. This way we don't worry about bitmasks and composite movement classes or things like that, we only ask the client "what is the cost from here to here".

For example, the client would enable a movement class (so we would create/modify our hierachy to support it) by calling some function:
int movementclass = PathLibrary::CreateMovementClass( pathcostfuncptr)
where pathcostfuncptr is a function pointer pointing to a function of the form:
int DwarfPathCost(point p1, point p2),
with point p1 and p2 being adjacent points (i.e. p2 is one of the 27 points surrounding and including p1). This DwarfPathCost will return MAX_INT if it is not passible, otherwise the path cost. Note that for the case of p1=p2, this determines whether or not a movementclass is allowed to be in this square, so it should be either 0 or MAX_INT.

Then the client could get routes using PathLibrary::GetPath(p1, p2, movementclass) to use the hierarchical model, or PathLibrary::GetPath(p1, p2, pathcostfuncptr) to use plain A*.

[Shades]

No reason we can't for some algorithms. some require to be able to pre-calculate zones though so although they might be able to ask the cost on the fly they would want to be able to generate a zone based on movement type.

Might be able to do the HAA* clusters like that though.

[Sunken]

shadow_slicer, I already pointed out that this flexibility was necessary a few pages back. But you're forgetting a key thing - the connectivity map. That can't be computed on demand like this; that would be insanely expensive. And we need one if we're going to use any sort of A*, otherwise that will become insanely inefficient.

It's a real problem but we can perhaps tackle it by problem relaxation and heuristics - like maintaining only some connectivity maps and supplementing them on demand, somehow. Or merging them on demand.

[CobaltKobold]

I'm no pathfinding whiz, but to me, there are common move methods- swim/fly/walk(later, burrow)- and uncommonly passable things- locked doors, buildings, for instance.

From what I read around here, the current solution is to just have one real connectivity map (for walking)- and those with odd abilities path to the nearest affected passable- to destroy or pass through it- and then path onward after they do so. Fliers and swimmers seem to be a bit wonky, not sure how they're handled.

I can think of easy ways to out-engineer this solution- making a support with a brick wall on it for buildingdestroyers, making a locked doorway to magma for lockpickers-so it's clearly granting suboptimal results.

So, what ways of MOSTLY ignoring these edges will still produce good  (This may be a bad idea.)

[Footkerchief]

From what I read around here, the current solution is to just have one real connectivity map (for walking)- and those with odd abilities path to the nearest affected passable- to destroy or pass through it- and then path onward after they do so. Fliers and swimmers seem to be a bit wonky, not sure how they're handled.

It just runs A* between the goal and destination.  Ramps, stairs, water and flight are just ways to move from tile to tile.  It won't try an A* path if the connected components don't match up, which is where some problems arise (as with flight-modded dwarves in fort mode and so on).  Regular flying creatures use something more like short-range flood fills to combat this, if I remember, but they can't use arbitrary A* if they don't have a component check or else the processor will die on pathing failures.

I think swimmers do the same thing, since they only aggro for nearby creatures.

[qwertyuiopas]

Why bother with movement types at all? Why can't we just use a callback function to determine the cost/if pathable of some opaque movement class? There's really no reason to store all the path costs (27 of them per each tile!) since they're easy to calculate. This way we don't worry about bitmasks and composite movement classes or things like that, we only ask the client "what is the cost from here to here".

For example, the client would enable a movement class (so we would create/modify our hierachy to support it) by calling some function:
int movementclass = PathLibrary::CreateMovementClass( pathcostfuncptr)
where pathcostfuncptr is a function pointer pointing to a function of the form:
int DwarfPathCost(point p1, point p2),
with point p1 and p2 being adjacent points (i.e. p2 is one of the 27 points surrounding and including p1). This DwarfPathCost will return MAX_INT if it is not passible, otherwise the path cost. Note that for the case of p1=p2, this determines whether or not a movementclass is allowed to be in this square, so it should be either 0 or MAX_INT.

Then the client could get routes using PathLibrary::GetPath(p1, p2, movementclass) to use the hierarchical model, or PathLibrary::GetPath(p1, p2, pathcostfuncptr) to use plain A*.

That is written as if this was going to be an internal library, I think, but most of the other discussion assumes an external library(DLL, I think?)
That, or I have no clue how inter-program function calls work in C++.