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

选择显示字体大小

• 最大
• 较大
• 标准

游戏ai中a*寻路算法实现

游戏ai中a*寻路算法实现
作者cleverpig

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

文章概要：

很久以前就知道了a*算法，但是从未认真读过相关的文章，也没有看过代码，只是脑子里有个模糊的概念。这次决定从头开始，研究一下这个被人推崇备至的简单方法，作为学习人工智能的开始。
所以本人编写了一个a* pathfinding的算法，并制作了一个applet作为算法测试和演示的平台，希望能够与喜欢制作游戏和玩游戏的fans共享ai带来的快乐！

一、a*寻路算法简介：

详细的算法描述见：http://www.matrix.org.cn/thread.shtml?topicid=21385&forumid=4 。

下图为applet运行结果截屏：


二、a*寻路算法实现：

下面是全部的代码列表：其中astar.java是实现a*算法的核心类。

node.java：地图中的节点

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

/**
 * 地图中的节点
 * 按照a*算法：h=f+g,
 * h为从起点a到终点b的评估耗费，
 * g为从起点a，沿着产生的路径，移动到网格上指定方格的移动耗费,
 * f为从网格上那个方格移动到终点b的预估移动耗费
 * @author cleverpig
 *
 */
public class node {
        //从起点a沿着产生的路径移动到当前节点的预估移动耗费
        public int costfromstart=0;
        //从当前节点移动到终点b的预估移动耗费
        public int costtogoal=0;
        //从起点a到终点b的评估耗费
        public int totalcost=0;
        public location location=null;
        public node parent;
        
        public boolean equals(object node){
                if (((node)node).location.equals(location)){
                        return true;
                }
                else{
                        return false;
                }
        }
        
        public string tostring(){
                return "x="+location.x+" y="+location.y+" g="+costfromstart
                +" h="+costtogoal+" f="+totalcost;
        }
        
}

nodelist.java：节点列表：用于开启列表和关闭列表

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

import java.util.vector;
/**
 * 节点列表：用于开启列表和关闭列表
 * @author cleverpig
 *
 */
public class nodelist extends vector{
        /**
         * 
         */
        private static final long serialversionuid = 1l;
//        private vector v=null;
        public nodelist(){
//                v=new vector();
                super();
        }
        
        /**
         * 获得第一个节点（最小的）
         * @return 第一个节点
         */
        public node pop(){
                if (this!=null){
                        node node=(node)this.elementat(0);
                        this.removeelement(node);
                        return node;
                }
                else{
                        return null;
                }
        }
        /**
         * 按照升序添加节点
         * @param node 被添加的节点
         */
        public void addnode(node node){
                if (this.size()==0){
                        this.addelement(node);
                }
                else{
                        for(int i=0;i<this.size();i++){
                                node temp=(node)this.elementat(i);
                                if (temp.totalcost>=node.totalcost){
                                        this.insertelementat(node,i);
                                        return;
                                }
                        }
                        this.addelement(node);
                }
        }
        
        public void sort(){
                if (this.size()==0){
                        return;
                }
                else{
                        for(int i=0;i<this.size()-1;i++){
                                node first=(node)this.elementat(i);
                                node next=(node)this.elementat(i+1);
                                if (first.totalcost>next.totalcost){
//                                        node temp=first;
//                                        first=next;
//                                        next=temp;
                                        this.setelementat(next,i);
                                        this.setelementat(first,i+1);
                                }
                        }
                }
        }
        
        public string tostring(){
                string s=&quot;&quot;;
                for(int i=0;i<this.size();i++){
                        s+=((node)this.elementat(i)).tostring()+&quot;\n&quot;;
                }
                return s;
        }

}

location.java：节点位置对象

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

/**
 * 节点位置对象
 * @author cleverpig
 *
 */
public class location {
        public int x=0;
        public int y=0;
        
        public location(int x,int y){
                this.x=x;
                this.y=y;
        }
        
        public boolean equals(object obj){
                if ((((location)obj).x==x)&&(((location)obj).y==y)){
                        return true;
                }
                else{
                        return false;
                }
        }
        
        public string tostring(){
                return "x="+x+" y="+y;
        }
}

constants.java：定义用于计算预估耗费的常量

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

