0
$\begingroup$

I'm working on some kind of multiplayer game and for the best experience for the users I want to make sure the rooms are somewhat balanced at all time. By balancing I just mean the amount of users in the room (not score based or anything). I already figured out what the size of rooms should be and how many users there should be per room (based on a fixed maximum number of users per room). For a maximum of 4 users per room I came to the following distributions:

(total users) | (array of rooms (number is amount of users in room))
----------------------------------------------------------------------
4:              [4]
5:              [3, 2]
7:              [4, 3]
9:              [3, 3, 3]
13:             [4, 3, 3, 3]
...

I use the following code/algorithm to determine the distribution:

function calculateRoomDistribution(numUsers, maxUsersPerRoom) {
  const numRooms = Math.ceil(numUsers / maxUsersPerRoom)
  let distribution = []
  for (let i = 0; i < numRooms; i++) {
    distribution[i] = 0
  }
  for (let i = 0; i < numUsers; i++) {
    distribution[i % numRooms]++
  }
  return distribution
}

What I couldn't figure out however, is how to transition from one state to another. Let's say I have 13 users, divided over 5 rooms, respectively 4, 2, 2, 3, 2 users... I want to redistribute them into 4 rooms, with 4, 3, 3, 3 users. How would I approach such a problem? I was thinking of first removing the rooms that already have the right amount of users (4 and 3). That would leave me with [2, 2, 2]. But I noticed I would have to write a lot of edges and exceptions and I have a feeling there must be a smarter way. What type of algorithm am I looking for?

$\endgroup$
  • 1
    $\begingroup$ "13 users, divided over 5 rooms, respectively 4, 2, 2, 3, 2 users" is not a distribution that can be produced by your algorithm. Are you interested in the transition procedure for general distributions or for the balanced distributions? By the way, you may want to define what is a balanced distribution. Here is a possible definition. A balanced distribution means the difference between the maximum number and the minimum number of users in a room is at most 1. $\endgroup$ – John L. Jan 20 at 16:48
2
$\begingroup$

Here is one simple algorithm. Pick one room that has too many people in it, and one room that has too few people in it, and move one person from the first room to the second room. Repeat until convergence.

$\endgroup$
  • $\begingroup$ Yeah, I think I was really overthinking it. But I wanted to limit the amount of changes to a room a little bit, so instead of just moving 1 person a time I've added some logic. I couldn't fit it all in the comments, so I've added my own answer. $\endgroup$ – thomasjonas Jan 22 at 10:54
0
$\begingroup$

I think I've been really overthinking and came up with a bit of an awkward solution, but it seems to work! I've tried to limit the amount of modifications to the rooms as much as possible (without making it super complicated) by using the following strategy:

We know the amount of rooms we need, and we know their sizes. We loop over each room and try to adapt the current rooms to get the required size. We do this with the following steps:

  1. if we already have a room of the required size, move to the next
  2. if we have rooms bigger than required size: move users to smaller room until we reach required size
  3. then we only have rooms left that are smaller than the required size:
    • first we try if we combine 2 of them to create 1 room of the required size
    • in case we can't we will move clients from smaller rooms to a bigger one until we get the required size
$\endgroup$

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.