Java实现基于回溯的迷宫搜索算法 --- Backtrack Based Maze Searching Algorithm in Java

 

 

• Definition: 

0. use a 2d array of integers to represent a maze;
1. 0 for passable, 1 if not;
2. the first element (maze[0][0]) is the entry;
3. the last element (maze[maze.length - 1][maze[maze.length - 1].length - 1]) is the exit;
eg.
 0, 1, 1
 1, 0, 1
 1, 1, 0

4. horizontal, vertical and diagonal moves are allowed;

 

• Question:

Find out all the possible ways out and figure out the shortest one.

 

• Solution:

0. start from the entry point of the maze, define and initialize three pointers: previous, current and next;

1. search all passable points next to current point and store them in a linked list;

2. remove one from the passable list as next, point previous to current and point current to next, then push the rest passables into a stack for later backtracking;

3. if no more passable point is found at the current position, pop one point from the stack, go back to the right place and choose a different move;

4. wrap 1-3 in a loop until all paths of the maze are searched.

 

• Codes:

0. MazeSearcher

package co.speedar.dsal.maze;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * Search all the ways out in a given maze.
 * 
 * @author ben
 * @creation 2014年4月13日
 */
public class MazeSearcher {
	/**
	 * 2d integer matrix, representing the maze.<br/>
	 * Definition: <br/>
	 * 1. 0 for passable, 1 if not;<br/>
	 * 2. the first element (maze[0][0]) is the entry;<br/>
	 * 3. the last element (maze[maze.length - 1][maze[maze.length - 1].length - 1]) is the exit;<br/>
	 * eg.<br/>
	 * 0, 1, 1<br/>
	 * 1, 0, 1<br/>
	 * 1, 1, 0<br/>
	 */
	private int[][] maze;

	/**
	 * current search trunk<br/>
	 * {currentLoc,preLoc}
	 */
	private List<Point[]> currentPath = new LinkedList<Point[]>();

	/**
	 * holds candidate movables, used for backtracking<br/>
	 * {currentLoc,preLoc,nextLoc}
	 */
	private Stack<Point[]> stack = new Stack<Point[]>();

	/**
	 * holds all the solutions.
	 */
	private List<List<Point[]>> paths = new LinkedList<List<Point[]>>();

	public MazeSearcher(int[][] maze) {
		super();
		this.maze = maze;
	}

	/**
	 * find out all the possible paths
	 */
	public void searchAllPaths() {
		Point current = new Point(0, 0);
		Point pre = null;
		Point next = null;
		// add the start point
		currentPath.add(new Point[] { current, pre });
		List<Point> movables = searchNext(current, pre);
		do {
			if (movables != null && !movables.isEmpty()) {
				// still movable
				next = movables.remove(0);
				if (movables != null && !movables.isEmpty()) {
					// has optional paths, push them into the stack for backtracking
					for (int i = 0; i < movables.size(); i++) {
						// {current position, pre position, next position}
						Point temPoint = movables.remove(0);
						System.out.println("stack.push: " + "{" + current + ","
								+ pre + "," + temPoint + "}");
						stack.push(new Point[] { current, pre, temPoint });
					}
				}
				pre = current;
				current = next;
				currentPath.add(new Point[] { current, pre });
				next = null;
			} else {
				// backtrack
				if (!stack.isEmpty() && !currentPath.isEmpty()) {
					Point[] backtrackPoints = stack.pop();
					System.out.println("stack.pop: " + "{" + backtrackPoints[0]
							+ "," + backtrackPoints[1] + ","
							+ backtrackPoints[2] + "}");
					Point[] currentPathPoints;
					while (!currentPath.isEmpty()) {
						currentPathPoints = currentPath.remove(currentPath
								.size() - 1);
						if (currentPathPoints[0].equals(backtrackPoints[0])
								&& ((currentPathPoints[1] == null && backtrackPoints[1] == null) || currentPathPoints[1]
										.equals(backtrackPoints[1]))) {
							// track back to the right position
							currentPath.add(currentPathPoints);
							break;
						}
					}
					// choose a different position at that point
					next = backtrackPoints[2];
					pre = backtrackPoints[1];
					current = backtrackPoints[0];
					pre = current;
					current = next;
					currentPath.add(new Point[] { current, pre });
					next = null;
				}
			}
			// check and save path if exit
			if (isExit(current)) {
				rememberCurrentPath();
			}
			// search next movables
			movables = searchNext(current, pre);
			// print out current path
			printCurrentPath();
		} while ((movables != null && !movables.isEmpty()) || !stack.isEmpty()); // continue loop if still movable or backtrackable
	}

