maze.java

Maze solving using java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * maze.java
 *
 * Created on May 24, 2009, 6:35:01 PM
 */

package maze;

/**
 *
 * @author James Bond 007
 */

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class Maze {

    public StringBuilder output = new StringBuilder();
    
    private int rows;
    private int columns;
    private Square[][] elements;
    private Square goal;
    public int[][] map;     //Raw data loaded from file
    public int startx,starty,goalx,goaly;

    public boolean ready = false;

    //Variable for Drawing in text mode
    private static final String CLOSED_TOP = "+ - ";
    private static final String OPEN_TOP = "+   ";
    private static final String CLOSED_LEFT = "|   ";
    private static final String CLOSED_LEFT_PATH = "| . ";
    private static final String CLOSED_LEFT_START = "| S ";
    private static final String CLOSED_LEFT_GOAL = "| G ";
    private static final String OPEN_LEFT = "    ";
    private static final String OPEN_LEFT_PATH = "  . ";
    private static final String OPEN_LEFT_START = "  S ";
    private static final String OPEN_LEFT_GOAL = "  G ";

    public List<Square> opened = new ArrayList<Square>();
    public List<Square> closed = new ArrayList<Square>();
    public List<Square> bestList = new ArrayList<Square>();

    public Maze(int rows, int columns) {        //Create Random maze
        this.rows = rows;
        this.columns = columns;
        elements = new Square[rows][columns];
        createSquares();
        generateAdjacenies();
        setStartAndGoal();
        this.ready = true;
    }

    public Maze(int rows, int columns, int[][] map, int startx, int starty, int goalx, int goaly){ //Create maze using predefine map
        this.rows = rows;
        this.columns = columns;
        elements = new Square[rows][columns];
        this.map = map;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                elements[i][j] = new Square(i, j, this);
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                elements[i][j].loadAdjacencies(map);
            }
        }
        this.startx = startx;
        this.starty = starty;
        this.goalx = goalx;
        this.goaly = goaly;
        elements[startx][starty].setStart(true);
        goal = elements[goalx][goaly];
        goal.setEnd(true);
        this.ready = true;
    }

    /*Load maze from file,
     * maze file format
     * width height
     * startx starty goalx goaly
     *                  <width> element
     * next <height> line: 0 1 0 0 0 0
     * 1 is wall
     * 0 is free
     */
    public Maze (String filename) throws FileNotFoundException{              //Load maze from file
        this.ready = false;
        File mazefile = new File(filename);
        if(!mazefile.exists()){
            output.append("File not found: " + filename + "\n");
            System.out.println("File not found: " + filename);
            return;
        }
        BufferedReader reader = new BufferedReader(new FileReader(mazefile));
        String line;
        String[] arg;
        try{
            line = reader.readLine();
            arg = line.split(" ");
            if(arg.length < 2){
                output.append("Invalid file format, First line must be width and height" + "\n");
                System.out.println("Invalid file format, First line must be width and height");
                return;
            }
            this.columns = new Integer(arg[0]);
            this.rows = new Integer(arg[1]);
            this.elements = new Square[rows][columns];      //renew the map
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    elements[i][j] = new Square(i, j, this);
                }
            }
            try{
                line = reader.readLine();
                arg = line.split(" ");
                if(arg.length < 2){
                    output.append("Invalid file format, Second line must be startx starty goalx goaly" + "\n");
                    System.out.println("Invalid file format, Second line must be startx starty goalx goaly");
                    return;
                }
                startx = new Integer(arg[0]);
                starty = new Integer(arg[1]);
                goalx = new Integer(arg[2]);
                goaly = new Integer(arg[3]);

                //Load map data
                //use temp map
                map = new int[rows][columns];
                for (int i = 0; i < rows; i++) {
                    try{
                        line = reader.readLine();
                        arg = line.split(" ");
                        if(arg.length < columns){
                            output.append("Invalid file format, line " + (i+3) + " must have " + columns + " elements." + "\n");
                            System.out.println("Invalid file format, line " + (i+3) + " must have " + columns + " elements.");
                            return;
                        }
                        for (int j = 0; j < columns; j++) {
                            map[i][j] = new Integer(arg[j]);
                        }
                    }catch(Exception ex){
                        output.append("Error: " + ex.getMessage() + "\n");
                        System.out.println("Error: " + ex.getMessage());
                        output.append("Invalid file format, line " + (i+3) + " must have " + columns + " elements." + "\n");
                        System.out.println("Invalid file format, line " + (i+3) + " must have " + columns + " elements.");
                        return;
                    }
                }
                //Add map data to our real data

                /*Just test map data loaded correctly*/
                System.out.println("Loaded map from file");
                for (int i = 0; i < rows; i++) {
                    for (int j = 0; j < columns; j++) {
                        System.out.print(map[i][j] + " ");
                    }
                    System.out.println();
                }
                
                for (int i = 0; i < rows; i++) {
                    for (int j = 0; j < columns; j++) {
                        elements[i][j].loadAdjacencies(map);
                    }
                }

                //Set start and goal
                elements[startx][starty].setStart(true);
                goal = elements[goalx][goaly];
                goal.setEnd(true);
                this.ready = true;
            }catch(Exception ex){
                System.out.println("Error: " + ex.getMessage());
                return;
            }
        }catch(Exception ex){
            System.out.println("Error: " + ex.getMessage());
            return;
        }
    }

    public int getRows() {
        return rows;
    }

    public int getColumns() {
        return columns;
    }

    private void setStartAndGoal() {
        elements[0][0].setStart(true);
        Random random = new Random();
        int goalX = 0, goalY = 0;
        while (goalX == 0 && goalY == 0) {
            goalX = random.nextInt(rows);
            goalY = random.nextInt(columns);
        }
        goal = elements[goalX][goalY];
        goal.setEnd(true);
    }

    private void generateAdjacenies() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                elements[i][j].randomAdjacencies();
            }
        }
    }

    private void createSquares() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                elements[i][j] = new Square(i, j, this);
            }
        }
    }

    public Square getSquare(int x, int y) {
        return elements[x][y];
    }

    public void setSquare(Square square) {
        elements[square.getX()][square.getY()] = square;
    }

    public void draw() {
        if(!this.ready){
            System.out.println("Maze is not loaded!!!");
            output.append("Maze is not loaded!!!" + "\n");
            return;
        }
        System.out.println("Drawing maze");
        output.append("Drawing maze" + "\n");
        drawContents();
        drawBorder();
    }

    private void drawContents() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                Square square = elements[i][j];
                drawTop(square);
            }
            output.append("+" + "\n");
            System.out.println("+");
            for (int j = 0; j < columns; j++) {
                Square square = elements[i][j];
                drawLeft(square);
            }
            output.append("|" + "\n");
            System.out.println("|");
        }
    }

    private void drawLeft(Square square) {
        int x = square.getX();
        int y = square.getY();
        if (y - 1 < 0) {
            if (square.isStart()) {
                    System.out.print(CLOSED_LEFT_START);
                    output.append(CLOSED_LEFT_START);
                    return;
            }
            if (square.isEnd()) {
                    System.out.print(CLOSED_LEFT_GOAL);
                    output.append(CLOSED_LEFT_GOAL);
                    return;
            }
            if (bestList.contains(square)) {
                    System.out.print(CLOSED_LEFT_PATH);
                    output.append(CLOSED_LEFT_PATH);
                    return;
            }
            System.out.print(CLOSED_LEFT);
            output.append(CLOSED_LEFT);
            return;
        }

        for (Square neighbor : square.getAdjacencies()) {
            if (neighbor.getX() == x && neighbor.getY() == y - 1) {
                if (square.isEnd()) {
                    System.out.print(OPEN_LEFT_GOAL);
                    output.append(OPEN_LEFT_GOAL);
                    return;
                }
                if (bestList.contains(square)) {
                    System.out.print(OPEN_LEFT_PATH);
                    output.append(OPEN_LEFT_PATH);
                    return;
                }
                System.out.print(OPEN_LEFT);
                output.append(OPEN_LEFT);
                return;
            }
        }

        if (square.isEnd()) {
            System.out.print(CLOSED_LEFT_GOAL);
            output.append(CLOSED_LEFT_GOAL);
            return;
        }

        if (bestList.contains(square)) {
            System.out.print(CLOSED_LEFT_PATH);
            output.append(CLOSED_LEFT_PATH);
            return;
        }
        System.out.print(CLOSED_LEFT);
        output.append(CLOSED_LEFT);
    }

    private void drawTop(Square square) {
        int x = square.getX();
        int y = square.getY();
        if (x == 0) {
            System.out.print(CLOSED_TOP);
            output.append(CLOSED_TOP);
            return;
        }
        for (Square neighbor : square.getAdjacencies()) {
            if (neighbor.getX() == x - 1 && neighbor.getY() == y) {
                System.out.print(OPEN_TOP);
                output.append(OPEN_TOP);
                return;
            }
        }
        System.out.print(CLOSED_TOP);
        output.append(CLOSED_TOP);
    }

    private void drawBorder() {
        for (int i = 0; i < columns; i++) {
            System.out.print(CLOSED_TOP);
            output.append(CLOSED_TOP);
        }
        System.out.println("+");
        output.append("+\n");
    }

    public void findBestPath() {
        if(!this.ready){
            System.out.println("Maze is not loaded!!!");
            output.append("Maze is not loaded!!!\n");
            return;
        }
        System.out.println("Calculating best path...");
        output.append("Calculating best path...\n");
        Set<Square> adjacencies = elements[0][0].getAdjacencies();
        for (Square adjacency : adjacencies) {
            adjacency.setParent(elements[0][0]);
            if (adjacency.isStart() == false) {
                opened.add(adjacency);
            }
        }
        while (opened.size() > 0) {
            Square best = findBestPassThrough();
            opened.remove(best);
            closed.add(best);
            if (best.isEnd()) {
                System.out.println("Found Goal");
                output.append("Found goal\n");
                populateBestList(goal);
                draw();
                return;
            } else {
                Set<Square> neighbors = best.getAdjacencies();
                for (Square neighbor : neighbors) {
                    if (opened.contains(neighbor)) {
                        Square tmpSquare = new Square(neighbor.getX(), neighbor.getY(), this);
                        tmpSquare.setParent(best);
                        if (tmpSquare.getPassThrough(goal) >= neighbor.getPassThrough(goal)) {
                            continue;
                        }
                    }

                    if (closed.contains(neighbor)) {
                        Square tmpSquare = new Square(neighbor.getX(), neighbor.getY(), this);
                        tmpSquare.setParent(best);
                        if (tmpSquare.getPassThrough(goal) >= neighbor.getPassThrough(goal)) {
                            continue;
                        }
                    }
                    neighbor.setParent(best);
                    opened.remove(neighbor);
                    closed.remove(neighbor);
                    opened.add(0, neighbor);
                }
            }
        }
        System.out.println("No Path to goal");
        output.append("No Path to goal\n");
    }

    private void populateBestList(Square square) {
            bestList.add(square);
            if (square.getParent().isStart() == false) {
                populateBestList(square.getParent());
            }
            return;
    }

    private Square findBestPassThrough() {   //Find min square with minimum distance to goal
        Square best = null;
        for (Square square : opened) {
            if (best == null || square.getPassThrough(goal) < best.getPassThrough(goal)) {
                best = square;
            }
        }
        return best;
    }
}