Print

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

[nondescuid]

From what I understand, the pathfinding that 200 dwarves have to do accounts for a lot of the performace hit one gets in large forts.

Suggestion: Let the player define routes for the dwarves to take from a point A to a point B. These would work as some kind of 'highways': dwarves who have to travel a longer distance will get to the nearest highway, from there to the point on the 'highway net' which is nearest to their destination, then to their destination.

This is kinda the same way modern car navigation systems work - if you are travelling a long distance, they first get on a highway, so all the other ways from A to B using lots of small roads do not have to be considered.

I don't know if this would work - it might not save much performance if often used routes are already cached or something, but I think this might be a way to combat the FPS hit which occurs in huge forts.

Of course, enemies (and maybe squads on duty) will ignore these, always taking the shortest way possible.

[Fieari]

This is sortof already in.  You can designate low, mid, and high traffic areas.

[FlexibleDogma]

Related things I'd love to see:

Tightly closed doors/forbidden doors treated as walls by path finding.  (Prevents pets from sitting a door trying it over and over again if it's tightly closed).

Always build on square with lowest traffic cost.  This would prevent dwarves from building walls/floodgates/etc that pin them in, assuming you assigned the proper traffic designations.

[Silverionmox]

quote:Originally posted by Fieari:
<STRONG>This is sortof already in.  You can designate low, mid, and high traffic areas.</STRONG>

Yes,  but I wonder: does it decrease the need for calculation or is it just the same pathfinding algorithm with differen numbers?

[Mikademus]

To the OP:

Basically, rather than putting the onus on the player, mature large-scale systems use multi-tiered pathfinding. My guess that pathing takes so much CPU time in DF is because the game only generates and updates one fine-meshed node-map for the entire fortress (or per Z-level). If so, this aspect could be optimised between ten and a thousand times depending on current implementation and design restrictions.

[Sowelu]

quote:Originally posted by Silverionmox:
<STRONG>
Yes,  but I wonder: does it decrease the need for calculation or is it just the same pathfinding algorithm with differen numbers?</STRONG>

Yes, it does decrease the need for calculation--due to the way the algorithm works.  People have noted, for example, that if you mark the only entrance to a small cave "Restricted", and someone wants to pick up a sock from the cave, it will try to search the rest of the map for a better way and slow the game down.  OTOH, if you mark a highway "High Traffic", then it will search along the highway first--and often won't do as much searching anywhere else, if the highway gets where the dwarf wants to go.

However all animals and hostiles ignore your designations, and they are often the biggest source of pathfinding problems.

To summarize:  Good use of high-traffic can speed up your dwarves' pathfinding.  Bad use of low-traffic/restricted can slow down their pathfinding.  It's possible to speed up pathfinding using restricted areas but only if you use them VERY VERY WELL.  But it probably won't matter because ambushers will always be slow anyway.

[numerobis]

quote:Originally posted by Mikademus:
<STRONG>To the OP:

Basically, rather than putting the onus on the player, mature large-scale systems use multi-tiered pathfinding.</STRONG>

Sadly, our fortresses aren't mature.  There are a lot of changes that happen pretty often.  Supporting that with a dynamic search structure is a bit tricky, which is, according to the gamasutra interview, part of the reason that Toady has opted for a slower but less bug-prone strategy of searching from scratch every time (except for the connected components stuff, which you will note has indeed spawned a couple bugs).