Print

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

[Slogo]

I still think the HAA* is the way to go. It allows us to minimize the amount of data we need in memory and provides an efficient way to both deal with changes to the environment and all the different sizes and movement types. The algorithm would need a few adjustments but I think its manageable.

For the Annotated A* portion of the algorithm (ignoring the hierarchy portion of the algorithm) I can see it working like this.

Two types of clearance metrics (transportation types).

One is a main type, in DF's case this would be Ground and Air. The other is a secondary type. For DF I think you'd need Water, Fire, Smoke, Magma, obstacle (all), and obstacle (no pet). Each main type would have a pre-calculated clearance value stored in the map. Each sub-type would be regulated for an on-the-fly clearance calculation. This saves a lot on memory and, as you can see by the sub-types, they're infrequently encountered and/or very dynamic. This makes calculating them on the fly the best option anyways.

Each tile would have to be tagged with a main type and optionally tagged with any relevant subtypes. In DF's case every Ground tile would also be an Air tile but not vice versa. Creatures can only navigate over tiles of the appropriate type (ground or air) and for each tile calculated in the path finding algorithm the subtypes would be checked before placing it on the priority queue used by A*. To check for subtypes for a given square you simply recalculate the clearance for a square up to the creature's size but counting any inappropriate subtypes as a blocking tile.

Handling non square creatures provides an interesting twist to the algorithm.

 The clearance based algorithm will actually have to be modified to handle non-square multi-tile creatures and the z-axis. I'd change the algorithm like this:

Each tile has the following stored (all short ints):

• Maximum x axis clearance measured left to right
• Maximum y axis clearance measured top to bottom
• Maximum z-axis clearance measured from low to high
• Maximum square clearance measured left->right and top->bottom
• Minimum z-axis clearance measured across the square above

It sounds like a lot to store but I don't really think it'll be too bad, some values like maximum z-axis clearance could be changed to be calculated on the fly as it may not be checked very often.

The way we can check if an entity can fit in a particular tile would go through these steps:

1. Is creature's x and y sizes < the Maximum square clearance and is the creature's height below the minimum z-axis clearance for this square (all pre-calculated values)? If so creature can fit on tile and end.
2. Starting at the specified tile and moving from left->right based on creatures x size check the following:

• Is Maximum y-size for this tile > creature's y length
• Is maximum z-size for this tile > creature's z height

3. Starting at the specified tile and moving top->bottom based on the creature's y size check the following:

• Is the maximum x-size for this tile > creature's x length
• Is maximum z-height for this tile > creature's z-height

4. For the remaining tiles that the creature would be occupying if he stood at our starting tile check the z-height to make sure he fits.

Essentially you are checking each tile one to make sure that each tile is clear if the creature stands at the rectangular tile given. Since we pre-compute all these values it's a O(n) algorithm where n = # of tiles a creature occupies, but it gets better than that. By using the square properties that are also pre-calculated this algorithm could be even further optimized. For example if we wanted to fit a 3x2 creature in a tile at x,y and our square size was 2 then if the square size of the tile at x,y-1 was 2 our creature could fit in the given location.

Handling updates to the world is relatively cheap.

Yes you have to recalculate clearance values but it's super easy to do and only requires a minimal amount of clearance values to be updated. You only need to recalculate clearance values for tiles to the left (lower x value), 'above' (lower y value), and lower down (lower z-value). All other tiles will be unaffected. The way the algorithm would work is you'd run four loops

1. Would check all tiles in a straight right->left line until an obstacle was hit
2. Would check all tiles in a straight bottom->top line until an obstacle was hit
3. Would check all tiles in a upper->lower line until an obstacle was hit
4. Flood fill of all tiles with a lower x, y, and/or z value (basically all tiles not covered by the loops above). The tricky part here is knowing when you can stop checking tiles, I believe it's possibly to generally only update a minimal number of tiles with a clever algorithm to do this.

This is just a rough outline of how something like this could work, I'll organize and collect my thoughts more as I look into it but I really do think it's the way to go for this sort of problem. It provides a way to efficiently store all the data we need for multi-tile pathfinding while also providing a potentially efficient algorithm.

Also remember that if a multi-threading solution is used performance becomes much less of an issue (though still important obviously). Given that creatures can take >1 frame to make a movement we can potentially have leeway in how long we have to calculate their specific path.

[Impaler[WrG]]

