Print

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

[elwessweettea]

It _is_ known that dwarves take 1.4 times as long to move diagonally as orthogonally: this was established back when diagonal movement was first permitted, in the first z-version, the one right after 28.

[Saposhiente]

Here's my idea: Every room and stockpile gets an endpoint, and you can place waypoints wherever, and choose how they connect. Each waypoint remembers the shortest path to everything it's connected to, which end points it connects to, and the total distance to them. If a dwarf is already at a waypoint when they start (say, a dwarf at a carpenter's workshop to pathing to the dining room) they can just lookup all the rooms they are connected to, and pick the shortest off the list. If they aren't (say, an interrupted task) or if the node isn't connected to a room of the right type (which is the player's fault) they will path the normal way. The pathings between connected nodes will never be recalculated except when the player refreshes a node explicitly to recalculate everything. You could even have things like one-way connections and nodes over a large area (say, by some important ore just mined out, so it'd behave like a stockpile for pathing except nobody would restock it) This would be memory intensive, but almost all of the processing would happen in pause-time.

[Lord Darkstar]

Dwarves are not ants. (I don't think. If beak dogs can be velociraptors and kobolds can be lizardmen maybe dwarves are pheromone-laying insects. They are kinda hive creatures. Hmm.)

I think of my dwarves as ants. They act the same way. I lay down a scent over something (designate a bulk dump, for instance), and they behave accordingly. If it wasn't for them wearing clothes, reproducing one at a time by individual members, and major tool creation and usage, DF would really be: ANT FORTRESS!

Seriously, they act more like ants than sentient, self-aware creatures. You are just the god brain bug, going around spraying pheramones on things to get them to do stuff. Dump this, dig here, cut this... Ants farm, war, raise and train helper animals and milking animals--- heck, they even do some basic "mega-construction" projects.

When dwarf children start playing with the toys, and dwarves start playing music and singing songs, then I'll start seeing them not so much as ants. But until then, they act likes ants--- that like magma and any booze. 

[Vastin]

I think a breadcrumb system would be particularly amusing to see, and they are v.simple to implement if you already have a traffic weighting system such as DF does.

Only problem in DF is that breadcrumbs would result in a lot of pathing collision, because it encourages dwarves to step on and through each other. If I'm not mistaken, when one dwarf steps on another in DF, the one who gets stepped on is 'stunned' for several frames as a penalty (a much more clever method than forcing them to re-path).

Still, if dwarves do a very quick 1-step look ahead for alternate squares to step on (legal only if the alternate square is still adjacent to their intended path for the NEXT step), then this wouldn't really be a problem. 2-space and 3-space corridors would still grant traffic relief by allowing dwarves to take 1 space deviations to avoid collisions.

Hmm. They might do that now in fact. I'll have to look closely and see if I can tell.

[pokute]

A bit late to the discussion, but I think the main problem here is the lack of tutorials and examples on how to use the pathfinding optimization tools that are already available in DF.  Burrows and traffic areas are absolutely fantastic tools that every player intent on having a high population fortress should know and learn.  I feel this is a much better approach than to build automatic bells and whistles into the pathfinding algorithm that can easily end up restricting large fortress architecture.

That said, I think there's another way players can help with pathfinding optimization by designating the dwarfs themselves instead of labeling the environment.  As we know, a dwarf's world can be a dangerous place, and the little bastards have to be able to react timely or risk death or worse.  But the reality is that not every dwarf needs that level of awareness all the time.  The dwarf who only works inside and especially those safely tucked away in their own burrows can afford to be a little sluggish. 

I feel there should be a way to segregate dwarfs into different levels of awareness.  Those with the highest awareness should use the pathfinding in the main game thread to react deterministically to changing conditions.  Meanwhile, those who can afford to be a bit absent minded can be delegated to secondary pathfinding threads resolving at their own leisure.  This might even be tagged onto the burrows system to define certain burrows as "safe and secure" so that all dwarfs assigned to it use multithreaded pathfinding instead.  It'd be the player's fault that those dwarfs died for the lack of keen awareness.

[Vastin]

I have found one very simple way to easily change the frame rate in my fort. Doors! Sealed ones.

I realized that whenever I started large scale mining operations, my game would soon begin to slow down very noticibly. I had huge grids of tunnels sprawling out beneath my fortress. Like many I blamed all those little rocks, but that wasn't it. Quite simply, it was all the extra squares I was adding to the path finding grid. Different patterns of space have different costs, but rather than worrying so much about arcane pathing patterns, you should be trying to do away with spaces altogether when you aren't using them.

Luckily, DF is very good at compartmentalizing its path finding spaces into separate 'regions' whenever you close off a space with a sealed door or wall. (not sure about un-traversable open space) In fact, you can easily see this by putting a door in some critical spot that cuts off one large chunk from the rest of the map. When you seal this door, you will often actually see the game hitch for a second - I believe this is the path finding system running through the entire space, determining if you just segregated the pathing space into multiple regions.

The moment you do this long range pathing costs for entities in either of the newly created regions drops, and you should see a frame rate increase.

So simply put, don't dig endless warrens throughout the underground and leave them open. When you are done mining in a section, seal it off with walls or doors. When you break into a cavern, wall it off, or create a segregated section to 'live' in the same way you usually do on the surface, with sealed doors closing it off. As long as you do this and keep the main body of your fortress a reasonable size, you will be able to manage your frame rates.

Spoiler (click to show/hide)

As a note, I think this is why breaching the FHS reportedly massacres path finding so badly. Not only are there many smurfs, but they are generally flying/building-destroying smurfs who impolitely ignore most path restrictions and calculate their way using the ENTIRE path grid regardless of how it is broken up (including all those empty air tiles in the caverns...)

[pokute]

I have found one very simple way to easily change the frame rate in my fort. Doors! Sealed ones.

I actually wall-off areas that I don't use.  No doors, just walls.  If, god-forbid, my dwarfs REALLY need something from there, I'll just knock the wall down long enough to allow access before sealing it back up.  It works better than doors, IMO, since you can tell if the place is sealed just by looking at the map.  Plus, forgotten beasts won't make any unexpected shortcuts around your defenses this way.

My central shaft usually looks like this:

Code: [Select]

WWWWW
WXXXW
WXXXMW
WXXXW
WWWWW
W = wall
X = stairs
M = the wall you deconstruct and rebuild so that your dwarf always end up on the correct side

[LuckyLuigi]

Walls are better than doors as non-dwarves will still path trough doors (at least in 3.12)

Moving away from the target destination is very high cost.
                                                                            XXXXXXXXXXXXXXX
F                                                                           X D
                                                                             XXXXXXXXXXXXXX

X = Wall
F = Food
D = Dwarf

It's very likely your dwarf will starve to death instead of going around the wall (which also implies there's a maximum of pathing cost that the alogorithm will calculate before stopping, i.e. will not 'path' the whole map).
So you want straight highways and no twisting corridors. Make everything accessible, but do not make 4 openings for every room (this is where I went wrong). Instead work on a good highway system and use the traffic designation.

Still, flowing water is more of a FPS killer than any number of dwarves. Try to minimize spills !

Final note : There is something strange about z-path cost calculation. Not sure what exactly. I'm building a vertically layed out fort and regretting it already. My dwarves are having real trouble. They 'freeze up' a lot. Usually in odd locations, like at the right place but at the wrong z-level.
Might also be that the surface is near but my exit tunnel is very very long. So they plan to pick something up from the surface as it's 'close' then can't even find a route as the path is too long. Or maybe something totally different. Who knows ?
It seems certain to me that the target is chosen in a direct line 'as the crow flies' and then a path is made to that target and it's discovered it's 5000 tiles away.

[WrathNail]

This thread's a pretty good read. I'll keep this stuff in mind when I start my next fortress.