|
游戏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="";
for(int i=0;i<this.size();i++){
s+=((Node)this.elementAt(i)).toString()+"\n";
}
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=currnetToGoalCostEstimate(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("开启列表内容:\n"+open);
//计算邻居节点的耗费值
Node neighborNode=(Node)neighborList.elementAt(i);
System.out.println("比较邻居节点:"+neighborNode);
inOpenList=open.contains(neighborNode);
inClosedList=closed.contains(neighborNode);
System.out.println("is in Open="+inOpenList);
System.out.println("is in Closed="+inClosedList);
//如果它不可通过或者已经在关闭列表中，略过它
if (inClosedList){
System.out.println("邻居节点已经在关闭列表!");
continue;
}
//如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
else{
if (inOpenList==false){
System.out.println("记录这一格的F,G,和H值");
neighborNode.costFromStart=currentNode.costFromStart
+neighborToCurrentCostEstimate(currentNode,neighborNode);
neighborNode.costToGoal=currnetToGoalCostEstimate(neighborNode.location,goal);
neighborNode.totalCost=neighborNode.costFromStart+neighborNode.costToGoal;
neighborNode.parent=currentNode;
System.out.println("把它添加进开启表:"+neighborNode);
open.addNode(neighborNode);
System.out.println("邻居节点不在开启列表中，被添加:\n"+neighborNode);
}
//如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。
//如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。
//如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
else{
if ((currentNode.costFromStart+neighborToCurrentCostEstimate(currentNode,neighborNode))
<currentNode.costFromStart){
System.out.println("邻居节点是G值低的\n"+neighborNode);
currentNode=neighborNode.parent;
neighborNode.costToGoal=currnetToGoalCostEstimate(neighborNode.location,goal);
neighborNode.totalCost=neighborNode.costFromStart+neighborNode.costToGoal;
open.sort();
System.out.println("重新对开启列表排序:\n"+open);
}
}
}
}
}
}
System.out.println("路径没有被找到");
System.out.println("共耗时:"+(System.currentTimeMillis()-startTime)+"ms");
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[i][j]!=Constants.NOTHING){
// totalValue+=cost[grid[i][j]];
// count++;
// }
// }
// }
// return totalValue/count/1.1;
// }
/**
* 计算从某节点到目标节点的预估耗费
* @param start 计算的起始点
* @param goal 计算的终点
* @return 返回从某节点到目标节点的预估耗费
*/
private int currnetToGoalCostEstimate(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[grid[neighborNode.location.x][neighborNode.location.y]];
}
//如果为直线方向
else{
//G=(x轴距离+y轴距离)*直线单位耗费+当前节点的耗费
return (dx+dy)*linealCost+cost[grid[neighborNode.location.x][neighborNode.location.y]];
}//+cost[grid[neighborNode.location.x][neighborNode.location.y]];
}
/**
* 边界检测
* @param x x轴坐标
* @param y y轴坐标
* @return 如果出边界，则返回true
*/
private boolean isOutOfBorder(int x,int y){
//测试边界
if (x<0||x>=grid.length){
return true;
}
//测试边界
if (y<0||y>=grid[0].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[newX][newY]==Constants.SOLID){
return;
}
//判断左上角邻居节点
if ((dx==-1)&&(dy==-1)){
if (isSkiped(LEFT_TOP,newX,newY)){
System.out.println("跳过节点"+location+"的左上角邻居节点");
return;
}
}
//判断左下角邻居节点
if ((dx==-1)&&(dy==1)){
if (isSkiped(LEFT_BOTTOM,newX,newY)){
System.out.println("跳过节点"+location+"的左下角邻居节点");
return;
}
}
//判断右上角邻居节点
if ((dx==1)&&(dy==-1)){
if (isSkiped(RIGHT_TOP,newX,newY)){
System.out.println("跳过节点"+location+"的右上角邻居节点");
return;
}
}
//判断右下角邻居节点
if ((dx==1)&&(dy==1)){
if (isSkiped(RIGHT_BOTTOM,newX,newY)){
System.out.println("跳过节点"+location+"的右下角邻居节点");
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[x1][y1]==Constants.SOLID){
return true;
}
else{
return false;
}
}
if (isOutOfBorder(x2,y2)==false){
if (grid[x2][y2]==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 = "计算", clearString = "清除路径";
g.setColor(Color.white);
g.drawRect(buttonsLeft, goTop, buttonsWidth, buttonsHeight);
g.drawRect(buttonsLeft, clearTop, buttonsWidth, buttonsHeight);
g.setFont(new Font("SansSerif", 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[i][j] == Constants.START) {
g.setColor(tColor[Constants.START]);
g.drawRect(left, top, cellWidth, cellWidth);
g.setColor(Color.black);
g.fillRect(left + 1, top + 1, cellWidth - 1, cellWidth - 1);
} else if(grid[i][j] == Constants.FINISH) {
g.setColor(tColor[Constants.FINISH]);
g.drawRect(left, top, cellWidth, cellWidth);
g.setColor(Color.black);
g.fillRect(left + 1, top + 1, cellWidth - 1, cellWidth - 1);
} else if(grid[i][j] == Constants.NOTHING) {
g.setColor(Color.black);
g.fillRect(left + 1, top + 1, cellWidth - 1, cellWidth - 1);
} else {
g.setColor(tColor[grid[i][j]]);
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("SansSerif", Font.BOLD, 12));
if(i == Constants.START || i == Constants.FINISH) {
g.setColor(tColor[i]);
g.drawRect(left, top, cellWidth, cellWidth);
g.setColor(Color.white);
if(i == Constants.START) {
g.drawString("起始点",left + cellWidth + pad * 2, top + cellWidth);
} else if(i == Constants.FINISH) {
g.drawString("终点",left + cellWidth + pad * 2, top + cellWidth);
}
} else {
if (i>Constants.NOTHING){
g.setColor(tColor[i]);
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 ? "固体" : String.valueOf(costs[i])),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("SansSerif", 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[i][j] == Constants.START) {
startI = finishJ = Constants.EMPTY;
}
if(grid[i][j] == Constants.FINISH) {
finishI = finishJ = Constants.EMPTY;
}
if(current == Constants.START) {
if(startI != Constants.NOTHING) {
grid[startI][startJ] = Constants.EMPTY;
drawCell(startI, startJ);
}
startI = i;
startJ = j;
} else if(current == Constants.FINISH) {
if(finishI != Constants.NOTHING) {
grid[finishI][finishJ] = Constants.EMPTY;
drawCell(finishI, finishJ);
}
finishI = i;
finishJ = j;
}
grid[i][j] = 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类游戏。
五、源代码下载：[下载文件]
|
