迷宫算法设计 - 图文

《数据结构与算法设计》

课程设计任务书

题 目 学生姓名 迷宫设计 学号 专业班级 【问题描述】 在迷宫中求从入口到出口的一条简单路径。迷宫可用方块来表示， 每个方块或者是通道或者是墙。 “迷宫求解”这个经典的问题，应用栈这种数据结构设计一个方案， 并在图形界面上实现从入口到出口的一条简单路径，设计这个游戏可以加强自己的编程能力，自己找通路时还可以加强观察能力。 【软件功能】 1、求解迷宫通路的图形界面演示程序，根据用户界面提示自定义迷宫。 2、根据用户界面提示，用键盘输入，Home键设置迷宫起点，End键设终点，上下左右箭头键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，演示完毕后可F5刷新题图，重新对地图的起点、终点、障碍进行设置，Esc键退出； 3、在找迷宫通路的过程中，演示查找的过程并查找成功的一条路径。 4、用户可以通过界面上提供的菜单选项，选择“A*算法求最短路径”演示求解迷宫最短路径。 【算法思想】 1、以一个长方阵表示迷宫，采用数组对迷宫信息进行存储，数组的元素的值表示迷宫对应位置的内容。0表示迷宫对应位置可通过；1表示迷宫对应位置为墙；2表示迷宫对应位置为已经走过的足迹3，表示迷宫对应位置是从栈中弹出的点，并且不能再次通过；4表示迷宫对应位置为起点，保证起点不可通过。 2.在设计走迷宫算法的过程中，主要是利用栈对路径信息进行存储，类Node，定义了栈中存储的节点元素的类型，栈中的元素采用链式存储的结构。 3、采用A*算法，找到起点到终点的最短路径； 4、采用回溯算法控制并绘制人物在迷宫图形界面窗口中的位置。 5、用java编程语言，有简单、美观的图形界面。 【提交成果】 1.“《数据结构与算法设计》课程设计任务书”一份，打印装袋； 2.“《数据结构与算法设计》课程设计报告”一份，打印装袋； 3、上面两项内容的word文档，通过电子邮件交到指导教师。 2012 年 6 月18日 至 2012 年7月 1 日 2012年 6 月 18 日 2012年 6 月 18 日 2012 年 6 月 18 日 设 计 内 容 与 要 求 起止时间 指导教师签名 系（教研室）主任签名 学生签名

数据结构与算法设计课程设计

专业 班级 学号

姓名（签名） 完成日期 指导教师（签名）

1、程序设计说明书

【设计题目】迷宫设计 【问题描述】

在迷宫中求从入口到出口的一条简单路径。迷宫可用方块来表示， 每个方块或者是通道或者是墙。 “迷宫求解”这个经典的问题，应用栈这种数据结构设计一个方案， 并在图形界面上实现从入口到出口的一条简单路径，设计这个游戏可以加强自己的编程能力，自己找通路时还可以加强观察能力。

【软件功能】

1、求解迷宫通路的图形界面演示程序，根据用户界面提示自定义迷宫。

2、根据用户界面提示，用键盘输入，Home键设置迷宫起点，End键设终点，上下左右箭 头 键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，演示完毕后可F5刷新题图，重新对地图的起点、终点、障碍进行设置，Esc键退出；

3、在找迷宫通路的过程中，演示查找的过程并查找成功的一条路径。

4、用户可以通过界面上提供的菜单选项，选择“A*算法求最短路径”演示求解迷宫最短路径。

【算法思想】

1、以一个长方阵表示迷宫，采用数组对迷宫信息进行存储，数组中的元素的值表示迷宫对应位置的内容。0表示迷宫对应位置可通过；1表示迷宫对应位置为墙；2表示迷宫对应位置为已经走过的足迹3，表示迷宫对应位置是从栈中弹出的点，并且不能再次通过；4表示迷宫对应位置为起点，保证起点不可通过。

2、在设计走迷宫算法的过程中，主要是利用栈对路径信息进行存储，类Node，定义了栈中存储的节点元素的类型，栈中的元素采用链式存储的结构。 3、采用A*算法，找到起点到终点的最短路径；

4、采用回溯算法控制并绘制人物在迷宫图形界面窗口中的位置。 5、用java编程语言，有简单、美观的图形界面。

【逻辑结构设计】

运行程序，进入设置迷宫大小界面，输入行和列的值点击生成迷宫按钮进入迷宫自定义界面，根据操作菜单中的帮助选项，用键盘上的按键进行自定义操作（设置迷宫的起点、终点和墙）按F9或者操作菜单中的A*算法寻找最短路径选项即可实现对应的通路。

【存储结构设计】

该程序主要采用数组对迷宫信息进行存储，数组的元素的值表示迷宫对应位置的内容，主要是利用栈对路径信息进行存储，类Node，定义了栈中存储的节点元素的类型，栈中的元素采用链式存储的结构。 栈：

public class Stack {

private Node top;//节点为Node类型 private int size;//栈中节点数 public Stack(){//构造方法

public void push(Object o)//进栈 public void pop()//出栈

public boolean isEmpty()//判断栈是否为空

public Node(Object o,Node n){//Node类构造方法 Position类中;

public class Position

public int x, y;// x代表图形界面的横坐标, y代表图形界面的纵坐标 public Position(int x, int y)//构造方法

public boolean equals(Object o)// 判断当前位置的o对象是否和调用该方法的Position类对象的内容相等 MazeGUI类中

public class MazeGUI //迷宫GUI

final Object obj=new Object();//锁对象 int row=0,col=0;//设置值迷宫图形界面的大小

Image offScreen = null;// 双缓冲技术防止屏幕闪烁 Maze maze;//构建迷宫参数

Rollback rollback;// 求解迷宫，并绘制人物在迷宫图形界面中的位置。

Thread t1 = new Thread(new SolveThread(),\);//寻路进程，在初始化Thread类时，把目标对象传递给这个线程实例 Thread t2 = new Thread(new AThread(),\);

public void paint(Graphics g){//调用绘制地图的draw()方法和绘制人物位置的draw()方法

public void update(Graphics g)//双缓冲防止屏幕闪烁 public MazeGUI(int row,int col)//初始化窗体

private class SolveThread implements Runnable{//提供一个实现借口Runnable接口的类的实例，作为一个线程的目标对象

private class AThread implements Runnable//展示用A*算法求解迷宫过程的线程

【基本操作设计】

1、 运行程序，进入设置迷宫大小界面，输入行和列的值点击生成迷宫按钮

进入迷宫自定义界面，

2、 根据操作菜单中的帮助选项，用键盘上的按键进行自定义操作（设置迷

宫的起点、终点和墙）按F9或者操作菜单中的A*算法寻找最短路径选项即可实现对应的通路。

【模块流程图】

模块划分图:

设置迷宫大小 主界面 文件 操作 退出 刷新地图 A*算法最短路 帮 助