Yea I'm also staring to favor the know and documented methods more, they at least provide a well defined starting point.  HAA* has the simplest tiling system, it just chops the map into a grid without doing anything fancy.  Lets start by building what you've described a HAA* system with support for for multiple movement types and multi-tile agents and see if the other schemes provide an improvement, which I think they will ultimately be able.  In fact I see no reason that the concept of TCV cant be mixed with zones that must be crossed with A*, the high level zone search can be agnostic as to the nature of the zones so long as it can query them for being able to be crossed by various agents.

[cephalo]

I've done some pathfinding work in the past. One thing you might look at is a seed fill algorithm. There's a fast 2D one in Graphics Gems 2 that might be extended to 3D. Once you have the map's connectable regions mapped out, you can update it incrementally when a local choke point is blocked off. Do a seed fill on one of the blocked tiles neighbors to see if it ends up on the other side, if not then you are left with two distinct regions already mapped out for next time.

For 'soft' blocks, treat them like hard blocks as far as region ID is concerned. Each region could have list of what regions it might be connected to depending on door state.

This way you can avoid failed paths. I believe it's much cheaper to seed fill an area than to search a whole area for a path with the astar algorithm.

[Shades]

Just a thought, how often does DF currently recalculate paths for moving critters. Because if it's often we might be better off not improving how path finding runs but just how often by storing a map of current paths and only recalculate them if one of those grids changes. Granted this will ignore any new shorter paths being opened while a critter is moving.

[Sunken]

In fact I see no reason that the concept of TCV cant be mixed with zones that must be crossed with A*, the high level zone search can be agnostic as to the nature of the zones so long as it can query them for being able to be crossed by various agents.

Right, that's an important point. And this modularity should be maintained while developing, so that new approaches for each layer can be tried out and compared.

[Shades]

Right, that's an important point. And this modularity should be maintained while developing, so that new approaches for each layer can be tried out and compared.

As long as our testing harness is suitably templated then we can just make sure all map operations are reasonably standard operations and so easy to replace with a new system. Maybe it's worth knocking up a quick harness this weekend, what kind of testing environment do we need to run.

A simple grid based on a fake df map of some kind? Ideally with some horrible example paths to attempt? Then the harness can just be run and display times taken at each stage, as well as distances generated (or at least % of optimal path).

[Impaler[WrG]]

Theirs no reason not to use real map data we have access to it with dfhack and Khazad, we can even get the workshops and stockpiles so I'd go with a system that takes those into account when doing the path requests.  Something mixture of the following types of path requests

Random Workshop -> Random Workshop
Random stockpile tile -> Random Workshop
Random Workshop -> Random stockpile tile
Random stockpile tile -> Random stockpile
Random Map tile -> Random stockpile tile
Random Map tile -> Random Map tile

(Random Map tile means a tile any ware on the map which is to simulate things like item pickup, tree cutting etc etc)

This would produce paths that are more like those actually coming out of DF and provide a lot of identical repeat path requests (or at least very close to identical) which will be a major factor in determining the efficiency of path caching.

[Starver]

One is a main type, in DF's case this would be Ground and Air. The other is a secondary type. For DF I think you'd need Water, Fire, Smoke, Magma, obstacle (all), and obstacle (no pet).[...]

I forgot to bring in my memory stick with what I wrote up last night, but (if I remember correctly) I had seven different types of basic "passable" listed down for the system I was thinking of:

