Print

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

[shadow_slicer]

If you're designing a pathfinding library, why not just keep it generic?

Use a bitmask to denote some required capability or cost class modifier (if capability then cost is infinite) to pass through this tile. Then the library doesn't have to worry at all about what all of it really means. This also would make it trivial to add additional classes if they turn out to be needed.

Code: [Select]

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


[Slogo]

Isn't that what we've been talking about? We just put it in context because it makes it easier to understand and to understand if we've satisfied all of the requirements.

I'd imagine that all of our tile 'types' and 'subtypes' (if we go that route) would be user configurable so they could add in or remove whatever they want. Some of the... fancier... things to do with the pathing data (like stop to destroy a building) are beyond the scope of path finding, we just need to make sure we can support it.

[Impaler[WrG]]

I think both terrain and creatures will need to be represented as a bit field that corresponds to a set of 'raw' movement types.  That allows multiple combination like the way that flying would be valid in all walkable  and climbable tiles.  A simple & between the creature and tile would then suffice to determine if a creature can move through a tile (along with volumetric checks on multi-tile creatures of course).

In any even the engine doesn't really need to worry about the nature of movement types other then to know how many bits are needed.  It might be a nice idea to have this be flexible in some way so data storage is as efficient as possible.  An option (perhaps a compiler time option) for either an 8 or 16 bit field to hold the movement types would be nice.

The far more interesting challenge is going to be maintaining the zone hierarchy and high level connectivity map along side all this movement type data.

[Sunken]

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.

[Exponent]

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.

Just want to point out one reason why something like A* should be the minimum in digging scenarios, rather than the far more simplistic idea of naïvely making a straight/staggered line:  Things like open spaces (such as chasms/pits) or liquids would require pathing around, even for a digger, unless the digger is also a flier or swimmer.  And in the future, various densities of materials might be used, such that some diggers can only dig through dirt or soft stone, and not harder stones.

[Fieari]

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.

I wouldn't want to use Building Destroyer 1 and 2 though.  I'd much prefer to use the new attack physics and just have the movement tag there to specify that a creature will TRY to break through stuff that's been built.  The COST of movement can be calculated by the material of the object.  I think this should be kept seperate from those who dig through natural materials, because I'm thinking about the way army seiges should work.  Some unit types should try to bash through walls, while different ones dig under.

[chmod]

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

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.

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.

[Sunken]

Are you talking about learning a specific map, or do you want to apply the learned information more generally?

[Sunken]

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

I'm sure what we've been talking about could be tailored to deal with this. For example, each TCZ (or convex or rectangular zone) can have a cache containing its stored items. A* would simply search until the topmost open node is any node in a TCZ with the desired items in it, instead of one with the desired goal tile in it.
So it's not a huge conundrum; We'd just do well to have this in the back of our minds.

[Impaler[WrG]]

I think a learning system should be thrown in, and I'd be happy to contribute.

I'd love too but I'm afraid of encoring the wrath of the fans of your Dwarf Therapist tool if I pull you away from that wonderful tool. (jk)  We have Puzzlemaker and Slogo working on the initial implementation and if anyone else wants to get SVN access talk to them, they will send referrals to me for who should be given access.

[Shades]

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.

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.

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

Agreed, it's trivial to write tests that take this into consideration (find me the path to the nearest stone rather than the path to square X) so we might as well. The A* heuristic for this is simple as well although other algorithms might be more complex.

[Kardos]

There are a few things to keep in mind for a project such as this.
1: Any Pathfinding system will need to work on a 16x16 embark area and or an area with extreme z-level variances withen the constraints of CPU and memory usage.  Keep in mind that even if someone has 8GB of ram, DF might not neccesarily be built to use more then 1GB.

2: Allowing the system to utilize various pathfinding algorithms should be encouraged.  What might work well outdoors might work poorly withen the fortres or in the water.  This of course means that the various pathfinding algorithims might need some sort of interation for the purpose of creatures tracking other creatures.

3: Even if an algorithm works on a 2-d level, it has to be able to interact on a 3-d scheme to avoid the cube mechanics currently utilized in DF (climbing 30 z-levels for a piece of stone on a path thats several hundred tiles long when there's another perfectly acceptable piece 31 tiles away on the x/y plane.)

4: Movement types that aren't common now shouldn't be disregarded or thought of as trivial.  With progressieve releases, flying, swimming and multi-tile creatures (and objects) will be become more and more common.  Any system thats developed should be able to absorb and integrate these types into the pathfinding without massive changes to the code.

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

[qwertyuiopas]

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.

I can tell you that you want at LEAST an unsigned byte for each tile, partly because each access of a bit would take a few more precious CPU cycles, and then multiply that by the potential millions per second. It doesn't add much, but preformance is essential. Also, by using a full byte, you add support for conditional blockage at a future date(8 bits per tile).

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.

30 megs is nothing these days. If it doubled the speed, 100 megs would mean nothing.
Storage space is not important. Speed is. 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.

[Shades]

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.

std::bitset is not a bit, its a very very fast way of allowing array concept flags for boolean values. Also any structure that supports the array operators could replace it with zero other code changes, so if we found an array of bytes was enough faster to warrant the memory it's easy to do.

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'd class this as premature optermisation which is always a mistake, once we have something working then if it's a problem it's easy to refactor away classes and remove any overhead. Compilers are pretty good at avoiding such things these days anyway though, and personally I'd rather work with the features than without because I'm lazy.

(And lazy people are efficient and being inefficient takes more effort)

[Draco18s]

It should be coded in C++ because DF is coded in C++.