public Astar(Maze maze){//构造方法 this.maze=maze;
aMap=new Aposition[maze.row][maze.col];//该二维数组的元素都为null this.begin=new
this.end=new Aposition(maze.end.x,maze.end.y,null,-1);//-1 is aMap[this.begin.y][this.begin.x]=this.begin; aMap[this.end.y][this.end.x]=this.end;
Aposition(maze.begin.x,maze.begin.y,null,0);//1:close,0:open end
open.add(this.begin);//将起点放入关闭列表 }
public void probe(Aposition cur){//试探方法 for(int i=0;i<4;i++){
int tx=cur.x+direction[i][0]; int ty=cur.y+direction[i][1];
if(maze.mazeMap[ty][tx]==0&&this.aMap[ty][tx]==null){//是通 aMap[ty][tx]=new Aposition(tx,ty,cur,0);//使引用明确,并开启 setH(aMap[ty][tx]); setG(aMap[ty][tx]); setF(aMap[ty][tx]);
open.add(aMap[ty][tx]);//加入到开启列表中 }else if(aMap[ty][tx]!=null){//已存在的
if(close.contains(aMap[ty][tx])){}//已在关闭列表中则不处理 else if(aMap[ty][tx].equals(this.end)){//若找到终点，将终点加入
this.end.pre=cur; close.add(this.end);
if(aMap[ty][tx].g>cur.g+1){//已在开启列表中，比较是否更优
aMap[ty][tx].pre=cur; setG(aMap[ty][tx]); setF(aMap[ty][tx]); }
路，并且还不存在，引用为null
到关闭列表中
}else{
} } }
sort(); }
//将开启列表排序
public void sort(){//根据F值从小到大排序 Aposition temp;
for(int i=0;i for(int j=i+1;j 36 } } } } if(open.get(i).f>open.get(j).f){ } temp=open.get(i); open.set(i,open.get(j)); open.set(j,temp); public void solve(){ //求解 } public void setH(Aposition p){//求H值 p.h=Math.abs(this.end.x-p.x)+Math.abs(this.begin.y-p.y); } public void setG(Aposition p){//求G值 p.g=p.pre.g+1; } public void setF(Aposition p){//求F值 p.f=p.g+p.h; } Aposition temp;//设置回滚对象 while(open.size()!=0){//当开启列表不为空时，循环 } JOptionPane.showMessageDialog(null, \); return ; this.cur=(Aposition)open.poll();//取开启列表中F值最小的,并从开close.add(this.cur);//加入到关闭列表中 this.cur.flag=1;//标记为关闭 probe(this.cur);//探索启发 if(close.contains(this.end)){ } temp=this.end; while(temp!=null){ } return ; as.push(temp); temp=temp.pre; 启列表中删除 37 3.9 Aposition.java（A*算法存储结构） 3.9.1 UML图 Aposition类是Position类的派生类，APosition类创建的对象是Astar类、MazeGUI类和Rollback类最重要的成员之一。该类负责在Astar类、MazeGUI类和Rollback类之间传递消息，其对象存有当前位置的坐标信息、A*算法的评估函数值、开关标记和父节点等。标明Astar类的主要成员变量、成员方法的UMl图如图13所示。 图9-13 Aposition类的UML图 3.9.2代码（Aposition.java） package maze; /** * A*算法点坐标类 * */ public class Aposition extends Position{//继承了Position类 int f=0,g=0,h=0; } int flag;//标记是否开启 Aposition pre; public Aposition(int x,int y,Aposition p,int flag){ } super(x,y); this.pre=p;//前驱节点 this.flag=flag; 4程序测试调试 程序编码的过程中，我们遇到过各种问题，有的是编译时错误，还有的是运行时的异常。编译时错误主要是，对象未初始化。运行时异常主要包括空指针、数组越界等。 在程序编码完成后，由我们的测试人员进行测试时（程序功能测试，黑盒测试），也发现了很多问题，有的不符合需求分析中的要求，有的是用户非正常操作引起的。以下是程序 38 测试中遇到的一些问题。 4.1消除脚印问题 本问题主要是不符合需求分析中的要求，即找不到路径时没有消除脚印，还有在找不到出路返回时也没有消除脚印。 调试：在栈顶元素出栈时，为了区分该位置已经走过，即mazeMap[][]中相应的值不为0，又要绘制出通路的图像。于是在出栈时，将该点位置mazeMap[][]的值变为3，而在mazeMap[][]值为1和3的点都绘制通路图像，即可解决问题。 调试结果：解决。 4.2 定位方框越界 本问题主要是由用户非正常操作引起的，即定位方框能移到迷宫外围的墙上，不符合设计人员的本意。截图如下。 图14 定位方框越界问题截图 调试：在actionPerformed方法中，按上下左右代码前增加坐标判断的语句，防止定位方框越界。 调试结果：解决。 4.3 求解迷宫过程中，画面闪烁不定 本问题是影响程序美观，即在求解迷宫过程中，画面闪烁。 调试：查找资料，运用双缓冲技术，增加数行代码几个解决，此代码为javaGUI设计中的常用固定代码。这也正是MazeGUI类中Image类型的变量offScreen存在的原因。 public void update(Graphics g){//双缓冲防止屏幕闪烁 if(offScreen == null){ } Graphics offg = offScreen.getGraphics(); Color c = offg.getColor(); offg.setColor(Color.BLUE); offg.fillRect(0, 0, col*50, row*50); offg.setColor(c); paint(offg); g.drawImage(offScreen, 0, 0, null); 39 offScreen = this.createImage(col*50, row*50); } 调试结果：解决。 4.4 求解过程中或者求解完再按F9 本问题是由用户的非法操作引起的，导致了程序的非正常运行。本问题涉及线程方面编程技巧，由于水平有限，解决的方法也较笨拙，可能存在不合理的地方。 调试：根据当前原先线程的状态，新建一个线程，编写maze.resume（）方法，恢复演示前地图的状态，编写Rollback.flush（）方法清空栈，重新开始演示。 调试结果：解决。 4.5 输入迷宫大小时用户非法输入 本问题是由用户的非法操作引起的，导致程序不能正常运行。本问题应该涉及文本框内容的处理。以下是本问题的截图，程序抛出java.lang.NumberFormatException。 图14 用户非法输入 调试： Integer.parseInt(tf1.getText()), Integer.parseInt(tf2.getText() 由于编码时是将文本框的字符串内容转化成Integer类型的，Integer的封装类。对字符串的内容我们无法判定其值是什么类型的。 调试结果:未解决（后来查询了相关资料，可以用KeyListener实现，判断按下的键是否符合的我们规定）。 4.6 A*算法和回溯法的冲突 本问题是有用户非法操作引起的，导致程序不能按照期望的规则运行。即在演示回溯法时点击了“A*算法求解最短路”，或者演示A*算法时按F9，导致程序抛出异常，但仍能运行。 调试：本问题设计到线程状态编程技巧，由于水平有限，但是有解决问题的大致思路，即判断另一个线程的状态是否处于运行态，若处于运行态则不响应动作。 40