Maze DFS/BFS example file for Coursera : UCSD Advanced Data Structures - Week 2

Coordinate.java

package util;

public class Coordinate {
	private int row;
	private int col;
	
	public Coordinate(int row, int col) {
		this.row = row;
		this.col = col;
	}
	
	public int getRow() {
		return row;
	}

	public void setRow(int row) {
		this.row = row;
	}

	public int getCol() {
		return col;
	}

	public void setCol(int col) {
		this.col = col;
	}

	@Override
	public String toString() {
		return "Coordinate [row=" + row + ", col=" + col + "]";
	}
	
}

Maze.java

/**
 * A class that represents a maze to navigate through.
 */
package week2example;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

import util.Coordinate;

/**
 * 
 *
 */
public class Maze {
	enum SearchType { DFS, BFS };
	
	private MazeNode[][] cells;
	private int width;
	private int height;

	private final int DEFAULT_SIZE = 10;

	public Maze() {

		initialize(DEFAULT_SIZE, DEFAULT_SIZE);
	}

	/** Create a new empty Maze */
	public Maze(int width, int height) {
		initialize(width, height);
	}

	private void initialize(int width, int height) {
		cells = new MazeNode[height][width];
		this.width = width;
		this.height = height;

	}

	public void addNode(int row, int col) {
		cells[row][col] = new MazeNode(row, col);
	}

	/**
	 * Link the nodes that are adjacent (and not null) to each other with an
	 * edge. There is an edge between any two adjacent nodes up, down, left or
	 * right.
	 */
	public void linkEdges() {
		for (int row = 0; row < height; row++) {
			for (int col = 0; col < width; col++) {
				if (cells[row][col] != null) {
					if (row > 0 && cells[row - 1][col] != null) {
						cells[row][col].addNeighbor(cells[row - 1][col]);
					}
					if (col > 0 && cells[row][col - 1] != null) {
						cells[row][col].addNeighbor(cells[row][col - 1]);
					}
					if (row < height - 1 && cells[row + 1][col] != null) {
						cells[row][col].addNeighbor(cells[row + 1][col]);
					}
					if (col < width - 1 && cells[row][col + 1] != null) {
						cells[row][col].addNeighbor(cells[row][col + 1]);
					}
				}
			}
		}
	}

	public void printMaze() {
		for (int r = 0; r < height; r++) {
			for (int c = 0; c < width; c++) {
				if (cells[r][c] == null) {
					System.out.print('*');
				} else {
					System.out.print(cells[r][c].getDisplayChar());
				}
			}
			System.out.print("\n");
		}

	}

	public void setPath(List<MazeNode> path) {
		int index = 0;
		for (MazeNode n : path) {
			if (index == 0) {
				n.setDisplayChar(MazeNode.START);
			} else if (index == path.size() - 1) {
				n.setDisplayChar(MazeNode.GOAL);
			} else {
				n.setDisplayChar(MazeNode.PATH);
			}
			index++;
		}

	}

	public void clearPath() {
		for (int r = 0; r < cells.length; r++) {
			for (int c = 0; c < cells[r].length; c++) {
				MazeNode n = cells[r][c];
				if (n != null) {
					n.setVisited(false);
					n.setDisplayChar(MazeNode.EMPTY);
				}
			}
		}
	}
	
	public List<MazeNode> dfs(Coordinate startPoint, Coordinate endPoint) {
		return search(startPoint, endPoint, SearchType.DFS);
	}
	public List<MazeNode> bfs(Coordinate startPoint, Coordinate endPoint) {
		return search(startPoint, endPoint, SearchType.BFS);
	}

	public List<MazeNode> search(Coordinate startPoint, Coordinate endPoint, SearchType searchType) {
		
		MazeNode start = cells[startPoint.getRow()][startPoint.getCol()];
		MazeNode goal = cells[endPoint.getRow()][endPoint.getCol()];

		if (start == null || goal == null) {
			System.out.println("Start or goal node is null!  No path exists.");
			return new LinkedList<MazeNode>();
		}

		boolean found = searchPath(start, goal, searchType);
		
		if (!found) {
			System.out.println("No path exists");
			return new LinkedList<MazeNode>();
		}

		return constructPath(start, goal);
	}
	