	public void printCurrentPath() {
		for (Point[] currentPoints : currentPath) {
			System.out.print(currentPoints[0] + " -> ");
		}
		if (isExit(currentPath.get(currentPath.size() - 1)[0])) {
			System.out.print("end");
			System.out.println();
			System.out.println("a way out found!");
		} else {
			System.out.println();
		}
	}

	public void printShortestPath() {
		int shortestLength = paths.get(0).size();
		List<Point[]> shortestPath = paths.get(0);
		for (List<Point[]> tempPath : paths) {
			if (tempPath.size() < shortestLength) {
				shortestLength = tempPath.size();
				shortestPath = tempPath;
			}
		}
		System.out.println("The shortest path is: ");
		for (Point[] currentPoints : shortestPath) {
			System.out.print(currentPoints[0] + " -> ");
		}
		System.out.println("end");
	}

	public void printAllPaths() {
		System.out.println("Here are all the ways out: ");
		for (List<Point[]> currentPoints : paths) {
			for (Point[] points : currentPoints) {
				System.out.print(points[0] + " -> ");
			}
			System.out.println("end");
		}
	}

	private void rememberCurrentPath() {
		List<Point[]> currentPoints = new LinkedList<Point[]>();
		for (Point[] points : currentPath) {
			currentPoints.add(points);
		}
		paths.add(currentPoints);
	}

	/**
	 * the current point is exit or not
	 * 
	 * @param current
	 * @return
	 */
	private boolean isExit(Point current) {
		if (maze.length - 1 == current.x
				&& maze[maze.length - 1].length - 1 == current.y
				&& isAvailable(current)) {
			return true;
		}
		return false;
	}

	/**
	 * search all next movable positions<br/>
	 * 
	 * @param current
	 * @param pre
	 * @return
	 */
	private List<Point> searchNext(Point current, Point pre) {
		Point next = null;
		List<Point> movables = new LinkedList<Point>();
		if (isExit(current)) {
			return movables;
		}
		next = searchNorth(current);
		checkAndSaveNext(current, pre, next, movables);
		next = searchNorthEast(current);
		checkAndSaveNext(current, pre, next, movables);
		next = searchEast(current);
		checkAndSaveNext(current, pre, next, movables);
		next = searchSouthEast(current);
		checkAndSaveNext(current, pre, next, movables);
		next = searchSouth(current);
		checkAndSaveNext(current, pre, next, movables);
		next = searchSouthWest(current);
		checkAndSaveNext(current, pre, next, movables);
		next = searchWest(current);
		checkAndSaveNext(current, pre, next, movables);
		next = searchNorthWest(current);
		checkAndSaveNext(current, pre, next, movables);
		return movables;
	}

	/**
	 * 1.check if null;<br/>
	 * 2.check if available;<br/>
	 * 3.check if duplicated to previous;<br/>
	 * 4.check if circled;
	 * 
	 * @param current
	 * @param pre
	 * @param next
	 * @param movables
	 */
	private void checkAndSaveNext(Point current, Point pre, Point next,
			List<Point> movables) {
		if (next != null && isAvailable(next) && !next.equals(pre)
				&& !containsCircle(next)) {
			movables.add(next);
		}
	}

	private boolean containsCircle(Point next) {
		for (Point[] path : currentPath) {
			if (path[0].equals(next)) {
				return true;
			}
		}
		return false;
	}

	private boolean isAvailable(Point next) {
		if (maze[next.x][next.y] == 0) {
			return true;
		}
		return false;
	}

	private Point searchNorthWest(Point current) {
		Point next = null;
		if (current.x - 1 >= 0 && current.y - 1 >= 0) {
			next = new Point(current.x - 1, current.y - 1);
		}
		return next;
	}

	private Point searchWest(Point current) {
		Point next = null;
		if (current.y - 1 >= 0) {
			next = new Point(current.x, current.y - 1);
		}
		return next;
	}

	private Point searchSouthWest(Point current) {
		Point next = null;
		if (current.x + 1 < maze.length && current.y - 1 >= 0) {
			next = new Point(current.x + 1, current.y - 1);
		}
		return next;
	}

	private Point searchSouth(Point current) {
		Point next = null;
		if (current.x + 1 < maze.length) {
			next = new Point(current.x + 1, current.y);
		}
		return next;
	}

	private Point searchSouthEast(Point current) {
		Point next = null;
		if (current.x + 1 < maze.length
				&& current.y + 1 < maze[current.x + 1].length) {
			next = new Point(current.x + 1, current.y + 1);
		}
		return next;
	}

