Print

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

[Fieari]

As well all know, DF's connectivity map works great for walkin dwarves, but not so great for flying or amphibious creatures.  This is because of the Connectivity Map, which determines whether the A* pathfinding system should be run at all.  If the spot can't be walked to, the game assumes it can't be reached, even if it could be reached via flying.

This problem gets worse the more movement types you have, such as tunneling, or climbing.  Because you'd not only have to make a connectivity map for each movement type, but also for each COMBINATION of movement types, which is the harsh part.

I'm not sure if Toady has considered methods by which multiple movement types could be implemented, but here's one.  It would likely require a couple days of coding, and more days optimizing, but it's a method, and I'd like to see what people think.

Assume we have 8 different movement types requiring continuous movement (thus, removing teleportation).  We don't have eight right now, but maybe one day.  Let's say Walking, Swimming, Magma Swimming, Flying, Climbing, Jumping, Tunneling, and Demolishing.  Eight is convenient because it's one byte.  We can add more bytes too, for example "Trap Avoid" or some such.

Step one utilizes the current system for making connectivity types, except this time we do it 8 times, a linear increase in processor requirement, so we're pretty safe.  Each tile is thus flagged with a number like 10011100, which means that if you can walk, fly, climb(aka crawl), or jump, you can move through the square.

Then, the game must find all adjacent numbers, that is, all adjacent tiles with 10011100, and mark that as one continuous region.  From this region, create a nodal graph of the map.  This must be done once every time the map changes-- otherwise, you just need to keep the same map.  Remember, this is a linear increase in processor time, so it's expandable.

Now, for connectivity checking, first the game sees whether you are within the same exact region, just like now.  If not, however, it then checks to see if there is a path utilizing all your movement types.  If each character is assigned a byte determining how they can move... such as 11000001 (for a troll perhaps), just do a Logical AND with each node of the connectivity map, then use a flood fill technique to see if it is possible to get to point A to point B.  After that, A* to your heart's content.

Here's an example.

Aribtrary Map:

01101100 10110011 11111110
11010100 11100111 00110110
00111011 10101010 01010101

Our creature's movement: 01001000

AND map:

01001000 00000000 01001000
01000000 01000000 00000000
00001000 00001000 01000000

Truth map:

101
110
111

And there's our connectivity map!

EDIT: If this is too slow, you could even cache such a map for each movement type possessed by a creature on the map.

[Karadan]

If a creature can fly, why would it need to check for the ability to walk anywhere?  If a creature can swim and walk, why not just set it so that it counts water and land tiles the same way?  You really don't need to check for multiple 'movement styles' you just need the movement style to adjust what tiles are and aren't considered as accessible.

It shouldn't take too much effort to be honest (Based on how things are set up) to simply have creatures with flying movement treat certain tiles as everything else treats normal tiles.  For example, a flying creature could treat open space tiles as all up/down stairs.  A creature that can break walls with some effort would consider walls to simply be restricted areas.  A creature that can swim just treats water tiles like dwarves treat land tiles and so on and so forth.

Not exceedingly hard, Toady just has about 1000000000000000.....0000 other things he is working on.

[Fieari]

It doesn't necessarily need to check for walking.  It might need to check for swimming though, if you consider a completely flooded underground passageway.  It might need to check for digging, if it can fly and dig.  It might need to check for destroyable areas.  Better to have a system that can have all that, with a linear increase in computation time.

[Karadan]

It doesn't necessarily need to check for walking.  It might need to check for swimming though, if you consider a completely flooded underground passageway.  It might need to check for digging, if it can fly and dig.  It might need to check for destroyable areas.  Better to have a system that can have all that, with a linear increase in computation time.

My point though is why does it need to run a separate check for swimming?  Why can't all tiles have different movement values for each movement type (Exactly like traffic can already do for a single movement type) and run.

A flooded chamber would have a movement value of 0 for walking creatures and flying creatures, but a value of 1 for swimming creatures.  A wall would have a value of 0 for everything except digging creatures which could have a 10 or something.  Then the game just has to run a normal pathfinding.  If a creature has multiple movement types, then it just takes the best value for each tile.

[Fieari]

I don't think you understand how the system works.  A* is the most efficient known hueristic for pathfinding in existence-- assuming that it is even POSSIBLE to get from point A to point B.  If there is no possible way to get there, A* will try EVERY COMBINATION OF MOVEMENT POSSIBLE before giving up.  For a map the size of a DF map, this will finish sometime after the heat death of the universe.