/**
 * 用于计算预估耗费的常量
 * @author cleverpig
 *
 */
public class constants {
        //nothing
        public static final int nothing = -1;
        //无任何障碍对应cost数组的下标
        public static final int empty = 0;
        //地形1对应cost数组的下标
    public static final int terrain1 = 1;
    //地形2对应cost数组的下标
    public static final int terrain2 = 2;
    //地形3对应cost数组的下标
    public static final int terrain3 = 3;
    //不可穿过的固体对应cost数组的下标
    public static final int solid = 4;
    //起始点对应cost数组的下标
    public static final int start = 5;
    //终点对应cost数组的下标
    public static final int finish = 6;
    //数组的数量
    public static final int numcolors = finish + 1;
}

astar.java：实现a*算法的核心类

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

import java.util.vector;
/**
 * 实现a*算法
 * @author cleverpig
 *
 */
public class astar {
        //地图数组
        int[][] grid=null;
        //路径寻找的开始位置
        location start=null;
        //路径寻找的目的位置
        location goal=null;
        //开启节点列表
        nodelist open=null;
        //关闭节点列表
        nodelist closed=null;
        //预估耗费用的常量
        int[] cost=null;
        //直线单元耗费值
        public static final int linealcost=10;
        //对角线单元耗费值
        public static final int diagonalcost=14;
        //左上
        final int left_top=1;
        //左下
        final int left_bottom=4;
        //右上
        final int right_top=6;
        //右下
        final int right_bottom=8;
        
        public astar(int[][] grid,int[] cost,location start,location goal){
                this.grid=grid;
                this.start=start;
                this.goal=goal;
                open=new nodelist();
                closed=new nodelist();
                this.cost=cost;
        }
        
        /**
         * 释放节点，从起点到指定节点的所有节点
         * @param node 指定节点
         * @return 从起点到指定节点的所有节点的集合
         */
        private vector solve(node node) {
        vector solution = new vector();
        
        solution.addelement(node);
        while(node.parent != null) {
            solution.insertelementat(node.parent, 0);
            node = node.parent;
        }
        
        return solution;
    }
        
        /**
         * 进行路径查找
         * @return 返回路径集合
         */
        public vector find(){
                long starttime=system.currenttimemillis();
                //为起点赋初值
                node startnode=new node();
                startnode.location=start;
                startnode.costfromstart=0;
                startnode.costtogoal=cur.nettogoalcostestimate(start,goal);
                startnode.totalcost=startnode.costtogoal+startnode.costfromstart;
                startnode.parent=null;
                
                open.addnode(startnode);
                        
                while(open.size()>0){
                        //寻找开启列表中f值最低的格子。我们称它为当前格
                        node currentnode=open.pop();
                        system.out.println("寻找开启列表中f值最低的格子:"+currentnode);
                        
                        //把目标格添加进了开启列表，这时候路径被找到
                        if (currentnode.location.equals(goal)){
                                system.out.println("路径被找到");
                                system.out.println("共耗时:"+(system.currenttimemillis()-starttime)+"ms");
                                return solve(currentnode);
                        }
                        else{
                                //把当前格切换到关闭列表
                                closed.addnode(currentnode);
                                //获得当前附近的节点集合
                                vector neighborlist=getneighbors(currentnode);
                                
                                boolean inopenlist=false;
                                boolean inclosedlist=false;
                                
                                for(int i=0;i<neighborlist.size();i++){
//                                        system.out.println(&quot;开启列表内容:\n&quot;+open);
                                        //计算邻居节点的耗费值
                                        node neighbornode=(node)neighborlist.elementat(i);
                                        
                                        system.out.println(&quot;比较邻居节点:&quot;+neighbornode);
                                        
                                        inopenlist=open.contains(neighbornode);
                                        inclosedlist=closed.contains(neighbornode);
                                        
                                        system.out.println(&quot;is in open=&quot;+inopenlist);
                                        system.out.println(&quot;is in closed=&quot;+inclosedlist);
                                        //如果它不可通过或者已经在关闭列表中，略过它
                                        if (inclosedlist){
                                                system.out.println(&quot;邻居节点已经在关闭列表!&quot;);
                                                continue;
                                        }
                                        //如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的f,g,和h值。
                                        else{
                                                if (inopenlist==false){
                                                        system.out.println(&quot;记录这一格的f,g,和h值&quot;);
                                                        neighbornode.costfromstart=currentnode.costfromstart
                                                                +neighbortocurrentcostestimate(currentnode,neighbornode);
                                                        neighbornode.costtogoal=cur.nettogoalcostestimate(neighbornode.location,goal);
                                                        neighbornode.totalcost=neighbornode.costfromstart+neighbornode.costtogoal;
                                                        neighbornode.parent=currentnode;
                                                        system.out.println(&quot;把它添加进开启表:&quot;+neighbornode);
                                                        open.addnode(neighbornode);
                                                        system.out.println(&quot;邻居节点不在开启列表中，被添加:\n&quot;+neighbornode);
                                                }
                                                //如果它已经在开启列表中，用g值为参考检查新的路径是否更好。更低的g值意味着更好的路径。
                                                //如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的g和f值。
                                                //如果你保持你的开启列表按f值排序，改变之后你可能需要重新对开启列表排序。
                                                else{
                                                        if ((currentnode.costfromstart+neighbortocurrentcostestimate(currentnode,neighbornode))
                                                                        <currentnode.costfromstart){
                                                                system.out.println(&quot;邻居节点是g值低的\n&quot;+neighbornode);
                                                                currentnode=neighbornode.parent;
                                                                neighbornode.costtogoal=cur.nettogoalcostestimate(neighbornode.location,goal);
                                                                neighbornode.totalcost=neighbornode.costfromstart+neighbornode.costtogoal;
                                                                open.sort();
                                                                system.out.println(&quot;重新对开启列表排序:\n&quot;+open);
                                                        }
                                                        
                                                }
                                                        
                                                        
                                        }
                                }
                        }
                }
                system.out.println(&quot;路径没有被找到&quot;);
                system.out.println(&quot;共耗时:&quot;+(system.currenttimemillis()-starttime)+&quot;ms&quot;);
                return null;
        }
        
