Print

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

[Puzzlemaker]

Currently, if I remember correctly, Jobs choose dwarves.

Making it so Dwarves choose Jobs could lead to many improvements, mostly around in sequential jobs (AKA after you finish the job, you will be close to another job that you could do).  The problem is it would be hard to prioritize jobs as much, because the dwarves choose them.  Each time they look for a job they would have to weigh their choice based on priorities, and maybe jobs farther away (Like a tower on the other side of the map) would not be completed.

So, what is the best system for assigning jobs to dwarves?

The system should lower deadheading (The moving around between jobs; When you finish one job, you should be close to another job you can do without having to run across the fortress).

The system should also allow for priorities.

I think the best system would be thus:  A global list of jobs along with priorities of the jobs, which assign each dwarf a list of jobs it can choose from.  Dwarves would choose their own jobs from the list without having to search for them, based on distance, priority, and other factors.  Each dwarf would have their own queue of jobs that they have chosen.  AKA, a dwarf might choose to melt ten metal ores down to bars, then go have a drink.  They would go down their list, finishing jobs.  So it would be a hybrid of the two methods.

How do you think the best job-selection system should work?

[korora]

  Dwarves would choose their own jobs from the list without having to search for them, based on distance

This is a contradiction.  You can't know the distance to a job unless you path to it.

[Impaler[WrG]]

A rough calculation can be made by comparing the x/y coordinates of the dwarf and job site, the distance can't be less then the combined X,Y and Z differences thus eliminating a large number of jobs from a full path-finding check.  On top of that a rough zone based heuristic can further refine the distance to the remaining jobs, cull more jobs and pick randomly from the handful that remain.  Only then do we do a full path-finding operation.

[korora]

A rough calculation can be made by comparing the x/y coordinates of the dwarf and job site, the distance can't be less then the combined X,Y and Z differences thus eliminating a large number of jobs from a full path-finding check.

But the job with the largest straight-line distance could easily be the job with the shortest actual path, so this fails.  (A* also already takes this into account, which is what makes it different from Dijkstra's).

[Puzzlemaker]

  Dwarves would choose their own jobs from the list without having to search for them, based on distance

This is a contradiction.  You can't know the distance to a job unless you path to it.

The list would hold the jobs X/Y location.  They wouldn't have to search for anything, all the information would be in the list.  But they might still have to path to it.

[Symmetry]

But the job with the largest straight-line distance could easily be the job with the shortest actual path, so this fails.  (A* also already takes this into account, which is what makes it different from Dijkstra's).

But, if you have a job with distance 20 you know no job more than 20 straight line squares distance away can be closer.  So if you start with the linearly closest jobs you're very likely to be able to exit early.

Unless someone has built a fort like a corkscrew, and they get what they deserve

[korora]

But the job with the largest straight-line distance could easily be the job with the shortest actual path, so this fails.  (A* also already takes this into account, which is what makes it different from Dijkstra's).

But, if you have a job with distance 20 you know no job more than 20 straight line squares distance away can be closer.  So if you start with the linearly closest jobs you're very likely to be able to exit early.

Sure, that's what A* does already.  But what I originally disagreed with was whether you could choose a job based on distance without pathing there, and I stand by my statement that you cannot. Not if you want to be optimal. This is a good heuristic, but not a good way of eliminating jobs from consideration, as Impaler seems to be suggesting.

Anyways, this pathfinding discussion is slightly off-topic.  To get to the original question, I don't think it makes sense to focus on prioritizing specific jobs (like "build this wall section") because it's too much micro and a pain for UI. I also don't think a "hybrid" system is necessary or will accomplish what is intended.  Instead, I think in v-p-l you should be able to not only enable/disable tasks but also rank them in the order that that dwarf should prioritize them.  This is also much more useful than prioritizing specific jobs, since you only have to do it once.

Implementation-wise, a first step would be to split the job list into separate queues for each item in v-p-l.  This reduces the number of jobs a dwarf needs to consider when it's choosing.  This is sufficient if you don't care about choosing the closest job: an idle dwarf can just choose the first job in the list for its highest-priority task.  (This also means all jobs will get done eventually.)

If you do want to find the closest job, it will (of course) be more expensive, and it also means that some far-away jobs might fall by the wayside, although I don't think this will be a huge problem. (One solution might be to weight older jobs higher.)  I would guess that since the game is pretty snappy about giving you distances to every kind of building material available, Toady probably has a pretty good system for when you need to path to a bunch of things at once (you can cut corners because when you're calculating the path to the nearest orthoclase stone, you can re-use some of the pathing information from when you found the nearest microcline).  This would probably let you find paths to the available jobs pretty quickly.

One advantage here is you could be more subtle with priority than just "Urist always chops wood before hauling wood."  Instead you could, say, subtract 100 from the path cost for a high-priority job, or something to that effect, so Urist would go farther to cut wood but wouldn't cross the map to cut a tree down before hauling the log he's standing on.

  Dwarves would choose their own jobs from the list without having to search for them, based on distance

This is a contradiction.  You can't know the distance to a job unless you path to it.

The list would hold the jobs X/Y location.  They wouldn't have to search for anything, all the information would be in the list.  But they might still have to path to it.

OK, but putting the XY coordinates in a list doesn't help you a whole lot, because there could be any number of obstacles between the dwarf and the job.

[Impaler[WrG]]

but the job with the largest straight-line distance could easily be the job with the shortest actual path, so this fails.  (A* also already takes this into account, which is what makes it different from Dijkstra's).

No A* uses a distance heuristic to optimize its search but its a point to point search, it would need to be repeated for every single dwarf/job combination if their isn't a massive amount of culling the game will chug.  I'm talking about using the distance heuristic to cull jobs entirely and NOT do an A* search on them.

Run the heuristic on all the jobs (super fast), then A* for that one 'closest' job, the result will almost always be longer then the heuristic value but its got a great chance of being the actually closest.  Now cull everything from the job list that had a heuristic distance greater then that A* value, they can not possibly be closer (unless we add magical telaporter gates which will break the A* algorithm).  Then we might wish to crunch additional A* distances for the remaining jobs as their is some slim chance their shorter then the current 'best', each time a shorter distance is found we can cull the list again with anything with a larger heuristic.

In addition A* can be greatly accelerated by using 'zones' rather then individual tiles, because of the editable terrain these zones will need to be updated when ever theirs a change.  Basically put all the contiguously connected tiles in an area up to an arbitrary maximum (say 20x20), then get a distance from its center to the center of its neighbors.  As you modify the terrain the zones may get created or chopped up into smaller bits when updated.  Running A* on this zone map is 100 to 1000 times faster, you could probably blast through every path at the cost of doing one full A* run on a single path and the result wouldn't be off by a significant amount.

I do like the idea of using Priority to modify the distance, I'd go with designations like that of the traffic designation system, High, normal, low, suspended and they just act as multipliers, suspended is essentially an infinite multiplier.  I think Dwarfs themselves should also be applying a multiplier based on the task type and their skills, at progressively higher skills a progressively smaller multiplier is applied to the distance, at Legendary it would be 1/2 to 1/3 multiplier so they strongly prefer those tasks their good at (they don't currently seem to do this).

[korora]

but the job with the largest straight-line distance could easily be the job with the shortest actual path, so this fails.  (A* also already takes this into account, which is what makes it different from Dijkstra's).

No A* uses a distance heuristic to optimize its search but its a point to point search, it would need to be repeated for every single dwarf/job combination if their isn't a massive amount of culling the game will chug.  I'm talking about using the distance heuristic to cull jobs entirely and NOT do an A* search on them.

Run the heuristic on all the jobs (super fast), then A* for that one 'closest' job, the result will almost always be longer then the heuristic value but its got a great chance of being the actually closest.  Now cull everything from the job list that had a heuristic distance greater then that A* value, they can not possibly be closer (unless we add magical telaporter gates which will break the A* algorithm).  Then we might wish to crunch additional A* distances for the remaining jobs as their is some slim chance their shorter then the current 'best', each time a shorter distance is found we can cull the list again with anything with a larger heuristic.

I see what you're saying now, and it makes a lot more sense than what I thought you meant.  But at this point, I'm not sure you wouldn't be better off running Dijkstra once (single-source to all other nodes) than running A* a bunch of times.  Much easier to implement (and most importantly, would work just fine with portals ), and they're both polynomial so I can't imagine it's a huge difference in cost.  You could even tweak Dijsktra's to terminate after you find a job and you can't reach any nodes with lower cost than the path to that job.

In addition A* can be greatly accelerated by using 'zones' rather then individual tiles, because of the editable terrain these zones will need to be updated when ever theirs a change.  Basically put all the contiguously connected tiles in an area up to an arbitrary maximum (say 20x20), then get a distance from its center to the center of its neighbors.  As you modify the terrain the zones may get created or chopped up into smaller bits when updated.  Running A* on this zone map is 100 to 1000 times faster, you could probably blast through every path at the cost of doing one full A* run on a single path and the result wouldn't be off by a significant amount.

I don't think you're considering the cost of cutting the map up into zones and keeping it updated, or the memory overhead.  I'm sure it still helps, but I don't think it's as dramatic as you suggest.

I do like the idea of using Priority to modify the distance, I'd go with designations like that of the traffic designation system, High, normal, low, suspended and they just act as multipliers, suspended is essentially an infinite multiplier.  I think Dwarfs themselves should also be applying a multiplier based on the task type and their skills, at progressively higher skills a progressively smaller multiplier is applied to the distance, at Legendary it would be 1/2 to 1/3 multiplier so they strongly prefer those tasks their good at (they don't currently seem to do this).

The problem with treating suspended as infinity is that if you only have a suspended job available to a particular dwarf, it'll still path every connected tile and hurt your CPU.  Better to just ignore suspended jobs.  And whatever method Toady is using to make dwarves go farther for new food would work just fine here.

I like dwarves choosing jobs they like, have posted in favor of it elsewhere on these forums, and I think eventually, with large numbers of dwarves, they should be largely autonomous within a more macro-level economics-focused game.  But that's a matter to be discussed elsewhere.