labyrinth.java

数据结构中的迷宫算法

package labyrinth;

import java.util.EmptyStackException;
import java.util.Stack;

class Labyrinth {
	Location[][] path;

	int startX = 1;

	int startY = 0;

	int endX;

	int endY;

	static Labyrinth labyrinth;

	Car car;

	Stack stack = new Stack();

	public final static Labyrinth getLabyrinth() {
		if (labyrinth == null) {
			// 在这里初始化path
			labyrinth = new Labyrinth();
			labyrinth.iniPath(10, 10);
			labyrinth.creatBalks();
			return labyrinth;
		}
		return labyrinth;
	}

	private Labyrinth() {

	}

	public final void iniPath(int w, int h) {
		endX = w - 2;
		endY = h - 1;
		path = new Location[w][h];
		for (int i = 0; i < w; i++) {
			for (int j = 0; j < h; j++) {
				path[i][j] = new Location(i, j, 1);
			}
		}
	}

	AnimaPanel ap;

	public final void creatBalks() {
		for (int i = 0; i < path[0].length; i++) {
			path[0][i].balk = true;
			path[path.length - 1][i].balk = true;
			path[i][0].balk = true;
			path[i][path[0].length - 1].balk = true;
		}
		path[1][0].balk = false;
		path[8][9].balk = false;
		path[1][3].balk = true;
		path[1][7].balk = true;
		path[2][3].balk = true;
		path[2][7].balk = true;
		path[3][5].balk = true;
		path[3][6].balk = true;
		path[4][2].balk = true;
		path[4][3].balk = true;
		path[4][4].balk = true;
		path[5][4].balk = true;
		path[6][2].balk = true;
		path[6][6].balk = true;
		path[7][2].balk = true;
		path[7][3].balk = true;
		path[7][4].balk = true;
		path[7][6].balk = true;
		path[7][7].balk = true;
		path[8][1].balk = true;
		path[8][7].balk = true;
	}

	public void resetLocation(boolean balked) {
		for (int i = 0; i < path.length; i++) {
			for (int j = 0; j < path[0].length; j++) {
				path[i][j].direction = 1;
				path[i][j].passed = false;
				path[i][j].finishSeek = false;
				if (balked) {
					path[i][j].balk = false;
				}
			}
		}
		stack.clear();
	}

	public final void getAway() throws EmptyStackException {
		int curx = 0, cury = 0;
		do {
			curx = car.curx;
			cury = car.cury;
			// System.out.println(curx+" "+cury);
			if (curx == endX && cury == endY) {
				ap.ready();
				ap.start(true);
				ToolPanel.win = true;
				ToolPanel.end = true;
				ap.repaint();
				new Thread(ap).start();
				return;
			}
			if (car.direction != 1) {
				if (curx == startX && cury == startY) {
					resetLocation(false);
					car.reset();
					ap.reset();
				}
			}

			if (path[curx][cury].canPass()) {
				// System.out.println("in canpass--"+curx+" "+cury);
				path[curx][cury].passed = true;
				stack.push(path[curx][cury]);
				// animation 从上一个位置到现在的位置
				ap.ready();
				if (!ap.start(true)) {
					return;
				}
				car.lastx = curx;
				car.lasty = cury;
				goToNext(curx, cury);

				if (path[curx][cury].direction++ == 4) {
					path[curx][cury].finishSeek = true;
				}

			} else {
				// System.out.println("in no pass--"+curx+" "+cury);
				Location lpath = (Location) stack.pop();
				car.curx = lpath.x;
				car.cury = lpath.y;
				while (lpath.finishSeek) {
					car.curx = lpath.x;
					car.cury = lpath.y;
					lpath = (Location) stack.pop();
					// System.out.println("in while pop"+lpath.x+" "+lpath.y);
					changeCarLocation(lpath.x, lpath.y);
					ap.ready();
					if (!ap.start(true)) {
						return;
					}
				}
				if (!lpath.finishSeek) {
					stack.push(lpath);
					car.lastx = car.curx;
					car.lasty = car.cury;
					goToNext(lpath.x, lpath.y);
					if (lpath.direction++ == 4) {
						lpath.finishSeek = true;
					}
				}
			}

		} while (!stack.empty() && ToolPanel.active);
	}

	public final void goToNext(int curx, int cury) {
		switch (path[curx][cury].direction) {
			case 1:
				car.cury++;
				break;
			case 2:
				car.curx++;
				break;
			case 3:
				car.cury--;
				break;
			case 4:
				car.curx--;
				break;
			default:
				// System.out.println("invalid value");
				break;
		}
	}

	public final void changeCarLocation(int x, int y) {
		// System.out.println("in changeCarlocation");
		car.lastx = car.curx;
		car.lasty = car.cury;
		car.curx = x;
		car.cury = y;
	}
}