• Walk - standard movement: i.e. surface spot to surface spot
• Tunnel - for (future) burrowing entities (though might want to make distinction between burrowing (soil) and tunelling (rock (and soil)) entities, or even avoid "burrow" as a term to avoid mixing up with the upcoming user-defined areas thingummy): relates to all underground-to-underground pathing possibilities, and any initial transition from 'open' to subterrainean, if required[1](
• Fly - all controlled aerial manouevers, with or without a surface immediately below (though perhaps flyer/walker creatures could choose the method that best suits them, if there is a 'ground' of some kind to stand on, given their energy levels?)
• Swim(Water) - all movement within water, though surface swimming might want to be decoupled from subsurface swimming
• Swim(Magma) - ditto as water, but separated for obvious reasons
• Climb - for those that can (c.f. Adventure mode single Alt-movement out of a river, but also spiders and other 'wallcrawlers' without limit, could also govern movement across ceiling of multi-Z cavern).  Paths for climb-enabled creatures might allow only a certain number of successive climb 'movements' in a path (perhaps a single one), representing the limit to their ability to heave themselves on top of a certain height wall.  Large creatures or ones that can jump might be given an allowance in the Raws, and the pathing algorithm would decrement accordingly in searching for the movement
• Jump - relates initially to a deliberate stepping off of edges (applicable only to those that don't fly, of course), but for the sake of compactness includes "fall" (air-only location to air-only location immediately below, unless inertia is a concept, in which case larger and gap-crossing can be weighted in according to ability).  Bigger (or "jumping") creatures might have an allowance based on how far they can 'step down', but otherwise a 'jump' is weighted according to relative chance of injury (perhaps literally 'weighted'... drop a mouse down a mineshaft and it might survive when it hits the bottom, drop an elephant and it'll 'splash').  While not strictly a pathing issue, emergency movement away from danger (comparable to the current dodging away from opponents) might force creatures to take action beyond any 'jump+fall' allowance they would have and enter a 'plummet' count, which would of course be heavily injury penalised.

Obviously, the above relates to my own ideas, I'd completely forgotten about pet-specific routing biases (despite mentioning my ideas about it, the other day) and I'm not sure what if smoke features in my idea (save for a visibility bias in pathing, in which case would 'mist' and 'miasma' also be necessary?), and for a moment (until I saw the "(no pet)" version), I wasn't sure if 'obstacle' meant like lone pillars in TCZs or my climb/jump idea.

For creatures with multiple movement opportunities would have weighted tendencies towards one or another method, but would consider shorter 'difficult' paths than longer 'easy' ones, where the shortcut is short enough.  e.g. tunnelers, except as mentioned in [1], below, would walk normally but (assuming they had 'knowledge' of a target they want to reach, like breaching a fortification or wanting quick egress from a half-closed trap situation) would be free to tunnel.  Scrambling across a barrier might suit a climber who normally walks, flying creatures who could might be forced to perambulate in single-tile-cross-section tunnels for some reason or another, or at least be penanalised for trying to flap their way through when other creatures exist.  But I appreciate that a lot of this is no longer strictly pathing, but involves (possible future) game mechanics.


[1] I could imagine some creatures could be purely rock-dwellers leaving no trace of tunnel, and not intruding upon 'open' areas, but the main three possibilities would be: a) rock-morphers 'eating' or otherwise digging through leaves behind 'solid' rubble like snail trails; b) classic tunelling, a la dwarf, with certain (variable? improvable?) chance of leaving/not leaving spoil; c) full on consumption, evaporation or metabolising of all rock, leaving void.


PPS, I don't know if it's since I last let IE update, but the textarea editing box on this machine doesn't scroll like it should/used to, and keeps jumping back up even when I'm cursoring down.  Annoying.  I'm having to type this in a text editor and CnP it in.

[Slogo]

Digging creatures probably isn't really a concern of ours. If a creature is digging through rock then I'd imagine their ideal route would be a straight line down the tunnel. I'd expect any path finding algorithm to simply get the location of the next hole to dig and we'd be responsible for moving them to the appropriate dig location.

Dodging and falling really isn't a concern of path finding either but rather an issue of locomotion. A creature dodges to a specified location or falls down based on gravity and dodging, not some pre-planned path.

As for having preference for certain types of routes, well that's easy! All you need to do is allow for our methods to accept a set of weights for different types/sub-types of tiles. These weights would factor into the A* heuristic causing the optimal path to 'bend' towards prefered methods of movement when possible.

[Sunken]

Digging creatures probably isn't really a concern of ours. If a creature is digging through rock then I'd imagine their ideal route would be a straight line down the tunnel. I'd expect any path finding algorithm to simply get the location of the next hole to dig and we'd be responsible for moving them to the appropriate dig location.

I assume he was talking about tunneling creatures, not just digging straight down. Still, since a tunneler has such great freedom of movement, raw A* will probably be plenty fast for that.

Dodging and falling really isn't a concern of path finding either but rather an issue of locomotion. A creature dodges to a specified location or falls down based on gravity and dodging, not some pre-planned path.

Jumping down a low cliff or hole is very much a valid choice of deliberate pathing in some situations. Some creatures may be impervious to the effects of a fall and it would be silly of them not to use gravity to get to where they want to go.

