H5版俄罗斯方块游戏开发：游戏的AI算法

03月

324 0 0

　　点击tetris.html, 在浏览器上运行(由于HTML5程序, 最好在Chrome/Firefox上运行)。

　　算法分析:

　　核心算法参考了如下博文:

传统规则俄罗斯方块AI技术介绍
控制台彩色版带AI的『俄罗斯方块』

　　本程序也采用改进的Pierre Dellacherie算法(只考虑当前方块)。

　　其对局面的评估, 采用6项指标:

　　1)Landing Height(下落高度): The height where the piece is put (= the height of the column + (the height of the piece / 2))

　　2)Rows eliminated(消行数): The number of rows eliminated。

　　3)Row Transitions(行变换): The total number of row transitions.A row transition occurs when an empty cell is adjacent to a filled cell on the same row and vice versa.

　　4)Column Transitions(列变换): The total number of column transitions.A column transition occurs when an empty cell is adjacent to a filled cell on the same column and vice versa.

　　5)Number of Holes(空洞数): A hole is an empty cell that has at least one filled cell above it in the same column.

　　6)Well Sums(井数): A well is a succession of empty cells such that their left cells and right cells are both filled.

　　对各个指标进行加权求和, 权重系数取自经验值:

-4.500158825082766
2 　　3.4181268101392694
3 　　-3.2178882868487753
4 　　-9.348695305445199
5 　　-7.899265427351652
6 　　-3.3855972247263626

