1

我正在考虑将玩家加入游戏的有效算法。由于会有大量玩家，算法应该是异步的（即可扩展到集群中的任意数量的机器）。有细节：想象有一个无向图（每个节点都是一个玩家）。玩家之间的每个优势意味着玩家可以参加同一场比赛，如果没有优势，他们就不能参加。我需要实现将按照以下标准对玩家进行分组的算法：

  • 每个玩家都有一个状态：“等待游戏”或“游戏中”。只有等待的玩家才应该被分组到游戏中
  • 每场比赛都有最少和最多的玩家人数

我对实现的想法：该图将通过 NoSQL 数据库（来自集群中的不同机器）进行存储和访问。目前还没有特定的模式（有什么建议吗？）。此外，锁定对单个玩家的访问（也称为悲观锁）不是一种选择，因为它是减慢试图访问/收集相同玩家的其他进程的潜在瓶颈。

我的问题是：有没有人实现过这样的算法？有什么建议么？

PS：我已经有了原始想法，但首先想讨论/检查人们的建议。

谢谢！

EDIT1：回应Thomas Jungblut：使用游戏插槽是一个有趣的想法，但（只要我理解正确）它在某些情况下可能不起作用。Fox 示例：每场比赛都应该有 3 名玩家。新的 6 个玩家（我们称他们为 ABCDEF，参见示例 1）按以下顺序依次进入图形/队列：A、B、E、F、C、D。

示例 1

结果只会创建一个游戏（A，B，C），加上两个空槽游戏：（D）和（E，F）。但最佳应该是 2 场比赛：（A，C，D）和（B，E，F），对吧？

4

1 回答 1

3

我怀疑您没有正确考虑业务需求。

像任意条件的“最佳匹配”这样的短语对我来说是 NP 完全的。您不会为拥有大量数据集的人找到有效的精确解决方案，而只是一个合理的近似值。

次优匹配的成本是多少？你最终不得不等待稍长的时间才能找到有人玩。真的不是问题。

我会实现一些像这样简单的东西。有一个你正在设置的游戏队列。每个进来的人都试图进入第一场比赛，第二场失败，第三场失败，依此类推。如果找不到，则在队列末尾创建一个新游戏。游戏在达到最大尺寸或达到最小值后的固定时间时开始。当比赛开始时，它会从队列的前面移除。

有了这个决定，你为什么认为会有一百万活跃玩家？

如果是因为你是一家有远大梦想的创业公司，我强烈建议你需要专注于尽可能有效地解决已知问题。在不太可能成功的情况下（说真的，您看过统计数据吗？），您可以稍后进行扩展。只有解决真正的问题才能大大提高你成功的几率，从可怕到仅仅很差。（我并不是要气馁。但创业梦想确实是疯狂回报的可能性很小。你采取的每一个行动都应该以提高几率为目标。）

如果您是一家成熟的游戏公司，有充分的理由相信您会达到这些数字，请继续阅读。

我不应该提到的明显注意事项是，您将希望以相对快速的语言实现性能关键位。例如，如果您主要使用 Python 编写代码，那么这将是使用 Java、Go 或 C++ 编写的好作品。

接下来，第一个不会扩展的是玩家信息。所以分发那个。这样做会减慢您的“玩家是否适合游戏”检查。因此，添加每个游戏锁定，并异步分配该计算。限制你在放弃和创造新游戏之前尝试进入游戏的努力程度。

下一个瓶颈是游戏匹配计算。因此，继续将“这里的新游戏”分发到多台机器。现在一个玩家出现了，得到一个要检查的游戏的中央列表，开始检查它们。为避免出现瓶颈，玩家应随机排序等待游戏列表。

净瓶颈是要求该列表。该列表大部分是只读的，因此您可以只使用 Redis 的复制实例。写入（用于新游戏和标记游戏开始）可以转到 master，读取可以根据需要分布在尽可能多的机器上。玩家会随机打一个Redis副本，得到一个列表，随机排序。

如果你达到这个规模，我会感到震惊。如果你超过了它，我将把 Redis 分片等后续步骤留给你。

随手记。这是一个体面的面试问题。“设计这个简单的东西。让它扩大规模。让它扩大规模。让它扩大规模。” 如果您实际上正在寻找一个了解分布式性能的人，那是一个很好的测试。（但前提是面试官可以分辨出好与坏的答案。）

于 2013-06-28T17:40:50.667 回答