acting almost like a server in which it receives an initial dump of map data from the client,
Major challenge you will face are disconnected / reconnected world areas and 'soft' changes.What he said, the smartest move probably is to let the 'server' constantly run to calculate different map possibilities and store them. Maybe even try and program the pathfinder to change the blocked parts? (If bridge is in way, then take route 16)
Simple drawbridge raise or door lock can disconnect and reconnect large parts of world, leading to potentially huge overhead and path recalculations with no benefit, if you are to deliver real improvement, you will need to be able to store several versions of already pathed map cached to avoid pointless recalculations for expected, but random, changes.
Also, since you know how map will look like in n+ seconds (cue taken from dig/build/cut tree designations and dwarf locations), you can have pathed maps (or sections of pathed map) ready to be instantly plugged in when construction/designation is being excecuted and when it is finished.
You can also, for example, precalculate map for next season because you know that tree saplings will become obstacles.
If you work with prediction in separate thread, you can have already updated map when game commints changes and really requests path.
I think you are looking for more df-connected system than you would expect.
---
Also, I hope you did consider batching map changes and not commiting them and recalculation pathing before actual path is requested: Often, several changes can happen at same time.
What he said, the smartest move probably is to let the 'server' constantly run to calculate different map possibilities and store them. Maybe even try and program the pathfinder to change the blocked parts? (If bridge is in way, then take route 16)
Also, I hope you did consider batching map changes and not commiting them and recalculation pathing before actual path is requested: Often, several changes can happen at same time.
Major challenge you will face are disconnected / reconnected world areas and 'soft' changes.
@Draco18s: I think I see more or less what you mean, but, I'm not 100% sure how it'd work. How do you path from a location with a dorf to one, say, on the other side of the map (which would, presumably, be in none of the chunks you've stored)? Would that cause the system to suddenly store a good portion of the map in memory?
A major problem with that room idea is dynamically defining the rooms. The players can create very strange shapes, which may be hard to keep track of using any algorithm.
A major problem with that room idea is dynamically defining the rooms. The players can create very strange shapes, which may be hard to keep track of using any algorithm.We should piggyback on the player's efforts there. He uses room definitions, burrows and zones, and we should make good use of that. As soon as workshops are defined similarly to bedrooms etc., much of the interior of a fortress will have been defined as rooms - and that's where most of the pathfinding happens. When the military arc gets some more attention, there probably will be first line of defense zones, second line of defense zones etc. that the player can define as part of his fortress strategy, to give orders more easily. Those can be used as well.
There's no need for the divisions to be defined along any sort of human friendly mechanism. It's about what the computer can handle the best.If we're using divisions, we might as well use the existing divisions that are supplied ready-made by the player. Those automatically are in the areas where the player wants stuff to happen and pays attention to. If we save on calculations at the cost of reduced accuracy, nobody cares if something in the wilderness doesn't go in a straight line to its goal. Inside of a fortress, that might be annoying if it happens systematically.
To path through the tree the two leaf nodes containing the endpoints are identified and an upward propagating check is made for a matching parent node is made. If a common 'ancestor' node can be identified below the root node then it means theirs a path and the path must exist within the set of tiles described by that ancestor node. Now starting with common ancestor the tree is descended in successive steps. In each step a group of nodes is searched for a path at Inter-node levels between two nodes known to contain the end points. The resulting set of nodes on the path are then opened and their non-leaf daughter nodes become the search set the next step until all nodes on the path are leaf nodes. Because each search level is through a small number of possible nodes it will be far faster to do a dozen searches through networks of only a dozen nodes each then to search the leaf level nodes directly.
It is not as important, however, if our computed path is sub-optimal (longer) than the current best-path method.
I'm a bit fuzzy about how you handle coalescing, and mainly quickly detecting a coalesce is desirable. Also the exact way you'd split a node with more than a single tile border is fuzzy too.
That's part of the problem, and why I'd say it's important for whatever algorithm is chosen to have two characteristics: that segmentation works locally (i.e., I just mined a tile, I don't have to recalculate all the pathing for the whole damn world), and that different areas can be re-zoned (divided or merged). If those two criteria are met, it shouldn't be a problem to deal with terrain modifications
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 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 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.That's a possibility, although it's not trivial to carry out in practice.
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.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.
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.
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.
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.Are you sure it's mostly the wagons and not the critters?
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...
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.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.
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.
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.
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.)
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
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.
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.
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'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.
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.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.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.
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.
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.
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.
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:
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.
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.
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.
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.
OpenSpace = 0x0001, //flying
Building = 0x0002, //building destroyer
Water = 0x0004, //swimming
Rock = 0x0008, //digging
Magma = 0x0010, //swimming (magma)
Outside = 0x0020, //keep dwarves inside
Sunny = 0x0040, //for vampires
Smelly = 0x0080, //eewww miasma
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.
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.
In my very brief tests of this type of system I actually thought it was quite the opposite. I got very promising results in an afternoon. The simple punishment and reward system isn't really machine learning as much as it is prodding pseudo-randomness. If a generic framework gets set up for testing different pathfinding, I think a learning system should be thrown in, and I'd be happy to contribute.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.
I'm all for learning and Toady likes the idea too, I've heard, but I think it is just too hard. You need an appropriate representation to learn things in, and that is the most difficult part to set up. What are the abstract features that you are going to feed into the trained system? And how will you get them? Very interesting issues, and the subject of my ever procrastinated Ph.D., and also immensely complicated. Even in a "toy" world.
I think a learning system should be thrown in, and I'd be happy to contribute.
The question is how many bits we want to assign to movement types. Just remember how many map tiles there are, and that each bit can really add up when applied to each and every map tile in a world.
Here's something y'all may have thought of but that I hadn't. In the "stockpiling pathfinding" thread (and many others previously) it is pointed out that dwarfs often select startin points and destinations stupidly - getting the "closest" stone from 30 Z-levels away for example.
I think no pathfinding scheme will be complete unless it can help deal with this problem as well.
The bottom line is, we won't always be given "go from this tile A to this tile B", but will sometimes be asked to "go from this tile A to any tile B that has these properties P".
Doesn't matter, just use an std::bitset and we can treat it like an array. Even a 500 x 500 map with 100 z levels would only add 3 megs of map. We don't need to care about types else where in the world only the live game.
Also, by ONLY storing a pit per tile, you cannot precompute common paths, you cannot optimize in any way. You reduce the options down to storing data elsewhere or having an implementation no better than the one integrated into DF itself. In fact, probably worse.
And on the topic of speed, should C++ be used? The overhead of it's enhanced features might be an issue if C can be used just as easily.
I highly doubt you'll be able to optimize the algorithms any more than what they currently are now. For the most part, I believe that the only way to optimize pathing is to allow players to be able to place waypoints instead of dreaming up a magical computer algorithm for figuring out rooms/halls or a TCZ that players already do naturally.
5: It might be a good idea to work in parrallel on other objects that require a path such as liquid or gaseos flows, as well as siege mechanics, allowing catapults and ballista to fire in varying degrees of rotation in both the horizontal and verticle plan
They will do it automatically when defining rooms. Especially the new burrows will be useful in that regard (they will also reduce the length of the average path that needs to be found, and that will potentially mean huge FPS gains). Burrows will typically be defined functionally by the player (eg. the farming burrow, the kitchen and pantry burrow, the residential burrow, etc.) and that means most of the movement of a typical dwarf between burrows can be predicted. That opens perspectives.I highly doubt you'll be able to optimize the algorithms any more than what they currently are now. For the most part, I believe that the only way to optimize pathing is to allow players to be able to place waypoints instead of dreaming up a magical computer algorithm for figuring out rooms/halls or a TCZ that players already do naturally.
Apart from the arrogant tone, I agree with the potential of letting the players help. TCZs can already utilize what is already in place - doors - to let the player influence the shape of zones. Waypoints is one possibility, surely. But would players bother?
I remembered something, that may point to an obvious inefficiency in the current code. The normal traffic weight for an open space is two. Experiments have demonstrated that reducing the normal weight on the entire map down to one produces a marked benefit in terms of frames per second, as dwarfs manage to determine paths faster.Changing it in the init settings doesn't make a difference apparently (129 dwarves and a fair bit of tunnels).
Relying on player hints for zones is a bad road to go down. It means that the library we write isn't a 3d tile based path finding algorithm but instead a pathfinding algorithm specifically for dwarf fortress. You can't expect every use of the path finding library to be Dwarf Fortress, even if its requirements are the driving force behind the design.Designing the Universal 3d Based Path Finding Algorithm might be a little too ambitious. If that's the goal, a lot more factors will have to be taken into account and as a result the project will become larger and less focused. That requires more work, more persons involved, more coordination and all that for less tangible and slower improvement in DF. If recruiting happens elsewhere too, fine. If it doesn't, the project will flounder due to overextension. I think it's better to develop a library primarily useful for DF, that's also useful for other projects, rather than a universal library that might also be useful for DF.
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.I'm not married to 'just' seven types, they were just the seven that occured to me. And another one nicely gives fills 'flag' byte. Not to mention that I quite like the Build Destroyer routing possibility. (Although had I also missed the Pet Passable possibility (being unintentiaonally alliterative, there)?)
I highly doubt you'll be able to optimize the algorithms any more than what they currently are now. For the most part, I believe that the only way to optimize pathing is to allow players to be able to place waypoints instead of dreaming up a magical computer algorithm for figuring out rooms/halls or a TCZ that players already do naturally.I think there's two different Optimisations at stake here:
Relying on player hints for zones is a bad road to go down. It means that the library we write isn't a 3d tile based path finding algorithm but instead a pathfinding algorithm specifically for dwarf fortress. You can't expect every use of the path finding library to be Dwarf Fortress, even if its requirements are the driving force behind the design.Designing the Universal 3d Based Path Finding Algorithm might be a little too ambitious. If that's the goal, a lot more factors will have to be taken into account and as a result the project will become larger and less focused. That requires more work, more persons involved, more coordination and all that for less tangible and slower improvement in DF. If recruiting happens elsewhere too, fine. If it doesn't, the project will flounder due to overextension. I think it's better to develop a library primarily useful for DF, that's also useful for other projects, rather than a universal library that might also be useful for DF.
how are you going to optimize pathfinding based on room definitions in Adventure mode?
I would recommend sticking to the basic bit array for things like magma and water and looking into expanding it if and when it's required. As long as the check functions are isolated and well tested its easy to refactor and the basic system should allow duplication of the DF system without overly complicating the problem.
Designations like Indoor/Outdoor could also be solved easily if we use a Type->Subtype allowance flag system like I described earlier.
Quite, but it's important to remember not to circumscribe ourselves while coding. No optimizations based on the knowledge that capabilities will be bitmasks of a certain size! No optimizations based on the knowledge that the goal is a single tile!
Designations like Indoor/Outdoor could also be solved easily if we use a Type->Subtype allowance flag system like I described earlier. If a creature is designated to only be allowed indoors then they can check the sub tile of any tiles during A* to see if its of a valid type much like they might with water or magma.More importantly, subtyping can make for efficient representation of the connectivity map. For example, a dwarf with access to a certain room is also a dwarf with general dwarf access; thus, if a goal is reachable in the general-access connectivity map he doesn't need to check (or create) a connectivity map that uses his special room.
I remembered something, that may point to an obvious inefficiency in the current code. The normal traffic weight for an open space is two. Experiments have demonstrated that reducing the normal weight on the entire map down to one produces a marked benefit in terms of frames per second, as dwarfs manage to determine paths faster.This only happened if you manually overrode the weights in your fortress because it would tell DF to ignore the exterior of the fortress until you've fully explored the interior of the fortress. Since for the most part, the interior of the fortress is smaller than the exterior.
Relying on player hints for zones is a bad road to go down. It means that the library we write isn't a 3d tile based path finding algorithm but instead a pathfinding algorithm specifically for dwarf fortress. You can't expect every use of the path finding library to be Dwarf Fortress, even if its requirements are the driving force behind the design.How would adding player hints make it specifically for Dwarf Fortress?
Objects like doors should naturally be along any hierarchy divisions. Not because there's a door there but because it's a narrow chokepoint giving us a well defined region with limited routes to neighboring regions.
The tricky bit is that A* needs a connectivity map to be efficient. We can't maintain a connectivity map for each such custom request so we must find some way of cache the most commonly used ones, and compute an exact or approximate variation of the connectivity map when a special path request needs it. Requests for unusual restrictions are just that - unusual, so maybe we can get by with a flood fill every time for them. The more common ones ("general indoor worker dwarf walking through any unlocked door") will stay cached and updated constantly.Thank you for the clarification. Most of what I could got from all the previous posts was that "We'll optimize the algorithm," which didn't make any sense since A* is already optimal assuming that the heuristic is >= actual cost. I still would like to know though, what is the algorithm are you planning on using to discover areas, since an idea is one thing, but an implementation is something else.
It's not a trivial problem but should be possible to solve, and with big dividends.
Thank you for the clarification. Most of what I could got from all the previous posts was that "We'll optimize the algorithm," which didn't make any sense since A* is already optimal assuming that the heuristic is >= actual cost. I still would like to know though, what is the algorithm are you planning on using to discover areas, since an idea is one thing, but an implementation is something else.
Marking an area as especially relevant for certain actions is something that comes up in a lot of games, I imagine. It's certainly useful.Relying on player hints for zones is a bad road to go down. It means that the library we write isn't a 3d tile based path finding algorithm but instead a pathfinding algorithm specifically for dwarf fortress. You can't expect every use of the path finding library to be Dwarf Fortress, even if its requirements are the driving force behind the design.Designing the Universal 3d Based Path Finding Algorithm might be a little too ambitious. If that's the goal, a lot more factors will have to be taken into account and as a result the project will become larger and less focused. That requires more work, more persons involved, more coordination and all that for less tangible and slower improvement in DF. If recruiting happens elsewhere too, fine. If it doesn't, the project will flounder due to overextension. I think it's better to develop a library primarily useful for DF, that's also useful for other projects, rather than a universal library that might also be useful for DF.
Well obviously that's why we're keeping it focused on Dwarf Fortress, I just don't think we should rely on things ultimately DF specific so the game can keep a broader application to other tile based rogue-ish games.
For example doors, or more generally dynamic open/shut tiles (in DF's case this would also mean floodgates, bridges and hatches) are a good criteria for breaking up regions. It's something that would likely apply to other games. Something like stockpiles, room definitions, zones, or burrows on the other hand are very DF specific and would likely pose problems for applying the game to other applications. Even with DF these are a bad idea, how are you going to optimize pathfinding based on room definitions in Adventure mode?
Thank you for the clarification. Most of what I could got from all the previous posts was that "We'll optimize the algorithm," which didn't make any sense since A* is already optimal assuming that the heuristic is >= actual cost. I still would like to know though, what is the algorithm are you planning on using to discover areas, since an idea is one thing, but an implementation is something else.
How would adding player hints make it specifically for Dwarf Fortress?
Even within DF there are plenty of cases where player hints may be less than ideal or just not workable. What about a general 'barracks' bed room design where you have an open room with many bedroom designations in it? What about a stockpile room that's really 8 different stockpiles? What about non-continuous stockpiles or overlapping rooms? The divisions based on the player hints in these cases are going to be less than ideal or outright ambiguous.I was thinking more of global scale. What you're thinking of is localized conditions, in a localized situation like you describe path-finding is already near optimal. The path-finding that really slows DF down is at a large scale, when it pointlessly explores winding tunnels.
Even with waypoints the issue still stands: It's DF specific. It has no application outside of a manager type role. You couldn't even use the waypoints in adventure mode for example.Waypoints are a general method for taking a complex topography and creating a simple representative graph. In no way is it limited to a manager type role.
A Hierarchy with caching of movement between regions is essentially the same as a pre-computed path. Instead of A* ing over 100s of tiles you simply A* to the first border of your region, follow the computed paths between regions, then A* to the destination. Even without the precomputed route cached you can at least distribute the pathing work over time using the hierarchy.
On another note, has anyone looked around for any open source projects that do the same kind of thing? It seems unlikely (albeit possible) that the DF community would be the first to come up with such an idea. It's entirely possible that someone else has already done the original work and we can build from there.
Shiny. That gives me even more reason to read the article (it's open in one of my tabs already, but I'm a little behind on going through them).On another note, has anyone looked around for any open source projects that do the same kind of thing? It seems unlikely (albeit possible) that the DF community would be the first to come up with such an idea. It's entirely possible that someone else has already done the original work and we can build from there.
The much-linked article on HAA* (http://harablog.wordpress.com/2009/02/05/hierarchical-clearance-based-pathfinding/) includes the code that guy used for testing (http://code.google.com/p/ahastar/downloads/list) and a link to what looks like a more generalized library. (http://www.cs.ualberta.ca/~nathanst/hog.html)
Well, then design the library for other games... but then I wonder what it's doing here? Trying to to serve many masters will end up satisfying none. Both approaches are complementary rather than mutually exclusive anyway.QuoteHow would adding player hints make it specifically for Dwarf Fortress?
Because the idea of sectioning off a large enough % world with designations is something pretty unique to dwarf fortress. A lot of other tile based games, including adventure mode of DF, don't have the luxury of these designations. It's something that would require a fair bit of coding for vague benefits at this point. Since we need to support the 'no hints' case anyways (even in DF) the whole idea is basically committing to a lot of work for unclear at best gains.
Even within DF there are plenty of cases where player hints may be less than ideal or just not workable. What about a general 'barracks' bed room design where you have an open room with many bedroom designations in it? What about a stockpile room that's really 8 different stockpiles? What about non-continuous stockpiles or overlapping rooms? The divisions based on the player hints in these cases are going to be less than ideal or outright ambiguous.A barracks/communal bedroom can be defined as a single room.. If the player wants to do the work to make a barracks-like bedroom setup (because of space constraints, roleplaying goals, etc.), why shouldn't the dwarves think that way and try to avoid the personal space of as many dwarves as possible? The same for the 8 different stockpiles in the same room. If the player considers them separate spaces, then the dwarves will too. Non-continuous rooms are invalid as section and should be considered as two parts - trivial to check and split. The overlapping part of the rooms can be considered a separate space, and merged with a nearby one if it happens to be to small to be meaningful. Alternatively, room overlap could be cut out since it doesn't serve a useful function anyway - introducing shared rooms instead, if and when that's necessary. Otherwise ignore them if they don't give clear information on cells. But how is that going to be any worse than making the computer guess what the player wants to happen?
Let it be able to draw on parameters for each creature. Let you be able to draw on predetermined factors. (such as sociability), or the ratio of the times the dwarf has traveled a path to the number of times it has had to walk around another dwarf.A Hierarchy with caching of movement between regions is essentially the same as a pre-computed path. Instead of A* ing over 100s of tiles you simply A* to the first border of your region, follow the computed paths between regions, then A* to the destination. Even without the precomputed route cached you can at least distribute the pathing work over time using the hierarchy.
One potential problem with this is that heavily trafficked paths (specifically in DF, but possible in other games) impose a penalty to movement when there are multiple agents in the same square.
It's not a horrible problem in the case of larger hallways because the agents can have a secondary routine that automatically routes them around each other in problems like that. Like staying to the right when passing (or left as the case may be).
The bigger problem comes from narrow/twisty paths that have similar costs. IMO, a good path finding algorithm should be able to randomly choose the worse path proportionately to how much worse and the average traffic through both to help balance the load along precomputed paths.
On another note, has anyone looked around for any open source projects that do the same kind of thing? It seems unlikely (albeit possible) that the DF community would be the first to come up with such an idea. It's entirely possible that someone else has already done the original work and we can build from there.
Well, then design the library for other games... but then I wonder what it's doing here? Trying to to serve many masters will end up satisfying none. Both approaches are complementary rather than mutually exclusive anyway.
Just use any present designations as a starting point. Let the algorithm determine the rest of the terrain sections automatically.. which would have to happen anyway without using the designations. The result will be a little different than full automation, but the sections will resemble the vision of the player more closely.
Create a flexible BSD licensed C++ path-finding library specialized for grid based systems like that of Dwarf Fortress and able to efficiently handle rapidly changing map geometry and other challenges such as but not limited too multiple travel domains, multi-tile creatures, variable movement cost terrain and path caching.
Now I remember why I was mentally averse to this thread. Good luck with your general library, because you will need it for certain.QuoteCreate a flexible BSD licensed C++ path-finding library specialized for grid based systems like that of Dwarf Fortress and able to efficiently handle rapidly changing map geometry and other challenges such as but not limited too multiple travel domains, multi-tile creatures, variable movement cost terrain and path caching.
That is our goal. Nothing more nothing less. Considering that using designations both backs us into a corner and creates more headaches than performance gains I don't see the value in it.
Any sane design approach will have both some very general low-level pathfinding code and some DF-specific code, with clear divisions between them.Wait... We play DF. I don't think any one of us is completely sane by any definition.
And I'm voicing my concerns with that approach in the very same thread, where else? Trying to be useful to an unknown number of hypothetical future games might prove to be just as constricting.Well, then design the library for other games... but then I wonder what it's doing here? Trying to to serve many masters will end up satisfying none. Both approaches are complementary rather than mutually exclusive anyway.
Just use any present designations as a starting point. Let the algorithm determine the rest of the terrain sections automatically.. which would have to happen anyway without using the designations. The result will be a little different than full automation, but the sections will resemble the vision of the player more closely.
It was written clear as day on the very first post...QuoteCreate a flexible BSD licensed C++ path-finding library specialized for grid based systems like that of Dwarf Fortress and able to efficiently handle rapidly changing map geometry and other challenges such as but not limited too multiple travel domains, multi-tile creatures, variable movement cost terrain and path caching.That is our goal. Nothing more nothing less. Considering that using designations both backs us into a corner and creates more headaches than performance gains I don't see the value in it.
Solving general goals from a general viewpoint has been attempted by a lot of people already. If you want to do useful work in that area, the first months will encompass looking for papers, projects and studying what your predecessors did and what their problems were.
http://www.cs.ualberta.ca/~nathanst/talks/mmabstraction_talk.pdfInteresting. Read through that. Have also glanced at the white paper link, but not been able to absorb it all in the few minutes I can spend right now.
BTW, not that my own ideas are going in this direction, but could you see a major problem with taking a roughly calculated route, far from optimal (e.g. could easily be /\/\/\/\/\), subdividing it into segments and then assessing the optimal pathing between the centres of each segments as mini challenges (all of them resource-light, even combined) rinsing and repeating for a loop or three until the inefficiences of the route are smoothed out (becoming __________, in this stupidly simple example). On a 100-step-line cycle, 49 quite trivial "two steps at a time" tests highlighting kinks in an unecessarily bendy route (but necessarily and unavoidable bendy around obstacles), and then paying attention to the areas around that route neighbouring that 'betterment' might help. (Of course, the ultimate counter-example is where, from the start point, one has a choice of stepping left to go through one obstacle course or right through another, the exit to each being straight onto the finish-point. The 'shrinking' algorithm would never have chance to 'snap' the route from one side to another, to see if that were more optimal. Or even not an obstacle course at all. Which is a bit of a downer. God job that's not my chosen approach, eh? :))I think you put your finger on it. In formal terms: a simulated annealing approach; sensitive to local minima
I doubt if you'd see many cache hits for DF on a tile-by-tile level, but it might be more practical on a higher abstraction level such as rooms or zones. The cached path might be suboptimal in that case, but one could live with that.
Any successful caching system will defiantly need to work at higher levels in the abstraction hierarchy to be successful, if done properly I expect >99% hits at high level abstraction if the cache size is north of a thousand.
Sure, but "frequented locations" will be whole stockpiles, farm plots and other multi-tile regions, not single tiles. The restriction of one log or stone per stockpile tile, for example, ensures that you will never get a single cache hit when pathing to get logs or stones from a stockpile.
i assume that most movements are not between quasi-random destinations (e.g. a hunter wandering around until he finds game) but few highly frequented locations.
I still conclude that abstract locations will be absolutely crucial for path caching to have any utility. But feel free to prove me wrong!
3x3 would roughly covers a workshop and already be a huge improvement.
eager to test that :)
Actually, it would be useless, because workshops only ever use central tile: that is where all the workers and haulers path to
If the game knows where the creature and the desired location are before hand, using a higher level caching system might be feasable until the creature is within, lets say, 10 tiles of the destination, upon which the creature begins moving on a 1x1 system.Actually, it would be useless, because workshops only ever use central tile: that is where all the workers and haulers path to
great, that strengthens my point of path caching being useful :)
still, 3x3 greatly reduces the numbers of paths needed for piles and farms, though it introduces the a problem, namely that adjacent tiles are not necessary coverable by one step (e.g. if the slope's too steep).
i agree: grouping adjacent pile and farm tiles would be a huge win. someone should implement it :)
* i wouldn't make it update-aware (too expensive). paths get invalidated when dwarves that follow it run into a (permanent) problem. i bet that works well enough; also, it's a bit like how it works now. also, cheap.
9 C:\programming\pathing\graph.h boost/iterator/iterator_facade.hpp: No such file or directory.
Pets just need to path towards their owner. There should be a parameter how close they need to be (i.e. within how many squares). A pet following the dwarf should only get through the door if the dwarf wants it to stay close, and that means stay directly adjacent.
That code can be reused for things like ducklings behind their mother, a chain gang, caravans, military formations etc. The distances that need to be pathed are very short and shouldn't pose a significant burden, while still allowing the complete flexibility to move out of the way, should there be a problem with that route.
Yes, rooms should have multiple connections. The choice between them would be made with A*. If they are along paths with the same distance to the destination, then the choice of which door is implementation dependent.
This could be made random if in the implementation of A*, potential next-nodes are added to the priority queue such that their relative position among other nodes with the same score is random. (i.e. Find position of queue of first node with that score, and last node with that score and choose a random number between 0 and 1 + [the difference between the two positions], insert the potential next-node at position [position of first node]+[random number]).
This could be made to select for larger hallways if a secondary score consisting of the average width or minimum width of the path was used as a tie-breaker. Also the presence/absence of cats/goblins/miasma could also be used similarly. Or an heuristic taking into account all of the above could be used (anything you can describe mathematically is possible).
What version boost? iterator_facade has been around a while, but some versions of boost out there are *ancient*.Code: [Select]9 C:\programming\pathing\graph.h boost/iterator/iterator_facade.hpp: No such file or directory.
#include <limit>Which file needs those includes? And which printf? All the printfs are printing either unsigned with a %u format, or uint64_t with a %llu format, so those should be clean -- they compile 32 or 64 bit on my machine, but I recognize these things differ across platforms.
#include <algorithm>
and comment out one of the printfs on account of 64bitness.
(http://imgur.com/rgnon.png)I'd go for the artificial stupidity that the red path brings.
C:\programming\pathing\main.cpp In function `point randomPassablePoint(const grid*)':
16 C:\programming\pathing\main.cpp `random' undeclared (first use this function)
Traffic costs dose make me think how were going to combine that with movement types, a flying creature should have the same cost at all time ware as a walking creature would be slowed down by mud and other unfavorable conditions. Each movement type might require its own cost which may present a significant memory overhead.If you sum up the movement cost of a tile on demand you could also add some sort of ignore flag to just skip these types of factors.
If you change random() to rand(), it compiles runs and works. Now just to see how it works and tinker away on my day off...Ugh. I haven't suffered from the lack of random() in about 10 years. In real code we'd probably end up rolling our own PRNG, but the real lesson is that cross-platform stuff like this bites. Maybe I'll set up automake this weekend, which should help a bit.
The wow power leveling usual point where break evenNNNNNNNNNNOOOOOOOOOOOOOOOOOOOOOOoooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
happens is around 4,000 copies. If you're printing wow gold
4,000 copies of a given item, aion power leveling it's
almost always better aion gold to go to an offset press for
the job, though cheap wow power leveling this will vary
considerably buy wow power leveling by region and services
offered.When looking at the cost effectiveness aion kinah
of colour laser printing,
This is dead, also, the problems with pathfinding are rather... derivative.probably right. The best way to optimize path finding is caching or parallelization.
not a problem with one path, but rather with many simultaneous paths that must all recalculate when they intercede.
This is dead, also, the problems with pathfinding are rather... derivative.I find the announcement that this is a dead project a little premature for my taste. The fact that different people (and even the same people, at different times, puts hand up... "Guilty!") have been discussing different aspects from those that other people consider core has made it a bit less concentrated than it perhaps could have been, but I, for one, have learnt that some of the terms I 'made up' for my own thought experiments were surprisingly similar to some that actually dedicated problem solvers had layed down in full-on published papers. Which is gratifying to know.
not a problem with one path, but rather with many simultaneous paths that must all recalculate when they intercede.
Then the path finding could just treat non-passable as inf cost if that critter cannot pass that way. Not perfect, but fairly simple.returns bad routes if no route exists-the current problem people ha'e with "restricted" not really stopping dwarfs if it's the only way.
Not only are rectangles the most common thing people build in DFBAHAHAHAHAHAHHAAAAA...er, sorry.
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).I'm not the only one who Restricts or Lows saplings when wood is a problem, or Highs valuable sand tiles.
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.this is one of the main reasons Toady is off multi-tile critters atm, I believe. (Balance issues, nailing down tile size are others). Wagons are currently in because you need, basically, to check the Depot Access twice per wagon merchantgroup- plus when you hit shift-D, ne'er actively...well, I think. Prolly wrong- I hear dead pathfinding kills(scuttles) a wagon.
You can also, for example, precalculate map for next season because you know that tree saplings will become obstacles.uh, trampling.
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.
it seems relatively trivial to maintain parallel route-maps for such as aerial, aquatic, magma-surviving,Except these features are nonexclusive! You can perfectly well have flying amphibious fireimmunes. (We don't, yet, I think). This would be able to use a path that, in theory, existed in none of the individual maps. So, maintaining each would be 2^flags. your 5x becomes 32x, which, considering the problem looked at...is nasty. And I count 8+ (okay, really 7 and a tristate, for 384x)
[snip]
The above possibilities means multiplication 5-fold of the map (or, rather, 5 maps if better optimisation of each map can be made),
Also, by using a full byte, you add support for conditional blockage at a future date(8 bits per tile).Um, we're already past 8 options
Then the path finding could just treat non-passable as inf cost if that critter cannot pass that way. Not perfect, but fairly simple.returns bad routes if no route exists-the current problem people ha'e with "restricted" not really stopping dwarfs if it's the only way.
Terrain Move Abilities (starver got some, but not all (http://www.bay12games.com/forum/index.php?topic=43265.msg816787#msg816787)Not all of these should be movement types. At least not "inclusive" movement types, where a creature can move through the tile if he has -any- of the movement options available. But if we must add the complexity of exclusionary movement types, where the creature MUST have a movement type to move through it, we can cut down on even more.
Terrain Move Abilities (starver got some, but not all (http://www.bay12games.com/forum/index.php?topic=43265.msg816787#msg816787)Not all of these should be movement types.
...
But if anyone has an idea on how to add exclusionary movement types without increasing CPU load, I'm all ears.
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.
....
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.
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?
Here's a link to the HAA* website with accompanying paper that I'm referring to: here. (http://harablog.wordpress.com/2009/02/05/hierarchical-clearance-based-pathfinding/)
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...)
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.
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.
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*.
I'm not saying we're calculating everything on demand. What I mean is that the client program defines a movement class with a function instead of a capabilities bit-vector.
@Shades: It was passed in the GetPath function only to get uncached paths. The cached paths use a movementclass which was set up using PathLibrary::CreateMovementClass. CreateMovementClass will set everything up.
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?Different movement types imply different hierarchies for running the pathfinding over. Until we know how to compute the cost, we can't build anything and we're stuck with the basic A*.
Not only are rectangles the most common thing people build in DF their also efficient at covering the unmodified terrain as well and are much simpler to set up and can aid in doing multi-tile creatures as we can be assured that a creature thats longest dimention is shorter then the rects shortest can move through the rectangle.
qoute by DeathofRats
That's part of the problem, and why I'd say it's important for whatever algorithm is chosen to have two characteristics: that segmentation works locally (i.e., I just mined a tile, I don't have to recalculate all the pathing for the whole damn world), and that different areas can be re-zoned (divided or merged). If those two criteria are met, it shouldn't be a problem to deal with terrain modifications.
AI settlements will need to be generated with their own set of room definitions, traffic designations, etc.. That will break save compatibility again, so it's not trivial - but something like that has to happen if the townsfolk ever are not to act like they all suffer from terrible amnesia, don't really know what they're doing there, and just amble around wondering whether they are just a randomly generated npc in a big simulation.
quote by Heph:
Rectangles also would support a simple idea i had a bit Better. A little discussion about shading gave me it. Idealy The shortest connection between two (not moving) points is a straight line. Since we know the accesnodes between two mapchunks/Leaves we could use Bresenhams algorithm to calculate The shortest way in a leave betwee two nodes. If a soft obstacle, like a dorf is on the path we can use at this point a short A* to path around the obstacle to continue the precalculated path or we just dodge (1 step forward in a certain angle) and use a bresenham again.
quote by Heph:
In my opinion we should implement apart from heuristics multiple takes on (in mapchunk) pathing because depending on the pathing task and outer influences (like the sidelenghts/radius of a mapchunk) a different pathing variant could be more efficient then the usual one. For example bresenham might be enought to traverse 3 mapchunks and in the 4rd a A* might be needed.
I don't think the pathing library should be responsible for handling AI.At some le'el, it becomes the AI. "Do I take the path nearer the goblin archers or the one past the spiked pits?"
"Do I take the path nearer the goblin archers or the one past the spiked pits?"Thats a good point, actually. Although it should not be handled by pathing lib, but rather it should provide ALL possible paths, one for each way of traversing the graph.
"Do I take the path nearer the goblin archers or the one past the spiked pits?"Thats a good point, actually. Although it should not be handled by pathing lib, but rather it should provide ALL possible paths, one for each way of traversing the graph.
Earlier all-edge comment:Arguably, the flier will automatically fly at least one level above ground as soon as rock, trees etc. are proper obstacles. Also, air currents will make some directions easier than others so they might be inclined to soar up along with warm air and then glide down towards their destination and descend. Personal preferences also could play a role. Prey birds would habitually stay sufficiently far above ground as a matter of habit, to avoid predators.
The cliff case is meaningless: You could have a tile group for the upper path, and one for the lower. Where the edges of the groups cross, you could describe the movement costs between them. The advantage is that you don't have to store the data of every identical sky tile in an empty 10x10x10 cube, only where it connects to other groupings. When breaking up the grouping, you simply transfer the edge data, either to the tile itself(unlikely) or to the new edge.
Also, a suggestion: maybe put a slight extra weight against direction changes? Not tile-based, but a flier going up over a mountain wouldn't follow the ground exactly... (Of course, such behaviour might develop naturally...)
The Bresenham algorithm is fundamentally aesthetic in nature and doesn't help you find the shortest way between points in any meaningful way. Sure, it might look better if creatures moved in what looks like straight lines towards their goal in open areas, but it has no effect on the cost of the path, and it is more expensive in implementation than just "if x < targetx && y < targety then up-right" (since Bresenham would require storing extra values and performing computations slightly more complex than the above, each step).
x, xtarget, y ytarget // get the coords of dorf and dorfs target
xst, yst // x and y steps
if x = targetx
then
xst = x;
else
if x < targetx
then
xst = x+1;
else
xst = x-1;
if y = targety
then
yst = y;
else
if y < targety
then
yst = y+1;
else
yst = y-1;
store (xst, yst)
get xa, ya // get start coordinate
get xe, ye // get end coordinate
d = 2×Δy – Δx // Δy = ye - ya ; Δx = xe - ye
ΔO = 2×Δy
ΔNO = 2×(Δy − Δx)
y = ya
store tile (xa, ya)
for every x of xa+1 till xe
if d ≤ 0
then
d = d + ΔO
else
d = d + ΔNO
y = y + 1
store tile(x, y)
x, xtarget, y ytarget // get the coords of dorf and dorfs target
xst, yst // x and y steps
As long x!=xtarget && y!=ytarget
do
if x = targetx
then
xst = x;
else
if x < targetx
then
xst = x+1;
else
xst = x-1;
if y = targety
then
yst = y;
else
if y < targety
then
yst = y+1;
else
yst = y-1;
store (xst, yst)
Planning movement within a rectangle is not a problem, no matter which algorithm you select. Nor is it within TCZs, using silly-move. The computational costs for these are all absolutely negligible...
The problem is the search. What is needed is a reduction in branching factor and search tree depth (and a good heuristic).
Has anyone corresponded with Tarn about supporting a team to create an official path finder utility for DF?I'd wait until something actually appeared.
As far as the zones and branching goes, however, I'm not so much of a fan of the TCZ's that Sunken is proposing. I don't see the advantages of silly-move over A* for the scenarios silly-move is applicable for outweighing the flexibility of A*. Additionally I think we can do better if we allow for zones that do not satisfy TCZ (such as a windy passage that doubles back), but which are trivially pathable with A*. I also think that zones should be 3D since this allows for similar windy passages in the z-direction (and the sky could be one gigantic zone).
I'm just popping in now to point out that in a tile based game, convex zones are rectangles. Any other shape ceases to be convex. Diagonals in a square area are an odd case, as the square the line passes through may or may not be traversable (eg. diagonal movement around a corner). Currently such diagonals are allowed at normal cost (1.4), but this may change.Here's a convex zone to disprove your claim:
##
####
####
As for using bezier curves or other algorithms[...]
As for curves - a curve is never the shortest way (in Euclidean space) and so again I think aesthetics must give way to efficiency.
Is there? Oooh, I assumed it was equal in all eight basic directions.1: You're working from an incorrect assumption. Diagonal movement and orthogonal movement cost the same in DF.
Edit: Scratch that, there's a sqrt(2) factor in there
I'm just popping in now to point out that in a tile based game, convex zones are rectangles. Any other shape ceases to be convex. Diagonals in a square area are an odd case, as the square the line passes through may or may not be traversable (eg. diagonal movement around a corner). Currently such diagonals are allowed at normal cost (1.4), but this may change.If you enforce wossisnames[1] algorithm, then a diagonal in a zone might preclude a 'convexity', as the 'ideal stagger' hits the wall, but otherwise shouldn't matter.
########
######b a#
########c #
#d #
# #
For example:Code: [Select]########
######b a#
########c #
#d #
# #
a->d 17W,2S which would be a sum of 15W,2SW, or "ideally" 5W,SW,5W,SW,5W, which would hit the wall next to 'c'. (This was quickly rendered in ASCII, I may not have made the wall stagger B-algorithmically correct! It might more correctly miss the wall.)[...]
###
#####################a#
#b c #
# #
# d #
#######################
...that would be as much convex as the rectangle minus the alcove, given that no shorter route exists between all points within than the shortest route that must avoid the boundary. The route a->b would have to be SW, then a number of Ws, but would not be longer than the stagger that travelled 'through' the wall then emerged at or around 'c'.Sounds like you're on your way to inventing the TCZ ;-)Well, to be honest I had invented something prior to hearing of the TCZ that was very TCZ-ish, but then came in after the weekend/night-off to see almost all of my considerations[1] mentioned. (Straight off, I must have skimmed over what TCZ was, and thought the "C" was for "Convex", but rewound after a while when I decided I really needed to know the title.)
There's a trade-off: The more complex the intra-zone navigation is allowed to be, the larger the zones can be -
straight-line -> convex zones
silly-move -> TCZs
A* -> more convoluted zones (entire maps, in fact)
We simply have to experiment to see which trade-off is most beneficial.
I'll say this, though: There has been no automatic cut-off criterion proposed for A* zones. As I just said, they can be as big as you want - but unlike the other two, the intra-zone pathing becomes more and more expensive for A* as the zones grow. Silly-move and straight-line are constant-time no matter how big the zone.
So, saying that we should use A* inside zones just begs the question - what zones to use? I thought up TCZs because they seemed a reasonable compromise.
I'm not sure that intra-zone pathing is difficult for A* than it is for silly-move for the cases where the two are applicable. If your silly-move algorithm is simply "move to the tile that is closest to the destination," then A* will have similar complexity since the only tiles A* would consider are the same ones the silly-move algorithm would (So both are algorithmic on the order of the zone size). A* has some additional overhead since it handles non-uniform costs, but this does not affect the algorithmic complexity.OK, amortized over the entire path you are correct, since silly-move has to either check the next step at each step, or precompute the entire path at cost O(N). A* has to do the latter.
Having smaller zones can actually decrease performance as well. As zone size decreases, the ratio "surface area" (number of external links) to the enclosed volume increases linearly (or is it even superlinearly?). In order to perform A* routing over the set of zones, the source link must know the cost to each of the other links in the zone. This means that the required calculation and storage grows as O(n^2) in terms of the number of links, resulting in the total algorithmic complexity increasing as O(n^3) in terms of the "smallness" of the zone. Note that this will be true regardless of what method of pathing is chosen inside the zones.Yes, that was the whole point of TCZs. They are strictly larger than convex zones or rectangles, while guaranteeing a constant-per-step complexity intra-zone. Again, even larger zones would be better, but not if that means losing intra-zone complexity guarantees.
I'm not saying that the zones should be too large. A large zone with lots of chokepoints or doubling back or something like that would perform horribly, regardless of the pathing algorithm chosen. There definitely needs to be a tradeoff between zone size and complexity. I still haven't found a good algorithm to define the zones. All I really have so far is that the edges should follow chokepoints as much as possible to reduce external links. And I would probably use rectangular prisms as zones since this makes it easier to determine which zone a tile belongs to.Rectangles will always be smaller than TCZs, that's what I've been trying to tell you. I'd still use rectangular bounding boxes to speed up TCZ lookup though.
Also, A* can be modified to produce the diagonal pattern that several posters have suggested seems more natural. If A* was adjusted to order (ascending) candidate nodes with equal heuristic cost by "sqrt(dx^2+dy^2+dz^2)", where dx, dy, and dz are the differences between that node's x,y, z and z positions to that of the destination, the paths found by A* would look like those "straight" lines.Even assuming that computing that polynomial (leaving out the sqrt) is not too expensive, I think that would tend to make the algorithm try suboptimal paths first? Because that formula is not, in fact, the straight-line distance to the goal as the dwarf would walk in an open world. I'm not sure about that.
#####
#### #
### ##
## ###
# ####
is convex enough but would not benefit from the hierarchy you propose, I think? Correct me if I'm wrong.
...
Yes, that was the whole point of TCZs. They are strictly larger than convex zones or rectangles, while guaranteeing a constant-per-step complexity intra-zone. Again, even larger zones would be better, but not if that means losing intra-zone complexity guarantees.
....
Rectangles will always be smaller than TCZs, that's what I've been trying to tell you. I'd still use rectangular bounding boxes to speed up TCZ lookup though.
And to my mind TCZs will be better at isolating chokepoints than rectangles. The biggest problem with TCZs is their tendency to overlap each other.
###########
a # # #
# # # # # #
# # # # # #
# # # b
###########
Even assuming that computing that polynomial (leaving out the sqrt) is not too expensive, I think that would tend to make the algorithm try suboptimal paths first? Because that formula is not, in fact, the straight-line distance to the goal as the dwarf would walk in an open world. I'm not sure about that.The way I mean it, it shouldn't cause suboptimal paths to be tried first. I realize this formula isn't the distance as the dwarves see it (for them its actually max(dx,dy,dz)). It's actually more of a tie-breaking rule. We already have the cost (which in A* is equal to cost so far plus estimate of cost to go) for each candidate node. All I'm suggesting is if there is more than one node with the same cost, they can be sorted based on Euclidean distance (purely for aesthetic reasons).
Anyway, it means adding computational complexity for an essentially cosmetic effect. It would work, though, and could be tried easily enough on top of any other approach AFAICS.
I actually think that A* rectangles will be larger than TCZs. TCZs need a region of a) uniform cost and b) trivial complexity. How many TCZ regions (and purely A* regions) will be necessary to span the following design:You obviously don't mean the same by rectangles as I do. I mean unoccupied rectangles - unoccupied being the prerequisite for search-less pathing such as the Bresenham algorithm. You allow obstacles in your rectangles. It would take 11 unoccupied rectangles.Code: [Select]###########
a # # #
# # # # # #
# # # # # #
# # # b
###########Spoiler (click to show/hide)
I am thinking though that pure rectangles may not be best. I was thinking that some sort of subtractive geometry might be efficient. We could define zones as "all of this rectangle except for those in the followingCan't say if this would work or not. It seems like it might be sensitive to changes in the map, the way quadtrees et al. are, and the diagonal-tunnel example I put forth a couple of posts ago applies here too. But these are just hunches on my part. If you think it will work then you should try it out.rectangleszones". This could be represented as a "tree" (actually more of an acyclic graph -- since I would allow nodes to have multiple parents) where zones further down the "tree" have higher priority over the ones higher up. To determine what zone a node is, the algorithm goes down the path of the "tree" with zones containing the node until there are no zones further down containing the node. Pathing proceeds normally just using zones. This hierarchy is only used for determining a node's zone (though if we require zones to be completely contained in their parent zone: 1) we would have a multi-level hierarchy we could use to optimize pathing 2) the "tree" is a tree).
Yes, as a tie-breaking rule it would do the trick, though I'm not sure how you'd make sure the modification doesn't go beyond pure tie-breaking. But it's probably not a hard problem to solve.Even assuming that computing that polynomial (leaving out the sqrt) is not too expensive, I think that would tend to make the algorithm try suboptimal paths first? Because that formula is not, in fact, the straight-line distance to the goal as the dwarf would walk in an open world. I'm not sure about that.The way I mean it, it shouldn't cause suboptimal paths to be tried first. I realize this formula isn't the distance as the dwarves see it (for them its actually max(dx,dy,dz)). It's actually more of a tie-breaking rule. We already have the cost (which in A* is equal to cost so far plus estimate of cost to go) for each candidate node. All I'm suggesting is if there is more than one node with the same cost, they can be sorted based on Euclidean distance (purely for aesthetic reasons).
Anyway, it means adding computational complexity for an essentially cosmetic effect. It would work, though, and could be tried easily enough on top of any other approach AFAICS.
You obviously don't mean the same by rectangles as I do. I mean unoccupied rectangles - unoccupied being the prerequisite for search-less pathing such as the Bresenham algorithm. You allow obstacles in your rectangles. It would take 11 unoccupied rectangles.
I'm just popping in now to point out that in a tile based game, convex zones are rectangles. Any other shape ceases to be convex. Diagonals in a square area are an odd case, as the square the line passes through may or may not be traversable (eg. diagonal movement around a corner). Currently such diagonals are allowed at normal cost (1.4), but this may change.It's not hard to define a discrete version of convexity that would obviate your worry (straight-line obstacle-free path from the center of each tile to the center of all other tiles, for example).
But all we seem to be using of convexity is that there is a closed-form solution for the cost from one tile in the region to another, looking just at their coordinates -- this is a larger class than what you'd normally call convex. For example, TCZs have this property when diagonals are the same cost as the other directions (which is not the case here, but it might still form a good approximation).Exactly. "Convex" doesn't have an unambiguous definition on discrete sets, AFAICS, but if one can define a closed-form next-step algorithm (math people would probably use "ordering" here somehow), then a convex region is one where that algorithm takes you on a path that never leaves the region to your goal.
5 TCZs have more overhead than 11 rectangles, obviously. But I will stick my neck out and claim most fortresses don't look much like the example. Only testing in the wild will tell which is the more practical.You obviously don't mean the same by rectangles as I do. I mean unoccupied rectangles - unoccupied being the prerequisite for search-less pathing such as the Bresenham algorithm. You allow obstacles in your rectangles. It would take 11 unoccupied rectangles.
Which solution has more overhead in terms of memory cost:
11 rectangles
5 regions
?
A question not yet raised in this thread: what heuristic to use. One issue with traffic designations is that if you're actually using them heavily, the standard heuristic (euclidean distance) can make you sad: it assumes it costs 1 to cross each unit distance, when in fact it probably costs 2 or maybe 25.It's a tough one. I think it will be extremely hard to come up with a heuristic that is more efficient than the obvious one - not Euclidean, but
It's not clear to me how to improve on that, but maybe someone has an idea.
Both vastly and rapidly changing terrain, hundreds of agents constantly demanding paths, multiple movement types and nearly completely user controlled/designed terrain. You can't assume anything! Terrifying.At least our world will always be a grid of discrete squares! That's a great strength compared to pathfinding in, say, reality. :)
The stuff laid out in the thread so far makes sense to me though, especially how it makes sense to divide the world into zones to simplify the graphs involved. TCZ's sort of remind me of navigation meshes, only squashed into this 2D grid-world. The basic idea is the same, they define interconnected trivially walkable areas with local agent steering filling in to walk around unexpected obstacles. (Here's a easy to digest article about em: http://www.ai-blog.net/archives/000152.html Obviously, nothing from that is really directly applicable, but having more buzzwords to google is always good.)Interesting, even though it's mostly a comparison of two systems none of which is on a discrete grid. Doesn't mean one cannot take inspiration from it, though. Convex polygons do have their interpretation in discrete space, as we've found.
It seems like no matter how you define your zones though, there are going to be situations that will be less than optimal. It'd be nice if there was a way to intelligently recognize those cases and reduce them appropriately. (That winding passageway posted previously, for example, has only one possible path through it, so it'd be nice if it was able to merge those into a neat single black box path from a to b instead of a long chain of TCZs.)Indeed! I have no idea how to adjudicate that automatically, nor whether the overhead would mean it wasn't worth it, but a system that could pick its zone types optimally would be golden.
Starver, I just skimmed over your description;[...]Just bear in mind that was a v0.1 (Alpha) thing that I wrote before I integrated and evolved what everyone else was talking about, if you're talking about the Spoilered bit. (I just thought "I spent at least 3/4 hour writing it, way back when, maybe I should give it a belated airing... :))
but essentially, you're proposing a tree-like decomposition into convex zones, right? A non-overlapping, mutually exclusive decomposition?Essentially, although crucially I was going on the premise of the boundaries actually overlapping by exactly one unit (at whatever level of [meta-^n]zoning we're at).
<--Zone 1-->
......01234567890......
<--Zone 2-->
...in a 1D example. In 2D that boundary would be a B-line (consistently defined for both zones) which would allow a calculation of where the segment "[point-in-Zone1] to [point-in-Zone2]" intersected the "boundary between Zone1 and Zone2" segment (or, indeed, if it did not intersect, and thus had to be doglegged around the end of the "bbZ1&Z2" segment closest to the off-segment intersection point. The [piZ1] and [piZ2] coordinates possibly being the entry point to the Z1 or Z2 from/to Z0 or Z3, as guided by the meta-zone path-finding. However, I later saw problems with that.Path-planning-wise this will have all the attributes of a convex subdivision, which has been part of the discussion for a bit now: trivial to path across, larger and thus potentially more efficient than rectangles; smaller and (or so I maintain) potentially less efficient than TCZs.Again, that's historic. But you've got the essential flavour of what was proposed, with a couple of minor differences that don't bear going into.
And you're suggesting a structure to create and maintain that convex subdivision, correct?
I'm doubtful as to the tree approach, though. Won't it be inefficient wherever the edges of the convex zone runs in the diagonal direction? This zoneWith travel between the (inserted) "a" to "b" locations may (with the 1.4 multiple penalty for diagonality) be less quick to travel between than the (equivalent in crow-flies) "c" to "d" route. My original concept would have split the constrained diagonal containing a and c into one convex area and the large one leading to b and d into another, with a shared boundary somewhere a couple of cells to the right of "c" (and however far off-diagram you needed to go). Which would have meant a path dog-legging around the top of that "/|" shape from either a or c, and then straight to d or stagger to b. An a->b journey would actually be longer than a vector-based approach, of course, due to the disproportionate acumulation of 4x(root(2)-1) additions to the pure horizontal distance compared with the proper trigonometric adjustment for the angling across.Code: [Select]#####c d
is convex enough but would not benefit from the hierarchy you propose, I think? Correct me if I'm wrong.
#### #
### ##
## ###
#a #### b
###############
########### #
########## ##
######### ###
######## ####
####### #####
###### ######
##### #######
#### ########
### #########
## ##########
# ###########
###############
I was afraid the tree structure wouldn't be able to efficiently represent that as one unit. A quadtree wouldn't, but if you can then that's cool.
(Here's a easy to digest article about em: http://www.ai-blog.net/archives/000152.html Obviously, nothing from that is really directly applicable, but having more buzzwords to google is always good.)Interesting. That's very close to the approach I never-quite-implemented back when I was so impressed by Doom, but thought it needed a proper third dimension (and the rest of the funny tweaks, like rotational symmetries of 1/2)... Looks like another thing I could have gotten rich from but didn't. :)
(That winding passageway posted previously, for example, has only one possible path through it[...]Yes/No (*delete as inapplicable). There's only one shortest path, but there are others. c.f:
##### #####
#+++# ##+##
#+#+# and #+#+#
#+#+# #+#+#
++#++ +###+
##### #####
7.2 to 11 only 7.2
steps steps
(based on 1.4 for diagonal)
I'm afraid you misunderstood my diagram... I meant an indefinitely long diagonal corridor surrounded by rock. I'll make it clearer:It would from the B-line "vectorised" format. The tree structure was just the start but after merging based upon adjacent tree-ends that are mergable (in a manner I could spend ages explaining, but won't[1]) that would end up with something not so much a classic quad-tree.
<snip>
I was afraid the tree structure wouldn't be able to efficiently represent that as one unit. A quadtree wouldn't, but if you can then that's cool.
And the cost isn't max(dx,dy,dz) (or max(abs(dx), abs(dy), abs(dz)), if one is to nitpick), but actually:
max(abs(dx), abs(dy))-min(abs(dx),abs(dy)) + sqrt(2)*min(abs(dx), abs(dy)) + abs(dz)
"straight bit plus diagonal bit plus vertical". Or at least I think so - I think movements in the "vertical diagonal" aren't possible.
Also, dwarves can't move diagonally upward? I can understand the case for staircases, but for ramps and flying/swimming creatures it seems really silly.I understood that as like up the following diagonal-on-the-horizontal-plane as well as ramp-traversal:
Z0 Z+1
### ##+
#^# #v#
+## ###
And I wasn't sure enough about it to say, but I thought it was possible. I'm sure my Adventurer can do it, wandering diagonallly across landscapes) but haven't got the game in front of me to test, right now.. (Plus Alt-Move climb at that angle, where otherwise permssable.
To the best of my knowledge, diagonal movements in 2D cost sqrt(2) times as much as orthogonal ones. At least during search.
It's funny, because a fair number of FPSs...do not cap your speed properly, and thus it is faster to proceed at an angle to your view (gi'ing you that sqrt(2) factor boost, if strafing is as fast as walking)
And yeah, no clue about the ramp travel cost-define, though it'd clearly be root2 for straight and root3 for diagonal normally...but that doesn't really model the cost right for a creature in a gravity well. (Likewise < > as 1 cost)
Doesn't make your leg any longer ::)Ok, I wandered offtopic a bit, but I should point out that leg length isn't an issue. People with shorter legs don't hover, after all. Larger subtended angles just means a lower centre of body mass during the stride. (And awkwardness of stride, at extreme examples, just to auto-pedant myself.)
Why not a SPZ(Single Path Zone) to complement the TCZ. It would cover any area with exactly two exits, and cache the fastest path between them. Pathing within it would use A*.Two exits as in two exit-tiles, or two 'walls of exit'?
############################
# ######################
# ##### ###########
# ##########
####### #########
####### #########
####### #
####### # #############
######## # # ###########
######### ############
############ ###############
############ ###############
Could be seen as a single SPZ containing many lesser zones, but as one(or more) node up the heiarchy(I think), it could reduce massive quantities of pathing, as long as neither endpoint is inside of it.Single-tile.Now, I think there's merit in something there. (If not for the system being worked on, another one.) Assuming your Zoning system likes differently 'headered' zones, they can be packed and optimised better, and (if push comers to shove) travel between points within such a convoluted zone can be left to ad-hoc calculation (assuming that there's not such a regular occurance that it deserves to be put upon and stay in any cache) as the load per-calculation would be trivial.
<snip>
Haven't had the time to read the whole thread, but has anyone mentioned "pheromone" style caching for the pathfinding? Could be useful for a colony-style game like DF.In eternal voting as: "Automatically adjust pathfinding for traffic (http://www.bay12games.com/forum/index.php?topic=29716.0)".
Also, when it comes to dividing zones, why not leverage user brainpower and divide zones based on door placement? Any one door has zone a on one side and zone b on the other (zone a and b may of course be the same). A bit of smart map searching could look for known door-like construction patterns as well.I agree that we should use the player's brain cycles whenever we can, especially since doors, zones etc. are likely concentrated in areas where the most dwarves and hence the most pathfinding requests are.
Haven't had the time to read the whole thread, but has anyone mentioned "pheromone" style caching for the pathfinding? Could be useful for a colony-style game like DF.
11 12 13 14 15 16 17 18
21 22 23 24 25 26 27 28
31 32 33 34 35 36 37 38
41 42 43 44 45 46 47 48
51 52 53 54 55 56 57 58
61 62 63 64 65 66 67 68
71 72 73 74 75 76 77 78
81 82 83 84 85 86 87 88
000000 000010 001000 001010 100000 100010 101000 101010
000001 000011 001001 001011 100001 100011 101001 101011
000100 000110 001100 001110 100100 100110 101100 101110
000101 000111 001101 001111 100101 100111 101101 101111
010000 010010 011000 011010 110000 110010 111000 111010
010001 010011 011001 011011 110001 110011 111001 111011
010100 010110 011100 011110 110100 110110 111100 111110
010101 010111 011101 011111 110101 110111 111101 111111
(7,7) -> 111100
(2,2) -> 000011
Stored: 110000 = (-1,-1)
(6,6) -> 110011
Stored: 110000 = (-1,-1)
(5,5) -> 110000
Stored: 110000 = (-1,-1)
(4,4) -> 001111
Stored: 001100 = (-1,-1)
(3,3) -> 001100
Stored: 001100 = (-1,-1)
(2,2) = Destination
(6,6) -> 110011
(3,1) -> 001000
Search: 110000
Found: 110000 = (-1,-1)
(5,5) -> 110000
(3,1) -> 001000
Search: 110000
Found: 110000 = (-1,-1)
(4,4) -> 001111
(3,1) -> 001000
Search: 000100
Not found!
(4,4) -> 001111
(3,1) -> 001000
Stored: 000100 = (-1,-1)
(3,3) -> 001100
Stored: 000100 = (0,-1)
(3,2) -> 001001
Stored: 000010 = (0,-1)
(3,1) = Destination.
The Department for Unwanted Enlightenment would like to inform the readers of this thread about the word Stigmergy (http://en.wikipedia.org/wiki/Stigmergy).That just closed my browser.
That is all.
The Department for Unwanted Enlightenment would like to inform the readers of this thread about the word Stigmergy (http://en.wikipedia.org/wiki/Stigmergy).
That is all.
Of course, we're dealing with globally-omniscient agents. Given that we have these[1] and not limited-knowledge agents with[2] or without[3] communicative learning, Stigmergy isn't relevent to the current situation, though I know it would be an interesting thing to put into the world simulation. With associated change of game balance.
[1] "Oh, I feel sad. I need to speak to the Mayor. He's deep in the caverns and I will now calculate how to get to him, and recalculate arbitrarily to his new position he moves around, despite being way beyond my vision or hearing."
[2] "Hoi! Freind McMiner, I have been tasked to cut some fine amethyst, and I understand that you can tell me down which long tunnel they may be found... Pray tell me, good sir, which way hither?"
[3] "Where is that log? Where is that log? I've been asked to get a log, and I don't know where it is. It wasn't to the east of this wall last time I looked, but is it there now.... No, first I'll check the northern forests. It may be there..."
Just because we're not constrained to a limited-knowledge approach doesn't mean we can't use one. Consulting a global knowledge bank costs cycles, more so the larger it is. An effective limited-knowledge technique, of which stigmergy is a good and intriguing example, can be more efficient by structurally ignoring parts of the knowledge bank not likely to be relevant to an agent's decision.That's not really true. It is significantly simpler (and faster) to solve problems using global knowledge. Any problem that can be solved with limited information can be solved at least as fast (and in the vast majority of cases faster and better) using global information. This is one of the central ideas of information theory. Techniques such as stigmergy are useful when the problem MUST be solved in a distributed manner. They are slow to converge and require significantly more overhead.
Anyway, it's not so much a question of "what we have," if you mean the current pathfinder, because the point is to rip it out and replace it with something better. There's nothing inherently globally omniscient about DF critters; it's just a question of them being programmed that way or not.But there is a significant difference between the kind of AI you're suggesting and pathfinding. Pathfinding really doesn't care where the knowledge comes from or how it is used. What you're talking about is AI.
The problem is that pathfinding pretty much is one of the core heart pieces of artificial intelligence, it is about finding a preferred path, where to go, where to move, how to get there, and why that path.This is probably where our difference of opinion comes from. I see pathfinding as finding the lowest cost path on an arbitrary graph. This is a mathematical property of the graph and has nothing really to do with AI. The AI determines where to go, and by defining the costs for going different routes, defines the graph. The costs themselves define "why" that route. If a dwarf is operating under limited information, some tiles could be "unexplored". These would have some default cost (a relatively high "exploration cost"). In essence all aspects of AI you want to include are simply found through defining an appropriate cost function.
I do feel that Stigmergy is incredibly Awesome, and will be perfect for the dwarf swarm intelligence.I actually disagree about this. I think there are significantly easier ways to achieve the effects you want to achieve. Stigmergy is complicated and poorly understood. It makes sense if you want to build cheap, simple hardware to perform complex distributed tasks, but not when you're using a single powerful processor with global information on a centralized task.
############################
#c ######################
# ##### | ###########
# | | ##########
####### | #########
#######______|_____#########
####### #| | b
####### # |_#############
######## # # ###########
######### _ ############
############ ###############
############a###############
Well, "which way thither" would be a valid way of "which way to get there", but I'm sure I was writing something more like "which way from here". So "...which way, hither?"Quote[2] "Hoi! Freind McMiner, I have been tasked to cut some fine amethyst, and I understand that you can tell me down which long tunnel they may be found... Pray tell me, good sir, which way hither?"
btw, I believe you mean "thither," not "hither." "Hither and thither" is like "here and there," and I believe the usage parallels this in general. TMYK
A few quick questions: How are we expecting calls from the program to the pathfinder to work? Given that some critters may be moving towards a moving target, I'm assuming that it's a series of "I am at location X and I need to get to location Y, what is the next step I should take?" and the return value will be a direction in some format (sub-question: is there a standard format for these vectors?). The primary goal is then to return from that call as quickly as possible, without returning an impossible move and without causing "waggle dance" or other atrtfacts.
DirectionVector GetNextStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination);
Returning the entire path works very poorly for a moving target (e.g. a meeting), and also means that if several dwarves are following a common path (e.g. trade-depot -> stockpile) then you have multiple memory copies of the same path.Apologies, I meant to add that to the "advantages of a single move" side. With the caveat that if it's converging paths (at least temporarily) the two pathers could be given event-driven instructions to pop the successively nearer destination locations of of each other, and if one is chasing the other considerations might be given to adding the 'done' movements of the latter to the former's path. Worst case scenario is when the disinterested 'target' agent is moving in a topologically 'perpendicular' manner and the changes to the seeker's path are not simple splice-on/off functions.
Each critter has to make a call that says "What is my next move" - whether it makes that to its own stored copy of the path or to a pathfinding engine is largely irrelevant. I'm not suggesting that the engine recalculate every path for every call, although we can program a reference engine that does that if necessary. But the call to the engine should be (pseudo-typed):I see, so pathing is initiated by the GetNextStep function if there's no acknowledged (and irrefutable) path already in existence, but the next step merely shifted from the required path store (not sure what syntax your pseudo-code would use, but some sort of hybrid of a "state %path; $path{$agentID} = GetNewPath($src,$dst) unless (defined $path{$agentID} && !PathChangeNeeded{$agentID});" command that I might use in my Perl testbed's version of the above[1]) whenever possible. With the PathChangeNeeded() function covering a variety of relevent sins...Code: [Select]DirectionVector GetNextStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination);
and everything inside there should be a black box to the client, returning DirectionVector in as few cycles as possible (averaged over many calls).
PathIterator GetFirstStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination); // for paths to static destinations
DirectionVector GetNextStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination); // for paths to mobile destinations
where PathIterator has an "increment" operator, and is convertible to a DirectionVector.void MapDataChange(const CoOrdinate& Location, const bool IsPassable, const Cost& = 0);
That doesn't help us for moving targets, and if we just used the single function, it would involve the constant creation and destruction of iterators, which might be expensive.I was thinking something more like:
However, we could have different functions so that we can optimise the calling code depending on whether we are aiming for a moving or a static target:Code: [Select]PathIterator GetFirstStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination); // for paths to static destinations
where PathIterator has an "increment" operator, and is convertible to a DirectionVector.
DirectionVector GetNextStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination); // for paths to mobile destinations
PathIterator path(const point& CurrentLocation, const point& Destination); //for all pathfinding
PathIterator changeDestination(Pathiterator currentIterator, const point& newDestination); //only used when destination changes
I think we will definitely need state for each active path. Otherwise it becomes impossible to use A* or other methods that need to calculate the entire path in one step.If we code that properly, the path finding engine can keep a register of the current PathIterators, and make sure that the nothing in the path cache will be dropped if it is on a current iterated path.
One other bonus of just having the GetNextStep function is that you can be vague at the beginning of a long path - how you implement this in code is up to you, but for instance if you are outside in the far south and you know you need to get to the far north, then you can tell the critter to start moving north, and get more specific the closer you get. See my heirarchical coordinate system for details of why this might be useful, also moving targets again.
Back to the interface, I think the engine needs a "MapDataChange" function, which (ideally) the game could call when map data changes (would obviously require Toady's input), but in the meantime, critters could call when the direction specified in the return from GetNextStep was impassable. You could use this as a very inefficient (in the beginning) way of building up the map data without having to read memory at all, or alternatively have a sub process which scans the map at intervals and checks for changes:In the current code base the client creates a "grid" class which implements two functions:Code: [Select]void MapDataChange(const CoOrdinate& Location, const bool IsPassable, const Cost& = 0);
or similar.
cost_t edgeCost(const point& a, const point&b);
unsigned max(unsigned dim);
where max returns the size of the grid along dimension dim and edgeCost returns the cost to travel from point a to an adjacent point b. A cost of -1 is used to represent disconnection. You can use edgeCost(a,a)!= -1 to determine if point a is passable.I was thinking something more like:OK, the PathIterator with the ChangeDestination method is good, that's a clean single interface.Code: [Select]PathIterator path(const point& CurrentLocation, const point& Destination); //for all pathfinding
I think we will definitely need state for each active path. Otherwise it becomes impossible to use A* or other methods that need to calculate the entire path in one step.
PathIterator changeDestination(Pathiterator currentIterator, const point& newDestination); //only used when destination changes
In the current code base the client creates a "grid" class which implements two functions:Code: [Select]cost_t edgeCost(const point& a, const point&b);
where max returns the size of the grid along dimension dim and edgeCost returns the cost to travel from point a to an adjacent point b. A cost of -1 is used to represent disconnection. You can use edgeCost(a,a)!= -1 to determine if point a is passable.
unsigned max(unsigned dim);
Then the client passes this grid to the library, which does stuff based on that.
For the cached pathing methods there is another function "registerChanged(const point &p)" which needs to be called for every tile that has changed.
It's C++, with CoOrdinate and DirectionVector being as-yet-unidentified types.What I meant was "not sure how I'd do this Perlish statement in C-Code". See "Persistent Private Variables" in the appropriate PerlSub perldoc (http://perldoc.perl.org/perlsub.html#Persistent-Private-Variables) for the mechanism I was employing. In leiu of making it a global (i.e. ($main::<foo>) implementation or needlessly package/object-wide. Sorry, minor distraction, that.
One other bonus of just having the GetNextStep function is that you can be vague at the beginning of a long path - how you implement this in code is up to you, but for instance if you are outside in the far south and you know you need to get to the far north, then you can tell the critter to start moving north, and get more specific the closer you get. See my heirarchical coordinate system for details of why this might be useful, also moving targets again.
half of the stuff in this thread goes way over my head. the other half goes way way over.Personally, I'm working on a testbed system of my own, having not yet grappled the published testbed system (also standalone, merely simulating[1] the general conditions of DF, not tapping into its code. But this is to address one particular design feature of a pathing algorithm.
are you guys working on actual df code, or are you just theorizing as of now?
How aboutMost of those things are just moving the GetNextStep call to various points in the algorithm by making assumptions about algorithm behaviour that the implementor may not wish to conform to.
-GetShortestPathLength (for stockpile distances and stuff)
-GetFullPath (should be rarely used, but still exist)
-GetStep (As mentioned before)
-GetNSteps (Allows program to cache a few steps at a time)
-GetLOSSteps (Gets the steps between the unit and where the path leaves LOS. This would be closest to real life, since I doubt you think "Okay, next I must go that way for a step. Okay, next I must go that way for a step. Okay, next I must go that way for a step. Okay, next I must go that way for a step. " When all 4 are in the sime direction)
How aboutMost of those things are just moving the GetNextStep call to various points in the algorithm by making assumptions about algorithm behaviour that the implementor may not wish to conform to.
-GetShortestPathLength (for stockpile distances and stuff)
-GetFullPath (should be rarely used, but still exist)
-GetStep (As mentioned before)
-GetNSteps (Allows program to cache a few steps at a time)
-GetLOSSteps (Gets the steps between the unit and where the path leaves LOS. This would be closest to real life, since I doubt you think "Okay, next I must go that way for a step. Okay, next I must go that way for a step. Okay, next I must go that way for a step. Okay, next I must go that way for a step. " When all 4 are in the sime direction)
However, the PathLength you mention is an important function for the engine. It could be a method of the PathIterator concept.
pool:
00000100
least significant bit - dwarfs
2nd - flyer
3rd - swimmer - water
4th - swimmer - salt water (do fresh water fish die in salt water?)
5th - building destroyer
6th - digger
etc.
up to 32 or 64 bits with dedicated bits for traders and siegers, pets, etc.
workshop: (hexadecimal)
30 30 30
33 33 33
33 33 30
the 2nd row and first 2 bottom fields are passable for dwarfs, flyers, building destroyers and diggers,
the top row and bottom right corner is passable only for building destroyers
we can use 64bit ints for 64 different kinds of movement. Now, if we want to get a path, we set a single bit in the bit mask and tell what kind of transport the creature wants and from where to where it wants to go.dwarf:
2 2 2 2 2
2 0 0 0 2
2 5 5 5 2
2 5 5 0 2
2 2 2 2 2
flyer:
2 2 2 2 2
2 0 0 0 2
2 2 2 2 2
2 2 2 0 2
2 2 2 2 2
building destroyer:
2 2 2 2 2
2 10 10 10 2
2 2 2 2 2
2 2 2 10 2
2 2 2 2 2
typedef coord_t int32_t;
add(coord_t[3] square, int ID, int count);
substract(coord_t[3] square, int ID, int count);
optionally functions for mass adding and removingcoord_t[3] findID(coord_t[3] starting_point, movement_t bit_mask, int ID);
movementVectors* GetFullPath(movement_type, beginningxyz, endxyz);
movementVector GetStep(movement_type, beginningxyz, endxyz);
movementVectors* GetNSteps(movement_type, beginningxyz, endxyz);
have to be included.setDefaultMovementPenalty(movement_cost[32]) - sets default movement cost for different movement types
updateMapData(cubestartxzy, movement_mask[][][]) - takes cube of space, it's starting field and puts it to the movement graph with fields being movement masks
updateMapMovementPenalty(cubestartxyz, cost_type, movement_costs[][][]) - takes movement type and cube of space with movement cost as filelds in the cube
* did anyone think about penalties for path going through creatures ? this is really important in DF
First thing, I don't think that the callback mechanism for detecting passability for tiles is a good idea - remember, the very paths we look for are directly influenced by it and to calculate it we would have to run it thousands of times. As such IMO the single tile in the map data that the library gets should be a bit field with each bit setting passability for certain type of transport
Resource mapsI don't think something like this belongs in a general purpose pathing library. I think it should be enough if we have something like
cost_t estimatePathCost(Point source, Point destination)
which finds a reasonable estimate of the cost of traveling between two points without actually calculating the path. This could be implemented by finding the path cost between the zones containing the source and destination (which is cached).InterfaceI don't think that these are really necessary at all. They can all be implemented by successive calls to GetStep or whatever. In fact if we implement GetStep as an STL-compatible iterator instead of as a function, we can use STL methods to implement each of them in a single function call. This means that they don't really add anything useful and complicate the interface. Remember KISS (http://en.wikipedia.org/wiki/KISS_principle)!
I think, that the functions qwertyuiopas mentioned:Code: [Select]movementVectors* GetFullPath(movement_type, beginningxyz, endxyz);
have to be included.
movementVector GetStep(movement_type, beginningxyz, endxyz);
movementVectors* GetNSteps(movement_type, beginningxyz, endxyz);
GetLOSSteps() is optional, GetShortestPathLength() is findID()
First thing, I don't think that the callback mechanism for detecting passability for tiles is a good idea - remember, the very paths we look for are directly influenced by it and to calculate it we would have to run it thousands of times. As such IMO the single tile in the map data that the library gets should be a bit field with each bit setting passability for certain type of transport
The problem is that you don't have to have a single bitvector for each tile, you have to have a bitvector for all 27 possible directions from the tile! This is necessary to implement stairways, adjacent floors, ramps, etc. without nasty special cases. Then we also need separate costs for each movement type, creature size and everything else (possibly for each direction!).
I don't see a way of storing all that information without using gobs of memory. But if we simply use a call-back function, the client can calculate that information procedurally. This function doesn't have to be slow. Odds are if Toady implemented one for DF it would probably only consist of some modulo arithmetic, bit tests, and table lookups -- all of which is pretty fast.still, pushing a 3D table through a single function call will be much faster, and this doesn't inform the pathfinder when the passability is invalidated. So we would have to run it over each and every field when map change occures. So if we have to get this data one way or another, why not force the programmer to give it to us in the first place?
In what game that needs pathfinding you don't need to search for nearest enemy or resource?QuoteResource mapsI don't think something like this belongs in a general purpose pathing library.
I think it should be enough if we have something likeAnd that's the problem: the application has to loop, if it has no idea which, for example - a stone, is closest, it may run our function thousand times and it still won't find really the nearest one (or one even close to). There are many situations when stones that are near in cartesian space may well be most remote ones. (even the ones that are in a 20x20x20 cube) and for a 50x50x50 cube you get 125000 calls. "oops!" (simple situation - each and every level mined, mason on a level with a stair case in far corner, with stones near it, you get 50x50x49 stones to check and you still don't find the closest one - the one 26 fields south and you get exacly the same situation as now, only a bit later with much bigger computational cost)Code: [Select]cost_t estimatePathCost(Point source, Point destination)
which finds a reasonable estimate of the cost of traveling between two points without actually calculating the path. This could be implemented by finding the path cost between the zones containing the source and destination (which is cached).
Then the client can loop over all the items they want to consider and choose the shortest themselves.
But this doesn't allow for the programmer to not make the creatures onmniscient - creature gets a path (it is saved in the creature), it tries to follow it, if it can't return to it in, let's say 4 steps (to allow passing other creatures in corridors) using simple A*(because a door it just got to is closed or cavern collapsed), it only then asks for another one.QuoteInterfaceI don't think that these are really necessary at all. They can all be implemented by successive calls to GetStep or whatever. In fact if we implement GetStep as an STL-compatible iterator instead of as a function, we can use STL methods to implement each of them in a single function call. This means that they don't really add anything useful and complicate the interface. Remember KISS (http://en.wikipedia.org/wiki/KISS_principle)!
I think, that the functions qwertyuiopas mentioned:Code: [Select]movementVectors* GetFullPath(movement_type, beginningxyz, endxyz);
have to be included.
movementVector GetStep(movement_type, beginningxyz, endxyz);
movementVectors* GetNSteps(movement_type, beginningxyz, endxyz);
GetLOSSteps() is optional, GetShortestPathLength() is findID()
The problem is that you don't have to have a single bitvector for each tile, you have to have a bitvector for all 27 possible directions from the tile! This is necessary to implement stairways, adjacent floors, ramps, etc. without nasty special cases. Then we also need separate costs for each movement type, creature size and everything else (possibly for each direction!).
This will work for anything except movement that can pass though walls and floors, people have long theorized such a digger type ability. This would probably be best handled with a different system.
QuoteIn what game that needs pathfinding you don't need to search for nearest enemy or resource?QuoteResource mapsI don't think something like this belongs in a general purpose pathing library.
Add ceiling as an additional level (with whatever cost for movement - or 0 for DF) and we have all directions covered.
Then what would be your solution for a lone stonecrafter on a level with stones that are as far as a ladder to higher and lower levels that are full of stone?1. Determining a destination is a separate task from finding a path, and should be treated as such.QuoteIn what game that needs pathfinding you don't need to search for nearest enemy or resource?QuoteResource mapsI don't think something like this belongs in a general purpose pathing library.
2. A general purpose pathfinding library can't determine the destination on its own, because it's not necessarily just "nearest." It can involve lots of game logic, creature preferences, weird item requirements for jobs, anything.if you have only few items that are very specific then you can easly iterate over them, ask for path length to each and every one of them and this way find the nearest one.
Every direction, for every movement type!? What for!? If two adjectant tiles are passable for creature of type 0x01, then it can move there. Add ceiling as an additional level (with whatever cost for movement - or 0 for DF) and we have all directions covered.If you add an extra level to represent the ceiling, then you can't support vertical diagonal movement, which is already used for things such as ramps (or later jumping off of cliffs).
As for movement/cost - in 90% of cases the penalty will be exacly the same for each and every tile, movement cost different than default will be the exception, I see no problem with that (you just keep second 3d table with pointers for data about non default values - pointer=NULL - defaults).While it's true that the penalty is likely to be the same for each tile, keeping a second table doesn't save anything. A 32 bit pointer is just as big as a 32 bit float.
still, pushing a 3D table through a single function call will be much faster, and this doesn't inform the pathfinder when the passability is invalidated. So we would have to run it over each and every field when map change occures. So if we have to get this data one way or another, why not force the programmer to give it to us in the first place?Pushing the table through would not be faster. Unconditional function calls are dirt cheap. Modern CPU's can execute them without even a single cycle of extra delay. Copying and maintaining a working set that does not even fit in L3 cache is expensive. With the function call, we have less memory overhead so we displace much less of the client's working set out of cache.
In what game that needs pathfinding you don't need to search for nearest enemy or resource?Honestly, I can think of quite a few. But not to dismiss your point, I understand what you're saying, and I admit that the problems seem quite coupled from a certain point of view. We definitely need to take into consideration the needs of users, but I feel that if we choose a simpler interface and let the client glue together the pieces he needs, the library will be much more flexible, robust and faster.
And that's the problem: the application has to loop, if it has no idea which, for example - a stone, is closest, it may run our function thousand times and it still won't find really the nearest one (or one even close to). There are many situations when stones that are near in cartesian space may well be most remote ones. (even the ones that are in a 20x20x20 cube) and for a 50x50x50 cube you get 125000 calls. "oops!" (simple situation - each and every level mined, mason on a level with a stair case in far corner, with stones near it, you get 50x50x49 stones to check and you still don't find the closest one - the one 26 fields south and you get exacly the same situation as now, only a bit later with much bigger computational cost)First of all, loops are not slow --especially small repeated loops such as iterating over a list -- even if they have unconditional function calls. Everything is already in L1 and branch prediction will be near perfect, so this should be rather fast.
Path EstimateCostToNearest(Point Start, Point[] Targets)
That's also not true. However much information you want the creature to have should be reflected in the map you provide to the pathfinder. If you don't provide omniscient information, then the creatures won't be omniscient. It's up to the client to decide what they want.QuoteI don't think that these are really necessary at all. They can all be implemented by successive calls to GetStep or whatever. In fact if we implement GetStep as an STL-compatible iterator instead of as a function, we can use STL methods to implement each of them in a single function call. This means that they don't really add anything useful and complicate the interface. Remember KISS (http://en.wikipedia.org/wiki/KISS_principle)!But this doesn't allow for the programmer to not make the creatures onmniscient - creature gets a path (it is saved in the creature), it tries to follow it, if it can't return to it in, let's say 4 steps (to allow passing other creatures in corridors) using simple A*(because a door it just got to is closed or cavern collapsed), it only then asks for another one.
Then what would be your solution for a lone stonecrafter on a level with stones that are as far as a ladder to higher and lower levels that are full of stone?
if you have only few items that are very specific then you can easly iterate over them, ask for path length to each and every one of them and this way find the nearest one.
Problem starts when you have hundreds or thousands of items that are exacly the same - then the engine can't easly decide which is nearest (as with our lone stonecrafter).
coord_t[3] findID(coord_t[3] starting_point, movement_t bit_mask, int ID);
The problem is that you don't have to have a single bitvector for each tile, you have to have a bitvector for all 27 possible directions from the tile! This is necessary to implement stairways, adjacent floors, ramps, etc. without nasty special cases. Then we also need separate costs for each movement type, creature size and everything else (possibly for each direction!).You could....take the wordsright out of my mouth.
I don't see a way of storing all that information without using gobs of memory. But if we simply use a call-back function, the client can calculate that information procedurally. This function doesn't have to be slow. Odds are if Toady implemented one for DF it would probably only consist of some modulo arithmetic, bit tests, and table lookups -- all of which is pretty fast.
Footkerchief: So long as it's a 'pure' pf thing, yeah. But, eventually, pf = ai.
Ramps don't use vertical diagonal movement, you can't have such situation:Every direction, for every movement type!? What for!? If two adjectant tiles are passable for creature of type 0x01, then it can move there. Add ceiling as an additional level (with whatever cost for movement - or 0 for DF) and we have all directions covered.If you add an extra level to represent the ceiling, then you can't support vertical diagonal movement, which is already used for things such as ramps (or later jumping off of cliffs).
(cross section)
__#
##↑
ramps work just like stairsIMO you're a bit over estimating the capability of CPUs, but that's not the point.QuoteAs for movement/cost - in 90% of cases the penalty will be exacly the same for each and every tile, movement cost different than default will be the exception, I see no problem with that (you just keep second 3d table with pointers for data about non default values - pointer=NULL - defaults).While it's true that the penalty is likely to be the same for each tile, keeping a second table doesn't save anything. A 32 bit pointer is just as big as a 32 bit float.Quotestill, pushing a 3D table through a single function call will be much faster, and this doesn't inform the pathfinder when the passability is invalidated. So we would have to run it over each and every field when map change occures. So if we have to get this data one way or another, why not force the programmer to give it to us in the first place?Pushing the table through would not be faster. Unconditional function calls are dirt cheap. Modern CPU's can execute them without even a single cycle of extra delay. Copying and maintaining a working set that does not even fit in L3 cache is expensive. With the function call, we have less memory overhead so we displace much less of the client's working set out of cache.
And that's still not mentioning the size of the table! If you decide to devote 8 bits for each tile (not for each edge, each tile!) just to determine is this tile passable by movement type x, a 256x256x16 map would require 1MB of memory. If we add ceilings, it goes to 2MB. Note that this is a really small map. A 6x6 I am currently using is 288x288x32, which is 2.5 or 5 MB. Note that this does not include any cost information, and only supports 8 movement types. If you add terrain types or other features then this only gets worse. And, as you said the number of tiles on the map is only going to increase. If you get up to hundreds of z-levels with larger embark sizes, things get nasty very quickly.since when 5MiB of memory for such huge tool is much?! We're trying to trade in memory for cycles, 200MiB would be nothing!
i said nothing of such sort, i know that loop is faster than unrolled loop on current CPUs, that was not the pointQuoteIn what game that needs pathfinding you don't need to search for nearest enemy or resource?Honestly, I can think of quite a few. But not to dismiss your point, I understand what you're saying, and I admit that the problems seem quite coupled from a certain point of view. We definitely need to take into consideration the needs of users, but I feel that if we choose a simpler interface and let the client glue together the pieces he needs, the library will be much more flexible, robust and faster.QuoteAnd that's the problem: the application has to loop, if it has no idea which, for example - a stone, is closest, it may run our function thousand times and it still won't find really the nearest one (or one even close to). There are many situations when stones that are near in cartesian space may well be most remote ones. (even the ones that are in a 20x20x20 cube) and for a 50x50x50 cube you get 125000 calls. "oops!" (simple situation - each and every level mined, mason on a level with a stair case in far corner, with stones near it, you get 50x50x49 stones to check and you still don't find the closest one - the one 26 fields south and you get exacly the same situation as now, only a bit later with much bigger computational cost)First of all, loops are not slow --especially small repeated loops such as iterating over a list -- even if they have unconditional function calls. Everything is already in L1 and branch prediction will be near perfect, so this should be rather fast.
Second, once you have your interface, how would your method solve it? Would you do a breadth first search of the entire graph until at least one of the items is found? We could just as easily do this without storing the locations of items. Just provide a method:For starters it would search the item on accessible areas, simple 3D floodfill would be better than the current DF implementation.Code: [Select]Path EstimateCostToNearest(Point Start, Point[] Targets)
it was just a simple use case of the API, not the only way to use it.QuoteThat's also not true. However much information you want the creature to have should be reflected in the map you provide to the pathfinder. If you don't provide omniscient information, then the creatures won't be omniscient. It's up to the client to decide what they want.QuoteI don't think that these are really necessary at all. They can all be implemented by successive calls to GetStep or whatever. In fact if we implement GetStep as an STL-compatible iterator instead of as a function, we can use STL methods to implement each of them in a single function call. This means that they don't really add anything useful and complicate the interface. Remember KISS (http://en.wikipedia.org/wiki/KISS_principle)!But this doesn't allow for the programmer to not make the creatures onmniscient - creature gets a path (it is saved in the creature), it tries to follow it, if it can't return to it in, let's say 4 steps (to allow passing other creatures in corridors) using simple A*(because a door it just got to is closed or cavern collapsed), it only then asks for another one.
Edit: fix quote tags
As I suggested - that's the interface for stuff that's in the hundreds or thousands, not single items.Then what would be your solution for a lone stonecrafter on a level with stones that are as far as a ladder to higher and lower levels that are full of stone?
if you have only few items that are very specific then you can easly iterate over them, ask for path length to each and every one of them and this way find the nearest one.
Problem starts when you have hundreds or thousands of items that are exacly the same - then the engine can't easly decide which is nearest (as with our lone stonecrafter).
I see what you're getting at, but the scheme you described:Code: [Select]coord_t[3] findID(coord_t[3] starting_point, movement_t bit_mask, int ID);
is not going to work, if ID simply refers to "object type." Maintaining the client-side index would be extremely messy (does a given number refer to enemy goblins, or enemy goblin archers, or all goblin archers? do left-handed redheads get their own ID? what about thrones decorated with platinum but not with steel?) and it would be awkward for the client to request the nearest of an inhomogeneous set of objects.
There's no reason for the pathfinding library to care about object IDs at all. It's much cleaner for the client to simply pass in a set of candidate destination coordinates and for the library to find the nearest of those coordinates and pathfind to it. Obviously the client should first do some trivial pruning of the coordinate set.
As I suggested - that's the interface for stuff that's in the hundreds or thousands, not single items.
For items that are uncommon, a function that takes all coordinates of them and returns the closest one would be better.
Ramps don't use vertical diagonal movement, you can't have such situation:Are you sure about that? Because I've tested this on 40d15. No creature is ever on the top floor of a ramp. They all travel horizontally as well as vertically. Even wagons from trade caravans skip the top floor. If you put a dog on a chain next to a ramp, he can be on the top floor diagonal from the ramp, but never on the top floor of a ramp. If this is an item of dispute, I can take a screen cap.Code: [Select](cross section)
ramps work just like stairs
__#
##↑
IMO you're a bit over estimating the capability of CPUs, but that's not the point.I think you're overestimating the memory/cache system of modern CPUs. If something is not in the cache, you're talking about a stall of hundreds of clock cycles. If you read any recent works on optimizing program execution speed, it's all about reducing the size of the working set and increasing locality.
Most of the map is static, you displace client cache once, when loading the data, not every time it's called. And the data has to be stored somewhere - if we want the library to be opaque it needs to duplicate the data.
since when 5MiB of memory for such huge tool is much?! We're trying to trade in memory for cycles, 200MiB would be nothing!5MiB is a huge amount when it's sacrificed for no perceivable gain. I wouldn't mind using 200MiB of path caches if it was able to significantly speed things up, but that's a ridiculous amount just to obtain basic functionality. If you read the literature and look at other pathfinding implementations, none of them duplicate the connectivity map. Some (modern ones) even talk about pushing the path-finding footprint below 500kiB! On that 200x400x200 map you mentioned, the other method would only require 32 bytes(!) to achieve the same thing. Your design just doesn't scale.
and a 200x400x200 map with 32 movement types and 2 non standard penalty values per tile on average would take only about 244MiB, and first: that's a huge map, second: the amount of other game info that's needed will still dwarf it.
Remember, I told that the pathfinding world doesn't need to be uniform, the engine has to push to the lib only the fragments that have known resources or pathfinding creaturesAnd how will the engine know which portions of the map are relevant to pathfinding? The library is supposed to be opaque.
A 3D flood-fill, also known as a breadth first search. You could also use a multi-destination version of A* (though you'd need to be careful to keep the fringe from getting too large). You could even use the cache to estimate the distance and only path the shortest ones. The point is that, for the vast majority of potential optimizations, *what* the item is, is irrelevant. I agree with you (and a basic tenant of Information Theory) that the more information you have, the better and faster your estimates are. The problem is that speed is not the only goal, and if you're going to spend your memory on caches to help speed up pathing, you're better off storing partial paths or connections between zones than you are storing the location of all blue socks on the map.QuoteSecond, once you have your interface, how would your method solve it? Would you do a breadth first search of the entire graph until at least one of the items is found? We could just as easily do this without storing the locations of items. Just provide a method:For starters it would search the item on accessible areas, simple 3D floodfill would be better than the current DF implementation.Code: [Select]Path EstimateCostToNearest(Point Start, Point[] Targets)
Then we could optimise for stuff that's in abundance - by storing additional info whatever an item of such and such ID is in reduced movement graph of the map.
Besides I'm suggesting an interface, not a solution. When the library has full picture of the situation, we can optimise the whole situation, not just find local minima.
What A* needs of the graph is:
- iterate over the edges out of a vertex
- cost of an edge
- admissable heuristic for the distance between two vertices
At the moment, it doesn't seem like we need anything more for any of the extensions we've come up with.
It shouldn't be our job to determine how the graph is stored internally; anything that supports the interface should be acceptable.
What a game needs of our pathfinder is probably just:
- compute a path from s to t, returning a forward iterator over edges
Footkerchief: So long as it's a 'pure' pf thing, yeah. But, eventually, pf = ai.
And remember the dwarven pathfinding truism: sock.value>>elephant.costThe problem is that you don't have to have a single bitvector for each tile, you have to have a bitvector for all 27 possible directions from the tile! This is necessary to implement stairways, adjacent floors, ramps, etc. without nasty special cases. Then we also need separate costs for each movement type, creature size and everything else (possibly for each direction!).You could....take the wordsright out of my mouth.
I don't see a way of storing all that information without using gobs of memory. But if we simply use a call-back function, the client can calculate that information procedurally. This function doesn't have to be slow. Odds are if Toady implemented one for DF it would probably only consist of some modulo arithmetic, bit tests, and table lookups -- all of which is pretty fast.
26 directions though. When is it ever impermissible for a creature to move to where it already is? Also...I am fairly sure that flying or swimming are required to make a move to up-and-direction (without ramp, natch)
I'd suggest some manner of preclusions,but I already found a corner case I'd like preserving: swimming up waterfalls.solvable if swimming is permitted to go up.
I see why DF is loath to path fliers/swimmers right, now...for walkers, it's dead easy to see where you can go- up if on(up stair || up/down stair) && up(down stair || up/down stair) up+direction if on(ramp) && direction(wall), direction if directionIsFloored, and the downs are inverse of the ups (...actually, it won't check for the wall, as you're standing on it, leading to one-way ramps.)
The idea of using a global list for rare items is also an excellent idea, a heuristic can be run on each one and the best one selected. Its not as efficient when a great number of items are present in which case the breath-first search would be faster. Doing the right kind of search for each request will be key.Actually, I don't see why the pathfinder should be in the business of keeping that list. I suggest two possibilities:
for each destination, A*(src, dest)
A* (src, heuristic, success)
where heuristic and success loop over the destinations.I could think of one or two but they are fringe cases that are closer to a game mechanic than pathfinding.And yet...when it's doing that, it won't be looking for paths, so I think it can safely be ignored for groundlings?
EDIT: Here is a hint (http://www.bay12games.com/forum/index.php?topic=45390.0).
I could think of one or two but they are fringe cases that are closer to a game mechanic than pathfinding.And yet...when it's doing that, it won't be looking for paths, so I think it can safely be ignored for groundlings?
EDIT: Here is a hint (http://www.bay12games.com/forum/index.php?topic=45390.0).
I do wonder if there is any way for a [FLIER] to recover from projectile status more than others. but tht's off-topic.
1. Is it a necessity or a convenience there for the divisions in the example some pages back to be base 2 or a divisible of 2?Convenience. With everything evenly divisible things just work out nicely in my testing scripts. I could have used 3 instead of 2 just as easily.
2. How are zones ensured to be useful without potential misdirection?Zones, (at least in the current gridzone) just contain edge nodes (nodes on the edge of the zone that can lead to other zones). These edge nodes cache paths to all the edge nodes in their zone. The hierarchical A*, basically is just A* over these edge nodes. Of course we also need to add edge nodes for the source and destination temporarily. Since all the edge nodes are used and the path costs come directly from the original graph, this preserves optimality.Spoiler (click to show/hide)
26 directions though. When is it ever impermissible for a creature to move to where it already is?My internal objection to the original figure was that "staying where one is" is never a viable movement option.
2. How are zones ensured to be useful without potential misdirection?Zones, (at least in the current gridzone) just contain edge nodes (nodes on the edge of the zone that can lead to other zones). These edge nodes cache paths to all the edge nodes in their zone. The hierarchical A*, basically is just A* over these edge nodes. Of course we also need to add edge nodes for the source and destination temporarily. Since all the edge nodes are used and the path costs come directly from the original graph, this preserves optimality.Spoiler (click to show/hide)
Optimality is not preserved if there's only one node per edge, mind; indeed, hierarchical A* is not optimal.In the current zoneManager implementation there are as many nodes per zone edge as there are tiles on the edge (eg. 1 node for each tile with at least one edge leaving the zone), so it is still optimal.
Optimality is not preserved if there's only one node per edge, mind; indeed, hierarchical A* is not optimal.In the current zoneManager implementation there are as many nodes per zone edge as there are tiles on the edge (eg. 1 node for each tile with at least one edge leaving the zone), so it is still optimal.
Optimality is not preserved if there's only one node per edge, mind; indeed, hierarchical A* is not optimal.In the current zoneManager implementation there are as many nodes per zone edge as there are tiles on the edge (eg. 1 node for each tile with at least one edge leaving the zone), so it is still optimal.
So then, for example, in an open(no obstructions, no z axis considerations) 4x4 there are 12 nodes/tiles around the edge and each node caches a path to every other node in the same zone.
11+10+9+8+7+6+5+4+3+2+1=66 cached paths with an average length of ~3 for an open 4x4 zone. Is this right?
The current version is both worse and better than that would imply. It's worse than that because the path cache is stored directionally (though only calculated once for each direction), so all nodes have their own copy. Additionally nodes have paths to their adjacent neighbors in other zones, so there would be a total of 168 cached paths, of average length ~2.14.
It's actually better than it seems because 1) we don't usually deal with zones smaller than 8x8, and 2) the cache is actually calculated on demand, so paths that aren't ever considered won't be calculated or stored in cache. Since the cache is filled on demand, a zone in a completely open area will probably only have to calculate a single path (if not yet cached) each call. Further this path would simply be a portion of the path non-hierarchical A* would have needed to calculate anyway.
Anyway, I'm thinking in the long run, we'll probably have to sacrifice optimality. The current implementation uses too much memory and is only twice as fast as A* for a typical load. We really need to use less memory and calculate paths faster, which is not really possible if we want to maintain optimality.
Aside from the inter/intra zone node caching, how are the paths cached? What I mean is, are zone meta-paths cached or are the semi-explicit tile paths cached?The only path caching currently implemented is between the border nodes on the edge.
I am sorry for these odd questions. I have coded in C++, Java, and different flavors of Basic before but don't have the time(read as the willpower to learn more about C++) to really dig into and wrap my head around code someone else wrote.It's fine, really. This is a really hard problem, and I had to think carefully to come up with even the imperfect prototype we have now. The more we talk about it, and the more we think about it, and the closer we come to a good solution.
When is it ever impermissible for a creature to move to where it already is?I could think of one or two but they are fringe cases that are closer to a game mechanic than pathfinding.
Any given path through one zone or sub-zone to a neighboring zone or sub-zone on the same z-level will cost approximately the same **.This isn't really true. The path length through one of your 3x3 zones could be as little as 1, or as much as 5. This means that the path found can be more than twice the optimal path length. Additionally, I don't think your method supports non-uniform path costs.
That's certainly an interesting idea. The subzone portion sound similar to the "Memory Efficient Pathfinding" (https://www.aaai.org/Papers/AIIDE/2007/AIIDE07-006.pdf) paper Impaler linked to earlier.
I do have a few criticisms of your method:Any given path through one zone or sub-zone to a neighboring zone or sub-zone on the same z-level will cost approximately the same **.This isn't really true. The path length through one of your 3x3 zones could be as little as 1, or as much as 5. This means that the path found can be more than twice the optimal path length. Additionally, I don't think your method supports non-uniform path costs.
Also, you're only reducing the graph by a factor of 3. The overhead from keeping track of the new abstract graph (and its subgraphs) is likely to be larger than any gains you have from abstraction. I don't see a way to easily increase the amount of abstraction, so I'm not sure we can solve this without significant changes.
Trees still aren't fixed, but here's a screenshot of a path below ground.Spoiler: Screenshot (click to show/hide)
This isn't really true. The path length through one of your 3x3 zones could be as little as 1, or as much as 5.
This isn't really true. The path length through one of your 3x3 zones could be as little as 1, or as much as 5.
6, actually:
Regions:
a b
c d
MetaPath: a -> b -> c
region layout:
###|...
###|...
###|.##
-------
..#|...
..#|##.
...|...
The path through region D costs 6.
65.
##3.5
12.
Footkerchief: So long as it's a 'pure' pf thing, yeah. But, eventually, pf = ai.
And remember the dwarven pathfinding truism: sock.value>>elephant.costThe problem is that you don't have to have a single bitvector for each tile, you have to have a bitvector for all 27 possible directions from the tile! This is necessary to implement stairways, adjacent floors, ramps, etc. without nasty special cases. Then we also need separate costs for each movement type, creature size and everything else (possibly for each direction!).You could....take the wordsright out of my mouth.
I don't see a way of storing all that information without using gobs of memory. But if we simply use a call-back function, the client can calculate that information procedurally. This function doesn't have to be slow. Odds are if Toady implemented one for DF it would probably only consist of some modulo arithmetic, bit tests, and table lookups -- all of which is pretty fast.
26 directions though. When is it ever impermissible for a creature to move to where it already is? Also...I am fairly sure that flying or swimming are required to make a move to up-and-direction (without ramp, natch)
I'd suggest some manner of preclusions,but I already found a corner case I'd like preserving: swimming up waterfalls.solvable if swimming is permitted to go up.
I see why DF is loath to path fliers/swimmers right, now...for walkers, it's dead easy to see where you can go- up if on(up stair || up/down stair) && up(down stair || up/down stair) up+direction if on(ramp) && direction(wall), direction if directionIsFloored, and the downs are inverse of the ups (...actually, it won't check for the wall, as you're standing on it, leading to one-way ramps.)
##.|#..
##.|#..
##.|###
-------
###|...
..#|##.
...|...
27 is numpad's 9 times 3(up, down, and same-z)
HOWEVER, 5 + same-level = unchanged, making the true number 26, or solving the "stay in place" question.
This assumes your dwarves will move in relatively the same areas and pathways a majority of the time, which unless they are fleeing from goblins is a correct assumption.
On the other hand, it might be a good idea that, if all 27 directions are included, you ensure it can't "explore" what happens if a creature doesn't move, how it affect's it's path. Some very possible infinite loops there, unless not moving is automatically discarded by the pathing, and that makes the pathing check for moving to the source tile from it utterly worthless...I would have thought that any state-sensitive (all of them? by one means or another?) pathing algorithm would discount a movement of "no movement" on the same basis as moving back to a previously visited position is discounted.
I would have thought that any state-sensitive (all of them? by one means or another?) pathing algorithm would discount a movement of "no movement" on the same basis as moving back to a previously visited position is discounted.As far as I know, this is correct.
Of course, the caveat is the aforementioned (predictably) dynamic environment, where waiting for a door to open allows a quicker transit than keeping on moving around the longer route. If standing still were still disallowed, then hopping between two or more nearby cells could be 'allowed' as a movement.Actually, I would probably not implement waiting in the pathfinder. I would adjust the cost function so that the cost of an edge was related to the traveling time. This means that traveling through a door that is about to open includes the time cost of waiting for it to open. Basically, if the cost of every tile is 1, and there's a door that will open in T steps from now, 5 tiles away from here, the cost of going through that door should be (T-5). This will add significant complexity to the cost function and will require doors and other predictable close-able things to be within their own zones (and carried all the way up the hierarchy). Anyway, we probably won't support anything like that for a while (if ever).
27 is numpad's 9 times 3(up, down, and same-z)
HOWEVER, 5 + same-level = unchanged, making the true number 26, or solving the "stay in place" question.
Clarification:
By
"solving the "stay in place" "
I meant that it would make not moving a "valid" direction, so such concerns wouldn't be a problem.
On the other hand, it might be a good idea that, if all 27 directions are included, you ensure it can't "explore" what happens if a creature doesn't move, how it affect's it's path. Some very possible infinite loops there, unless not moving is automatically discarded by the pathing, and that makes the pathing check for moving to the source tile from it utterly worthless...
Actually, I would probably not implement waiting in the pathfinder. I would adjust the cost function so that the cost of an edge was related to the traveling time. This means that traveling through a door that is about to open includes the time cost of waiting for it to open. Basically, if the cost of every tile is 1, and there's a door that will open in T steps from now, 5 tiles away from here, the cost of going through that door should be (T-5).You'd need to modify the algorithm following the calculated path to avoid a juggernaut-like rush up to the not-yet-open pathway only for it to trigger on the current impassibility.
[...] Anyway, we probably won't support anything like that for a while (if ever).Yes, I'm being a bit speculative in the above. (A bit? Typical English understatement, some might contend. :))
Also, Impaler has gotten the connectivity rendering working on the current Khazad svn head.Because I haven't commented (I think... If I have, I've slept since): Nice.
This will add significant complexity to the cost function and will require doors and other predictable close-able things to be within their own zones (and carried all the way up the hierarchy). Anyway, we probably won't support anything like that for a while (if ever).
Synchronous and single threaded currently, when the client sends a map change or a path request execution passes to the server (the pathfinder code) and has to return before the client can continue. While multi-threading is interesting I'm not up too speed on it and I think a lot of performance can be squeezed out by optimizing the actual path finding code, perhaps far more then just multi-threading the old code.Optimizing your proposed pathing doesn't mean it must remain single-threaded, though. I haven't looked at any of your code, just skimmed the thread, but it seems to me that the closer to shared-nothing you can get (minimizing any critical execution segments) in a single-threaded iteration that you can get, the easier you can take advantage of a multithreaded option later.
Synchronous and single threaded currently, when the client sends a map change or a path request execution passes to the server (the pathfinder code) and has to return before the client can continue. While multi-threading is interesting I'm not up too speed on it and I think a lot of performance can be squeezed out by optimizing the actual path finding code, perhaps far more then just multi-threading the old code.Optimizing your proposed pathing doesn't mean it must remain single-threaded, though. I haven't looked at any of your code, just skimmed the thread, but it seems to me that the closer to shared-nothing you can get (minimizing any critical execution segments) in a single-threaded iteration that you can get, the easier you can take advantage of a multithreaded option later.
Talking about big-Oh when multithreaded stuff is involved gets weird, but in a perfectly shared-nothing system you can approach (never reach, of course, but approach) a 1/n multiplier to your entire execution time. That strikes me as being something that might be very, very useful down the line.
I'm not an algorithms guy, but it seems intuitively that you'll fairly quickly reach a point of diminishing returns in terms of the actual algorithm, whereas spreading it across multiple cores can reduce it further. It's not an either/or proposition.
(There's also graph knitting and all sorts of other stuff that can create a performance/accuracy tradeoff, but I'm sure that's already come up. :) )
Within an invocation of A*, I don't see how you're going to get any parallelism at all though. You're going through a priority queue one element at a time; you can't get much more sequential than that. With a hierarchy I suppose you could do something, but it wouldn't be entirely straightforward.
The problem is figuring out how to write the code that calls the pathing code so that it knows to do lots of path queries at once.
Within an invocation of A*, I don't see how you're going to get any parallelism at all though. You're going through a priority queue one element at a time; you can't get much more sequential than that. With a hierarchy I suppose you could do something, but it wouldn't be entirely straightforward.
could gain lots by pathing in background of queued but not yet chosen jobs...the relevant portion anyway (from material to workshop, say, and leaving the dwarf-to-material until a dwarf takes on the job)Possibly, but unless there's a minimal number/closely packed set of raw material items, what's the probability that the precalculated material-to-workshop path is relevent to the best accessible raw material for whatever worker picks up that task?
Perhaps have a single low-priority thread running searches for pathing optimizations by seeking out areas where an abstract zone may be placed, like a TCZ, SPZ, or anything else that anyone theorizes may help?
To be honest the really simple change of allowing pathing in the 'background' to the main DF thread would improve performance significantly for the majority of players without being a major amount of work. I'd suggest do that first then improve later. (following the "there is always time to improve later" mantra)
this is all fascinating, but I have nothing to contribute.You can just press the "notify" button instead of "reply" and you get updates without having to have a post in the thread. Try that in future.
I'm just posting here so I get updates.
stuff :)I think you misunderstood my post, I wasn't talking about doing any extra/speculative pathfinding, only to 'background' the current pathfinding so it doesn't tie up main game thread. Like you say when a number of new dwarfs enter the map there is no reason for the game to freeze.
You can just press the "notify" button instead of "reply" and you get updates without having to have a post in the thread. Try that in future.
Bidirectional, true. There's a common issue that your two paths may not usefully link up (e.g. the shortest path through a rectangle -- do you first go diagonally, then up, or first up, then diagonally? Making sure both paths meet somewhere is not necessarily easy, but maybe there's tricks.)Within an invocation of A*, I don't see how you're going to get any parallelism at all though. You're going through a priority queue one element at a time; you can't get much more sequential than that. With a hierarchy I suppose you could do something, but it wouldn't be entirely straightforward.
Well, you can go bidirectional at least, right?
I also make stuff fast for a living, and I have to say, parallelizing the solution to one problem is rarely low-hanging fruit. If you can rewrite things to that you need to solve the same problem repeatedly, and you can spawn off a bunch of threads to do it, then it can be pretty easy -- assuming that "rewrite things" is itself easy.
Your idea for a massive speedup is how A* is pretty much always implemented in a "real-time" game, and even in a number of turn-based games.
Bidirectional, true. There's a common issue that your two paths may not usefully link up (e.g. the shortest path through a rectangle -- do you first go diagonally, then up, or first up, then diagonally? Making sure both paths meet somewhere is not necessarily easy, but maybe there's tricks.)
...
There are a couple important things you can do to optimize performance.
1: work less.
2: work smart.
3: do more work at a time.
...
With "new ore" announcements, that is common.Mind that that's like to go away next version.
There is a fourth option in situations such as this:
4: Use ALL of your time.
Most home multi-core systems are around 2 or 4 cores and though a jump to 8 cores is inevitable it's not going to happen for a while. This means your maximum performance gain is around a factor of 4, realistically a factor of 3.
Better algorithms utterly blows that out of the water, improvement can be factors of 10 for an optimized hierarchical pathfinder vs an optimized non-hierarchical approach, all the papers I've read confirm this. Add a cache on top of that and we can probably get another factor of 10 improvement.
Sorry, there'd been talk about such stuff[1], and I misread your post as a continuation of same. :)stuff :)I think you misunderstood my post, I wasn't talking about doing any extra/speculative pathfinding, only to 'background' the current pathfinding so it doesn't tie up main game thread. Like you say when a number of new dwarfs enter the map there is no reason for the game to freeze.
Ok got an automated test suite running, it tests combinations of randomly selected passable points. A bunch of relavent info is written to file (I'll put it on the screen too soon).
UPDATE: 0.23 ;DWhat does this mean?
UPDATE: 0.23 ;DWhat does this mean?
Can I assume that that is blazing "set the atmosphere on fire" fast?
.01 ms...10000 cycles per tile?
What will it do when DF is paused?
It'd probably finish all pathfinding in that particular frame, unless you unpause before that, but a path is only defined for one instance, AND I DO MEAN EXACTLY ONE!What will it do when DF is paused?
Could it keep caching some random point-to-point paths so they can be used when you unpause game? On the other hand it might not be so great idea in DF universe where everything's constantly changing...
I don't know if anyone's tackled this but one of the other major slowdowns on DF is when no path exists it keeps trying to find one anyways. What needs to happen is potentially request future requests for that path for some time before allowing searches again.
I don't know if anyone's tackled this but one of the other major slowdowns on DF is when no path exists it keeps trying to find one anyways. What needs to happen is potentially request future requests for that path for some time before allowing searches again.
The game does prevent repeated requests in most cases -- the ones where it doesn't are bona fide bugs, like these:
# 000184 □ [dwarf mode][creatures] animals locked in a room lag the game heavily from path-finding, additional lag can be caused by assigning them to be butchered
# 000631 □ [dwarf mode][idle behavior] (Report) forbidding pet passage through the door of an enclosure creates lag
It also doesn't do it sometimes for skulkers and possibly siegers? Sometimes the entrance to my fortress temporarily gets impassable due to flooding, and if there's like 3 thieves, the FPS tanks -_-
Which will be needed when flying/(under)swimming pathing goes in.
But that's tiles, not necessarily nodes. There are smarter ways. (Also, average map would be 6x6 or so, which would be 288x288x~60 z on your average mountainside?)
Create a flexible BSD licensed C++ path-finding library specialized for grid based systems like that of Dwarf Fortress and able to efficiently handle rapidly changing map geometry and other challenges such as but not limited too multiple travel domains, multi-tile creatures, variable movement cost terrain and path caching.
If you decide to devote 8 bits for each tile (not for each edge, each tile!) just to determine is this tile passable by movement type x, a 256x256x16 map would require 1MB of memory. If we add ceilings, it goes to 2MB. Note that this is a really small map. A 6x6 I am currently using is 288x288x32, which is 2.5 or 5 MB. Note that this does not include any cost information, and only supports 8 movement types. If you add terrain types or other features then this only gets worse. And, as you said the number of tiles on the map is only going to increase. If you get up to hundreds of z-levels with larger embark sizes, things get nasty very quickly.
shadow_slicer gave a very good summery of the problem back at the end of NovemberIf you decide to devote 8 bits for each tile (not for each edge, each tile!) just to determine is this tile passable by movement type x, a 256x256x16 map would require 1MB of memory. If we add ceilings, it goes to 2MB. Note that this is a really small map. A 6x6 I am currently using is 288x288x32, which is 2.5 or 5 MB. Note that this does not include any cost information, and only supports 8 movement types. If you add terrain types or other features then this only gets worse. And, as you said the number of tiles on the map is only going to increase. If you get up to hundreds of z-levels with larger embark sizes, things get nasty very quickly.
Yes, my point was that this (1) was a lower bound/ conservative estimate for memory usage under that architecture and (2) would not significantly increase pathfinding speed.shadow_slicer gave a very good summery of the problem back at the end of NovemberIf you decide to devote 8 bits for each tile (not for each edge, each tile!) just to determine is this tile passable by movement type x, a 256x256x16 map would require 1MB of memory. If we add ceilings, it goes to 2MB. Note that this is a really small map. A 6x6 I am currently using is 288x288x32, which is 2.5 or 5 MB. Note that this does not include any cost information, and only supports 8 movement types. If you add terrain types or other features then this only gets worse. And, as you said the number of tiles on the map is only going to increase. If you get up to hundreds of z-levels with larger embark sizes, things get nasty very quickly.
This was talked about earlier, but I don't remember the verdict. Is this actually a problem, though? Dwarf Heaven, mentioned on the last page, was apparently 6x6 gridsize, with tile size around 288x288x50, going off the same numbers for 6x6 that shadow_slicer mentioned. That's 4 - 8MB of RAM. That's a pittance. Most computers in use have 1GB of RAM min, and most current computers come with 3-4GB. 8MB of RAM won't be missed, especially if it helps speed up pathing.
Which I think was the main concern. That it wouldn't actually have any improvement. Is that right?
As a sidenote, there was a link, to github I think, with current development. Does anyone have it, and is it actually up-to-date? I'd like to look at the code and pretend I know what I'm doing before the feeling of being in way over my head sinks in. <_<The current code base is part of Khazad, so you can find it on Khazad's sourceforge page (http://sourceforge.net/projects/khazad/).
actually, there is a barrier for data structures where increasing their size will reduce performance. Once a data structure can no longer fit in available cache space, it takes hundreds of cpu cycles to retrieve it from main memory. Its called cache thrashing, and its probably the biggest reason why AMD chips are less powerful than Intel, they just have smaller cache.a) A number of AMDs have less cache than a number of Intels, more like. Unless Intel's chucked all the budget/low-cache systems recently and AMD hasn't bothered with top-end variants, but I haven't cared to check the current situation in detail recently, so I could be wrong and my real comment is:
stuff
I'm not so sure the concept of having an overlay has been discarded. That's kind of the entire point here. It's not clear that quadtrees are the way to go for the hierarchical structure: a twisty windy path with only one entrance and exit would be a lot of nodes in a quadtree, but might conceivably be contracted to a single node using some other partitioning of space.There have been many discussions about different partitioning systems but the biggest problem is the lack of a convenient way for those interested to implement and compare them. Last I head this was being worked on.
Parallelism has indeed been discarded twenty times over, because it's unlikely to be helpful compared to just working hard on the sequential code.Yes and no. Good sequential code will always be useful. Parallelism is also useful to a point. Somethings would work well parallel and some wouldn't. Map preprocessing could probably be made parallel, and reprocessing after a map change may also be doable. Each path if individually treated as a thread might be a workable means of implementing a parallel method with minimal collusion and overhead. However, I am not doing the coding so I can not be sure of the details. Besides those who are doing the coding have said they aren't going to do anything parallel, at least for now.
Is this still being worked on?
Just wondering. I found it rather fascinating, if a bit over my head.
I'm also interested and bumping this. Going to read through the whole thread, but I'm wondering what the status of the project is. Real life definitely takes a toll on these things :-[
I apologize for not having read the thread, but has anyone tried something like ant trails, at least for civilian dwarfs?
I realise that this is not within the scope of this project (as it involves feature implementation by Toady), but in terms of Dwarf Fortress Pathfinding in general, if there was some option for the user to paint a rough route from point A to point B, would this make Pathfinding faster? The "brush" would be several tiles large, to give the system some flexibility. The basic idea would be that there would be far fewer tiles to search through, and even some of the most sub-optimal routes would be acceptable for most players (since they painted them). If the route was sliced in half (say by some deadly magma), it would simply revert to the standard Pathfinding method. Another advantage of this method is that you don't have to calculate total distances with objects many z-levels above. The main disadvantage is of course the lack of automation to this and the fact that you'd still need a much better Pathfinder for situations not involving stockpiles and workshops (or other specific start/end points).
Now I'm sure I'm missing something obvious due to my total lack of competence in this area, but I just thought that it might be worth thinking about (if it hasn't already been thought of).
I realise that this is not within the scope of this project (as it involves feature implementation by Toady), but in terms of Dwarf Fortress Pathfinding in general, if there was some option for the user to paint a rough route from point A to point B, would this make Pathfinding faster? The "brush" would be several tiles large, to give the system some flexibility. The basic idea would be that there would be far fewer tiles to search through, and even some of the most sub-optimal routes would be acceptable for most players (since they painted them). If the route was sliced in half (say by some deadly magma), it would simply revert to the standard Pathfinding method. Another advantage of this method is that you don't have to calculate total distances with objects many z-levels above. The main disadvantage is of course the lack of automation to this and the fact that you'd still need a much better Pathfinder for situations not involving stockpiles and workshops (or other specific start/end points).
Now I'm sure I'm missing something obvious due to my total lack of competence in this area, but I just thought that it might be worth thinking about (if it hasn't already been thought of).
You can already somewhat do this with traffic zoning.
That might lead to some exasperating situations, such as a dwarf entering a burrow with the aim to go through it and into the burrow next door and then to its destination, only to find that the second burrow is forbidden to it. It reverses, and then sees burrow 1 again, turns around and walks through it, leading to what people will soon call burrow dancing.
Create a flexible BSD licensed C++ path-finding library specialized for grid based systems like that of Dwarf Fortress and able to efficiently handle rapidly changing map geometry and other challenges such as but not limited too multiple travel domains, multi-tile creatures, variable movement cost terrain and path caching.
I realise that this is not within the scope of this project (as it involves feature implementation by Toady), but in terms of Dwarf Fortress Pathfinding in general, if there was some option for the user to paint a rough route from point A to point B, would this make Pathfinding faster? The "brush" would be several tiles large, to give the system some flexibility. The basic idea would be that there would be far fewer tiles to search through, and even some of the most sub-optimal routes would be acceptable for most players (since they painted them). If the route was sliced in half (say by some deadly magma), it would simply revert to the standard Pathfinding method. Another advantage of this method is that you don't have to calculate total distances with objects many z-levels above. The main disadvantage is of course the lack of automation to this and the fact that you'd still need a much better Pathfinder for situations not involving stockpiles and workshops (or other specific start/end points).
Now I'm sure I'm missing something obvious due to my total lack of competence in this area, but I just thought that it might be worth thinking about (if it hasn't already been thought of).
You can already somewhat do this with traffic zoning.
The idea will be expanded upon somewhat by the burrows concept. Which will prevent dwarfs from taking jobs etc. outside their assigned burrows thus limiting the destination possibilities. However, pathfinding will not take burrow boundary's into account.
There's a difference in intent here of using less CPU cycles vs. telling dwarves where to walk.
You can already tell your dwarves where to walk, somewhat, but you can't already save CPU cycles by doing manual pathfinding.
There's a difference in intent here of using less CPU cycles vs. telling dwarves where to walk.
You can already tell your dwarves where to walk, somewhat, but you can't already save CPU cycles by doing manual pathfinding.
Actually that is what your doing when you 'tell your dwarves where to walk', the high traffic zones are a lower weighting to normal traffic and so will be searched in preference to other areas. Assuming your traffic zones connect that start and end of the path then the solution is found with fewer steps and so saves CPU cycles.
You could enhance this affect by increasing the weight of 'normal' in the ini file however this will slightly increase the search space in other situations so probably isn't worth it.
*Game cancels run (now paused): Urist McMason needs path to masonry shopSounds like a game genre!
::)
Well, if I understand the pathing system correctly, it tries all least-cost unexplored tiles first(If that tile has, assuming the most optimal path starting at that tile to the destination, the least cost of all other tiles that the pather hasn't explored yet), that using restricted pathing zones where you don't want dwarves going often means that the path must be much longer before it will check that route for a connection, so if it would have taken another route entirely anyway, it will ignore that section for longer, and save cycles.
By putting restricted zoning all over the external areas that dwarves shouldn't access anyway, the pathing would be less likely to spill out into the external areas and flood-fill the map during an attempt to navigate a massive maze.
Of course, if it already does minor pathing on the macro-grid level, such a waste of CPU might be discounted anyway...
██████████████████████
█++++++█θ+█θ+█θ+█++++█
█+y++++█++█++█++█+x++█
█++++++█+██+██+██++++█
█++++++++++++++++++++█
█++++++██████████++++█
██████████████████████
██████████████████████
█111111█11█11█11█1111█
█111111█11█11█11█1111█
█111111█1██1██1██1111█
█11111111111111111111█
█111111██████████1111█
██████████████████████
██████████████████████
█*gfeee█cc█99█66█1112█
█*gfedd█bb█88█55█1012█
█*gfedc█a██7██4██1112█
█*gfedcba987654322222█
█*gfedc██████████3333█
██████████████████████
██████████████████████
█*gfeee█**█**█**█1112█
█*gfedd█**█**█**█1012█
█*gfedc█*██g██d██1112█
█*gfedcba987654322222█
█*gfedc██████████3333█
██████████████████████
A* adds heuristical minimum possible path cost from added tile to goal, which is not necessarily straight-line cost. More effective A*-based algorithms mostly works with other heuristics.
Gosh, this is a long thread. I've skimmed it and reckon I understand where you are at well enough not to be completely irrelevant.
I was thinking of Fuzzy Voroni Diagrams.
PencilinHand has been advocating a hierarchical structure. This makes a lot of sense to me given the size of the problem. I was thinking that you could do this by focusing on landmarks. A subnode would be in the vicinity of the landmark which is easiest to reach. It may also be fuzzily in the vicinity of another landmark if that were nearly as easy to reach. This dual status would help determine the connectedness and distance between two landmarks.
By definition these regions zones would be connected internally, though probably not convex if they form a warren of tunnels. In that case though, the point where paths to the local landmarks diverged should give you a good hint that it was time to find a more specific route.
The blocking and opening of paths would alter which neighbourhood a sub-node was in, but this change would be localised. Similarly the landmark nodes would gain or lose neighbours, but the numbers of connections made and broken would be small.
(So Now I say it) I am not a computer scientist, more like a mathematician. I am more used to dividing problems up so they will be easy for people to think about. I don't know enough about the computer algorithms you are using to know if there is any efficiency gain from this.
I haven't checked through the 35-page thread completely yet, but has anyone thought about just "cheating" it?Almost all of your suggestions would require a level of interactivity with the "non-pathfinding" code that only Toady would be able to do any of it if he ever spun off the pathfinding code from DF. A notable exception, however, is treating every movement model(swimming, flying, lava-passable, invader digging) as a special case, which is inevitable. However, it would almost certainly be an overloaded function or pre-programed "dumb" AI behavior.Spoiler (click to show/hide)
I *still* retain my opinion that a background optimization thread might be a good thing.
First, it can be *paused* at any time without losing the current state/location in the function.
Second, that pause/unpause command could be handled directly by DF itself, so that, for example, if DF hits both the FPS cap and the grapthical FPS cap consistantly, it could activate the pathing optimizer during the delay. Furthermore, DF could let it run when the game is paused.
Also, it's existance could easily be controlled with an external setting.
(Recently finished a 7DRL where the AI was on a second thread from the interface, so you could quit even when it was not your turn, and even if the AI froze.)
If what you are really pushing for is the library to function as an independent thread then that seems possible but likely that the benefits would be negligible most of the time. The processes would run regardless of if DF was paused, locked up, or otherwise limited but there would be some performance overhead associated with it plus some other likely complications.Consider:
I remember doing quasi-threaded pathfinding in Flash. Game is called Garden Raider, and mobs there are moving using A*. If some mob wants a path, it addstask in queue, and wait. Then each frame some pathes are calculated for some limited time. That way sometimes mobs where standing there doing nothing, but that's better than lags, I think.
Not to mention the current lack of multi-tile creatures...Aren't wagons considered creatures? (except the one you embark with)
Not to mention the current lack of multi-tile creatures...Aren't wagons considered creatures? (except the one you embark with)
This is why the fire trick works, indeed. It just does the DePOT-ACCESSIBLE thing for them to determine pathable space, I'm imagining.Not to mention the current lack of multi-tile creatures...Aren't wagons considered creatures? (except the one you embark with)
Yes, traders' wagons are 3x3 creatures, but they really travel around the "heart" of the wagon; you can see this in "D" mode. The starting wagon is treated as a creature in some ways; you can get error messages on some embarks that make this obvious.
What's the fire trick?Yes, traders' wagons are 3x3 creatures, but they really travel around the "heart" of the wagon; you can see this in "D" mode. The starting wagon is treated as a creature in some ways; you can get error messages on some embarks that make this obvious.This is why the fire trick works, indeed. It just does the DePOT-ACCESSIBLE thing for them to determine pathable space, I'm imagining.
3. Pathfinding is one of the slowest parts of DF.
Might have been mentioned before, but in terms of pathfinding performance in DF, pathfinding for invisible creatures applies a HUGE performance hit.
Might have been mentioned before, but in terms of pathfinding performance in DF, pathfinding for invisible creatures applies a HUGE performance hit.
Do we know that? I've not seen anything to show that. Why would a few extra units cause so much more pathfinding because they are invisible than a siege causes?
I agree the game slows down as there are more units (but it does with more rocks too).
Also I'll agree breaking into the fun stuff causes it to slow down as well.
But before we actually try and build all kinds of fun, paralleled processed, highly optimised and specialised super pathfinding system shouldn't we actually run some sort of test?
I did test. All it takes is a door. Close the door, my system runs fine, open the door and it drops down to almost nothing.
Did the same test with a siege which has even more units and the door test produces far less of a change in FPS.
Of course I'm assuming it is because they are invisible. It could just be their red noses and big feet.
I did test. All it takes is a door. Close the door, my system runs fine, open the door and it drops down to almost nothing.
Okay so there should have been little difference other than scope of search space between those two states.Did the same test with a siege which has even more units and the door test produces far less of a change in FPS.
Of course I'm assuming it is because they are invisible. It could just be their red noses and big feet.
However this makes no sense at all :) if it was purely pathfinding a siege should be as bad. Unless the invisible demons where fliers? but even then they should probably be able to path to a dwarf before needing to fly much.
I couldn't find the current algorithm (is there one? Conversation seems to go in circles a lot) but anyway, an observation:Toady has confirmed that the algorithm used in DF is a slight modification of A*. If you are asking about the implementation that Impaler[WrG] and shadow_slicer put together, read this paper (http://webdocs.cs.ualberta.ca/~nathanst/papers/mmabstraction.pdf), this power point (http://webdocs.cs.ualberta.ca/~nathanst/talks/mmabstraction_talk.pdf), this paper (http://webdocs.cs.ualberta.ca/~mmueller/ps/hpastar.pdf), and pages 23 through 26 of this thread.Spoiler (click to show/hide)
That pathfinding is a major source of slowdowns is not an assumption. To test this, make a simple fort and turn weather, economy, temperature, and invaders off, grow the fort to 200 dwarfs then remove all jobs so they are all idle and set a 200+ item stockpile to be moved from one place to another. You will observe a significant difference in the FPS between 200 idle dwarfs and 200 dwarfs hauling things even a short distance, and people have recorded this. I personally did a similar test with assigning 80 dwarfs to stone detailing and ordered a large area smoothed and watched as my FPS dropped from the low 40's to below 20.
The main reason I want to prove that it is pathfinding is that I work with A* on a game with node spaces orders of magnitude larger than in DF and we don't have anything like this slowdown, we don't do quite so many calls but the time per call shows we could easily with a hundred or so units 50 times a second.
Consider that every tile of a liquid under pressure needs to pathfind as well.3. Pathfinding is one of the slowest parts of DF.
Has anyone actually tested this? Because the pathfinding for a hundred or so critters on a map as small as we have should not be such a bottleneck, if it is a problem then simply improving the implementation of the A* used might be all that is needed.
Anything which causes the heuristic to break down by forcing you to move substantially way from your objective to get there causes havoc with A*, as it quickly ends up flood-filling the network. DF is rife with these situations.
Consider that every tile of a liquid under pressure needs to pathfind as well.
Generate zones (areas of limited size which are contiguous for the most limited movement type possible in them - i.e. a normal floor area would be part of a zone where the entire area is contiguous for a creature which can walk but not open doors, an area of water for one which can swim but not open doors, a tile with a door on it for creatures which can walk and open doors, etc) with connectivity links (not specific paths, just info that they zones are connected) to adjacent zones. Generate an initial path on this (comparatively very simple) zone network, and then just generate a path to reach the next adjacent zone as you need it.
If you are asking about the implementation that Impaler[WrG] and shadow_slicer put together, read this paper, this power point, this paper, and pages 23 through 26 of this thread.
Unfortunately we never progressed to the point of zone implementation, currently were at a decent tile-level A* implementation, a test-suite that runs large batches of randomly generated searches and reports time efficiency and a path-following class that serves as the interface between the Path engine and the agent and will navigate for an agent.
tylor: I already have something like that I call it 'interrupt-able' A*. Each search and all of its nodes remain in memory until some kind of completion is reached (a full path or failure) only then are resources freed. The actual node expansion loop is controllable, I can tell it to run for some number of expansions or until completion. At any time I can query the search to get back the best partial-path found so far.Why don't you instead use 'interrupt-able' A* to path from the destination to the current source position (or even the expected source position after N moves)? That way you don't have to request another path if the node went in the wrong direction -- they would just back track a bit. Since the dwarves already appear to do this anyway because of the delay assigning jobs, it probably wouldn't be that noticeable. You could even terminate early if the current source position becomes one of the explored nodes in the shortest path tree that you keep for A*.
But I still need work out having an agent that started moving on that partial path smoothly transition to the final one if it turns out that the initial path was flawed and the agent was sent in the wrong direction, most likely I'd just request another path from scratch.
For those of you not in the know, the overall effect is simply to 'smooth' that 'hang' that occurs when a larger number of agents all start pathing simultaneously. Though their are some potential side benifits, like terminating searches when they grow past a certain length but that get a bit more complex.
The flaw with pathing only from zone to zone is that some arbitrary goal needs to be put in each zone which results in a "choppy" path in which the agent unnecessarily moves to that goal point. My plan is to use a zone tree to both confirm connectivity and to progressively whittle-down a to a series of connected zones which will form a 'corridor' through witch an A* search will be confined. That prevents most wasted node expansions but still gives the optimum path.
No it doesn't, no it's not. If you where getting these problems then either your implementation was broken or the heuristic you picked was flawed. A* is designed to solve exactly this problem, it's what it is good at, it's the one reason you use it.
It just occurred to me, does Kobold Quest use pathfinding in any way similar to DF?
It should be possible to do "group" pathfinding.
If I have 20 dwarves sitting in the meeting area, and the designate 20 stone to be dumped, each dwarf paths to the stone individually.
But if the stones are near each other, in theory the "group" could path to the room, and then split up.
The game already provides a means to set up pathfinding routes. I'm not suggesting that players would be responsible for doing it, just that if an experienced player wanted to drop a reference point out where they do a lot of tree cutting or something, having the capacity to do so wouldn't be a bad thing.It's not unlike dropping a flag, beacon or lighthouse in real life. In fact, I think it would add a little bit of cool realism to have some sort of beacon system but I understand the above point. Some players wouldn't.
Some players wouldn't.
One further benefit to this is that, memory permitting, the game can maintain two (or more) different sets of caches - one for dwarves and one for enemies. Dwarves will know all the shortcuts, but enemies should not, so their cache should be incomplete. Early sieges and squads may bumble about the place, but each encounter will fill in the cache a little more and cause them to act more efficiently. [...]different caches can be in place for gobbos, orcs, etc. so each one can have their own knowledge of your site[...] [saved to disk, etc]
That, because of the way wagons are done, going up a one-thick ramp/wall/magma will put the donkeys through the magma, setting them on fire. But only going up.What's the fire trick?Yes, traders' wagons are 3x3 creatures, but they really travel around the "heart" of the wagon; you can see this in "D" mode. The starting wagon is treated as a creature in some ways; you can get error messages on some embarks that make this obvious.This is why the fire trick works, indeed. It just does the DePOT-ACCESSIBLE thing for them to determine pathable space, I'm imagining.
... Many things have already been discussed and it is just not an easy problem to solve. Significant concessions and game shaping choices may need to be made to really improve the pathfinding.
Knowing one way or the other would require Toady who has indicated he isn't really interested in this, at least currently. ....
With all of the recent talk I feel it is necessary to quote myself:... Many things have already been discussed and it is just not an easy problem to solve. Significant concessions and game shaping choices may need to be made to really improve the pathfinding.
Knowing one way or the other would require Toady who has indicated he isn't really interested in this, at least currently. ....
If you guys want to speculate that is fine with me, I would even be happy to see some code get produced from it. However, anything needing the level of interactivity with the game that is being proposed would require Toady to implement it and maintain it. We should not forget that Toady has said he would like to properly implement climbing and jumping, along with many other pathing algorithm breaking things.
Again, speculation is fine, but keep in mind that we are speculating over minutiae of an incomplete project.
... Many Significant concessions and game shaping choices may need to be made to really improve the pathfinding.
We should not forget that Toady has said he would like to properly implement climbing and jumping, along with many other pathing algorithm breaking things.
movement flags.
movement flags.
Storing that many movement flags per tile would be a huge amount of data, relatively.
movement flags.Storing that many movement flags per tile would be a huge amount of data, relatively.
Movement flags could easily be a bitset, if the unit pathing has the appropriate flags it can use that link if not it can't. Ideally we can link directly to the map anyway. You have to specify some form of system to allow pathing under different conditions. Either that or have a whole node map for each set of movement types, which I imagine would be more space.
Why would you bother? Just get the information from the adjacent tile. You only need connectivity data for a simplified node network (pathing zones, TCZs, reference points) and there would be several orders of magnitude fewer nodes on the path network than there are tiles in the game, so memory wouldn't be an issue.
2. Pathfinding should not affect FPS. Everyone has processor allowance for pathfinding. Followers can transfer their allowance to leader. If something can't find it's path soon enough, let it wait.
Would it be feasible to "stack" units, in the spirit of tile-based strategy games? So, a group would all jump in the same tile as their leader or other assigned pathfinder, path once and all move simultaneously to the destination, then de-stack on arrival?
It doesn't have to though... it's much more realistic to have a dwarf pause for a while than it is to abort fluid simulations. (I'm referring to the frame calculation time.)2. Pathfinding should not affect FPS. Everyone has processor allowance for pathfinding. Followers can transfer their allowance to leader. If something can't find it's path soon enough, let it wait.
Of course it will effect FPS, it uses cycles and you only have so many. Any taken up with pathfinding can not be used for other things. DF is CPU heavy so it's not like we are waiting on the graphics card (unlike most modern games)
It doesn't have to though... it's much more realistic to have a dwarf pause for a while than it is to abort fluid simulations. (I'm referring to the frame calculation time.)
The best you can do is avoid the processing spikes (where it drops a lot for a couple of frames) so it runs at a more constant, but lower overall, FPS.
The best you can do is avoid the processing spikes (where it drops a lot for a couple of frames) so it runs at a more constant, but lower overall, FPS.Which is preferable in 99% of cases.
Have you ever used the "All dwarfs except military are forbidden outside" at all? When you trigger that, lock a major door in your fort or several other things that cause a mass recalculation there's a spike in processing (or in the case of DF, a severe drop in FPS.) If not that, try assigning all dwarfs to military duty once. They will path somewhere and stop. Your FPS will skyrocket. Heck, even in the current build all you have to do is designate an area to be ramped out and you can watch the pathfinding throttle your fortress or forbid/allow collecting stone outside.The best you can do is avoid the processing spikes (where it drops a lot for a couple of frames) so it runs at a more constant, but lower overall, FPS.Which is preferable in 99% of cases.
I agree completely, although with DF I don't get that many spikes myself so I'm not sure how bad this problem is. Spreading the calculations across multiple turns only works if you get spikes of requests. Either way it still effects the frame rates.
What about making use of player-pauses?
In a lot of the post I see people talking about breaking areas down into small subsections and what not. if from there you made just ........ tip of the tongue and it just wont come off here have an example of what I am trying to say, sorry if this is what someone has already suggested and I just did not understand it because of it going over my head or me just missing it becuase I just read this whole thread in a couple hours straight.I have also thought about this, but apply your same logic to a flat open plane. Where you enter each block would determine the shortest path.this is the best I can explain what I am thinking. Most of my programming experience is with vb.net and c# so all the talk about A* is over my head by a bit. Also as a question I am currently learning programming in collage and in my free time, what language should I learn if I want to make games more specifically roguelike games?Spoiler (click to show/hide)
In a lot of the post I see people talking about breaking areas down into small subsections and what not. if from there you made just ........ tip of the tongue and it just wont come off here have an example of what I am trying to say, sorry if this is what someone has already suggested and I just did not understand it because of it going over my head or me just missing it becuase I just read this whole thread in a couple hours straight.The pathfinding code we're currently playing around with already implements such caching. In some cases it does significantly increase pathing speed. The bigger benefit from hierarchical pathing will be in the way it limits the size of the search space (i.e. if you know that B and C are not connected but D is connected to B and C, then you won't try to find a path to c from within B. Instead you should path towards D first). I don't think that part is fully implemented :-\.this is the best I can explain what I am thinking. Most of my programming experience is with vb.net and c# so all the talk about A* is over my head by a bit. Also as a question I am currently learning programming in collage and in my free time, what language should I learn if I want to make games more specifically roguelike games?Spoiler (click to show/hide)
Spoiler (click to show/hide)
...Sounds like a straight-forward breadth-first search, which unfortunately tends to be very slow and consumes a lot more memory.
Sounds like a straight-forward breadth-first search, which unfortunately tends to be very slow and consumes a lot more memory.
Of course, the paths you're suggesting be cached there are extremely trivial to recalculate (probably more so than to look them up). They're strait-line in a 1 tile wide corridor.If games really did always do straight line paths then okay, I just used them to make it easier on me, for instance I could have made the blocks be 100x100 and filled with the most odd and winding corridors you ever did see. also I look back on my idea and have realized that it should have been check that those paths where clear first because if it was not then you would not have already pathed anywhere you did not need to like in my example where you would have already pathed from point a to side of block B and so on when you might end up not even going into block B at all depending.
I figured that any of the precalc could be done during load up like everything else and that the goal was to make the pathfinding faster so I would be fine add a little extra time at start up for faster speed while playing....Sounds like a straight-forward breadth-first search, which unfortunately tends to be very slow and consumes a lot more memory.
The theme for this thread has largely been about how to improve pathfinding performance, with pathfinding quality being secondary, so improving the nearest item search has taken a bit of a back seat. And rightly so, in my opinion. It's a tough nut to crack, but might be easier if general pathfinding is significantly improved. Especially if a lot of useful data gets cached in such a way that it can be used to also make some quick guesses about which items are truly closest. The hierarchical stuff could help with that, for example, by providing very quick upper/lower bounds or estimates of costs from one area (dwarf) to another (potential item to grab). That way, multiple potential items could be scanned quickly, and the ones that obviously involve a long path (despite being physically close) can be skipped over without a large hit to performance.
I'm not sure how practical it is (or if anything like it has been suggested), but it seems to me that the main issue here is the search algorithm for "nearest item" more than the actual pathfinding to the object. It would make sense to improve that first, instead of using the existing "find nearest in terms of sheer physical distance" algorithm. What I came up with for that is a sort of radial trailer pathfinding algorithm. It's directly fractal at the moment and could use some refinement as a result, but I think it's on the right track.This assumes that looking up what item is at which coordinates is a free operation. It's a very expensive one. O(n), where n is the length of the item vector. It could make sense if it was O(log n) or O(1). Not like this.
Basically, it works something like this: for east, north, west, south, up, and down, perform an expanding cone of searches out 1 tile "forward", "up-forward", "down-forward", above, and below (for cardinal directions; up/down it'd get a lot messier since you'd have to do a genuine 9-tile radial search). If an acceptable item is found (or the trailer in that direction is impassible), its location and distance are noted (if there was an item; otherwise, it returns null) and that trailer of the search is cut off. Repeat until all trailers either locate something or null out, then do a comparison to find the genuinely closest object. This would lead to a LOT of trailers, and some noticeable search overlap, but it would also have very thorough coverage. Its main issue (besides the massive number of small checks) would be very odd layouts with lots of corners.
for each item
test if the item is reachable
if(reachable)
if(distance to item < distance to final item)
final item = item
I also believe that the 'reachable' test can be done 'for free', because DF stores information about the connected areas as part of its map (if item and dwarf are in disconnected areas, item is not reachable). This explains the lag from manipulating doors, floodgates and bridges using levers - the connected areas are recalculated.
Most of my programming experience is with vb.net and c# so all the talk about A* is over my head by a bit. Also as a question I am currently learning programming in collage and in my free time, what language should I learn if I want to make games more specifically roguelike games?
thanks Teiwaz!
next question should I learn some C and C++? it seems that many of the examples and stuff that I can find for roguelikes is in them and as I have learned from this thread DF is in C++.
The only problem with Taxicab Geometry with regards to stone distance is that the Z-axis is not as accessibly traversable as the X and Y are.
I'd actually argue that knowing a bit about C before diving into C++ is a great benefit. I'd actually recommend reading about data types, how they use memory and pointers from a C perspective, but from that point, branch into C++, reread how all that works in C++ and you'll start to understand it a little better than going straight to C++. All this will really cost you is a few chapters of reading about C. C++ makes C much more powerful IMHO (and people will disagree) in many ways.This sounds like a good idea. I probably have to take a class of C anyway so nothing lost in doing it anyway.
The only problem with Taxicab Geometry with regards to stone distance is that the Z-axis is not as accessibly traversable as the X and Y are.The Taxicab Geometry can easily be extended to 3 dimensions.
I like how you quoted the reason why it's not good for the third dimension in DF as you posted about how easy it was to extend. It's almost like starting an idea with the perfect point why your idea is flawed :)
(and I'm talking really low level stuff here, like polling the state of the keyboard or figuring out where the mouse is, or playing a sound that isn't a default windows beep, or loading an image into memory and displaying it on the screen).
From a technical standpoint I think the performance issues of dwarf fortress is the greatest limiting factor in the game for the future. I like the idea of a new separately-threaded path-finding routine but all this talk won't go anywhere unless Toady gives some kind of foundation to build an path-finding routine on.
How hard is it to do pathfinding for creatures that are able to dig, or even construct bridges and ladders? For, like, some really resourceful siegers?It needs at least modifications to the base pathing[1], if not parallel pathing trees (as previously discussed) which treat solid earth, bridgable gaps or climbable walls as appropriately high-cost travel routes[2] or limited-accumulation[3] pathway management where it's a matter of resource-based resourcefulness.
A B C D E F
#################
>..++_+++++_+++++_++..>
#+#+###+#+###+#+#
#+#+# #+#+# #+#+#
<arbitrary continuation>
#+#+# #+#+# #+#+#
#+#+# #+++# #+#+#
#+#+# ##### #+#+#
#+#+# #+#+#
#+#+#########+#+#
#++++++___++++#+#
#################
G
Given 'x' amount of bridging ability, the routes from start to finish range from completely non-bridging (down A, back B, down C, back D, down E, back F) to bridging any or all of A_B, C_D and E_F or even going via the triple-length G-bridge, which might need one, two or three bridging elements, depending on how much based on the player's own bridging materials requirements it is, but also might involve a hefty diversion southwards as part of the assesment of routing efficiency.If you can only bridge in straight lines, the second 'air' tile is free, but after that the line is set.As long as no supports exist to allow a new-bridge. (Although maybe weighted preference should be to a few longer bridges (with less dense material needs per distance) zig-zagging around an awkward gap, rather than single/double bridge-tiles being built hugging the wall and taking roughly 1:1 material:distance to do so... Really that needs a picture to explain properly.)
If you can only bridge X tiles, after X, air-tiles are impassable.And in two ways:
The trick is just getting the cost correct.Agreed. Utterly.
If you can only bridge X tiles, after X, air-tiles are impassable.
Finding where to build your bridge is a non-trivial problem.
Finding where to build your bridge is a non-trivial problem.Edit: Just realised you might have meant for the two square task, in which case it's similar but with limited air squares allowed, still fairly trivial.
Edit: Just realised you might have meant for the two square task, in which case it's similar but with limited air squares allowed, still fairly trivial.
Effectively this makes every air square within X from a land square potentially passable and so potentially on the network to path. There is no real complexity here at all as we are already checking cost to square as part of the A* search, we don't care if a square is sometimes passable and sometimes not all we care about is the current cost.
Ah, but if you only save two numbers: shortest distance to here, and least bridge material used, then you have to figure out how to get to that square with the least materials if you need all of the material to get across the gap. A* only stores the shortest path distance to a given location.
A* is wrong in this situation due to memory usage. I would use the Dijkstra Algorithm.
A* is wrong in this situation due to memory usage. I would use the Dijkstra Algorithm.
Congrats, you've successfully been a waste of time :P
QuoteThe trick is just getting the cost correct.Agreed. Utterly.
#############
# xxx #
# x###x #
# x # # x ##########
# x # # xxxxxxxxB #
# A # ##############
#######
#############
# X X #
# ### #
# # # ##########
# # # X B #
# A # ##############
#######
#############
# X#X #
# ### #
# # # ##########
# # # X B #
# A # ## ###########
#### # # #
# #### #
# #
#########
#############
# ☻#X #
# x### #
# x # # ##########
# x # # X B #
# Ax # ##x###########
####x # #x#
# x####x#
# xxxx #
#########
#############
# ☻# #
# ### #
# X # # ##########
# # # X B #
# A # ## ###########
####X # # #
# #### #
# X X #
#########
Posting in epic (dead)thread to be able to find my way back to it later.You could just click on the 'Notify' button at the bottom of the thread to subscribe to it...
You could just click on the 'Notify' button at the bottom of the thread to subscribe to it...
Whatever happened to this project? Is it still ongoing?