tetris_base.js: 公共的数据结构, 包括方块定义和方块池等
- tetris_ai.js: 具体定义了AI的核心算法和数据结构。
  - tetris_game。js: 是整个程序的展示和驱动。
  　　这边主要讲讲tetris_ai.js这个代码文件, 里面有三个重要的类, MoveGenerator, Evaluator, AIStrategy.
  
  　　MoveGenerator用于生成各个可行落点以及对应的路径线路：
  1. /*
    - 　　* @brief 走法生成器
      - 　　*/
        function MoveGenerator() {
        }
        
        MoveGenerator.prototype.generate = function(tetrisUnit, shape) {
        
        var keymapFunc = function(x, y, idx) {
        return + x + : + y + : + idx;
        }
        
        var moveMapFunc = function(step) {
        return {x:step.x, y:step.y, idx:step.idx};
        }
        
        var results = [];
        
        var boards = tetrisUnit.boards;
        var rownum = tetrisUnit.row;
        var colnum = tetrisUnit.col;
        var shapeArrs = shape.shapes;
        
        var occupy = {}
        
        var actionQueues = [];
        actionQueues.push({x:shape.x, y:shape.y, idx:shape.idx, prev:-1});
        occupy[keymapFunc(shape.x, shape.y, shape.idx)] = true;
        
        var head = 0;
        while ( head < actionQueues.length ){
        var step = actionQueues[head];
        
        // 1). 向左移动一步
        var tx = step.x - 1;
        var ty = step.y;
        var tidx = step.idx;
        if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) {
        var key = keymapFunc(tx, ty, tidx);
        if ( !occupy.hasOwnProperty(key) ) {
        actionQueues.push({x:tx, y:ty, idx:tidx, prev:head});
        occupy[key] = true;
        }
        }
        
        // 2). 向右移动一步
        tx = step.x + 1;
        ty = step.y;
        tidx = step.idx;
        if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) {
        var key = keymapFunc(tx, ty, tidx);
        if ( !occupy.hasOwnProperty(key) ) {
        actionQueues.push({x:tx, y:ty, idx:tidx, prev:head});
        occupy[key] = true;
        }
        }
        
        // 3). 旋转一步
        tx = step.x;
        ty = step.y;
        tidx = (step.idx + 1) % 4;
        if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) {
        var key = keymapFunc(tx, ty, tidx);
        if ( !occupy.hasOwnProperty(key) ) {
        actionQueues.push({x:tx, y:ty, idx:tidx, prev:head});
        occupy[key] = true;
        }
        }
        
        // 4). 向下移动一步
        tx = step.x;
        ty = step.y + 1;
        tidx = step.idx;
        if ( tetrisUnit.checkAvailable(tx, ty, shapeArrs[tidx]) ) {
        var key = keymapFunc(tx, ty, tidx);
        if ( !occupy.hasOwnProperty(key) ) {
        actionQueues.push({x:tx, y:ty, idx:tidx, prev:head});
        occupy[key] = true;
        }
        } else {
        
        // *) 若不能向下了, 则为方块的一个终结节点.
        var tmpMoves = [];
        tmpMoves.push(moveMapFunc(step));
        var tprev = step.prev;
        while ( tprev != -1 ) {
        tmpMoves.push(moveMapFunc(actionQueues[tprev]));
        tprev = actionQueues[tprev].prev;
        }
        tmpMoves.reverse();
        
        results.push({last:step, moves:tmpMoves});
        }
        head++;
        }
        return results;
        
        }
  复制代码
  　　Evaluator类, 则把之前的评估因素整合起来：
  1. function Evaluator() {
    - }
      - Evaluator.prototype.evaluate = function(boards) {
        }
        
        function PierreDellacherieEvaluator() {
        }
        
        PierreDellacherieEvaluator.prototype = new Evaluator();
        PierreDellacherieEvaluator.prototype.constructor = PierreDellacherieEvaluator;
        
        PierreDellacherieEvaluator.prototype.evaluate = function(boards, shape) {
        return (-4.500158825082766) * landingHeight(boards, shape) // 下落高度
        + (3.4181268101392694) * rowsEliminated(boards, shape) // 消行个数
        + (-3.2178882868487753) * rowTransitions(boards) // 行变换
        + (-9.348695305445199) * colTransitions(boards) // 列变化
        + (-7.899265427351652) * emptyHoles(boards) // 空洞个数
        + (-3.3855972247263626) * wellNums(boards); // 井数
        }
  复制代码
  　　AIStrategy整合了落地生成器和评估函数, 用于具体决策最优的那个落地点, 以及行动路线。
  1. function AIStrategy() {
    - 　　this.generator = new MoveGenerator();
      - 　　this.evalutor = new PierreDellacherieEvaluator();
        }
        
        /*
        * @brief 作出最优的策略
        * @return{dest:{x:{x}, y:{y}, idx:{idx}}, [{action_list}]}
        */
        AIStrategy.prototype.makeBestDecision = function(tetrisUnit, shape) {
        
        var bestMove = null;
        var bestScore = -1000000;
        
        // 1) 生成所有可行的落点, 以及对应的路径线路
        var allMoves = this.generator.generate(tetrisUnit, shape);
        
        // 2) 遍历每个可行的落点, 选取最优的局面落点
        for ( var i = 0; i < allMoves.length; i++ ) {
        var step = allMoves[i].last;
        
        var shapeArrs = shape.shapes;
        var bkBoards = tetrisUnit.applyAction2Data(step.x, step.y, shapeArrs[step.idx]);
        
        // 2.1) 对每个潜在局面进行评估
        var tscore = this.evalutor.evaluate(bkBoards, {x:step.x, y:step.y, shapeArr:shapeArrs[step.idx]});
        
        // 2.2) 选取更新最好的落点和路径线路
        if ( bestMove === null tscore > bestScore ) {
        bestScore = tscore;
        bestMove = allMoves[i].moves;
        }
        }
        
        // 3) 返回最优可行落点, 及其路径线路
        return {score:bestScore, action_moves:bestMove};
        
        }
  复制代码
  　　注: 该代码注释, 诠释了决策函数的整个流程。
  
  　　效果评估：
  
  　　该AI算法的效果不错, 在演示模式下, 跑了一晚上, 依旧好好的活着。这也满足了之前想要的需求和功能。
  
  　　总结：
  
  　　该算法的权重系数采用了经验值。当然了, 也可以借助模拟退火算法来学习参数, 不过由于游戏本身的不确定性/偶然性影响, 收敛的效果并非如预期那么好。有机会再讲讲。
  
  　　无论怎么样, 该AI可以扮演一个合格的麻烦制造者, 让游戏充满趣味和挑战性。勿忘初心, lets go！！！
  
  　　写在最后：
  
  　　如果你觉得这篇文章对你有帮助, 请小小打赏下。其实我想试试, 看看写博客能否给自己带来一点小小的收益。无论多少, 都是对楼主一种由衷的肯定。
  
  　　相关阅读：H5版俄罗斯方块游戏开发：需求分析和框架实现
  
  锐亚教育，游戏开发论坛|游戏制作人|游戏策划|游戏开发|独立游戏|游戏产业|游戏研发|游戏运营| unity|unity3d|unity3d官网|unity3d 教程|金融帝国3|8k8k8k|mcafee8.5i|游戏蛮牛|蛮牛 unity|蛮牛

标签：魔兽开发经验爬坑游戏开发者开发技术游戏开发论坛

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！