algorithm - 在配对多人游戏中到达 "pair with opponent"的最佳方法

Question

这个问题并不是特定于语言的，它更多的是关于在 1v1 配对游戏中用于配对玩家的算法背后的逻辑。

这是一个由两部分组成的问题。

---

如果我有一款配对 1v1 类型的游戏，你打开手机的应用程序，选择“玩”，它会为你找到一个对手，最好的方法是什么？

假设在我的玩家数据库中，我有一个名为“pairing”的键，其 BOOL 值为 YES/NO。

有人打开应用程序，点击播放，所以我需要将它们配对，所以我将此 BOOL 翻转为 YES，然后我们寻找具有 YES 值的其他人并进行确认，然后他们播放？

如果第一个用户在等待付款时因为无聊而离开而关闭了应用程序，会发生什么情况，服务器值将保持为"is"，因为我无法将其切换为否，因为应用程序已关闭。所以这行不通。

因此，我有一个带有 int 值的键“Pairing”，0 = no，除 0 之外的任何值都是 yes，所以每一秒我都会将该值从客户端增加 1 到服务器。在任何给定时间，如果这个值在 10 秒左右(服务器端)后没有改变，我假设用户关闭了应用程序并离开了，所以我们将值翻转为“0”。

好的，现在我们有了正确的配对模式检测(问题 1:这是检测正确配对模式的最佳方法吗？一个动态变量)

但是，现在服务器上有 10,000 名玩家都处于配对模式，进行配对的最佳方式是什么？如果我最终有 5 个玩家(玩家 A、B、C、D 和 E)都与同一个玩家(玩家 F)配对怎么办，当然我只是使用一些简单的 rand() 打破平局算法，但似乎有人可以最终总是打成平局并不断被抛来抛去，可能需要 20 秒才能确认两个玩家将互相战斗。最佳算法将有效地配对每个人，有什么想法吗？我有一种感觉，它会涉及某种队列，按照您等待配对的时间顺序排列。 (这是问题 2)

Answer 1

我的实现方式如下:

1. 每个玩家在数据库中都有一个唯一的player_id。
2. 当玩家连接到您的服务器时(它不应该连接到数据库本身)，将他们添加到事件 session 列表中。
3. 有一个特定的时间间隔作为超时。客户端应每秒(或您想要的任何时间段)向服务器发送一个 ping 数据包。如果服务器在指定的时间后没有收到来自客户端的 ping，则断开客户端。如果发生这种情况时玩家正在游戏中，请通知其他用户他们的对手已断开连接，并认为比赛无效。
4. 如果您想防止无效比赛，您可以将当前游戏 session 状态保存到数据库(或其他外部源)，当双方玩家再次准备就绪时，通知他们每个人比赛已经准备就绪。

至此，我们已经解决了连接问题。现在，关于多个用户是否与同一个人配对的问题。最简单的事情是像

while server is running
    if player is not currently in a match
        if there are available opponents
            set the first player's opponent to the opponent
            set the opponent's opponent to the first player
            remove each of them from the list of available players
        else
            wait for an opponent to become available

如果服务器在 n 时间后没有从客户端收到 ping 数据包，您还应该从可用播放器列表中删除该播放器。