	private Point searchEast(Point current) {
		Point next = null;
		if (current.y + 1 < maze[current.x].length) {
			next = new Point(current.x, current.y + 1);
		}
		return next;
	}

	private Point searchNorthEast(Point current) {
		Point next = null;
		if (current.x - 1 >= 0 && current.y + 1 < maze[current.x - 1].length) {
			next = new Point(current.x - 1, current.y + 1);
		}
		return next;
	}

	private Point searchNorth(Point current) {
		Point next = null;
		if (current.x - 1 >= 0) {
			next = new Point(current.x - 1, current.y);
		}
		return next;
	}
}

 

1. Point

package co.speedar.dsal.maze;

/**
 * Simulates a point in the maze.
 * 
 * @author ben
 * @creation 2014年4月14日
 */
public class Point {
	/**
	 * row index
	 */
	int x;

	/**
	 * column index
	 */
	int y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}

	@Override
	public boolean equals(Object obj) {
		if (obj instanceof Point) {
			Point that = (Point) obj;
			if (this.x == that.x && this.y == that.y) {
				return true;
			}
		}
		return false;
	}

	@Override
	public String toString() {
		return "(" + this.x + "," + this.y + ")";
	}
}

 

2. MazeSearcherTest

/**
 * 
 */
package co.speedar.dsal.maze;

/**
 * @author ben
 * @creation 2014年4月14日
 */
public class MazeSearcherTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] maze = new int[4][4];
		int[] tempInts;
		tempInts = new int[] { 0, 0, 1, 1 };
		maze[0] = tempInts;
		tempInts = new int[] { 1, 1, 0, 1 };
		maze[1] = tempInts;
		tempInts = new int[] { 1, 0, 1, 0 };
		maze[2] = tempInts;
		tempInts = new int[] { 0, 1, 0, 0 };
		maze[3] = tempInts;
		MazeSearcher searcher = new MazeSearcher(maze);
		searcher.searchAllPaths();
		searcher.printAllPaths();
		searcher.printShortestPath();
	}

}

 

• Test Result:

(0,0) -> (0,1) -> 
(0,0) -> (0,1) -> (1,2) -> 
stack.push: {(1,2),(0,1),(2,1)}
(0,0) -> (0,1) -> (1,2) -> (2,3) -> 
stack.push: {(2,3),(1,2),(3,2)}
(0,0) -> (0,1) -> (1,2) -> (2,3) -> (3,3) -> end
a way out found!
stack.pop: {(2,3),(1,2),(3,2)}
(0,0) -> (0,1) -> (1,2) -> (2,3) -> (3,2) -> 
stack.push: {(3,2),(2,3),(2,1)}
(0,0) -> (0,1) -> (1,2) -> (2,3) -> (3,2) -> (3,3) -> end
a way out found!
stack.pop: {(3,2),(2,3),(2,1)}
(0,0) -> (0,1) -> (1,2) -> (2,3) -> (3,2) -> (2,1) -> 
(0,0) -> (0,1) -> (1,2) -> (2,3) -> (3,2) -> (2,1) -> (3,0) -> 
stack.pop: {(1,2),(0,1),(2,1)}
(0,0) -> (0,1) -> (1,2) -> (2,1) -> 
stack.push: {(2,1),(1,2),(3,0)}
(0,0) -> (0,1) -> (1,2) -> (2,1) -> (3,2) -> 
stack.push: {(3,2),(2,1),(3,3)}
(0,0) -> (0,1) -> (1,2) -> (2,1) -> (3,2) -> (2,3) -> 
(0,0) -> (0,1) -> (1,2) -> (2,1) -> (3,2) -> (2,3) -> (3,3) -> end
a way out found!
stack.pop: {(3,2),(2,1),(3,3)}
(0,0) -> (0,1) -> (1,2) -> (2,1) -> (3,2) -> (3,3) -> end
a way out found!
stack.pop: {(2,1),(1,2),(3,0)}
(0,0) -> (0,1) -> (1,2) -> (2,1) -> (3,0) -> 
Here are all the ways out: 
(0,0) -> (0,1) -> (1,2) -> (2,3) -> (3,3) -> end
(0,0) -> (0,1) -> (1,2) -> (2,3) -> (3,2) -> (3,3) -> end
(0,0) -> (0,1) -> (1,2) -> (2,1) -> (3,2) -> (2,3) -> (3,3) -> end
(0,0) -> (0,1) -> (1,2) -> (2,1) -> (3,2) -> (3,3) -> end
The shortest path is: 
(0,0) -> (0,1) -> (1,2) -> (2,3) -> (3,3) -> end