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?


2 Answers 2

  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.


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

  • \$\begingroup\$ +1 Came here to say this - You can add some extra weighting per skill for if your algorithm needs to take into account a person who has several skills that could match other jobs. EG: Person A, B and C are skilled in Carpenting, but A and C are able to Smithy as well. A and C are better carpenters than B. There are 2 Carpenter jobs and one Smithy job available: A and C are matched to carpenting (because weight is greater) and so B is left to smithy even though he is unable to do so and A or C would be better at it. Just something to consider :) \$\endgroup\$ Commented May 6, 2013 at 8:33

You must log in to answer this question.

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