4
\$\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
    \$\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 '16 at 14:25
3
\$\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\$
  • \$\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\$ – user3797758 Jan 3 '16 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\$
  • \$\begingroup\$ Priority Queue could be not such a good solution if each agents has its own priorities (distance, qualification, etc) \$\endgroup\$ – Kromster says support Monica Jan 7 '16 at 20:56
1
\$\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\$
  • \$\begingroup\$ I'll look into it, thanks. I had an idea and I might just work around a hash table... :) \$\endgroup\$ – user3797758 Jan 1 '16 at 20:19
  • 3
    \$\begingroup\$ A Hash Table is the wrong choice here since it is not a sequence container. \$\endgroup\$ – Steven Jan 1 '16 at 22:16
  • 1
    \$\begingroup\$ Remark also that there is a Queue<T> object in C# \$\endgroup\$ – H. Pauwelyn Jan 2 '16 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 '16 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.