Assigning tasks

Question

---

In an RTS where workers are tasked e.g. build wall, how do the workers decide which walls to build?

The player decides which walls are to be built where, but they don't assign individual workers to individual wall squares. In many RTS games, workers simply do tasks that are near them, but in my RTS I want to use the strategic doing of explicit tasks on specific squares as the main strategy, so I don't want dumb workers clustering somewhere and leaving tasks further away not-done.

I use the example building wall; it could be mining stone, making a road, collecting wood or whatever. The key thing is the user picks where, but not who.

Workers can only work on squares that are adjacent to accessible squares; the squares they work on themselves may be impassable until work is complete.

Workers 1 and 2 are told to mine squares A,B,C and D.

They can move one square per game-tick, and mining a square takes 10 ticks.

How do you decide which worker mines which square?

It seems self-evident that 1 should mine A and 2 should mine C.

1 is 4 squares away from A, so will have finished mining it in 14 ticks. Where should 1 go next, and why?

And what if there was another square - E - to be mined directly above B?

What is the logic that a worker uses to decide where to proceed next?

Answer 1

Mark the resource node as busy, or limit the number of workers a tree can be used by. If a worked is assigned to gather at a certain point, what you are really telling them to is to harvest the closest available tree.

Two main paths for this: A realistic approach would be to evaluate and mark resource noes before they arrive. To prevent weird queuing issues, give workers a vision range to evaluate trees. This allows the worker to approach a particular resource node while walking to the patch. This gives a limited about of optimization.

However, many RTS's (SC and SC2) don't have workers evaluate a node until they arrive. This leaders workers to wander around until a resource node is found. This allows for more skill/optimization reward, (Ever see awesome worker splits?) However, most of your players are just going to box all, click, and be annoyed that they all go the same location first.

The exact implementation will vary based on how resources are grouped. In AoE trees and fish are continuous expanses, so gatherers might end up quite far away as the game progresses. But in games like SC and Red Alert resources are located in discrete patches. So a worker only has to look around that particular patch.

EDIT after your edit: Don't stress too much over worker inefficiencies. Any RTS I can think of has worker inefficiencies. Things like worker splits arise from the player being better at managing their workers than the game. I think you may be taking a programmers perspective at this and not a designers. The singe tick left issue can be worked around just by tweaking numbers and having nodes be harvestable in a discrete number of trips. Worker inefficiencies are glaring to you, because you know the system behind it. However, if your play testers don't notice then don't dwell too long.

Answer 2

Solution and a thought:

Solution: You could have the gathering nodes be placed in a queue when clicked, then as a job rises to the top of a queue, find the weighted task queue value for the workers then find the nearest neighbor with the best weighted task queue value (queue value).

In your example, you could have the optimal queue value be 0 (implying no current tasks). Add 1 to the queue value for each square they would have to travel (travel time) and 10 for each task (time to do the task). Remove 1 from each worker's queue value for each unit of time that passes (if starting queue value is 10 then after 3 units of time the queue value would be 7). Then you find nearest neighbor (in the event multiple workers have equivalent queue values) to find the worker that should do that task.

So for your example, assuming the gathering nodes pop from the task queue in alphabetical order (A-D) and no movement is done while queue pops:

(values in format [total] = [preexisting value] + [current task distance])
A Pops: 
    queue value of 1: 4 = 0 + 4 
    queue value of 2: 19 = 0 + 19
    Assigned to 1.
B Pops:
    queue value of 1: 24 = 14 + 10 (distance to B from A) 
    queue value of 2: 9 = 0 + 9
    Assigned to 2.
C Pops:
    queue value of 1: 25 = 14 + 11
    queue value of 2: 20 = 19 + 1 
    Assigned to 2.
D Pops:
    queue value of 1: 36 = 25 + 11
    queue value of 2: 41 = 20 + 21
    Assigned to 1.

Downside to doing it like this: highly computational.

---

Thought:

How is your game going to handle being blocked by resources? i.e. if there exists a 4x4 grid where every node is a resource, can workers get the inner 4 nodes? If not, make sure the workers don't just idle there trying to get to them, but maybe assign them a different task and assign one of the workers gathering one of the outside nodes to the inner ones once the outer node is complete (put it in a task queue for the worker).

Answer 3

try having some weight system, that if the tree is being collected, calculate some sort of stacking penalty and also some sort of distance bonus. ( how long does it take to get from point A->B with the wood, and so on. then you can do some algorithm that does check for the closest wood, and check it´s weight, and then comparing if it´s desirable. and then use the one with the lowest weight.

of course this requires some fine tuning. but the idea is simple.

Answer 4

Each job should have a) an importance b) assignment status (# of workers assigned)

A worker could then decide for the job that gives him the most "reward" per time. The reward is calulated by the importance divided by the number of workers assigned divided by the time he needs to invest (walking and doing the job). If your worker can specialize on jobs (e.g. wood chopping) they will actually prefer tasks they can efficiently do. Jobs should of course only be assigned, if they can be continued at the right moment (e.g. resources needed must be available).

To avoid having some jobs undone for long time (e.g. because its far away). The importance should increase with time. In case of harvesting the importance should also be dependent on how much resources of that type are available / needed at the moment (e.g. produced units divided by unit requested in a give period).

To avoid workers to change their job to quickly, let them only change their current job, if the reward gets significantly better (by a given threshold). Also you could apply the doubled costs for the initial walking to the job, when calculating the reward per time values. Furthermore, you should let recalculate the workers optimal job one after each other, not all at the same time.

Additionally, add some randomness to the calculated rewards. This will cause a better distribution of the workers to different jobs (this way they do not just "all" go to do the same job). But, this effect is already reduced by serially recalculating the next optimal job for a worker and adapting the number of workers already assigned (more workers on the same job reduce the expected reward).

The algorithm maybe needs to be adapted a bit, if your jobs can only be assigned to one worker. If this is the case do the following: A worker chooses the job with highest reward per time (importance divided by individual time needed). If another worker can do the same job with a higher expected reward per time, he kicks off the currently assigned worker. The new "unemployed" worker then tries to find another job. In your example this could be like this:

• "C" has a very high importance. And worker 1 assigns itself to "C", even he's farer away.
• Worker 2 is assigned next and has a higher reward per time for "C" (less walking). So it kicks worker 1 off the job and assigned itself to "C". This did not cost time, as we are still within the same simulation time slice. So the user will not see this reassignment of the job.
• Worker 1 is then looking for another job. Worker 1 doesn't kick off worker 2 from "C", as his reward per time isn't better. So he is assigned to "A" or "B" (depending on importance). Again, this is still within the same simulation time slice.