Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 3 down vote accepted
  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.

share|improve this answer

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

share|improve this answer
    
+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 :) –  Blue May 6 '13 at 8:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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