匹配规则相对比较简单,匹配只基于竞技场积分,有一个动态扩大的匹配区间。初始的简单粗暴的核心匹配算法是:
for playerA in players
for playerB in players
if playerA match playerB then
匹配成功;
end
end
end
但是这个算法实在是效率不好,是O(n^2)的复杂度。
后来又实现一个基于hash的匹配算法,将分数段每10分分为一段,作为hash表上一个key。玩家根据自己当前的匹配状态把自己插入到一个或多个key下。同个key下的玩家可直接匹配。
使用初始算法,1万人(50万同时在线以上)同时匹配耗时0.5s(单核)
优化后的算法,100万(5000万同时在线)同时匹配耗时0.3s(单核)