So what you do is first check to see if it's POSSIBLE to get from point A to point B, and then use A* -after- it's proven possible.  Proving the possibility of getting to point A to point B can either be done by never blocking off a map, such as most games do, or by making "connectivity maps", which is required for anything dynamic.  Connectivity maps are fast to calculate, but don't find the best route to travel.  That's why a combination of A* and floodfill is used.

The problem is that with multiple movement types, you'd need a seperate connectivity map.  The connectivity map for a giant eagle is different for that of a dwarf... using flight, the eagle can get places the dwarf can't.  But DF doesn't distinguish: if you can't walk there, it thinks you can't GET there.  The A* is fine, it WILL find the best way of getting there... but only if the connectivity map says that it's worth trying first.

That's what my suggestion is about.  It's about asking the question "Should we run A*" and making it apply to more than just walking.  Because it doesn't, right now.

[Footkerchief]

Because you'd not only have to make a connectivity map for each movement type, but also for each COMBINATION of movement types, which is the harsh part.

I don't see why you'd have to do that.  If you have a connectivity map for each movement type, a creature checking whether it's eligible for an A* attempt should just have to check if any one of its component numbers match up with the destination component numbers.

Step one utilizes the current system for making connectivity types, except this time we do it 8 times, a linear increase in processor requirement, so we're pretty safe.

Toady wasn't keen on calculating it twice, much less eight times.

Having an additional connectivity map was the first thing I considered, but it's too calculation intensive.  Repairing the connectivity map is one of the slower calculations in the game, and nearly doubling (or more if you allow creatures beyond 2x2s) the number of calculations would be bad.  It doesn't use some kind of path network and I haven't seen a feasible way to store such a thing, especially in the 3D grid, and fluids are also an issue there.  I'm also not eager to add a few more bytes to map storage, though that's a lesser problem.  And I'm not sold on the idea in general, since the overarching sentiment of giving tiles explicit sizes opens up a host of additional issues for very little gain in my opinion, relative to time spent on other tasks.

Then, the game must find all adjacent numbers, that is, all adjacent tiles with 10011100, and mark that as one continuous region. 

Adjacency isn't enough -- you could have two walkable floor tiles, one above the other, but you still wouldn't be able to walk between them.  Also, what does it mean to "mark them as one continuous region"?  Just to place a component number in each map tile, as currently?

Now, for connectivity checking, first the game sees whether you are within the same exact region, just like now.  If not, however, it then checks to see if there is a path utilizing all your movement types.  If each character is assigned a byte determining how they can move... such as 11000001 (for a troll perhaps), just do a Logical AND with each node of the connectivity map, then use a flood fill technique to see if it is possible to get to point A to point B.  After that, A* to your heart's content.

Again, the troll should be able to move through any tile that supports any ONE of his movement types -- it shouldn't have to match ALL of them.

[Fieari]

I don't see why you'd have to do that.  If you have a connectivity map for each movement type, a creature checking whether it's eligible for an A* attempt should just have to check if any one of its component numbers match up with the destination component numbers.

That's actually what I'm doing.  Consider the case where you calculate a connectivity map where you have a D&D black dragon, with his lair requiring you to fly and swim through a swamp to get in.  The destination is in a fly zone, but it is seperated by a swim zone.  For the dragon, it is connected.  For someone who can fly, he can't.  For someone who can't swim, he can't.  Each of these people have a different connectivity.

Toady wasn't keen on calculating it twice, much less eight times.

I may have described it wrong.  Rethinking it, I don't even think it needs eight passes. Currently, the game checks every tile for walkability, floodfilling a zone.  What I want it to do now is check each tile for ALL it's movement types, not just walking, and floodfill a zone.

After floodfilling, I then want to export a nodal graph, which is what would make this system work.  Now, the nodal graph may take more time, esspecially with flows as mentioned, but I don't think it'd double the processing time.  I'm pretty sure there are optimizations that can be done to the code here.

Adjacency isn't enough -- you could have two walkable floor tiles, one above the other, but you still wouldn't be able to walk between them.  Also, what does it mean to "mark them as one continuous region"?  Just to place a component number in each map tile, as currently?

Adjacency IS enough, because we're marking different movement types.  I would include the "hidden floor level" as part of the calculation.  The floor would require digging to get through, and then flight, not walking.

Marking them as a continuous region doesn't involve marking the map tile.  It involves creating a new, seperate, nodal graph.  Take the following map:

