迷宫算法设计 - 图文

public void actionPerformed(ActionEvent e) {

String es = e.getActionCommand(); if (es.equals(\退出\)) { System.exit(0);

} else if (es.equals(\刷新地图\)) { maze = new Maze(row, col);

rollback = new Rollback(maze, this); t2 = new Thread(new AThread(), \); repaint();

} else if (es.equals(\算法寻找最短路径\)) { if (maze.end == null || maze.begin == null) {

JOptionPane.showMessageDialog(null, \终点或终点没有设置！return;

JOptionPane.showMessageDialog(null, \最短路径已找到，请刷新return;

astar = new Astar(maze); astar.solve(); t2.start();

\);

} else if (t2.getState().equals(Thread.State.TERMINATED)) {

地图！\);

}

} else if (t2.getState().equals(Thread.State.NEW)) {

} else if (es.equals(\帮助\)) { JOptionPane.showMessageDialog(null,

\：设置起点\\nEnd：设置终点\\nEnter：设置墙\\nDelete：删

除墙\\nF9：演示\\n\);

} }

package maze; /** * 点坐标类 * */

public class Position{

public Position(int x, int y){ }

this.x = x; this.y = y; public int x, y; }

public Position (){

} }

package maze;

import java.awt.*; import javax.swing.*; /**

* 回溯算法实现 * */

public class Rollback {

public int isPass(Position p) {// 判断周围的通道那些没走过（东南西北） int j = p.x;

int i = p.y;

if (maze.mazeMap[i][j + 1] == 0) { }

if (maze.mazeMap[i + 1][j] == 0) { }

return 1; return 0;

public Rollback(Maze m, MazeGUI mt) { }

this.maze = m; this.mt = mt;

this.memory = new Stack(); Position curPos;// 当前位置 Stack memory;// 路径堆栈 Maze maze; MazeGUI mt;

Image person = new ImageIcon(\).getImage(); public boolean equals(Object o){ }

if(o == null){ }

if(!(o instanceof Position)){ }

Position p =(Position) o;

return this.x == p.x && this.y == p.y;

return false; return false;

{

if (maze.mazeMap[i][j - 1] == 0) { }

if (maze.mazeMap[i - 1][j] == 0) { }

return 3; return 2;

return -1; // 周围都无法通过 }

public boolean forward() {// 前进 }

public void back() {// forward()返回false时执行该方法 }

public boolean isOver() {// 判断是否结束,包括找到终点和没找到终点两种情况 if (this.curPos.x == maze.end.x && this.curPos.y == maze.end.y)

JOptionPane.showMessageDialog(null, \while (!this.memory.isEmpty()) {// 找到后，将栈清空 this.maze.mark((Position) this.memory.top(), 2); }

return true;

this.memory.pop();

this.maze.mark(this.curPos, 3);// 取消脚印 this.memory.pop();// 出栈

Position p = (Position) this.memory.top();// 获取前一个位置 if (p != null) {

this.curPos.x = p.x;// 将前一个位置设为当前位置 this.curPos.y = p.y; return;

this.maze.mark(this.curPos, 2);// 标记为已走过 int direction = this.isPass(this.curPos); if (direction == -1) {

return false;// 周围都无法通过时返回false }

int x = this.curPos.x + (1 - direction) % 2; int y = this.curPos.y + (2 - direction) % 2; this.curPos.x = x; this.curPos.y = y; remember(this.curPos); return true;

} else

found!\);

} else if (this.memory.isEmpty()) {// 栈已为空，找不到出路 JOptionPane.showMessageDialog(null, \

found!\);

}

}

return true;

return false;

public void remember(Position p) {// 保存当前路径 this.memory.push(new Position(p.x, p.y)); }

public void draw(Graphics g) {// 绘制人物的位置 if (curPos != null) { }

public void flush() {// 刷新，清空栈，并把sprite中的curPos对象恢复到初试

while (!this.memory.isEmpty()) { }

this.curPos.x = maze.begin.x; this.curPos.y = maze.begin.y; remember(this.curPos);

this.memory.pop(); }

g.drawImage(person, this.curPos.x * 50, 24 + this.curPos.y *

50, 50, null);

50,

位置 }

}

public void setCurPos(int x, int y) { }

this.curPos = new Position(x, y);

package maze; /** * 栈类 * */

public class Stack {

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

size=0; }

top=new Node(o,top); size++;

public void push(Object o){

}

}

}

if(isEmpty())return null; Object o=top.info; return o;

public Object top(){

public void pop(){ }

public boolean isEmpty(){ }

private class Node{ }

public Object info; public Node next;

public Node(Object o,Node n){//Node类构造方法 info=o; }

next=n;

return size==0;

if(isEmpty()) return ; else{ }

top=top.next; size--; return ;