Print

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

[Puzzlemaker]

Having a dwarf choose a job leads to the problem of some jobs getting done, like the ones near him, while others never getting done, like the ones farther away.

As in, if you decide to build a tower fairly far away from your main fort, it will end up not being worked on much as the dwarves all decide they have things to do closer then them.

Then to have a priority system means that the dwarves would have to scan all available jobs, then find the ones that need doing; again, not the best system...

Ima make a new thread to discuss job priority systems.

[Keldor]

By scanning the list of jobs to determine the closest, I mean simply estimating distance.  In 95% of cases the item that is closest in straight line distance is also at least fairly close in true distance.  No, they certainly won't be getting the absolute closest item each time, but at least they won't be choosing the one at the far side of the map!  Also, there are a lot of ways to improve the straight line estimate that don't involve doing a full blown path search which would allow at least a decent estimate even with obstacles and such.  We're not trying to get the dwarves to pick the most efficient order of tasks to perform (in fact, finding the most efficient order is NP-Complete!).  We just want them to find a reasonably efficient order.  Anything better than just picking them at random.

As for inaccessible items, we need only use a simple connectivity check, which can be completely precomputed by simply dividing the map into disconnected regions and indexing the squares of each one to refer to which region it is in.  If the square the dwarf is standing in has a different region number than the square the target item is in, then it is inaccessible.  A similar system is already used in fact.

[korora]

Dwarves can already choose the closest materials, so what makes you think they can't choose the closest job?

Code: [Select]

.A~D...B
..~....
..~....
..~....
..~....
.......

(Dwarf at D, jobs at A and B) Here's a not-so-uncommon scenario where the dwarf will make a very wrong decision using a straight-line estimate.  This example is condensed, but you can imagine a similar problem on the scale of the map, so dwarves very well could be traveling across the whole map to get to a job when a closer one exists. 

We're not trying to get the dwarves to pick the most efficient order of tasks to perform (in fact, finding the most efficient order is NP-Complete!).  We just want them to find a reasonably efficient order.  Anything better than just picking them at random.

No, we're trying to find the closest job to a dwarf.  You're overcomplicating the problem.

In 95% of cases the item that is closest in straight line distance is also at least fairly close in true distance.

Designing for a "good" or "easy" case is bad, because you won't always get what you're expecting. It's always far better to design for the worst case.  Especially in an application like DF where the player is changing the paths constantly and won't (and shouldn't have to) design around your fuzzy job selection.  If dwarves are finding the closest job, players will expect them to do it correctly.

[winner]

You don't need to be as concerned about the very shortest path, when they are all very far away but it's vital when they're near. 
I can't think of the perfect method but I'd have them path to the very closest one, but if that path is 2 (or some number) times or more the straight line distance to the next closest one then you store the value and compare it to the other jobs until their straight line distance grows greater.