        /**
         * 计算从start到goal的矩形区域中平均耗费值
         * @param start 起始位置
         * @param goal 目标位置
         * @return 从start到goal的矩形区域中平均耗费值
         */
//        private double getaveragecost(location start,location goal){
//                int left=math.min(start.x,goal.x);
//                int top=math.min(start.y,goal.y);
//                int right=math.max(start.x,goal.x);
//                int bottom=math.max(start.y,goal.y);
//                double totalvalue=0;
//                double count=0;
//                for(int i=left;i<=right;i++){
//                        for(int j=top;j<=bottom;j++){
//                                if (grid&#91;i&#93;&#91;j&#93;!=constants.nothing){
//                                        totalvalue+=cost&#91;grid&#91;i&#93;&#91;j&#93;&#93;;
//                                        count++;
//                                }
//                        }
//                }
//                return totalvalue/count/1.1;
//        }
        
        /**
         * 计算从某节点到目标节点的预估耗费
         * @param start 计算的起始点
         * @param goal 计算的终点
         * @return 返回从某节点到目标节点的预估耗费
         */
        private int cur.nettogoalcostestimate(location start,location goal){
                int dx=math.abs(start.x-goal.x);
                int dy=math.abs(start.y-goal.y);
                return (dx+dy)*linealcost;
        }
        
        /**
         * 计算从当前节点到其周围的邻居节点的预估耗费
         * @param currentnode 当前节点
         * @param neighbornode 邻居节点
         * @return 从当前节点到其周围的邻居节点的预估耗费
         */
        private int neighbortocurrentcostestimate(node currentnode,node neighbornode){
                int dx=math.abs(currentnode.location.x-neighbornode.location.x);
                int dy=math.abs(currentnode.location.y-neighbornode.location.y);
                //如果为对角线方向
                if (dx==1&&dy==1){
                        //g=(x轴距离+y轴距离)*对角线单位耗费+当前节点的耗费
                        return (dx+dy)*diagonalcost+cost&#91;grid&#91;neighbornode.location.x&#93;&#91;neighbornode.location.y&#93;&#93;;
                }
                //如果为直线方向
                else{
                        //g=(x轴距离+y轴距离)*直线单位耗费+当前节点的耗费
                        return (dx+dy)*linealcost+cost&#91;grid&#91;neighbornode.location.x&#93;&#91;neighbornode.location.y&#93;&#93;;
                }//+cost&#91;grid&#91;neighbornode.location.x&#93;&#91;neighbornode.location.y&#93;&#93;;
        }
        
