# How to implement a job queue system?

Essentially I'm trying to make a system which you can add a job to it then finds an AI which is idle and gives it that job to do, For an example look at Prison Architects job list system (image below).

I need to be able to add a job, removed them and look at all the jobs. The next job that this returns should be the oldest one in the list.

Initially I thought of using a queue as it already provides adding and removing but as it turns out I can only see the next item in that list (well at least thats the case with the standard C# implementation of it), meaning that if there is a certain requirement which isn't met I can't skip to the next task.

Is there a version of the queue that exposes all the items within the list or some other way of doing something similar? This will be coded in C# if that makes difference to the options available.

• By the way: the queue in prison architect is not pure first-in-first-out. For example, when the player gives an explicit order they are prioritized over automatically generated jobs, build jobs appear to be actually first-in-last-out and workers seem to prioritize jobs which are nearby. A pure FIFO data structure will likely turn out to be too restraining and inflexible in the long run. – Philipp Jan 2 '16 at 14:25

The job queue system in Prison Architect is actually far more complex than a pure first-in-first-out queue. Actors prioritize their jobs:

• They only take jobs they are actually qualified for (example: any staff member can perform the "open staff door" job, but only guards can do the "open jail door" job)
• In many cases they prioritize jobs given by the player over jobs generated automatically
• They often prioritize jobs which are nearby over those which require some walking
• In other situations they prioritize the jobs which were generated first. It seems like distance and age are somehow valued against each other.
• Some jobs immediately spring to the front. For example, guards will stop doing what they do when they witness a prisoner misbehaving.

I could imagine that the developers started out with a simple FIFO queue for their job system, but then realized that it is far too inflexible to allow actors to behave as efficiently as the player would expect it. I would recommend you to just store all jobs unsorted in an ArrayList or similar unsorted data-structure. When an actor needs a new job, it iterates that whole datastructure and uses a rating function to assign an own priority rating to each job and pick the job with the highest score for itself.

• I know that it is more complex but for now at least there are no auto generated tasks (for now) so I guess that this will probably be the better thing to do in the long run. For now Im using a dictionary and just looking for the first not used job that is in the queue, this is run on another thread so once I figure out a rating system FPS shouldn't be affected which is nice :) I will look back on this once I have more time to work on the project... – user3797758 Jan 3 '16 at 12:43

If you're going to be adding and removing tasks dynamically, and they may have differing times, then you may want to look at a C# implementation of a Priority Queue.

It's a pretty basic data structure and implementations will be easy to find based on trees (usually red-black) or heaps.

Access to the next available is O(1) and insertions in most implementations will be O(log n) which is pretty fast indeed.

• Priority Queue could be not such a good solution if each agents has its own priorities (distance, qualification, etc) – Kromster says support Monica Jan 7 '16 at 20:56

Use a List<T> instead. See How to add item to the beginning of List<T> for adding to front.

Not the most efficient but the Job Queue won't be the bottleneck in your game.

Alternatively, you can use a LinkedList<T> and wrap it in your own JobQueue class, here's a post showing how: Is there a better way to implement a remove method for a queue. This option is less cache performant but you can add/remove anywhere in the list.

• I'll look into it, thanks. I had an idea and I might just work around a hash table... :) – user3797758 Jan 1 '16 at 20:19
• A Hash Table is the wrong choice here since it is not a sequence container. – Steven Jan 1 '16 at 22:16
• Remark also that there is a Queue<T> object in C# – H. Pauwelyn Jan 2 '16 at 12:09
• @luis op noted in the question that queue can't remove anything but the head of queue so it doesn't help his use case. – Steven Jan 2 '16 at 16:37