Самый эффективный способ объединить группу пользователей для быстрой игры

У меня есть приложение, в которое пользователи входят, чтобы играть в быструю игру 1 на 1 (продолжительность 20 секунд). Я хотел бы знать наиболее эффективный способ объединения каждого пользователя с другим пользователем, чтобы играть в игру и перейти к следующему пользователю, не играя с одним и тем же пользователем несколько раз подряд.

Моей первой идеей было создание двух очередей, содержащих идентификаторы каждого пользователя в сети. Всякий раз, когда новый пользователь выходит в сеть, я добавляю его в ту очередь, которая является самой короткой, и постоянно высовываю одного человека из верхней части каждой очереди, чтобы играть друг с другом. После игры я просто добавил бы каждого пользователя в одну и ту же очередь, чтобы он не играл снова. Это кажется хорошим, но я хотел бы посмотреть, есть ли другие более эффективные способы реализовать эту концепцию без необходимости вести список предыдущих пользователей, играющих на сервере.

Источник

3 ответа

Решение

Вам нужна система подбора игроков, которая будет расставлять приоритеты игроков, которые ждали дольше всех.

Вам нужна только 1 очередь, и вам также нужно отслеживать историю пользователей, используя таблицу. Таблица может быть либо временными данными сеанса, либо таблицей базы данных, если вам нужны постоянные данные в нескольких сеансах или если происходит сбой сервера, создающего совпадения. Стол должен иметь идентификатор игрока и массив предыдущих идентификаторов игроков, против которых они ранее играли. Лучше всего ограничить размер массива и использовать LIFO, так как вы можете не сохранять только последние совпадения игроков, то есть историю матчей. Кроме того, у игрока может не хватить игроков, чтобы играть против, если они уже играли против всех остальных онлайн. Таблица должна выглядеть так:

  • playerID (целое число)
  • previousPlayerIDs (массив целых чисел)

Когда матч начинается, вы можете обновить предыдущие PlayerID для всех игроков в матче. Вам нужно прослушать событие, когда игрок присоединился к очереди, и назовем его onPlayerJoin(). Если в очереди более 1 игрока, вы должны взять самого длинного игрока в очереди и сравнить его playerID с предыдущими идентификаторами каждого игрока, пока не найдете историю совпадений.

const historyLimit = 10;

function onPlayerJoin(Player newPlayer){
  playerQueue.push(newPlayer);
  if(playerQueue.length > 1){
    for(let a=0; a<playerQueue.length-1; a++){
      Player player = playerQueue[a];
      for(int i=a+1; i<playerQueue.length; i++){
        Player otherPlayer = playerQueue[i];

        //if the player have not played before
        if(otherPlayer.previousPlayerIDs.indexOf(player.id) > -1){

          //save match up
          player.previousPlayerIDs.push(otherPlayer.id);
          otherPlayer.previousPlayerIDs.push(player.id);

          //limit matchup histroy
          if(player.previousPlayerIDs.length > historyLimit){
            player.previousPlayerIDs.removeAt(0);
          }
          if(otherPlayer.previousPlayerIDs.length > historyLimit){
            otherPlayer.previousPlayerIDs.removeAt(0);
          }

          //create lobby and remove players from the queue
          createLobby(player, otherPlayer);
          playerQueue.removeAt(a);
          playerQueue.removeAt(i);
        }
      }
    }
  }
}

Игрок может сыграть всех остальных, и они ждут, когда кто-то выйдет в онлайн, против чего он раньше не играл. Вам понадобится повторяющееся событие, чтобы проверить, не ждал ли самый долго ожидающий игрок слишком долго. Если это так, просто проигнорируйте совпадение предыдущих PlayerID и создайте лобби для игрока с другим потенциально долго ожидающим игроком.

Если вы хотите, вы можете добавить больше столбцов в таблицу, таких как отметка времени, когда они присоединились к очереди, и их рейтинг совпадений (elo). Но если вы просто хотите расставить приоритеты для самого последнего игрока, вам не нужны эти другие столбцы.

Кроме того, это решение может не очень хорошо масштабироваться, если у вас большое количество одновременно работающих пользователей, но это будет хорошо, если у вас меньше 1000-10000

Источник

Ваша идея не работает. В конце концов (возможно, очень быстро) вы окажетесь в положении, когда два игрока, которые играли ранее, окажутся в отдельных очередях. Вы не можете гарантировать, что они никогда не будут выбраны для совместной игры.

Представьте себе этот простой случай:

Queue 1       Queue 2
   A            B
   C

A и B играют, и добавляются в очередь 2:

Queue 1       Queue 2
   C            A
                B

A и C играют, и добавляются в очередь 1:

Queue 1       Queue 2
   A            B
   C

Теперь A и B играют снова. С никогда не получал возможность играть Б.

Этот конкретный пример вряд ли произойдет, правда. Но нечто подобное может произойти даже с большими очередями, так как пространство между игроком X и всеми игроками, с которыми он играл, со временем увеличивается. Вероятность того, что два игрока снова сыграют друг с другом, не сыграв ни одного потенциального игрока, довольно высока. Я подозреваю, что вероятность похожа на проблему дня рождения.

Источник

Ваше решение кажется хорошим, но вы должны просто использовать одну очередь.

Источник
Другие вопросы по тегам