文档章节

多人pvp玩法匹配算法的简单实现

1杯空气
 1杯空气
发布于 2016/10/08 23:28
字数 1699
阅读 773
收藏 2
点赞 0
评论 0

    在游戏中经常有多人参与的对战玩法,挺高玩家的互动乐趣,如data2,lol,守望先锋等竞技型游戏所有的战斗都是典型的多人匹配对战模式,如何保证对战的双方的平衡性,和公平性,就很重要。如lol等强竞技型的游戏采用的是ELO算法来实现的,比较复杂(有兴趣可以可以了解下ELO算法)。但对于手游特别是rpg类型的手游在公平性要求不是很高的情况下,简化了一些指标从而保证快速的开启一场战斗。

    为保证一定的公平性,以及如何去匹配出一组对战阵营,我们给每个对战的玩家赋予一个积分的属性。以此来作为匹配的依据。当然为进一步增加公正性,可以加入一些其他的衡量属性,如战力,ip地址(防止组队开黑)等等。每场战斗基于战斗结果如果该玩家是获胜方,增加其积分值,反之减少(为避免出现负积分情况,失败了则增加少量积分值比较合适些)。

下面是主要代码的实现:

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;
    }
}

运行结果:

当前正在匹配中的玩家:20837
一共整合出:4155个匹配组
共创建了:2077个战场
耗时:614毫秒!
当前正在匹配中的玩家:16310
一共整合出:3251个匹配组
共创建了:1625个战场
耗时:836毫秒!

 

© 著作权归作者所有

共有 人打赏支持
1杯空气
粉丝 3
博文 3
码字总数 4907
作品 0
海淀
程序员
手游后台PVP系统网络同步方案总结

概述   PVP系统俨然成为现在新手游的上线标配,手游Pvp系统体验是否优秀,很大程度上决定了游戏的品质。从最近半年上线的新手游来看,越来越多的游戏把核心玩法重心已经放在pvp多人游戏中,...

sharep ⋅ 2017/04/26 ⋅ 0

腾讯WeTest为Unity开发者打造免费自动化测试框架——20个体验资格免费发放

关于GAutomator为了保证线上游戏品质,保障玩家的游戏体验,上线前的测试工作是游戏开发的重要一环。要做好测试工作,往往需要重复测试一些重度游戏场景,例如:新手引导、pvp对战、多人团战...

负荷 ⋅ 2016/11/10 ⋅ 0

移动测试中游戏和应用的不同之处

随着智能设备的普及和移动互联网的兴起,各家互联网巨头纷纷在往移动端布局和转型,同时初创的移动互联网公司也都盯着这个市场希望分一杯羹。在这个大环境下,互联网的重心已经慢慢从Web端转...

fiawfo ⋅ 2017/03/14 ⋅ 0

java面试冷知识 string的indexof

java中String的玩法还真多,本文介绍的的是indexof这个查找字串的实现。 说到查找子串,最原始的算法就是先找到第一个字符是匹配的,然后从这个字符串开始往后比对,直到和子串完全匹配。很多...

xpbob ⋅ 2016/04/16 ⋅ 0

《欢乐坦克大战》微信小游戏开发总结

欢迎大家前往云+社区,获取更多腾讯海量技术实践干货哦~ 作者:木桶 前言 《欢乐坦克大战》是一款支持3V3实时对战并首批参与上线的微信小游戏中的作品。因为该游戏为微信小游戏中的重度之作,...

云加社区 ⋅ 01/04 ⋅ 0

《欢乐坦克大战》微信小游戏开发总结

欢迎大家前往云+社区,获取更多腾讯海量技术实践干货哦~ 作者:木桶 前言 《欢乐坦克大战》是一款支持3V3实时对战并首批参与上线的微信小游戏中的作品。因为该游戏为微信小游戏中的重度之作,...

⋅ 01/04 ⋅ 0

韦诺之战 Battle for Wesnoth 1.9.1

韦诺之战 1.9.1 是一个开发测试版,下载地址: Source (311.6MB) Linux Windows (288.2MB) MacOSX (311.7MB) and more. 韦诺之战是一款主要基于 C++ 的回合制SLG游戏, 使用SDL作为图形引擎,...

