• 丰搜首页
• 文档中心
• 视频中心
• 丰搜贴吧
• 问题集锦
• 更多功能

选择显示字体大小

• 最大
• 较大
• 标准

游戏ai中的pathfollowing算法实现

游戏ai中的pathfollowing算法实现
作者cleverpig

版权声明：任何获得matrix授权的网站，转载时请务必以超链接形式标明文章原始出处和作者信息及本声明
作者:cleverpig(http://www.matrix.org.cn/blog/cleverpig)
原文:http://www.matrix.org.cn/resource/article/43/43931_ai_pathfollowing.html
关键字:pathfollowing,ai,java


序言：

  pathfollowing算法顾名思义就是路径跟随的意思，使物体的运动按照定义好的路径循环往复。这个算法广泛的应用在游戏开发中，比如大家都玩过的pcman和超级马里奥中的怪物们就是遵循着由“原点”组成的道路行走。

   本人在阅读o'reilly的《ai for game developer》一书时，偶尔读到，顿时心动，便用代码实现之，与好友们共享。

一、路径跟随算法介绍：

  1.首先，如图计算物体在地图中周围8个方向上的权重值。即取出地图数组中物体当前位置周围8个数组成员的数值作为计算权重值的基数。


  2.根据物体当前的运动方向，更新周围8个方向上的权重值：
          a.与物体运动同向的方向权重+2；
          b.在与物体运动同向的方向两侧的两个方向权重各+1；
          c.与物体运动方向相反的方向权重-1；
          d.其它方向权重值保持原值。

  3.求出8个方向中权重值最大的那个方向作为物体运动的方向，并按照此方向将物体移动到下一个位置。

  4.回到第1步重复执行。

二、算法简要分析：

  该算法的优点：

  1.实现简单，适用于没有gamecanvas和sprite的midp1.0；
  2.运行速度优于在midp2.0中使用碰撞检测的方法实现的物体行走路径和a*算法。
  
  该算法缺点：

  物体只能呆板的在规定的运动路径上有规则的运动，缺乏随意性。

三、代码分析：

核心代码-pathfollowing.java

package cn.org.matrix.gmatrix.practice.arithmetic.pathfollowing;

/**
 * 路径跟随算法：
 * 1.首先，计算物体在地图中周围8个方向上的权重值。
 * 即取出地图数组中物体当前位置周围8个数组成员的数值作为计算权重值的基数。
 * 2.根据物体当前的运动方向，更新周围8个方向上的权重值：
 *                 a.与物体运动同向的方向权重+2；
 *                 b.在与物体运动同向的方向两侧的两个方向权重各+1;
 *                 c.与物体运动方向相反的方向权重-1
 *                 d.其它方向权重值保持原值
 * 3.求出8个方向中权重值最大的那个方向作为物体运动的方向，并按照此方向将物体移动到下一个位置。
 * 4.回到第1步重复执行。
 * 
 * 该算法的优点：
 * 1.实现简单，适用于没有gamecanvas和sprite的midp1.0；
 * 2.运行速度优于在midp2.0中使用碰撞检测的方法实现的物体行走路径。
 * 
 * 该算法缺点：
 * 物体只能呆板的在规定的运动路径上有规则的运动，缺乏随意性。
 * @author cleverpig
 *
 */
public class pathfollowing{
        private int[] map=null;
        private int currentrow=0,currentcol=0;
        private int direction=1;
        private int rows=0,cols=0;
        private directionweight weight=null;
        //单元权重值
        private final int unit_weight=10;
        //主增量
        private final int best_increasement=2;
        //次增量
        private final int better_increasement=1;
        //负增量
        private final int minus_increasement=-1;
        
        /**
         * 构造方法
         * @param map 地图数组：数组元素中为1，表示该元素对应的地图位置为物体行走路径
         * @param rows 地图总行数
         * @param cols 地图总列数
         * @param currentrow 当前物体在地图中的行号
         * @param currentcol 当前物体在地图中的列号
         * @param direction 当前物体的运动方向
         */
        public pathfollowing(int[] map,
                        int rows,int cols,
                        int currentrow,int currentcol,
                        int direction){
                this.map=map;
                this.rows=rows;
                this.cols=cols;
                this.currentrow=currentrow;
                this.currentcol=currentcol;
                this.weight=new directionweight();
                this.direction=direction;
                system.out.println("启始行号:"+currentrow+" 启始列号:"+currentcol);
        }
        
        /**
         * 获得当前位置的map数值
         * @param row 当前行号
         * @param col 当前列号
         * @return map数组对应的值,如果已经出边界,则返回-1
         */
        private int getmapvalue(int row,int col){
                //如果map数组对应的下标已经出边界,则返回-1作为权重值
                if (row<0col<0row>=rowscol>=cols){
                        return -1;
                }
                //否则返回地图数组中代表该位置的数组成员的数值
                else{
                        system.out.println(&quot;当前行号:&quot;+row+&quot; 当前列号:&quot;+col);
                        return map&#91;row*cols+col&#93;;
                }
        }
        
        /**
         * 计算各个方向的权重初始值。
         * 即取出地图数组中物体当前位置周围8个数组成员的数值作为计算权重值的基数
         */
        private void calculateinitialweight(){
                int weightvalue=0;
                //检查边界，并为当前位置的周围8个方向赋予权重值
                //处理up
                weightvalue=getmapvalue(currentrow-1,currentcol)*unit_weight;
                weight.setweight(directionweight.up,weightvalue);
                        
                //处理左侧（left、left_up、left_down）
                weightvalue=getmapvalue(currentrow,currentcol-1)*unit_weight;
                weight.setweight(directionweight.left,weightvalue);
                weightvalue=getmapvalue(currentrow-1,currentcol-1)*unit_weight;
                weight.setweight(directionweight.left_up,weightvalue);
                weightvalue=getmapvalue(currentrow+1,currentcol-1)*unit_weight;
                weight.setweight(directionweight.left_down,weightvalue);
                
                //处理down
                weightvalue=getmapvalue(currentrow+1,currentcol)*unit_weight;
                weight.setweight(directionweight.down,weightvalue);
                                
                //处理右侧(right,right_up,right_down)
                weightvalue=getmapvalue(currentrow,currentcol+1)*unit_weight;
                weight.setweight(directionweight.right,weightvalue);
                weightvalue=getmapvalue(currentrow-1,currentcol+1)*unit_weight;
                weight.setweight(directionweight.right_up,weightvalue);
                weightvalue=getmapvalue(currentrow+1,currentcol+1)*unit_weight;
                weight.setweight(directionweight.right_down,weightvalue);
        }
        
        /**
         * 根据物体运动方向更新各个方向的权重值:
         * 1.与物体运动同向的方向权重+2；
         * 2.在与物体运动同向的方向两侧的两个方向权重各+1;
         * 3.与物体运动方向相反的方向权重-1
         * 4.其它方向权重值保持原值
         */
        private void updateweight(){
                //由于受方向影响，更新各个受影响方向的权重值
                switch(direction){
                case directionweight.up:
                        weight.addweight(directionweight.up,best_increasement);
                        weight.addweight(directionweight.left_up,better_increasement);                        
                        weight.addweight(directionweight.right_up,better_increasement);
                        weight.addweight(directionweight.down,minus_increasement);
                        break;
                case directionweight.left_up:
                        weight.addweight(directionweight.left_up,best_increasement);
                        weight.addweight(directionweight.left,better_increasement);                        
                        weight.addweight(directionweight.up,better_increasement);
                        weight.addweight(directionweight.right_down,minus_increasement);
                        break;
                case directionweight.left:
                        weight.addweight(directionweight.left,best_increasement);
                        weight.addweight(directionweight.left_up,better_increasement);                        
                        weight.addweight(directionweight.left_down,better_increasement);
                        weight.addweight(directionweight.right,minus_increasement);
                        break;
                case directionweight.left_down:
                        weight.addweight(directionweight.left_down,best_increasement);
                        weight.addweight(directionweight.left,better_increasement);                        
                        weight.addweight(directionweight.down,better_increasement);
                        weight.addweight(directionweight.right_up,minus_increasement);
                        break;
                case directionweight.down:
                        weight.addweight(directionweight.down,best_increasement);
                        weight.addweight(directionweight.left_down,better_increasement);                        
                        weight.addweight(directionweight.right_down,better_increasement);
                        weight.addweight(directionweight.up,minus_increasement);
                        break;
                case directionweight.right_down:
                        weight.addweight(directionweight.right_down,best_increasement);
                        weight.addweight(directionweight.right,better_increasement);                        
                        weight.addweight(directionweight.down,better_increasement);
                        weight.addweight(directionweight.left_up,minus_increasement);
                        break;
                case directionweight.right:
                        weight.addweight(directionweight.right,best_increasement);
                        weight.addweight(directionweight.right_up,better_increasement);                        
                        weight.addweight(directionweight.right_down,better_increasement);
                        weight.addweight(directionweight.left,minus_increasement);
                        break;
                case directionweight.right_up:
                        weight.addweight(directionweight.right_up,best_increasement);
                        weight.addweight(directionweight.right,better_increasement);                        
                        weight.addweight(directionweight.up,better_increasement);
                        weight.addweight(directionweight.left_down,minus_increasement);
                        break;
                }
        }
        
        /**
         * 求出8个方向中权重值最大的那个方向，作为物体运动的方向，并将物体移动到下一个位置
         */
        private void move(){
                //计算8个方向的权重值中最大的那个方向
                int maxweightdirection=weight.getdirectionofmaxweight();
                //将最大的方向作为当前物体的移动方向
                direction=maxweightdirection;
                
                //对当前物体进行移动
                switch(direction){
                case directionweight.up:
                        currentrow--;
                        break;
                case directionweight.left_up:
                        currentrow--;
                        currentcol--;
                        break;
                case directionweight.left:
                        currentcol--;
                        break;
                case directionweight.left_down:
                        currentrow++;
                        currentcol--;
                        break;
                case directionweight.down:
                        currentrow++;
                        break;
                case directionweight.right_down:
                        currentrow++;
                        currentcol++;
                        break;
                case directionweight.right:
                        currentcol++;
                        break;
                case directionweight.right_up:
                        currentrow--;
                        currentcol++;
                        break;
                }
        }
        
        /**
         * 执行路径跟随
         */
        public void following(){
                //计算当前位置周围8个方向的权重值
                calculateinitialweight();
                //根据物体的运动方向，更新当前位置周围8个方向的权重值
                updateweight();
                system.out.println(weight);
                //求出8个方向中权重值最大的那个方向，作为物体运动的方向，并将物体移动到下一个位置
                move();
        }

        public int getcurrentrow() {
                return currentrow;
        }

        public void setcurrentrow(int currentrow) {
                this.currentrow = currentrow;
        }

        public void setcurrentcol(int currentcol) {
                this.currentcol = currentcol;
        }

        public int getcurrentcol() {
                return currentcol;
        }

        public int getrows() {
                return rows;
        }

        public int getdirection() {
                return direction;
        }
}

辅助类：directionweight .java和state.java

package cn.org.matrix.gmatrix.practice.arithmetic.pathfollowing;

/**
 * 权重类：记录并计算各个方向的权重
 * @author cleverpig
 *
 */
public class directionweight {
        //8个方向
        public static final int left_up=0,up=1,right_up=2,left=3,
                                        right=4,left_down=5,down=6,right_down=7;
        //8个方向上的权重值
        private int[] weight=new int[8];
        public static final string[] direction_str={"左上","上","右上","左","右",
                "左下","下","右下"};
        /**
         * 返回权重值数组
         * @return
         */
        public int[] getweight() {
                return weight;
        }
        
        /**
         * 返回某个方向上的权重值
         * @param direction
         * @return
         */
        public int getweight(int direction){
                return this.weight[direction];
        }
        
        /**
         * 设置8个方向上的权重值
         * @param weight 8个方向上的权重值数组
         */
        public void setweight(int[] weight) {
                this.weight = weight;
        } 
        
        /**
         * 设置某个方向上的权重值
         * @param direction 方向
         * @param weight 权重值
         */
        public void setweight(int direction,int weight){
                this.weight[direction]=weight;
        }
        
        /**
         * 增加某个方向上的权重值
         * @param direction 方向
         * @param detaweight 权重值增量
         */
        public void addweight(int direction,int detaweight){
                this.weight[direction]+=detaweight;
        }
        
        /**
         * 返回8个方向的权重值中最大的那个方向
         * @return 8个方向的权重值中最大的那个方向
         */
        public int getdirectionofmaxweight(){
                int index=-1;
                int max=-1;
                for(int i=0;i<weight.length;i++){
                        if (max<weight&#91;i&#93;){
                                max=weight&#91;i&#93;;
                                index=i;
                        }
                }
                system.out.println(&quot;8个方向的权重值中最大值为:&quot;+max+&quot; 方向id=&quot;+index+&quot; 方向为&quot;+direction_str&#91;index&#93;);
                return index;
        }
        
        public string tostring(){
                return weight&#91;0&#93;+&quot;,&quot;+weight&#91;1&#93;+&quot;,&quot;+weight&#91;2&#93;+&quot;,\n&quot;
                +weight&#91;3&#93;+&quot;,&quot;+weight&#91;4&#93;+&quot;,\n&quot;
                +weight&#91;5&#93;+&quot;,&quot;+weight&#91;6&#93;+&quot;,&quot;+weight&#91;7&#93;;
        }
}

package cn.org.matrix.gmatrix.practice.arithmetic.pathfollowing;

/**
 * 状态类：用于描述程序运行状态
 * @author cleverpig
 *
 */
public class state {
        //初始化状态
        public static int initial_state=0;
        //开始状态
        public static int start_state=1;
        //终止状态
        public static int terminal_state=2;
        //出错状态
        public static int wrong_state=-1;
        
        private int state=0;

        public state(){
                state=0;
        }
        public int getstate() {
                return state;
        }

        public void setstate(int state) {
                this.state = state;
        }
}

四、代码演示：

  本人仍然使用了applet进行pathfollowing算法的演示。
  下图为applet运行界面：


  以下是applet的使用方法：
  1.首先使用鼠标左键在黄色的画板上画出红色的物体运动路径（可封闭、也可不封闭），使用鼠标右键可以清除鼠标所点的位置；
  2.待路径画好后，使用鼠标点选路径上的一个格作为物体运动起始位置的选择，点击右侧按钮中的“设置起点”确认物体运动起始位置;
  3.点击右侧按钮中的“运行”，启动路径跟随算法，这时可以看到代表物体的一个绿色的方格在运动路径中按照算法计算的结果有规则地行走;
  4.点击右侧按钮中的“停止”，终止路径跟随算法的执行，绿色方格停止运动;
  5.点击右侧按钮中的“清除画板”清空画板，以便重新设计物体的运动路径。

  程序运行画面：


五、源代码下载：

[下载文件]

资源
·matrix-java开发者社区:http://www.matrix.org.cn/
·gmatrix和游戏开发论坛:http://www.matrix.org.cn/topic.shtml?forumid=35

 

关键字 本文所属关键字

相关 与本文相关文章

分类 所有文章关键字导航

标准 网站致力的规范