浅谈游戏服务器匹配机制

0x00导言

如今在游戏市场，越来越多的游戏都加入了多人匹配系统，如data2,lol,守望先锋等竞技型游戏所有的战斗都是典型的多人联机对战的模式，如何保证对战的双方的平衡性，和公平性，就很重要。如lol等竞技性很强的游戏采用的都是ELO算法来实现的(也就是大家所熟悉隐藏分机制)，ELO不是本次主题重点讨论的范围。点击了解ELO算法

0x01匹配系统的目的

1.保护新手不被有经验的玩家虐，让高手局中难以出现甚至没有新手，影响双方的游戏体验。

2.创造公平有竞技性游戏对局，使玩家的游戏乐趣最大化。

3.无需等待太久就能找到对手进入游戏，尽管有时候需要等待比较长的时间。

匹配系统尽其所能的匹配水平接近的玩家，玩家的水平评估是来自他们在此之前赢了谁以及他们对手的水平。当你战胜对手，系统会觉得你更强，当你输给对手，系统会觉得你更弱。尽管这对于某一局游戏并非那么的公平，可是长期来看，对于多局游戏是相当的公平。

0x02主要代码

public class MatchForBattleTask {
 
	private Set<Long> alreadyMatchTeams = new HashSet<>();
 
	public void process() {
		if (TestMatch.matchTeamInfos.isEmpty())
			return;
        int totalMatchRoleNum = 0;
        for (Map.Entry<Long, MatchingTeamInfo> entry : TestMatch.matchTeamInfos.entrySet()) {
            totalMatchRoleNum += entry.getValue().roleinfos.size();
        }
        System.err.println("当前正在匹配中的玩家:"+totalMatchRoleNum);
		List<MatchResult> matchResults = new ArrayList<>();//匹配成功的玩家
		Map<Integer, List<MatchTeam>> matchingCalssifyTeam = classifyTeams(TestMatch.matchTeamInfos);
		List<MatchGroupResult> matchingGroupResult = getCampMatchGroupResult(matchingCalssifyTeam);
		System.err.println("一共整合出:"+matchingGroupResult.size() +"个匹配组");
		if (matchingGroupResult.isEmpty()) 
			return;
		int size = matchingGroupResult.size();
		Set<Integer> alreadyOccupied = new HashSet<>();
		
		for (int i = 0; i < size; ++i) {
			if (alreadyOccupied.contains(i))
				continue;
			MatchGroupResult tempGroup = matchingGroupResult.get(i);
			int minVal = Integer.MAX_VALUE;
			MatchResult matchResult = null;
			int saveIndexI = -1;
			int saveIndexJ = -1;
			//这里可以优化下,遍历次数太多了点
			for (int j = 0; j < size; ++j) {
				if (i == j || alreadyOccupied.contains(j))
					continue;
				int subVal = Math.abs(tempGroup.averageScore - matchingGroupResult.get(j).averageScore);
				//设置个积分差上限,超过这个上限就慢慢等着
                if (subVal > 400) 
                    continue;
				if (subVal < minVal) {
					matchResult = new MatchResult();
					matchResult.blueGroup = matchingGroupResult.get(i);
					matchResult.reGroup = matchingGroupResult.get(j);
					minVal = subVal;
					saveIndexI = i;
					saveIndexJ = j;
				}
			}
			if (null != matchResult && saveIndexI != -1 && saveIndexJ != -1) {
				matchResults.add(matchResult);
				alreadyOccupied.add(saveIndexI);
				alreadyOccupied.add(saveIndexJ);
			}
		}
		for (MatchResult matchResult : matchResults) {
			for (long removeTeamId : matchResult.reGroup.teams.keySet())
                TestMatch.matchTeamInfos.remove(removeTeamId);
 
			for (long removeTeamId : matchResult.blueGroup.teams.keySet())
                TestMatch.matchTeamInfos.remove(removeTeamId);
			//TODO 通知创建战斗场景
		}
		System.err.println("共创建了:"+matchResults.size()+"个战场");
	}
	