        /**
         * 边界检测
         * @param x x轴坐标
         * @param y y轴坐标
         * @return 如果出边界，则返回true
         */
        private boolean isoutofborder(int x,int y){
                //测试边界
                if (x<0x>=grid.length){
                        return true;
                }
                //测试边界
                if (y<0y>=grid&#91;0&#93;.length){
                        return true;
                }
                return false;
        }
        
        /**
         * 条件性的增加节点
         * @param neighborlist 邻居列表
         * @param location 当前节点的坐标
         * @param dx x轴坐标增量
         * @param dy y轴坐标增量
         */
        private void conditionaladd(vector neighborlist,location location,int dx,int dy){
                int x=location.x;
                int y=location.y;
                int newx=x+dx;
                int newy=y+dy;
                
                //测试边界
                if (isoutofborder(newx,newy)){
                        return;
                }
                
                //跳过不能通过的物体
                if (grid&#91;newx&#93;&#91;newy&#93;==constants.solid){
                        return;
                }
                
                //判断左上角邻居节点
                if ((dx==-1)&&(dy==-1)){
                        if (isskiped(left_top,newx,newy)){
                                system.out.println(&quot;跳过节点&quot;+location+&quot;的左上角邻居节点&quot;);
                                return;
                        }
                }
                
                //判断左下角邻居节点
                if ((dx==-1)&&(dy==1)){
                        if (isskiped(left_bottom,newx,newy)){
                                system.out.println(&quot;跳过节点&quot;+location+&quot;的左下角邻居节点&quot;);
                                return;
                        }
                }
                
                //判断右上角邻居节点
                if ((dx==1)&&(dy==-1)){
                        if (isskiped(right_top,newx,newy)){
                                system.out.println(&quot;跳过节点&quot;+location+&quot;的右上角邻居节点&quot;);
                                return;
                        }
                }
                
                //判断右下角邻居节点
                if ((dx==1)&&(dy==1)){
                        if (isskiped(right_bottom,newx,newy)){
                                system.out.println(&quot;跳过节点&quot;+location+&quot;的右下角邻居节点&quot;);
                                return;
                        }
                }
                
                node neighbor=new node();
                neighbor.location=new location(newx,newy);
                neighborlist.addelement(neighbor);
        }
        
        /**
         * 判断处于拐弯处（左上、右上、左下、右下）的邻居节点，是否邻着不可穿透的固体，如果是则该节点被跳过
         * @param direction 表示邻居节点与当前节点位置关系的左上、右上、左下、右下方向常量
         * @param x 邻居节点的x坐标
         * @param y 邻居节点的y坐标
         * @return 判断处于拐弯处（左上、右上、左下、右下）的邻居节点，是否邻着不可穿透的固体，如果是则返回true
         */
        private boolean isskiped(int direction,int x,int y){
                int x1=0,y1=0;
                int x2=0,y2=0;
                
                switch(direction){
                        //如果当前位置为左上角，则判断其下方和右侧是否为不可穿过的固体
                        case left_top:
                                x1=x;
                                y1=y+1;
                                x2=x+1;
                                y2=y;
                                break;
                        //如果当前位置为右上角，则判断其下方和左侧是否为不可穿过的固体
                        case right_top:
                                x1=x;
                                y1=y+1;
                                x2=x-1;
                                y2=y;
                                break;
                        //如果当前位置为左下角，则判断其上方和右侧是否为不可穿过的固体
                        case left_bottom:
                                x1=x;
                                y1=y-1;
                                x2=x+1;
                                y2=y;
                                break;
                        //如果当前位置为右下角，则判断其上方和左侧是否为不可穿过的固体
                        case right_bottom:
                                x1=x;
                                y1=y-1;
                                x2=x-1;
                                y2=y;
                                break;
                }
                if (isoutofborder(x1,y1)==false){
                        if (grid&#91;x1&#93;&#91;y1&#93;==constants.solid){
                                return true;
                        }
                        else{
                                return false;
                        }
                }
                if (isoutofborder(x2,y2)==false){
                        if (grid&#91;x2&#93;&#91;y2&#93;==constants.solid){
                                return true;
                        }
                        else{
                                return false;
                        }
                }
                return false;
        }
        
