Print

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

[darkhog]

We all know that pathing is one of the biggest performance sinks in DF. But what if we wouldn't do path finding, but instead obstacle avoidance and steering (warning, sciency stuff, brain may hurt)?
From my (quite limited but good enough) understanding of it this would cause these things to happen:

- AI entities would behave in more natural way (i.e. could get lost or not necessarily take the most optimal path to the target) which would make them feel more like real people rather than robots.- It has much less performance requirements as the algorithms are simpler than popular pathfinding algorithms (such as A*), which would do wonders for big forts.
- Unless specifically programmed, the AI entities won't know the location of things which would allow invader forces to (literally) get lost if you mask entrance to your fort well enough and leave after a while of not finding it.Of course there are potential problems with that, but I think I have solutions for most of those.


Problem: Urist McChildinthefog lost himself in the fortress and can't get to the building site
Solution: Allow for building a "mental map" of the places the AI agent in question visit most often, then steer towards the closest tile of that map, then replay it (very limited pathfinding that wouldn't be recalculated every tick, only if something unexpected would be in the way, and then it would just navigate around it using obstacle avoidance and record the "new" way for future reference).

Problem: Invaders can't get to the fortress, no matter how many scouts they send and no matter if they successfully find the fortress and return.
Solution: Allow for sharing of "mental maps" of places between creatures. This would also help the migrants learn the layout of the fort from dwarves that were already there. Another interesting thing this would allow would be to follow the scout out of the map and then place traps on the route he took to kill most of the invading forces before they even get to the fortress.Also the algorithms involved are much simpler than any "fullblown" pathfinding and would make units move in more natural manner.

[Putnam]

Alright, problems with this:

We all know that pathing is one of the biggest performance sinks in DF. But what if we wouldn't do path finding, but instead obstacle avoidance and steering (warning, sciency stuff, brain may hurt)?

Immediately what jumps out to me here is that this particular algorithm only works well for trivial, open paths, nothing like dwarf fortress where with stairs, ramps etc. it's often non-trivial to get from A to B.

- AI entities would behave in more natural way (i.e. could get lost or not necessarily take the most optimal path to the target) which would make them feel more like real people rather than robots.- It has much less performance requirements as the algorithms are simpler than popular pathfinding algorithms (such as A*), which would do wonders for big forts.

Sure, optimal paths are very much worth giving up for performance purposes... but there's a point where people will start noticing oddities.

- Unless specifically programmed, the AI entities won't know the location of things which would allow invader forces to (literally) get lost if you mask entrance to your fort well enough and leave after a while of not finding it.Of course there are potential problems with that, but I think I have solutions for most of those.

This is very, very easy to degenerate into "dwarves never know where they're going in any respect", though you seem to realize this.

Problem: Urist McChildinthefog lost himself in the fortress and can't get to the building site
Solution: Allow for building a "mental map" of the places the AI agent in question visit most often, then steer towards the closest tile of that map, then replay it (very limited pathfinding that wouldn't be recalculated every tick, only if something unexpected would be in the way, and then it would just navigate around it using obstacle avoidance and record the "new" way for future reference).

Such a "mental map" is already stored, but on a map-level basis. Only one for every AI agent would mean that this is already using way more memory for less optimal results, and this can still be fooled by plenty of rather non-trivial paths. A*'s main advantage is that it will always find a good path, if one exists, which is absolutely desirable for the purposes of Dwarf Fortress--dwarves getting lost and you don't know why is not what players want.

Problem: Invaders can't get to the fortress, no matter how many scouts they send and no matter if they successfully find the fortress and return.
Solution: Allow for sharing of "mental maps" of places between creatures. This would also help the migrants learn the layout of the fort from dwarves that were already there. Another interesting thing this would allow would be to follow the scout out of the map and then place traps on the route he took to kill most of the invading forces before they even get to the fortress.Also the algorithms involved are much simpler than any "fullblown" pathfinding and would make units move in more natural manner.

Again, this is a massive loss in memory for questionable gains in performance and outright losses in convenience and a full possibility of the game becoming nigh unplayable because dwarves don't know how to get to their bedroom through two separate staircases.

[Pvt. Pirate]

how about using the first method, aslong as it works and the current one only if necessary?

[Shonai_Dweller]

how about using the first method, aslong as it works and the current one only if necessary?

Calculate the path and then decide if it was worth doing?

[darkhog]

how about using the first method, aslong as it works and the current one only if necessary?

Calculate the path and then decide if it was worth doing?

No, calculate the path only if dwarf got lost for way too long.

[Pvt. Pirate]

how about using the first method, aslong as it works and the current one only if necessary?

Calculate the path and then decide if it was worth doing?

No, calculate the path only if dwarf got lost for way too long.

this.
if a dorf found a way, use this way over and over again using the new method.
if the known way is no longer found, after some time of trying, use old method.
would that new method respect traffic zones?

[CyberianK]

Great suggestion. Not so sure if the autonomous move algorithms work great for DF as they can't always guarantee reaching your destination they might actually lead you in circles.
Having "incomplete" pathfinding and validation might only be part of the solution. But once you use it you can do multithreading because you are not fully sync anymore anyway..
I am not a game developer but I am a programmer. If I would have to solve it I would probably roughly do it this way:

• Make static snapshot of level data at time t in memory.
• Hand over pathfinding of objects for origin a to target b to seperate threads
• Give path back to main when finished
• Make new static snapshot when all threads have gone to zero or frame limit l was reached and start over

You'd need some kind of movement validation and if it fails spawn a new pathfinding.

Its probably doable when all dwarfs are able to pass through each other. It becomes insanely more difficult once you have actual colliding, moving objects.
That said if you are able to keep the frame limit l down by scaling up on many cores then maybe only tiny differences happen between real level and snapshot.
Probably hordes of dwarfs moving close to each other or something like a goblin siege massive battle would be brutal. But for prototyping you could try it with disabling collision on all moving objects first.

That said I am way out of my line of work here and you usually encounter all the real problems when you are superdeep in the details so anyone who knows more about pathfinding or how DF works feel free to point out if this is total BS. So I am in no way suggesting this is easy on the contrary just wanted to speculate some
Ideas are cheap actually doing it and solving the myriad of problems coming up is the hard work.

[Pvt. Pirate]

...
Probably hordes of dwarfs moving close to each other or something like a goblin siege massive battle would be brutal.
...

isn't it already?
this would even lead to more of reallife defensive designs to actually work.
i'm thinking of japanese castles which often have/had layouts that are confusing to wrap your head around even if you have full insight and so invaders often didn't know which way to take or wouldn't see that they're running straight into a death-corridor...

[darkhog]

how about using the first method, aslong as it works and the current one only if necessary?

Calculate the path and then decide if it was worth doing?

No, calculate the path only if dwarf got lost for way too long.

this.
if a dorf found a way, use this way over and over again using the new method.
if the known way is no longer found, after some time of trying, use old method.
would that new method respect traffic zones?

I guess it's possible to program traffic zones to be "obstacles" that should be or must be avoided unless there is no other way (depending on the "weight" of particular traffic zone).