algorithm - 为快速游戏重复配对一组用户的最有效方法

Question

我有一个应用程序，用户登录后可以玩一个快速的 1v1 游戏(时长 20 秒)。我想知道将每个用户与另一个用户配对以玩游戏并转移到下一个用户而不连续多次玩同一用户的最有效方法。

我的第一个想法是有两个队列，其中包含每个在线用户的用户 ID。每当有新用户上线时，我都会将他们添加到最短的队列中，并不断从每个队列的顶部弹出一个人来互相玩。比赛结束后，我会简单地将每个用户添加到同一个队列中，以避免他们再次互相比赛。这看起来不错，但我想看看是否有任何其他更有效的方法来实现这个概念，而无需在服务器上保留以前玩过的用户列表。

Answer 1

你需要一个匹配系统来优先考虑等待时间最长的玩家。

您只需要 1 个队列，还需要使用表格来跟踪用户历史记录。如果您想要跨多个 session 的永久数据或匹配服务器崩溃，则该表可以是临时 session 数据或数据库表。该表应包含玩家 ID 和他们之前对战过的一组玩家 ID。最好限制数组的大小并使用 LIFO，因为您可能不想只存储玩家最近的比赛，即比赛历史。此外，如果玩家已经在线与其他人对战，则玩家可能会用完所有玩家。该表应如下所示:

• 玩家ID(整数)
• previousPlayerIDs(整数数组)

比赛开始时，您可以更新比赛中所有球员的 previousPlayerID。当玩家加入队列时，您需要监听一个事件，我们称之为 onPlayerJoin()。如果队列中有超过 1 个玩家，您应该选择排队时间最长的玩家，并将他们的 playerID 与每个玩家的 previousPlayerID 进行比较，直到您找不到匹配的历史记录。

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);
        }
      }
    }
  }
}

一个玩家可能已经和其他人玩过，他们正在等待一个他们以前没有玩过的人上线。您将需要一个重复发生的事件来检查等待时间最长的玩家是否已经等待太久。如果是这种情况，只需忽略 previousPlayerID 的匹配，并为该玩家创建一个大厅，让另一个可能等待很长时间的玩家。

如果您愿意，可以向表中添加更多列，例如他们加入队列时的时间戳和他们的匹配排名 (elo)。但是，如果您只想优先显示最近的玩家，则不需要这些其他列。

此外，如果您有大量并发用户，此解决方案可能无法很好地扩展，但如果您的并发用户少于 1,000-10,000，应该没问题