        /**
         * 获得当前节点周围的邻居节点集合
         * @param currentnode 当前节点
         * @return 当前节点周围的邻居节点集合
         */
        private vector getneighbors(node currentnode){
                vector neighborlist=new vector();
                
                //增加左上角邻居节点
                conditionaladd(neighborlist,currentnode.location,-1,-1);
                
                //增加左侧邻居节点
                conditionaladd(neighborlist,currentnode.location,-1,0);
                
                //增加左下角的邻居节点
                conditionaladd(neighborlist,currentnode.location,-1,1);

                //增加上方邻居节点
                conditionaladd(neighborlist,currentnode.location,0,-1);
                
                //增加下方邻居节点
                conditionaladd(neighborlist,currentnode.location,0,1);
                
                //增加右上角邻居节点
                conditionaladd(neighborlist,currentnode.location,1,-1);
                
                //增加右侧邻居节点
                conditionaladd(neighborlist,currentnode.location,1,0);
                
                //增加右下角邻居节点
                conditionaladd(neighborlist,currentnode.location,1,1);
                
                return neighborlist;
                
        }
}

astarapplet.java：测试和演示a*算法的applet

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

import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import java.util.vector;

public class astarapplet extends applet implements mouselistener, mousemotionlistener {

    /**
         * 
         */
        private static final long serialversionuid = 847097589329261438l;

        /**
         * 
         */

        static final int appletwidth = 601, appletheight = 401, gridwidth = appletheight,
                     numrows = 20;
    
    static final int cellwidth = gridwidth / numrows;

                     
    static final int pad = 10;
    static int current = constants.empty, starti = constants.nothing, startj = constants.nothing, finishi = constants.nothing,
               finishj = constants.nothing;
    
    static color[] tcolor = new color[constants.numcolors];
    
    static int[][] grid = new int[numrows][numrows];
    static int[] costs = new int[constants.numcolors];
    static graphics g;
    
    public void init() {
        g = getgraphics();
        resize(appletwidth, appletheight);
        tcolor[constants.empty] = color.black;
        costs[constants.empty] = 1*astar.linealcost;
        tcolor[constants.terrain1] = new color(0, 88, 0);
        costs[constants.terrain1] = 5*astar.linealcost;
        tcolor[constants.terrain2] = new color(99, 77, 0);
        costs[constants.terrain2] = 10*astar.linealcost;
        tcolor[constants.terrain3] = color.blue;
        costs[constants.terrain3] = 15*astar.linealcost;
        tcolor[constants.solid] = color.white;
        costs[constants.solid] = constants.nothing;
        tcolor[constants.start] = color.green;
        costs[constants.start] = 1*astar.linealcost;
        tcolor[constants.finish] = color.red;
        costs[constants.finish] = 1*astar.linealcost;
        addmouselistener(this);
        addmousemotionlistener(this);
    }
    
    public void start() {
        paint(getgraphics());
    }
    
    public void stop() {
    }
        
    public void paint(graphics g) {
        g.setcolor(color.black);
        g.fillrect(0, 0, appletwidth, appletheight);
        drawall();
    }
    
    public void update(graphics g) {
        paint(g);
    }
    
    private void drawall() {
        for(int i = 0; i < numrows; i++) {
            for(int j = 0; j < numrows; j++) {
                drawcell(i, j);
            }
        }
        if(starti != constants.nothing) {
            drawcell(starti, startj);
        }
        if(finishi != constants.nothing) {
            drawcell(finishi, finishj);
        }
        int left = gridwidth + pad;
        for(int i = constants.empty; i <= constants.finish; i++) {
            int top = pad + (cellwidth + pad) * i;
            drawterrainbutton(i, left, top, (current == i ? true : false));
        }
        drawbuttons();
    }
    
    int buttonsleft = gridwidth + pad * 2;
    int buttonswidth = appletwidth - gridwidth - pad * 4;
    int buttonsheight = 20;
    int gotop = appletheight - pad - (buttonsheight + pad) * 2;
    int cleartop = appletheight - pad - (buttonsheight + pad);
    
