8
\$\begingroup\$

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).

Prison Architect Job system

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Philipp
    Jan 2, 2016 at 14:25

3 Answers 3

5
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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... \$\endgroup\$ Jan 3, 2016 at 12:43
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Priority Queue could be not such a good solution if each agents has its own priorities (distance, qualification, etc) \$\endgroup\$
    – Kromster
    Jan 7, 2016 at 20:56
0
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ I'll look into it, thanks. I had an idea and I might just work around a hash table... :) \$\endgroup\$ Jan 1, 2016 at 20:19
  • 3
    \$\begingroup\$ A Hash Table is the wrong choice here since it is not a sequence container. \$\endgroup\$
    – Steven
    Jan 1, 2016 at 22:16
  • 1
    \$\begingroup\$ Remark also that there is a Queue<T> object in C# \$\endgroup\$ Jan 2, 2016 at 12:09
  • \$\begingroup\$ @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. \$\endgroup\$
    – Steven
    Jan 2, 2016 at 16:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .