Print

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

[tps12]

DF isn't using Manhattan distance.

It is using Max(|x1-x2|,|y1-y2|,|z1-z2|).

If it was using Manhattan then a mason workshop making blocks in a quarry would clear out a diamond-shaped area. Now it clears a square/cube area.

The algorithm used to decide which input item to use for a reaction is different than the algorithm used as the heuristic in A*.

[Coaldiamond]

Lets switch tracks for a minute.

I was about to ask Toady this one directly, since I can't find a direct answer in my forum searches. Maybe the B12 forum can deliver?

Question: Has Toady ever mentioned taking the principle of stigmergy from the ACO scheme in order to dynamically modify the PATH_COST value for tiles as dwarves travel over those tiles? My thought is that since we can already improve framerate by manually designating High Traffic Areas, perhaps inserting some code to dynamically modify High Traffic areas as the dwarves are travelling would provide the same benefit while keeping the same A* algorithm in place.

So how about that? Have I missed Toady's prior comments on this very topic?

[Sheepherder]

I just tried this out with a community fort from the forums. I turned off all labors except stonecrafting and built enough workshops for everyone, then paused and put repeat rock craft jobs in each one. Then I duped the save and started up two copies of the game and assigned each to its own core. I used Dwarf Therapist to disable all labors in one game, then unpaused both.

The L2 and L3 cache are shared resources.  If it's being fully utilized the operating system will prioritize.  Also, which core was Dwarf Therapist running on?

[tps12]

I only assigned affinities to the two game processes, so I guess Therapist was just running wherever, although it wasn't doing anything once I wrote the changes so I doubt it would matter.

Not sure I understand the cache point; both processes' cores were pegged.

In any case, if you can run a better experiment then please do, but for the moment I don't think there's evidence that the "look for materials to use in a job" routine represents any kind of persistent drain on performance relative to everything else.

[ZioAnthros]

Although i am unable to offer technical assistance at this time, i would like to suggest something i would really like to see in the end game.
Creatures should be aware of locked doors and drawbridges in such a way that when no path exists, they linger around the door/bridge/obstacle and wait for it to open, maybe only occasionally looking for an alternative.

[Uristocrat]

Not sure I understand the cache point; both processes' cores were pegged.

I think he's saying that both CPU cores share the same L2 and L3 cache memory.  That is, that each core does not have its own, so running something else on one core can make it unavailable even when DF is being run on the other core.

[tps12]

Ah, interesting to know.

[Granite26]

IMHO, the best way to 'fix' pathfinding is to reduce the calls for it.  Right now, dwarves spend a miniscule amount of their time doing anything.  Make every task (eating, sleeping, cooking, smithing, crafting, etc) take more time and you'll see a game speed increase.  200 dwarves (+200 dom. animals) hurt when they are all pathing at once, but not so much when only 1/3 or less are trying to get someplace at a given time.

Obviously some rejiggering would be necessary for balance, but not too much

[Thizda]

How about static node generation with Worldgen? Then generate the dynamic nodes, like creatures or levers, nearby.

[PartyBear]

What about player-created paths?  Not traffic designations, but set point A to point B paths that creatures can incorporate into their calculated paths.  Only the player actually understands his or her fort's layout well enough to optimize pathfinding within it.  Or optimize it for aesthetics so they'll actually use the nice paved roads, or if the player wants the manic little beard transports to be sure to wander past all the nice calming statuary.

[NW_Kohaku]

What about player-created paths?  Not traffic designations, but set point A to point B paths that creatures can incorporate into their calculated paths.  Only the player actually understands his or her fort's layout well enough to optimize pathfinding within it.  Or optimize it for aesthetics so they'll actually use the nice paved roads, or if the player wants the manic little beard transports to be sure to wander past all the nice calming statuary.

I thought that was the point of traffic designations?  How would you go about doing that without traffic designations?

[Draco18s]

You still have to figure out which "waypoint" is nearest to both the dwarf and the destination, which is an NP-hard problem.

[PartyBear]

I thought that was the point of traffic designations?  How would you go about doing that without traffic designations?

It's the difference between driving a car and riding a train, basically.  You can only get on or off the train at stations, but you don't have to think much about the part of your route that goes on the train.

You still have to figure out which "waypoint" is nearest to both the dwarf and the destination, which is an NP-hard problem.

My thinking is that you don't search for an existing defined path intentionally, but use them when you stumble across them during regular pathfinding.  Going by the wiki's Path article, a path is calculated by checking every tile around a creature for both the cost to reach it and how far it is from the destination, then picking the best of those and doing the same for the tiles surrounding them.  If this just happens to lead to a well placed player-created path endpoint, probably with the aid of traffic designations, then the (sole, if it wasn't clear) other endpoint of that player-created path is considered as well.

[Crashmaster]

Would it be possible for dwarves to path make as well as path find? Similar to ants; when a dwarf takes a path to a stockpile or building he leaves an invisible (directional) trail terminating at that building and managed by the building. For the next path finding event to that building the AI would search for the building or for any trail to it. If it finds part of a trail first it would not need to expand it's path finding search any farther and could just follow the same path it decided on last time re-calculating only for obstacles. The route this dwarf took would then be tagged onto the end of the previously determined trail.

A maximum diameter from the building for the trails and having it take a number of trips on any route to lay a working trail would be required to prevent working dwarves from painting 1-tile wide route maps to each building from all locations on the map.

This would cause some potential for inefficiency in travel distances in open spaces due to not always going straight for the target.

'q'ing a building or stockpile would let you see all paths related to the building and delete or drag routes or manually make them.

[Granite26]

I like optimizing for rooms.  Every area surrounded by doors is a room, node map concentrates on room connectivity, pathfinding is just to the next room.  (each room contains traverse costs). 
Recalc your zones when digging, but only the affected ones.  Same with new doors