    private void drawbuttons() {
        int halfwidth = buttonsleft + buttonswidth / 2;
        string gostring = &quot;计算&quot;, clearstring = &quot;清除路径&quot;;
        g.setcolor(color.white);
        g.drawrect(buttonsleft, gotop, buttonswidth, buttonsheight);
        g.drawrect(buttonsleft, cleartop, buttonswidth, buttonsheight);
        g.setfont(new font(&quot;sansserif&quot;, font.bold, 12));
        g.drawstring(gostring, halfwidth - g.getfontmetrics().stringwidth(gostring) / 2, gotop + 15);
        g.drawstring(clearstring, halfwidth - g.getfontmetrics().stringwidth(clearstring) / 2, cleartop + 15);
    }
    
    private void drawcell(int i, int j) {
        int left = i * cellwidth, top = j * cellwidth;
        g.setcolor(color.lightgray);
        g.drawrect(left, top, cellwidth, cellwidth);
        if(grid&#91;i&#93;&#91;j&#93; == constants.start) {
            g.setcolor(tcolor&#91;constants.start&#93;);
            g.drawrect(left, top, cellwidth, cellwidth);
            g.setcolor(color.black);
            g.fillrect(left + 1, top + 1, cellwidth - 1, cellwidth - 1);
        } else if(grid&#91;i&#93;&#91;j&#93; == constants.finish) {
            g.setcolor(tcolor&#91;constants.finish&#93;);
            g.drawrect(left, top, cellwidth, cellwidth);
            g.setcolor(color.black);
            g.fillrect(left + 1, top + 1, cellwidth - 1, cellwidth - 1);
        } else if(grid&#91;i&#93;&#91;j&#93; == constants.nothing) {
            g.setcolor(color.black);
            g.fillrect(left + 1, top + 1, cellwidth - 1, cellwidth - 1);
        } else {
            g.setcolor(tcolor&#91;grid&#91;i&#93;&#91;j&#93;&#93;);
            g.fillrect(left + 1, top + 1, cellwidth - 1, cellwidth - 1);
        }
    }
    
    private void drawterrainbutton(int i, int left, int top, boolean on) {
        g.setfont(new font(&quot;sansserif&quot;, font.bold, 12));
        if(i == constants.start  i == constants.finish) {
            g.setcolor(tcolor&#91;i&#93;);
            g.drawrect(left, top, cellwidth, cellwidth);
            g.setcolor(color.white);
            if(i == constants.start) {
                g.drawstring(&quot;起始点&quot;,left + cellwidth + pad * 2, top + cellwidth);
            } else if(i == constants.finish) {
                g.drawstring(&quot;终点&quot;,left + cellwidth + pad * 2, top + cellwidth);
            }
        } else {
                if (i>constants.nothing){
                    g.setcolor(tcolor&#91;i&#93;);
                    g.fillrect(left, top, cellwidth, cellwidth);
                    g.setcolor(color.white);
                    g.drawrect(left, top, cellwidth, cellwidth);
                    g.setcolor(color.white);
                    g.drawstring((i == constants.solid ? &quot;固体&quot; : string.valueof(costs&#91;i&#93;)),left + cellwidth + pad * 2, top + cellwidth);
                }
        }
        if(on) {
            g.setcolor(color.red);
        } else {
            g.setcolor(color.black);
        }
        g.fillrect(left + cellwidth + pad / 2, top, pad / 2, cellwidth + 1);
    }
    
//    private void drawstartstop(int i, int left, int top, boolean on) {
//        if(on) {
//            g.setcolor(color.red);
//        } else {
//            g.setcolor(color.black);
//        }
//        g.fillrect(left + cellwidth + pad / 2, top, pad / 2, cellwidth + 1);
//    }
    
    public void mouseclicked(mouseevent e) {}

    public void mousepressed(mouseevent e) {
        int x = e.getx(), y = e.gety();
        
        if(x < gridwidth - 1) {
            checkgrid(x, y);
        } else {
            int left = gridwidth + pad;
            int old = current;
            boolean selected = false;
            for(int i = constants.empty; i <= constants.finish; i++) {
                int top = pad + (cellwidth + pad) * i;
                if(checkbounds(left, top, cellwidth, cellwidth, x, y)) {
                    drawterrainbutton(current = i, left, top, true);
                    selected = true;
                    break;
                }
            }
            if(!selected) {
                current = constants.nothing;
                if(checkbounds(buttonsleft, gotop, buttonswidth, buttonsheight, x, y) && starti != constants.nothing && finishi != constants.nothing) {
                    astar a = new astar(grid, costs, new location(starti, startj), new location(finishi, finishj));
                    vector solution = a.find();
                    if(solution != null) {
                        g.setfont(new font(&quot;sansserif&quot;, font.bold, 12));
                        for(int i = 0; i < solution.size(); i++) {
                            location nodeloc = ((node)solution.elementat(i)).location;
                            drawdot(nodeloc.x, nodeloc.y);

                            try {
                                thread.sleep(300);
                            } catch(interruptedexception ex) {
                            }
                        }
                    }
                } else if(checkbounds(buttonsleft, cleartop, buttonswidth, buttonsheight, x, y)) {
                    drawall();
                }
            }
            if(old != current) {
                drawterrainbutton(old, left, pad + (cellwidth + pad) * old, false);
            }
        }
    }
    
    
    public void mousedragged(mouseevent e) {
        int x = e.getx(), y = e.gety();
        
        checkgrid(x, y);
    }
    
    private void checkgrid(int x, int y) {
        if(x < gridwidth - 1) {
            if(current != constants.nothing) {
                int i = x / numrows, j = y / numrows;
                if(grid&#91;i&#93;&#91;j&#93; == constants.start) {
                    starti = finishj = constants.empty;
                }
                if(grid&#91;i&#93;&#91;j&#93; == constants.finish) {
                    finishi = finishj = constants.empty;
                }
                if(current == constants.start) {
                    if(starti != constants.nothing) {
                        grid&#91;starti&#93;&#91;startj&#93; = constants.empty;
                        drawcell(starti, startj);
                    }
                    starti = i;
                    startj = j;
                } else if(current == constants.finish) {
                    if(finishi != constants.nothing) {
                        grid&#91;finishi&#93;&#91;finishj&#93; = constants.empty;
                        drawcell(finishi, finishj);
                    }
                    finishi = i;
                    finishj = j;
                }
                grid&#91;i&#93;&#91;j&#93; = current;
                drawcell(i, j);
            }
        }
    }
    
    public void mousemoved(mouseevent e) {}
    
    private void drawdot(int i, int j) {
        int left = i * cellwidth + 1, top = j * cellwidth + 1, right = left + cellwidth - 2, bottom = top + cellwidth - 2;
        g.setcolor(color.yellow);
        g.drawline(left + cellwidth / 2 - 1, top, right, top + cellwidth / 2 - 1);
        g.drawline(right, top + cellwidth / 2 - 1, left + cellwidth / 2 - 1, bottom);
        g.drawline(left + cellwidth / 2 - 1, bottom, left, top + cellwidth / 2 - 1);
        g.drawline(left, top + cellwidth / 2 - 1, left + cellwidth / 2 - 1, top);
    }
    
    public void mousereleased(mouseevent e) {}
    public void mouseentered(mouseevent e) {}
    public void mouseexited(mouseevent e) {}
   
    private boolean checkbounds(int left, int top, int buttonwidth, int buttonheight, int x, int y) {
        return (x >= left && x < left + buttonwidth && y >= top && y < top + buttonheight);
    }

}

三、applet使用说明：

1。首先点选“起始点”，在图中确定起始点的位置。同样，以此方法点选“终点”，然后在图中确定路径的终点的位置。

2。然后选择适当的图例（图例后面的数值为该类图例的单元耗费值，如绿色为50），在图中勾画地图。

3。点击计算按钮后，开始计算“起始点”与“终点”之间的路径，并将路径画在画板上。

4。点击清除路径按钮来清除前一次的路径。

四、用途：

本算法用于计算npc或者玩家由起始位置到达终点的路径，为控制人物的移动和npc的运动提供依据。非常适用于rpg和pazzle类游戏。

五、源代码下载：[下载文件]

 

关键字 本文所属关键字

相关 与本文相关文章

分类 所有文章关键字导航

标准 网站致力的规范