Job finding algorithm

Question

My issue seems simple enough to me, but I can't break it down the the bare essentials to be able to program it into my game.

First of all different professions requires different skills, these skills are contained inside the class Person. I have a world map where I can ask for all empty buildings, thereby finding all available jobs.

With this information I want to calculate from some weights that the player can modify on each profession to how important it is to be fill a certain position.

so my current approach would be something like this pseudo code:

    Job findJob(wm : WorldMap) {
      Queue priority <- empty;
      for each building {
        queue.add(skill * need);
      }
      return prority.max();
    }

Does that sound inefficient stupid or do you see any special cases that you think I should be aware of?

Answer 1

1. Inefficient is fine if it's not using much cpu relative to other parts of your game. :) Start with the simple implementation and then go back and improve it later, only if needed.

2. Your pseudocode uses a queue but you don't really need the entire queue; you only need the max.

3. If you have lots of workers and lots of buildings, with your algorithm you may end up with lots of workers ending up in the same building. If you're trying to find the best assignment where no building gets more than one worker, you may find the Munkres-Kuhn algorithm to be useful. However I'd advise starting with the simplest algorithm (what you posted) first, and Munkres-Kuhn is not the simplest.

Answer 2

You might also want to take a look in other algorithms described in maximum weighted matching in bi-partite graphs.

In your case, all the people looking for the job should be placed in same group, and all the jobs should be placed in the other. Obviously there is no edge between vertices in the same group, and for person-job edge, it's weight would be equal to how much that person is needed for that job weight(Person,Job) = person.skill * job.need