《部落冲突》和其他游戏如何如此有效地对玩家进行排名和匹配？

Question

所以，几天前我开发了一个非常标准的 ELO 系统。一名玩家可以攻击另一名玩家的防守，并根据结果重新分配分数。

一开始运行得很好，但最终排名较低的玩家找不到比赛，因为系统找到比赛的方式是：

• 从排名第一的玩家开始
• 下降排名，直到找到请求比赛的玩家

显然，如果参与者的排名接近 2000，这会导致必须请求 2,000 名玩家的数据。

所以，现在低排名的玩家已经无法要求了。

我注意到在《魔灵召唤》和《部落冲突》等其他热门游戏中，每当你的积分调整时，你的排名就会立即可见，我无法想象他们会在每个玩家的列表中下降，直到达到 #200,000。

我无法使用我想到的第一个策略（猜数字游戏），即如果有 100 名玩家，请检查 #50 的分数。如果你的分数较低，请检查#75，较低：检查#88等。这是因为由于OrderedDataStore的性质，我无法在不检查#2、#3等的情况下检查#50。

我试图以这样的方式存储数据：

可显示前50名玩家
算法可以快速找到与你排名接近的玩家的4个防守
可以查看自己的排名

有什么解决办法吗？

Answer 1

您应该能够像这样获得前 50 名玩家（假设您的排名列表简称为“排名”：

ranks.GetSortedAsync(false, 50).GetCurrentPage() -- This will just be an array of the top 50 players. 找到您排名附近的特定玩家应该像以下一样简单：

local playerRating -- set this to your player's Elo rating
local searchWidth = 5
ranks.GetSortedAsync(false, 100, playerRating - searchWidth, playerRating + searchWidth)
--[[ the above is a DataStorePages of all players within searchWidth Elo points of your player;
     you may want to widen the search if matches are not found, which is why
     searchWidth is a variable instead of a magic number ]]

获得排名确实是最难的部分；事实上，我认为解决方案可能

实际上符合你所说的：

local playerRating -- set to player's Elo rating
local playerRank = 0
local allRanks = ranks.getSortedAsync(false, 100, playerRating)
while not allRanks.IsFinished do
    allRanks.AdvanceToNextPageAsync()
    playerRank = playerRank + #allRanks.GetCurrentPage()
end
playerRank = playerRank + #allRanks.GetCurrentPage() -- have to add the last page too

由于限制，每当存储更新时，最好将前 50 个缓存在自己的数据存储中。

你是对的，他们可能没有对所有排名进行线性搜索，但似乎这是必要的。

Answer 2

不幸的是，我不知道 Roblox 能够完成这项特定任务，但要求 2000 名玩家听起来确实是一个错误的设计。

对于排行榜（显然），您需要一个按分数排序的玩家有序列表。您需要两个功能：

确定玩家当前排名的能力；
能够查询排名处于某个已知区间内的玩家；

能够有效执行此操作的数据结构称为

Skip List。

如果你想大规模地做到这一点，那么你需要

Redis排序集，当你谈论真正的游戏时，几乎每个人都在使用它。