As for having preference for certain types of routes, well that's easy! All you need to do is allow for our methods to accept a set of weights for different types/sub-types of tiles. These weights would factor into the A* heuristic causing the optimal path to 'bend' towards prefered methods of movement when possible.

You can't factor them into the A* heuristic, only the exact cost.

[Starver]

Digging creatures probably isn't really a concern of ours. If a creature is digging through rock then I'd imagine their ideal route would be a straight line down the tunnel. I'd expect any path finding algorithm to simply get the location of the next hole to dig and we'd be responsible for moving them to the appropriate dig location.

Not right now it isn't, and I keep forgetting that this is a project to see how to handle currently expected pathing, but it should be considered insoar as future sapper/siege-breaking developments.  Normally, it would be a straight (or at least appropriately staggered) route, but if we're actively defending against such activities with water/magma-filled cavities, etc, and the sappers know that they need to dig around, it would be good to be able to cater for that.

Dodging and falling really isn't a concern of path finding either but rather an issue of locomotion. A creature dodges to a specified location or falls down based on gravity and dodging, not some pre-planned path.

I mention dodging and falling, but I meant for deliberate jumping off (and climbing up) to feature as a valid pathing possibility.  I know I've often made 'causeway' labyrinths (enforced by bridge removal, or just permanently like that) to guide enemies through a carefully controlled killing-fields.  Smart enemies could "Alt-Move" off-and-below like an adventurer on a river-bank, to no actual injury, and then Alt-Move onto the next adjacent leg of the causeway (or run around the channelled area, which often leeds more directly to my interior, given I might want to send soldiers there to handle enemies that did fall off).  And larger creatures should be able to stride up onto/down off of at least one Z-level of wall/equivalent, so they should be able to exploit that routing as a matter of course, no question.

But as long as we can get air/ground/possibly-amphibious routing sorted in the same algorithm, then the above concerns are probably minor details that can be easily integrated into an improved system, so I'll leave these as just considerations, and get back to the algorithm side, when I get chance.

[Starver]

I assume he was talking about tunneling creatures, not just digging straight down.

Yes, and I think "straight" was straight (and/or stagger-equivalent of straight) in any direction, A->B, was how Slogo meant as well.  Lestwise, that's how I took it.

(At least when it isn't 'random-walk' messing about by exploratory enemies without the information needed to head to a specific location.  I know that information, or at least the lack of, is beyond the immediate scope of this 'omniscient' pathing process, though...)

[Fieari]

For movement types, I think an important one would have to be "Building Destroyer", for pathing through gates or constructed walls with trolls or armies with battering rams, catapults, etc.  Also, Tunneling as a path type is important because while the underground is USUALLY trivially connected, there are gaps in the form of caves, magma, underground rivers, and so forth.

If we want to stick with 7 movement types, I'd drop "jump".  It's a cool idea, but I think it'd get too complicated, especially because if you wanted things to jump different heights you'd need a different movement category for each height.

[chmod]

I apologize for not reading the whole thread, but has anyone suggested simple machine-learning for pathfinding? I would start simple, as that's all you need in the beginning of a fort. Random movement coupled with reward/punishment for finding good paths. The whole thing would be a bit organic. But you could save a general routine to use with all dwarfs. So it would be like a hive-mind. I've seen some success with things this simple before, although it was just a proof on concept on a simple Cartesian plane.

[Slogo]

For movement types, I think an important one would have to be "Building Destroyer", for pathing through gates or constructed walls with trolls or armies with battering rams, catapults, etc.  Also, Tunneling as a path type is important because while the underground is USUALLY trivially connected, there are gaps in the form of caves, magma, underground rivers, and so forth.

If we want to stick with 7 movement types, I'd drop "jump".  It's a cool idea, but I think it'd get too complicated, especially because if you wanted things to jump different heights you'd need a different movement category for each height.

You can use another subtype to handle everything since they're relatively cheap to have. They don't need to drop out anything, you can easily have more than 7. Just add a building destroyer 1 subtype for tiles with floodgates, windows, etc. and allow for building destroyer creatures to pass through. Impassable workshop tiles and other constructions would get a building destroyer 2 subtype. For doors, hatches, and the like they'd be covered by allowing building destroyer creatures to path through obstacle (no pet) and obstacle (all) tiles. Building destroyer creatures, when ready to move, would just check that their next tile doesn't have a construction, if it does destroy it first.