红薯 ⋅ 2010/09/18 ⋅ 1

Battle for Wesnoth 1.9.2 开发版发布

韦诺之战是一款主要基于 C++ 的回合制SLG游戏, 使用SDL作为图形引擎, 目前已经一直到了Windows、Linux、FreeBSD和Mac OS X等多种操作系统上, 有16种不同部族, 可以进行单机战役、多人游戏. 与...

红薯 ⋅ 2010/11/08 ⋅ 0

用TensorFlow.js实现人体姿态估计模型(上)

Google Creative Lab发布了基于TensorFlow.js的PoseNet模型。 TensorFlow.js:https://js.tensorflow.org/ PoseNet:https://github.com/tensorflow/tfjs-models/tree/master/posenet Demo:......

GEETEST极验 ⋅ 05/22 ⋅ 0

Wesnoth 1.10.4/1.11.0 发布,韦诺之战

Wesnoth 1.10.4 (stable): Source (326.8MB) Linux Windows (300.6MB) MacOSX (328.1MB) and more. Wesnoth 1.11.0 (development): Source (334.1MB) Linux Windows (307.8MB) MacOSX (334.4......

oschina ⋅ 2012/08/28 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

面试-JVM 内存结构

JVM 内存结构

秋日芒草 ⋅ 7分钟前 ⋅ 0

马氏距离与欧氏距离

马氏距离 马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度。 如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧氏距离,如果协方差矩阵为对角阵,则其也...

漫步当下 ⋅ 30分钟前 ⋅ 0

聊聊spring cloud的RequestRateLimiterGatewayFilter

序 本文主要研究一下spring cloud的RequestRateLimiterGatewayFilter GatewayAutoConfiguration @Configuration@ConditionalOnProperty(name = "spring.cloud.gateway.enabled", matchIfMi......

go4it ⋅ 今天 ⋅ 0

Spring JavaConfig 注解

JavaConfig注解允许开发者将Bean的定义和配置放在Java类中。它是除使用XML文件定义和配置Bean外的另一种方案。 配置: 如一个Bean如果在XML文件可以这样配置: <bean id="helloBean" class="...

霍淇滨 ⋅ 今天 ⋅ 0

Spring clound 组件

Spring Cloud技术应用从场景上可以分为两大类:润物无声类和独挑大梁类。 润物无声,融合在每个微服务中、依赖其它组件并为其提供服务。 Ribbon,客户端负载均衡,特性有区域亲和、重试机制。...

英雄有梦没死就别停 ⋅ 今天 ⋅ 0

Confluence 6 重新获得站点备份文件

Confluence 将会创建备份,同时压缩 XML 文件后存储熬你的 <home-directory>/backups> 目录中。你需要自己访问你安装的 Confluence 服务器,并且从服务器上获得这个文件。 运行从 Confluence...

honeymose ⋅ 今天 ⋅ 0

informix的常用SQL语句

1、创建数据库 eg1. 创建不记录日志的库testdb,参考语句如下: CREATE DATABASE testdb; eg2. 创建带缓冲式的记录日志的数据库testdb(SQL语句不一定在事务之中,拥有者名字不被用于对象的解...

wangxuwei ⋅ 今天 ⋅ 0

matplotlib画图

最简单的入门是从类 MATLAB API 开始,它被设计成兼容 MATLAB 绘图函数。 from pylab import *from numpy import *x = linspace(0, 5, 10)y = x ** 2figure()plot(x, y, 'r')...

Dr_hu ⋅ 今天 ⋅ 0

RabbitMQ学习以及与Spring的集成(三)

本文介绍RabbitMQ与Spring的简单集成以及消息的发送和接收。 在RabbitMQ的Spring配置文件中,首先需要增加命名空间。 xmlns:rabbit="http://www.springframework.org/schema/rabbit" 其次是模...

onedotdot ⋅ 今天 ⋅ 0

JAVA实现仿微信红包分配规则

最近过年发红包拜年成为一种新的潮流,作为程序猿对算法的好奇远远要大于对红包的好奇,这里介绍一种自己想到的一种随机红包分配策略,还请大家多多指教。 算法介绍 一、红包金额限制 对于微...

小致dad ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部