Print

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

[LordDemon]

A quick pathing improvement suggestion, for those jobs that require dwarf to take some (undefined thing) to work location. (examples include Making food, brewing, loading cage/stonefall trap, many of the workshop orders.)

As of now, the dwarf get's a job (say, forge an steel helm). Dwarf looks for the closest steel bar, moves there, picks it up, hauls it to the workshop, and starts to work.

There is a small isuue with this: if the closest bar is away from the job location, this may be slower.
Ideally it works like this:

[Dwarf]..............[item].....................[workplace]

So the dwarf takes the item on while on the way to work. However, if the situation is like this:

[item]..........[dwarf]........................[item]...[workplace]

The dwarf will move to closest item, going in this case the wrong direction, before returning to work. This won't matter when you have defined item to use (the single "+<<+obsidian door +>>+" for example) since there is only one item, but with general items (steel bars, empty barrels, cookable items for food), there are multiple instances, and one might be closer to other end.

So, to simplily the work, the pathing should path
1) Dwarf to (item closest to dwarf), item to work
2) Dwarf to (item closest to work), item to work
It already does the first. Comparing the distance to the second would enable the dwarf to take the sorter route.

It would also make it so, that when your dwarf hauls the item right next to workplace before deciding to take a few week nap, the next dwarf would then decide to take that item (it is closest to workplace), and carry it to the work, instead of going to the other end of fortress to haul another item, and leave the first one to someone else to return.




 

[Bauglir]

-snip-

[Impaler[WrG]]

Their are no path-finding improvements as far as I know in the upcoming version.

Being able to specify a 'take from stockpile' for a workshop would mostly eliminates the need for the a map-wide search to be conducted in the first place, a dwarf would path to the the stockpile, pick up an item and path to the workshop without needing to compare any distances.  Of course the player might specify more then one 'take from stockpile' or their might be some of the desired item very near the workshop which should be used in preference to the stockpile so the situation you describe will still arise.

Essentially its a combination of two paths, a binary path.  The first by flood-fill (Dijikstra) out from the Dwarf to a desired item then from said item to a known final destination.  Your idea would indeed find a lot of paths better then the ones currently used but its not fully optimized.  The 'best' item to take might be one which is neither closest to the dwarf nor the workshop.  To fully optimized you'd need to run Dijikstra outward until the heuristic estimate for reaching the final destination from the fringe exceeds the best complete path so far found, using a bidirectional search (running with the dwarf and workshop reversed) is a good idea with Dijikstra algorithm because of its inefficiency.

[LordDemon]

Your idea would indeed find a lot of paths better then the ones currently used but its not fully optimized.  The 'best' item to take might be one which is neither closest to the dwarf nor the workshop. 

True, but this would give very nice boost for limited increase of processing IMO.

 

[The Architect]

Items already choose dwarves (according to what everyone more knowledgable than myself is saying on the forums). I like the idea of being able to designate a stockpile for a shop, and having it only use materials from that stockpile. The job should be suspended if the stockpile doesn't have the proper items available. We don't know how all of this will work in the new burrows system.

It'd be nice, but pathfinding is the prime cause of FPS hits right now. If the next version has much improved pathfinding, though, it might be ok.

From actual tests performed on the causes of lag, pathing isn't the prime hit to game speed. That was an outdated assumption that has been disproven.

Their are no path-finding improvements as far as I know in the upcoming version.

Toady has vaguely mentioned "performance improvements" in the new version, which may or may not include pathing improvements.

[tsen]

What *is* the big processing hit then? I'm not contradicting you, I am just curious.

[JanusTwoface]

What *is* the big processing hit then? I'm not contradicting you, I am just curious.

As far as I've read (mostly in the Stonesense thread and a few others), one of the main issues with lag is the item vector that keeps track of basically every item in the game.  Pathing is also a problem, but that's to be expected.

[HatfieldCW]

This is the main issue with the game's playability, as far as I'm concerned.  A big breakthrough in pathfinding would mean a great deal to me.  I get the feeling that a successful improvement will lead to less logical dwarf activities, like one dwarf walking around collecting silk goblin clothes for a few days before dropping them all off in a stockpile, or a worker taking time out from his gem cutting to get all OCD on the stockpile.

[Talanic]

What *is* the big processing hit then? I'm not contradicting you, I am just curious.

As far as I've read (mostly in the Stonesense thread and a few others), one of the main issues with lag is the item vector that keeps track of basically every item in the game.  Pathing is also a problem, but that's to be expected.

Huh.  So my practice of chasming everything I don't want actually was a good idea...who knew?

[The Architect]

Absolutely.

Actually, according to studies done, the biggest hits to framerate are:
#1 item tracking and job assignment, which becomes more difficult and time-consuming for your processor the more items are being tracked
#2 revealed space and pathfinding, which go hand in hand. Revealed space is a much bigger drag than pathfinding unless you screw up your corridors and leave dwarves/animals constantly repathing to avoid walking over each other.
#3, sometimes #2, dwarf and animal tracking. This is not pathfinding, though it does utilize pathfinding; it's more a matter of the processor continuously performing checks on said creatures, which multiply with the creatures. This is another reason, along with job assignment and bad fortress commute design, which tricks people into the illogical "fort slows down when I have more dwarves, must be pathfinding!" idea.
#4, #5, These are in debate. We don't know which is worse, and the results tend to depend on who is performing the tests. The culprits are fluid flow, and other interactive natural environment such as trees.

So you see, pointing the finger at pathing is silly. We will see a miniscule improvement (due to an extreme tradeoff) with any of the ideas put forward so far in any thread, including the pathfinding project.

Bottom line: if job assignment and item tracking received an overhaul, pathfinding wouldn't be a concern. It's nitpicking to focus on a secondary issue while item tracking destroys our framerate.

[btbtbtbt]

Although this idea might not improve the frame rate, it would mean less frames would be taken for the dwarf to get the item to the workshop, which is a practical speed increase. Perhaps if a workshop had standing orders, items could choose the workshop, and the workshop could then choose the dwarf?

[The Architect]

It's hard to speculate without details from Toady. I wish we had more information on how items and job selection work; I only have a vague idea from what more knowledgable people have told me.