玩家实时对战的游戏都会有一个匹配过程，根据玩家的分数，选择另一个分数接近玩家的对手，COC、皇室战争、DOTA和LOL的匹配都是这种方式。

之前做的一个游戏里有一个对战匹配的功能，大致的方法是设定一个初始匹配区间，如果匹配不到则尝试放大匹配区间，具体逻辑是：

1. 玩家A点击匹配，若当前匹配队列里有与A的分数 S 相差不超过 D1 的玩家，则直接匹配成功，否则把玩家加入匹配队列，等待 T1 秒。
2. 如果 T1 秒过后玩家A仍然没有匹配成功，则把匹配分差要求放宽到 D2，再等待 T2 秒。
3. 如果仍然没有匹配成功则循环如上操作直到 Tn 超时，返回匹配失败。

我们需要一种可以有效的进行范围查询的数据结构，这样我们能快速找到匹配队列中分数某个范围内的玩家。任何内部有序的数据结构其实都能满足要求，比如插入时保持有序的数组、二叉树或者是 redis 的 sorted set 使用的 skip list。

有了可以范围查询的数据结构，对于一个分数为 S 的玩家，我们查询出队列里分数落在 [S – D1, S + D1] 的玩家，选一个作为 S 的对手即可完成匹配，若没有等待 T1 秒后再次用 [S – D2, S + D2] 查询，直到找到对手或失败。

考虑这样一种情况，假设有一个玩家 A 分数为 500，D1 为100，D2 为200。

1. A 加入匹配，匹配范围是 [400, 600] 队列里没有玩家；等待T1秒；
2. A 等待的过程中分数为 650 的 B 加入匹配，匹配范围是 [550, 650]，匹配不上 A，等待 T1 秒
3. A 加入 T1 秒后匹配范围变成 [300, 700]，这样就匹配到了 B，但这时 B 的匹配范围仍然是 [550, 650]，所以仍然是匹配不成功。
4. B 加入 T1 秒过后 匹配范围变成了 [450, 750]，这时 A 和 B 匹配成功。

也就是说，对 A 进行匹配时，光按 A 的分数范围查询是不够的，还要检查查询出的玩家的匹配范围是否包含 A 的分数，要求查询出玩家的匹配阶段 小于等于 A 的阶段即可。

这意味着需要优先找到范围内匹配阶段最小的玩家，只要把等待阶段作为排序的第二键值就可以了，如果数据结构只支持单一排序键，就把等待阶段 L 编码到分数中：S’ = S * 10 + L, L∈[1, 9)。查询的时候把范围上下界乘以10，得到的玩家就是按匹配阶段排序的了。

本作品采用知识共享署名-相同方式共享 3.0 Unported许可协议进行许可。

本文永久链接：https://mainloop.cc/2016/06/pvp-matching-algorithm/