迷宫算法设计 - 图文

选择菜单操作中的A*算法寻找最短路径找到起点到终点的最短路径：

【程序性能评价】

该程序较好的对自定义的迷宫寻找通路，并且即可实现普通通路又可以用A*算法实现最短路径。

【性能改进方面】

该程序还可以提高系统容错能力，另外还可以添加部分功能，如可随机设置障碍物，或者对走完路径的时间进行记时，增加游戏的趣味性。

【收获及体会】

在这次课程设计的中，从任务书、程序的编写、运行、调试到设计报告，整个过程自己收获了许多，编写程序运行遇到错误时，一次次的修改，使我体会到要坚持有耐心，有毅力，同时通过一些资料的查找和运用使自己的程序运行成功。通过这次实践让我更好的了解到java语言在生活领域中的应用，更多的体会到算法思维的重要性，提高了自己独立思考、动手实践操作的能力。同时也认识到自己在学习中不足的地方，这些都让自己在以后的学习和生活中能更有方向的去提高自己。

4、 源程序代码

package maze; /**

* A*算法点坐标类 * */

public class Aposition extends Position{//继承了Position类 int f=0,g=0,h=0; }

package maze; import java.util.*;

import javax.swing.JOptionPane; /**

* A*算法实现 * */

public class Astar {

Maze maze;

Stack as = new Stack(); Aposition[][] aMap; Aposition cur;// 当前点 Aposition begin; Aposition end;

LinkedList open = new LinkedList();// 开启列表 LinkedList close = new LinkedList();// 关闭列int flag;//标记是否开启 Aposition pre;

public Aposition(int x,int y,Aposition p,int flag){ }

super(x,y);

this.pre=p;//前驱节点 this.flag=flag;

表 int[][] direction = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };//方向数组，右下左上

public Astar(Maze maze) {// 构造方法 this.maze = maze;

aMap = new Aposition[maze.row][maze.col];// 该二维数组的元素都为this.begin = new Aposition(maze.begin.x, maze.begin.y, null,

// ,

null

0);//1:close

//

0:open

this.end = new Aposition(maze.end.x, maze.end.y, null, -1);// -1 aMap[this.begin.y][this.begin.x] = this.begin; aMap[this.end.y][this.end.x] = this.end;

is 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)

//

//

{// 是通路， 并且还不存在

// ，

引用为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]);

} else {

是否更优

}

sort(); // 将开启列表排序

}

}

public void sort() {// 根据F值从小到大排序 Aposition 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;

for (int i = 0; i < open.size() - 1; i++) { }

for (int j = i + 1; j < open.size(); j++) { }

if (open.get(i).f > open.get(j).f) { }

temp = open.get(i); open.set(i, open.get(j)); open.set(j, temp);

从开启列表中删除

package maze;