	/**
	 * 整合所有的正在匹配的队伍数据,将其按照队伍人数分类,将5个人，4个人.....等等分类存储起来key：为队伍人数,value：队伍信息
	 * @param teamMap
	 * @return Map<Integer, List<MatchTeam>> 
	 */
	private Map<Integer, List<MatchTeam>> classifyTeams(Map<Long, MatchingTeamInfo> teamMap){
		Map<Integer, List<MatchTeam>> classifyResult = new HashMap<>();
		Set<Long> invalidateTeam = new HashSet<Long>();
		for (Map.Entry<Long, MatchingTeamInfo> entry : teamMap.entrySet()) {
			MatchingTeamInfo teamInfo = entry.getValue();
			long teamId = entry.getKey();
			int memNum = teamInfo.roleinfos.size();
			if (memNum <= 0) {
				invalidateTeam.add(teamId);
				continue;
			}
			MatchTeam mt = new MatchTeam();
			mt.serverid = teamInfo.serverId;
			mt.teamid = teamInfo.teamid;
			int totalScore = 0;
			for (MatchingRoleInfo roleInfo : teamInfo.roleinfos) {
				totalScore += roleInfo.score;
				mt.members.put(roleInfo.roleId, new BattleRoleInfo(roleInfo.roleId, roleInfo.score, roleInfo.name));
			}
			mt.totalScore = totalScore;
			mt.averageScore = totalScore / memNum;
 
			List<MatchTeam> resultList = classifyResult.get(memNum);
			if (null == resultList) {
				resultList = new ArrayList<>();
				classifyResult.put(memNum, resultList);
			}
			resultList.add(mt);
		}
        //删除无效的队伍
		for (long rmTeam : invalidateTeam)
			teamMap.remove(rmTeam);
		return classifyResult;
	}
 
	private void checkAddMatchGroupResult(List<MatchGroupResult> allTypeMatchResult, MatchGroupResult result) {
		if (null == result)
			return;
		allTypeMatchResult.add(result);
	}
	
	/**
	 * 为当前队伍，填充数据 (如当前队伍中有两人,此时需要再从队伍人数分组中找3个填满,这个3个又可以进一步分为，找 3个一个人的队伍，或者找1个一个的队伍,一个两个人的队伍)
	 * @param mTeam 当期队伍
	 * @param campClassifyTeams 所有的分组队伍数据
	 * @param groupTypes 需要填充的数据
	 * @return
	 */
	private MatchGroupResult matchMostEqualGroup(MatchTeam mTeam, Map<Integer, List<MatchTeam>> campClassifyTeams, List<Integer> groupTypes) {
		final int myAverageScore = mTeam.averageScore;//当前队伍的平均分
		Set<Long> cacheUsedTeam = new HashSet<>();//缓存已经分配过的队伍
		MatchGroupResult result = new MatchGroupResult();
		int totalScore = 0;
		int totalMemNum = 0;
        if (groupTypes.isEmpty()) {
            cacheUsedTeam.add(mTeam.teamid);
            result.teams.put(mTeam.teamid, mTeam);
            totalScore += mTeam.totalScore;
            totalMemNum += mTeam.members.size();
        } else {
            for (int groupType : groupTypes) {//根据group的信息,去找满足条件的数据
                List<MatchTeam> checkFromList = campClassifyTeams.get(groupType);
                if (null == checkFromList || checkFromList.isEmpty())
                    return null;
                int minVal = Integer.MAX_VALUE;
                MatchTeam currSelectTeam = null;
                for (MatchTeam checkTeam : checkFromList) {
                    if (mTeam.teamid == checkTeam.teamid)
                        continue;
                    if (cacheUsedTeam.contains(checkTeam.teamid) || alreadyMatchTeams.contains(checkTeam.teamid))
                        continue;
                    //从满足条件的队伍组中找到与当前队伍积分最相近的队伍,此处可以设置个最大积分差的限制,挺高公平性
                    int sub = Math.abs(myAverageScore - checkTeam.averageScore);
                    if (sub < minVal) {
                        minVal = sub;
                        currSelectTeam = checkTeam;
                    }
                }
                if (null != currSelectTeam) {
                    cacheUsedTeam.add(currSelectTeam.teamid);
                    result.teams.put(currSelectTeam.teamid, currSelectTeam);
                    totalScore += currSelectTeam.totalScore;
                    totalMemNum += currSelectTeam.members.size();
                } else
                    return null;
            }
        }
		if (cacheUsedTeam.isEmpty() || totalMemNum == 0)
			return null;
		result.averageScore = totalScore / totalMemNum;
		result.totalMemNum = totalMemNum;
		result.totalScore = totalScore;
 
		return result;
	}
 