	private boolean searchPath(MazeNode start, MazeNode goal, SearchType searchType)
	{
		Deque<MazeNode> toExplore = new LinkedList<MazeNode>();
		if (searchType == SearchType.DFS) {
			toExplore.push(start);
		} else {
			toExplore.add(start);
		}
		boolean found = false;

		// Do the search
		while (!toExplore.isEmpty()) {
			MazeNode curr = (searchType == SearchType.DFS)? toExplore.pop() : toExplore.remove();
			if (curr == goal) {
				found = true;
				break;
			}
			List<MazeNode> neighbors = curr.getNeighbors();
			ListIterator<MazeNode> it = neighbors.listIterator(neighbors.size());
			while (it.hasPrevious()) {
				MazeNode next = it.previous();
				if (!next.isVisited()) {
					next.setVisited(true);;
					next.setParent(curr);
					if (searchType == SearchType.DFS) {
						toExplore.push(next);
					} else {
						toExplore.add(next);
					}
				}
			}
		}
		return found;
	}
	
	private List<MazeNode> constructPath(MazeNode start, MazeNode goal)
	{
		LinkedList<MazeNode> path = new LinkedList<MazeNode>();
		MazeNode curr = goal;
		while (curr != start) {
			path.addFirst(curr);
			curr = curr.getParent();
		}
		path.addFirst(start);
		return path;
	}
	
	public static void main(String[] args) {
		String mazeFile = "data/mazes/maze2.maze";
		Maze maze = MazeLoader.loadMaze(mazeFile);		
		maze.printMaze();
		List<MazeNode> path = maze.dfs(new Coordinate(9, 9),new Coordinate(0, 0));
		maze.setPath(path);
		System.out.println("\n");
		maze.printMaze();
		maze.clearPath();
		maze.setPath(maze.bfs(new Coordinate(9, 9), new Coordinate(0, 0)));
		System.out.println("\n");
		maze.printMaze();
	}
}

MazeLoader.java

/**
 * 
 */
package week2example;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.List;


/**
 * @author Christine
 *
 */
public class MazeLoader {

	public static Maze loadMaze(String filename)
	{
		Maze maze = null;
		BufferedReader reader = null;
		try {
            String nextLine;
            int width = 0;
            int height = 0;
            reader = new BufferedReader(new FileReader(filename));
            if ((nextLine = reader.readLine()) != null) {
            	String[] dims = nextLine.split(" ");
            	width = Integer.parseInt(dims[0]);
            	height = Integer.parseInt(dims[1]);
            	maze = new Maze(width, height);
            }
            int currRow = 0;
            int currCol = 0;
            while ((nextLine = reader.readLine()) != null) {
            	currCol = 0;
            	for (char c : nextLine.toCharArray()) {
            		if (c != '*') {
            			maze.addNode(currRow, currCol);
            		}
            		currCol++;
            	}
            	while (currCol < width) {
            		maze.addNode(currRow, currCol);
            		currCol++;
            	}
            	currRow++;
            	
            }
            while (currRow < height) {
            	for (int c = 0; c<width; c++) {
            		maze.addNode(currRow, c);
            	}
            	currRow++;
            }
    		reader.close();
		} catch (IOException e) {
            System.err.println("Problem loading maze file: " + filename);
            e.printStackTrace();
        }

		maze.linkEdges();
		return maze;
	}
	
}

MazeNode.java

/**
 * 
 */
package week2example;

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

/**
 * MazeNode.java
 * 
 * @author UCSD Intermediate Programming MOOC team
 * 
 * A class to represent a Node in a graph which is a Maze that the robot navigates.
 */
public class MazeNode {
	private List<MazeNode> neighbors;
	// Since our maze is always a grid, nodes keep track of their row and column
	private int row;
	private int column;
	private char displayChar;
	private boolean visited;
	private MazeNode parent;
	
	public static final char EMPTY = '-';
	public static final char PATH = 'o';
	public static final char START = 'S';
	public static final char GOAL = 'G';

	/**
	 * @return the displayChar
	 */
	public char getDisplayChar() {
		return displayChar;
	}

	/**
	 * @param displayChar the displayChar to set
	 */
	public void setDisplayChar(char displayChar) {
		this.displayChar = displayChar;
	}

	public MazeNode(int row, int col)
	{
		this.row = row;
		this.column = col;
		neighbors = new LinkedList<MazeNode>();
		displayChar = EMPTY;
		visited = false;
	}

	public void addNeighbor(MazeNode neighbor) 
	{
		neighbors.add(neighbor);
	}
	
	/**
	 * @return the neighbors
	 */
	public List<MazeNode> getNeighbors() {
		return neighbors;
	}

	/**
	 * @return the row
	 */
	public int getRow() {
		return row;
	}

	/**
	 * @return the column
	 */
	public int getColumn() {
		return column;
	}
	public boolean isVisited() {
		return visited;
	}
	
	public void setVisited(boolean visited) {
		this.visited = visited;
	}
	public MazeNode getParent() {
		return parent;
	}
	public void setParent(MazeNode parent) {
		this.parent = parent;
	}
}