PVP匹配算法

玩家实时对战的游戏都会有一个匹配过程,根据玩家的分数,选择另一个分数接近玩家的对手,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,得到的玩家就是按匹配阶段排序的了。

This entry was posted in 技术学习 and tagged , . Bookmark the permalink.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据