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

Question

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

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

Answer 1

您的解决方案似乎不错，但您应该只使用一个队列。

Answer 2

你的想法行不通。最终（可能很快），您将处于这样一个位置，即之前玩过游戏的两名玩家最终处于不同的队列中。你不能保证他们再也不会被选中一起玩了。

想象一下这个简单的例子：

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再玩一次。 C一直没机会打B.

这个例子不太可能发生，是的。但是随着玩家 X 和他玩过的所有玩家之间的 space 随着时间的推移增加，即使队列更大，也会发生类似的事情。两名玩家在没有与所有其他潜在玩家对战的情况下再次对战的可能性非常高。我怀疑概率类似于the birthday problem。

Answer 3

您需要匹配系统，优先考虑等待时间最长的玩家。

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

playerID（整数）
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);
        }
      }
    }
  }
}

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

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

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

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

Most efficient way to repeatedly pair up a group of users for a quick game

algorithm

computer-science

computer-science-theory

data-structures