    /**
     * 匹配分配组情况
     * 当队伍中有5个人时,直接放到类型为5的分组中
     * 当队伍中有4个人时,组合情况就是 {4,1}
     * 当队伍中有3个人时,组合情况就是{3,2},{3,1,1}
     * 当队伍中有2个人时,组合情况就是{2,2,1},{2,1,1,1}
     * 当队伍中有1个人时,组合情况及时{1,1,1,1,1}
     * @param mTeam
     * @param classifyTeams
     * @return
     */
	private MatchGroupResult matchBestGroup(MatchTeam mTeam, Map<Integer, List<MatchTeam>> classifyTeams) {
		List<MatchGroupResult> allTypeMatchResult = new ArrayList<>();
		switch (mTeam.members.size()) {
            case 5:
                checkAddMatchGroupResult(allTypeMatchResult, matchMostEqualGroup(mTeam, classifyTeams, Arrays.asList()));
                break;
            case 4:
                checkAddMatchGroupResult(allTypeMatchResult, matchMostEqualGroup(mTeam, classifyTeams, Arrays.asList(1)));
                break;
            case 3:
                checkAddMatchGroupResult(allTypeMatchResult, matchMostEqualGroup(mTeam, classifyTeams, Arrays.asList(2)));
                checkAddMatchGroupResult(allTypeMatchResult, matchMostEqualGroup(mTeam, classifyTeams, Arrays.asList(1, 1)));
                break;
            case 2:
                checkAddMatchGroupResult(allTypeMatchResult, matchMostEqualGroup(mTeam, classifyTeams, Arrays.asList(2, 1)));
                checkAddMatchGroupResult(allTypeMatchResult, matchMostEqualGroup(mTeam, classifyTeams, Arrays.asList(2, 1, 1)));
                break;
            case 1:
                checkAddMatchGroupResult(allTypeMatchResult, matchMostEqualGroup(mTeam, classifyTeams, Arrays.asList(1, 1, 1, 1)));
                break;
            default:
                break;
        }
 
		MatchGroupResult finalResult = null;
		final int mAverageScore = mTeam.averageScore;//当前队伍的平均积分
		int minVal = Integer.MAX_VALUE;
		//进一步再从组合情况中找到积分最相近的一个，然后把自己丢进去
		for (MatchGroupResult result : allTypeMatchResult) {
			int sub = Math.abs(mAverageScore - result.averageScore);
			if (sub < minVal) {
				minVal = sub;
				finalResult = result;
			}
		}
		if (null == finalResult)
			return null;
		finalResult.totalScore += mTeam.totalScore;
		finalResult.totalMemNum += mTeam.members.size();
		finalResult.teams.put(mTeam.teamid, mTeam);
		return finalResult;
	}
	
	/**
	 * 将分类整合后的队伍进一步的去整合,将team中不足5人的队伍补满。
	 * @param campTeams
	 * @return
	 */
	private List<MatchGroupResult> getCampMatchGroupResult(Map<Integer, List<MatchTeam>> campTeams) {
		List<MatchGroupResult> campMatchResult = new ArrayList<>();
        //优先给人数多的队伍分配
		for (int i = 5; i > 0; --i) {
			List<MatchTeam> teams = campTeams.get(i);
			if (null == teams || teams.isEmpty())
				continue;
			for (MatchTeam mt : teams) {
				if (alreadyMatchTeams.contains(mt.teamid))
					continue;
				MatchGroupResult matchResult = matchBestGroup(mt, campTeams);
				if (null == matchResult)
					continue;
				campMatchResult.add(matchResult);
 
				alreadyMatchTeams.addAll(matchResult.teams.keySet());
			}
		}
		return campMatchResult;
	}
}

