设计一个多人在线的匹配系统

基本流程

1.统一使用 组 来 作为 一个匹配单元，加入匹配；

2.过滤规则、超时检测、结果推送；

3.使用?优先队列 实现（积分Score）自动排序、匹配、结果推送；

4.前面的流程可以作为 匹配 队友、匹配对手两类的通用流程；

1

做了几次匹配系统发现，前期设计基本是1v1,可是后期都会扩展到 2v2,甚至5v5, 而如果前期数据结构卡的很死，后面就不好扩展，甚至需要重写代码；直接将每个加入匹配的单元，设计成一个组，不管是单人，还是组队都可以满足

?关于重复匹配的问题

分析

?实际上，会有很大的可能，玩家会加入匹配再退出，当然写完功能我们也会跑测试，假设我们加入匹配，但是突然取消匹配，但程序已经匹到玩家，这个时候我们就需要处理很多状态，最简单就是，搜索清理所有数据，但这个会把所有任务暂停下来，可想而知，代价是很大的，当上百万人同时取消；

这里我们可以把握几个点，

????????1.保持匹配队列不动，只有加入和取出，不能直接去除特定元素；

????????2.同一时刻只保持一个有效的组在队列中；

? ? ? ? 3.代码支持，已经匹配的组，失效或则其它各种无效情况；

方案?

在上面的基础上我们可以有两种方案：?

? ? ? ? 1.延迟加入(耗时长)

? ? ? ? 2.使用虚拟GroupId（一段时间浪费一些内存）

?延迟加入(耗时长)早期做法

1.当前玩家组 退出 匹配时，记录一个标记，标记这个 玩家组 退出匹配；

2.每次主流程结束都会清理过期的玩家组，并且清理过期数据，但要确保过期的数据都已被处理；

3.在每次开始 主流程时 可以记录一个状态，当中间有玩家退出时，改变这个 状态，只有在 主流程开始到结束，这个中间 所记录的状态 依然为每次开始时标记的状态，才清理过期数据，如下代码

4.这个时候如果玩家重新加入匹配，则会先将消息放入，延迟队列，下次再加入

void MainLoop(){
    NoReceiveLeaveGroupMsg = true;
    // ...

    if(NoReceiveLeaveGroupMsg){
        // 清理过期数据
    }
}

void LeaveMatch(){
    NoReceiveLeaveGroupMsg = false;
    // ...
}

?可能存在的问题是，导致玩家没有立即加入匹配队伍，基本上无感，如果对时间比较敏感的，可以在加入的时候直接记录玩家的匹配时间。

使用虚拟GroupId（一段时间浪费一些内存）下面的流程是按这个做的

每次加入的时候

生成一个随机的GroupId; 建立一个映射关系 根据组信息可以找到 GroupId;

GroupKey -> GroupId

GroupId 可以找到对应的组信息

GroupId -> GroupData

每次玩家离开的时候，清除GroupId->Groupdata 的映射

匹配流程发现这个GroupId 的GroupData 找不到时，直接跳过（保证匹配流程正常进行）

组的基本结构：?

public class GroupData
{
    // 组内ids
    public List<long> Ids = new();
    // 积分
    public uint Score;

    // 上下积分
    public uint LowerScore;
    public uint UpperScore;
}

// 生成 groupId
uint CreateGroupId(GroupData gd)
{
    if(RandomId == MAX) RandomId = 0;
    RandomId++;
    return RandomId;
}

void EnterMatch(GroupData gd)
{
    // 这个组的key
    var groupKey = GetGroupKey(gd);

    // 这个组本次加入的groupId
    var groupId = CreateGroupId(gd);

    GroupKeyAndGroupIdDic.Add(groupKey, groupId);
    self.GroupIdAndGroupDataDic.Add(groupId, gd);
}

void LeaveMatch(GroupData gd)
{
    // 这个组的key
    var groupKey = GetGroupKey(gd);
    
    // groupKey -> groupId
    GroupKeyAndGroupIdDic.Remove(groupKey, out var groupId);

    // 移除组信息
    self.GroupIdAndGroupDataDic.Remove(groupId)
}

2

设计相关的过滤条件：

1.什么时候扩分；

2.是否匹配超时；

3.是否匹配机器人；

void Loop(){
    // 取出组信息
    
    // 处理组信息

    // 放回队列
}

3

这里使用优先队列自动对数据进行排序，获取的时候只比较相邻的数据是否满足匹配条件，如果满足，则匹配成功，否则将前一个放入后备list, 再取出一个和后一个重复前面的流程,直到取出一定数量的元素结束

基本流程

void Loop()
{

    List<(uint groupId, int priority)> backupList = new();
    HashSet<uint> finishGroupIdSet = new();

    int singleDeQueCount = self.GroupIdAndScoreQue.Count;
    Print($"Queue remain {singleDeQueCount}");
    while(singleDeQueCount > 1)
    {
        if (!self.GroupIdAndScoreQue.TryDequeue(out var groupId1, out var priority1))
        {
            break;
        }
        singleDeQueCount--;

        if (finishGroupIdSet.Contains(groupId1))
        {
            continue;
        }

        if (!self.GroupIdAndGroupDataDic.TryGetValue(groupId1, out var matchGroupData1))
        {
            break;
        }

        var count = self.GroupIdAndScoreQue.Count;
        var groupId2 = 0u;
        for (int i = 0; i < count; i++)
        {
            singleDeQueCount--;
            if (!self.GroupIdAndScoreQue.TryDequeue(out groupId2, out var priority2))
            {
                backupList.Add((groupId1, priority1));
                break;
            }

            if (groupId1 == groupId2)
            {
                backupList.Add((groupId2, priority2));
                groupId2 = 0;
                continue;
            }
            
            if (finishGroupIdSet.Contains(groupId2))
            {
                continue;
            }

            if (!self.GroupIdAndGroupDataDic.TryGetValue(groupId2, out var matchGroupData2))
            {
                backupList.Add((groupId1, priority1));
                break;
            }

            if (!CanMakeGroup(matchGroupData1, matchGroupData2))
            {
                backupList.Add((groupId1, priority1));
                    
                // 比较下一轮
                groupId1 = groupId2;
                priority1 = priority2;
                matchGroupData1 = matchGroupData2;
                continue;
            }

            // 发送匹配结果
            var code = await self.SendSuccMatchMsg(groupId1, groupId2);
            if (code != 0)
            {
                // groupId1 离开
                if (code == 1)
                {
                    finishGroupIdSet.Add(groupId1);
                    
                    // 比较下一轮
                    groupId1 = groupId2;
                    priority1 = priority2;
                    matchGroupData1 = matchGroupData2;
                    continue;
                }

                // groupId2 离开
                if (code == 2)
                {
                    finishGroupIdSet.Add(groupId2);
                    continue;
                }
            }

            // succ
            finishGroupIdSet.Add(groupId1);
            finishGroupIdSet.Add(groupId2);
            break;
        }

        if (groupId1 == groupId2)
        {
            // return groupId2
            backupList.Add((groupId1, priority1));
            break;
        }
    }

    // 将未处理的组放入队列
    self.GroupIdAndScoreQue.EnqueueRange(backupList);
}

4

1.进入下一个流程，匹配队友，或匹配对手

2.等待玩家特定时间（如果匹配时间要求严格，可以当玩家进入时，打破这里的等待）

void Loop(){
    while(true){
        // 核心匹配流程
        MainProcess();

        // 等待 1s 或 等待玩家加入
        WaitNotify(1000);
    }
}

void EnterMatch(){
    // ...

    // 玩家加入
    Notify();
}

?