前言:
首先, 我得假正经的郑重宣布: "取这个名字, 并非卖萌", ^_^. 萌萌哒的世界, 大叔你不懂, hoho.
言归正传, 记得我还在读大学的时候, 学院老师和某社团搞了一个"老鼠吃大米"的游戏比赛, 其平台是基于J2SE实现, 意在推广JAVA语言, 门槛不高, 活动反响好. 游戏重在参与, 寓教于乐, 很happy!!!
本文是想借这个"老鼠吃大米"这个游戏, 来讲述下简易的游戏对战平台的搭建以及设计思路, 顺便附带讲解下"小老鼠"游戏AI的设计.
简介:
让我们先来介绍下游戏规则和平台功能.
游戏的场景和规则很简单:
1).迷宫中散布着大米
2).小白鼠行动选项: {上, 下, 左, 右, 吃, 休息}
目标:在规定的时间范围内, 吃到最多大米的小鼠获胜.
参赛的玩家多且数量不确定, 采用单局群K(玩家数量不确定,灵活)+淘汰赛制.
玩家需要提交,实现特定接口的JAVA实现类的代码即可.
实现:
运行平台是个J2SE的桌面应用, 其实现本身极富技术含量的, 让我们来一一道来.
1).接入游戏平台
玩家的AI如何接入平台? 有约束不?
没有约束是不可能, 但最小化限制和约定, 是一个好平台应该追求的.
运行平台负责, 比赛组织和游戏判定. 而游戏玩家扮演好比赛者的角色.
鉴于此, 我们引入接口类, 用于描述小鼠AI的决策行动.
定义具体行为:
public enum MoveAction {LEFT,// 左RIGHT,// 右UP,// 上DOWN,// 下EAT,// 吃SLEEP,// 休息NONE// 无效}
注: 该枚举类, 描述了小鼠每一次决策时, 能执行的动作类型.
决策定义类:
public interface BaseMouse {/*** @brief返回代表老鼠的名称，与申请的保持一致*/public String getName();/*** @brief决策当前的行动* * @param x小鼠的x坐标* @param y小鼠的y坐标* @param maze迷宫地图0: 平地, 1: 障碍物, 2: 大米* @param others其他小老鼠的信息列表(x, y, score)*/public MoveAction execute(int x, int y, int[][] maze, List<MouseInfo> others);}
注: 函数execute是玩家的具体类中需要好好实现的.
玩家实现该BaseMouse类后, 提交该java源码即可.
由于java的类加载机制,只要把类文件编译后的class文件, 放入桌面应用的classpath中去. 运行平台就能加载和运行该游戏AI, 并进行模拟比赛.
2).游戏规则的约束实现
游戏PK环节中, 其主逻辑可以描述如下:
for ( i = 0; i < max_step; i++ ) {// 在1秒内, 执行完各个游戏AI的决策函数foreach ( player in player list ) {// 执行决策函数action <- player.execute(x, y, maze, list)actions <- (player, action)}// 更新并作用游戏game.update(actions);}
这边的难点比较隐蔽, 是对接口调用的时间约束.
尽管我们对数据的输入和输出做了控制和限定, 看上去一切完美. 但接口的实现方, 可能因某个错误逻辑, 导致内部调用超时, 甚至死循环. 这会导致外部的主循环阻滞和无法及时响应.
框架层, 如何对用户实现的函数做个超时控制/约束呢?
Java并发库的Future模式可以轻松解决这个问题(做Java开发的同学真幸福).
ExecutorService executor = Executors.newFixedThreadPool(20);// 超时增强控制FutureTask<String> task = new FutureTask<String>(new Callable<String>() {@Overridepublic String call() throws Exception {return "Hi";}});executor.execute(task);// 结果聚合处理try {// 在1秒的限定内， 等待结果返回/超时String result = task.get(1, TimeUnit.SECONDS);// Do thing about result} catch (InterruptedException | ExecutionException | TimeoutException e) {task.cancel(true);}
在Callable回调函数中, 放置用户/玩家的execute函数调用即可.
框架代码会增强并发计算能力, 其代码逻辑比这更复杂一些.
3).抽签和比赛安排
不像世界杯, 限定在32支队伍. 游戏本身参与的用户数不确定, 给安排比赛带来麻烦.
按2进1晋级这种模式, 有些幸运的玩家可以首轮轮空, 直接晋级. 略微有些不好的地方是, 对于一个小竞赛而言,总场次多了一点.
利好的是单局群K, 其人数配置比较灵活. 数量配得多点, 可以加速游戏的收敛进程.
把比赛过程分为: 小组赛和淘汰赛.小组赛的每局玩家数相对灵活, 范围选为[k, 2k), 每局选取第一名晋级.淘汰赛的每局玩家数固定为k, 第一名晋级. k个第一名进行下一轮的晋级, 直至总决赛. 对于用户总数为M.寻找n使得: k*k^n <= M < 2k*k^n(M>=2, k>=2).首轮总共 k^n 场次, 每场人数灵活设定在[k, 2k)之间.比如参与用户数为M=31, 晋级比k=4, 则n=1, 满足 4*4^1<=31< 8*4^2.首轮共4场, 每场人数在[4, 8)之间,比如按(8,8,8,7)分配.晋级赛一轮, 即为总决赛.
注: 这边只是提供了一种思路, 感觉这边比赛安排这块, 是个可深挖的切入点.
游戏AI:
这边的老鼠AI, 需要用户/玩家去设计实现. 最基本的实现方式, 贪心法. 每次最短路径到最近的大米.
具体的算法: 可参见之前的博文<谈谈面试--迷宫寻路系列>.
当然贪心策略会步入局部最优的陷阱, 在具体决策时, 需要综合考虑全局的大米分布以及对手的行动.
对对手的行为预测分析, 以及对大米分布综合分析, 将决定用户最终的得分.
不管怎么样, 该游戏AI设计的三个层次:
1). 决策
2). 路径规划
3). 移动执行
当目标状态发生变化时, 则立即决策下一个目标. 选定一个目标后, 就坚定地执行该任务, 直至目标完成或变化.尽量避免行动过程中的决策震荡.
由于用户/玩家的众多, 以及策略的相克. 游戏充满了偶然性, 就像石头剪子布一样, 想多了输, 想少了输. However, Just a Game! Enjoy Happy.
总结:
其实该平台可挖掘的点很多, 很多都不能一一细说. 我希望将来我能实现一个类似的网页版游戏对战平台,就像腾讯的"在线编程对战游戏--CodeTank"一样.
写在最后：如果你觉得这篇文章对你有帮助, 请小小打赏下. 其实我想试试, 看看写博客能否给自己带来一点小小的收益. 无论多少, 都是对楼主一种由衷的肯定.