测试代码如下

public class TestMatch {
    //存储所有的匹配玩家数据,可以存储在数据库中,同样也可以用concurrentHashMap来存储(真实环境一定是多个线程操作该数据的)
    public static Map<Long, MatchingTeamInfo> matchTeamInfos = new HashMap<>();
 
    public static void main(String[] args) {
        Runnable runnable = new Runnable() {
            @Override
            public void run() {
                long now = System.currentTimeMillis();
                addTestData();
                new MatchForBattleTask().process();
                long end = System.currentTimeMillis();
                System.err.println("耗时:"+(end - now)+"毫秒!");
            }
        };
        //每隔5秒钟执行一次
        ScheduledExecutorService service = Executors.newSingleThreadScheduledExecutor();
        service.scheduleAtFixedRate(runnable, 5, 5, TimeUnit.SECONDS);
    }
    
    /**
     * 测试代码生成测试数据
     */
    private static void addTestData() {
		long baseId = System.currentTimeMillis()/1000;
		int createTeamNum = getRandomBetween(5000, 7000);
		int index = 0;
 
		for (int i = 0; i < createTeamNum; ++i) {
			MatchingTeamInfo maInfo = new MatchingTeamInfo();
			maInfo.serverId = i;
			maInfo.teamid = baseId + index;
            TestMatch.matchTeamInfos.put(maInfo.teamid, maInfo);
 
			int teamNum = getRandomBetween(1, 5);
			for (int j = 0; j < teamNum; ++j) {
				MatchingRoleInfo matchrole = new MatchingRoleInfo();
				long temp = createTeamNum;
				long roleId = (temp << 32) + i + j;
				matchrole.roleId = roleId;
				matchrole.score = getRandomBetween(0, 3000);
				maInfo.roleinfos.add(matchrole);
			}
			index++;
		}
	}
    
    public static int getRandomBetween(final int start, final int end) {
        Random random = new Random();
        return end > start ? random.nextInt(end - start + 1) + start : random.nextInt(start - end + 1) + end;
    }
}

运行结果

当前正在匹配中的玩家:20111
一共整合出:4219个匹配组
共创建了:2064个战场
耗时:507毫秒!
当前正在匹配中的玩家:15383
一共整合出:3216个匹配组
共创建了:1648个战场
耗时:751毫秒!

0x03总结

匹配系统是怎么完成的?

首先，系统将你放进一个合适的匹配池里——根据游戏模式的不同(如5V5，排位，匹配等等)

然后，系统会尝试将匹配池里的人分到更细的匹配池里——5人组队 VS 5人组队，低等级新手 vs 其它一些低等级新手，以此类推。

当你在匹配池中，系统会开始尝试找到合适的配对，目标是撮合一个两方获胜机会都为50%的游戏。

第1步：确定你的实力：

假设你是单排(solo)，就直接使用你的个人匹配分（也就是elo值）
假设你是预先组队的，你的匹配分是你队伍的平均分。

第2步：确定你合适匹配对手：

首先，系统会基于你的rating值，给你匹配跟你很相近的玩家（设置一个正负偏差值）。系统会尝试平衡这个队伍，尽量使两方的获胜机会都为50%。在绝大多数时间，误差会在3%之内——类似50/50，49/51，48/52。如果匹配不到，系统会放宽匹配的条件，给你一些不是那么完美的匹配。

新手会得到一些特殊的保护，通常新手仅仅会匹配到其它新手（在成熟的server里，这个比例达到了99%+。除非这个新手和一个高级玩家朋友预先组队）

第3步：结果计算：

可以采用elo算法去计算你和对手的下一次积分。

0x04资料

ELO详情

https://www.zhihu.com/question/41011877

TrueSkill 介绍

http://www.cnblogs.com/baiting/p/5591614.html

wh1t3zer