11111122
11112222
11111332
11111322
44111111

This would be translated into:

1 connects to 2, 3, and 4.
2 connects to 1, and 3.
3 connects to 1, and 2.
4 connects to 1.

Except the 1, 2, 3, and 4, are instead our movement flag number. 10110001 = 177, for instance.

Again, the troll should be able to move through any tile that supports any ONE of his movement types -- it shouldn't have to match ALL of them.

That's what the logical AND does.  The map tile allows creatures that can fly or climb, but not walk, "110".  Our creature can climb or walk, but not fly, "011".  110 & 011 = 010, which is non-zero ("truth value").

Anything that has a non-zero value after the logical and would form one great big map-- for that creature only.

[zchris13]

This seems slightly less dubious than the normal suggestions.  You appear to know your stuff. Congratulations.

[irmo]

If a creature can fly, why would it need to check for the ability to walk anywhere?

It still can't fly to places that are completely enclosed.

If a creature can swim and walk, why not just set it so that it counts water and land tiles the same way?

Because of the way the connectivity map works. It doesn't use path costs; it just looks at what's reachable and what's not. Generating the map is expensive and so it's done once for everyone.

[Sowelu]

I'm liking this.

[Impaler[WrG]]

Indeed Fieari knows his stuff, I think you might be able to get still more efficiency by considering how certain movement classes are super-sets of others.  For example Flying can pass through all places that could be walked, A creature that can Dig through Rock should also be able to dig through soil.   Perhaps making certain assumptions about sub-set/super-set travel class allow the speeding up of the assignment or comparison?

[Footkerchief]

That's actually what I'm doing.  Consider the case where you calculate a connectivity map where you have a D&D black dragon, with his lair requiring you to fly and swim through a swamp to get in.  The destination is in a fly zone, but it is seperated by a swim zone.  For the dragon, it is connected.  For someone who can fly, he can't.  For someone who can't swim, he can't.  Each of these people have a different connectivity.

Oh, yeah, you're right.

Adjacency IS enough, because we're marking different movement types.  I would include the "hidden floor level" as part of the calculation.  The floor would require digging to get through, and then flight, not walking.

I'm still not sure exactly what you mean.  Are you saying the pseudo-tile "floors" that exist between Z-levels would be treated as real tiles for purposes of "adjacency"?

Take the following map:

11111122
11112222
11111332
11111322
44111111

This would be translated into:

1 connects to 2, 3, and 4.
2 connects to 1, and 3.
3 connects to 1, and 2.
4 connects to 1.

Except the 1, 2, 3, and 4, are instead our movement flag number. 10110001 = 177, for instance.

That last line threw me for a loop -- you're not saying that all areas with 10110001 would be considered the same node, are you?  I doubt you mean that, but I don't see the significance of saying "Oh, this is another 177 node, not node #2" when the node is still unique.

Anyway, yeah, overall this seems pretty clever.

[Fieari]

I'm still not sure exactly what you mean.  Are you saying the pseudo-tile "floors" that exist between Z-levels would be treated as real tiles for purposes of "adjacency"?

They'd have to be, since the game considers them, even if we can't set our view to the half level.

That last line threw me for a loop -- you're not saying that all areas with 10110001 would be considered the same node, are you?  I doubt you mean that, but I don't see the significance of saying "Oh, this is another 177 node, not node #2" when the node is still unique.

No, you're right.  A unique identifier would be more useful.

[Siquo]

The idea is good, but recalculating could be heavy, and might be necessary too often. Especially with fluids, every tile that's switching between 3/4 (or was it 4/5?) switches between swim/walk, and I see a lot of 3/4 switching in my pond.

[Fieari]

Hm.  What might help frame rate would be to floodfill the zones as now.  When pathfinding is requested, if you're in the same zone, it will assume you have the right movement type and let you get there.  If you're not in the same zone, then and only then do the full graphed calculation (and cache it).  So you'd still get slowdown if there was a lot of calculation trying to get to the other side of a dry riverbed that is now flooding, but if your dwarves were staying on one side of the change, or if not a lot of changes are happening at once, it'd be the same speed as now.

Alternatively, you could have some code ensuring that things are not recalculated every frame, and rely on cancellations in cases of severe map changes.

EDIT: In order to make this work, you'd have to save a copy of the old map every so often, and do pathfinding on it.  This would increase RAM requirements, but would significantly improve speed at the cost of occasional pathfinding accuracy.  Maybe you could even add some multithreading here...