I am unable to display the path taken inside my maze from start to finish

Question

I am reading the maze outline in from an input file and storing the values in a 2D array. I am able to find the exit in my findPath() method, but i am unsure how to trace the actual path from start to finish.

I want to change the char value in the "Room" to a '.' if it is on the actual path. Please advise how i can accomplish this. Any help is greatly appreciated. Thanks.

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.*;
import javax.swing.JOptionPane;

public class Maze {
    String inFile,   // Name of file to be used as input
           outFile,  // Name of file to output completed maze to
           line;     // Current line being read by scanner
    Room [][] rooms; // Holds the values that create maze
    Room [] theStack;
    Room goal;
    Room current = new Room();
    int rows, columns;
    int tos = 0;
    char [][] mazeC;

    public static void main(String []args) throws Exception {
        Maze m = new Maze();
    }

    public Maze() throws FileNotFoundException {
        // Prompts user for the name of the file they wish to use as the input file.
        inFile = JOptionPane.showInputDialog(null, "Please enter the name of the file you wish to read, including " + "the file path:");
        if(inFile.equals("")) inFile = "C:/java/javaFiles/maze1.txt";

        // Prompts user to enter the name they wish to save the file under.
        outFile = JOptionPane.showInputDialog(null, "Please enter the filename you wish to save the data to:");
        if(outFile.equals("")) outFile = "C:/java/javaFiles/mazeoutput1.txt";

        // Creates a scanner object to read in the input file.
        Scanner readFile = new Scanner(new FileReader(inFile));
        PrintWriter output = new PrintWriter(outFile);        
        rows = readFile.nextInt();
        columns = readFile.nextInt();
        readFile.nextLine();
        theStack = new Room[1000];
        rooms = new Room [rows][columns];
        for(int i = 0; i < rows; i++) {
            line = readFile.nextLine();
            for(int j = 0; j< line.length(); j++) {
                Room r = new Room();
                r.setValue(line.charAt(j));
                if(r.getValue() == '$')
                    r.setGoal(true);
                r.setBlocked(false);
                if (r.getValue() == '*') {
                    r.setBlocked(true);
                    r.setGoal(false);
                } else {
                    r.setGoal(false);
                    r.setBlocked(false);
                }
                r.setCord(i, j);
                rooms[i][j] = r;
                //mazeContent[i][j]  = line.charAt(j);    
            }
        }

        createRooms();

        findPath();
        for(int i = 0; i < rows ; i++) {
            for(int j = 0; j < columns ; j++) {
                System.out.print(rooms[i][j].getValue());
            }
            System.out.println();
        }
    }

    public void createRooms() {
        for(int i = 1; i < rows - 1; i++) {
            for(int j = 1; j < columns -1; j++) {
                rooms[i][j].setCord(i,j);
                rooms[i][j].setValue(rooms[i][j].getValue());
                rooms[i][j].setUp(rooms, i, j);
                rooms[i][j].setDown(rooms, i, j);
                rooms[i][j].setRight(rooms, i, j);
                rooms[i][j].setLeft(rooms, i, j);
                if(rooms[i][j].getValue() == '*')
                    rooms[i][j].setBlocked(true);
                else
                    rooms[i][j].setBlocked(false);

                //System.out.println(rooms[i][j].getValue());
            }
        }
    }

    public void findPath() {
        for(int i = 0; i < rows ; i++) {
            for(int j = 0; j < columns ; j++) {
                System.out.print(rooms[i][j].getValue());
            }
            System.out.println();
        }
        Room start = rooms[1][1];
        push(start);
        while(!isEmpty()) { 
            current = pop();
            System.out.println("The value stored in current is" + current.getValue()+ "");
            if (current == null) 
                System.out.println("current is null");
            else if(current.getValue() == '$') {
                System.out.println("Success"); 
                current.setValue('f');
                /*for (int i = 0; i < tos; i++) {
                }*/
            }
            //System.out.println("The value is " + current.getValue());
            else if(current.getBlocked() == false && current.getVisited() == false) {
                System.out.println("pushing currents neighbors left, right....etc" + 
                    "current is at" +  current.getCord());
                current.setVisited(true);
                //
                if(current.getRight() != null){
                    push(current.getRight()); System.out.println("Inside push 1" +current.getRight().getCord());}
                else System.out.println("Inside push right is null");
                if(current.getLeft() != null){
                    push(current.getLeft()); System.out.println("Inside push 2 " + current.getLeft().getCord());}
                else System.out.println("Inside push left is null");
                if(current.getUp() != null)  {
                    push(current.getUp()); System.out.println("Inside push 3" + current.getUp().getCord());}
                else System.out.println("Inside push up is null");
                if(current.getDown() != null) {
                    push(current.getDown()); System.out.println("inside push 4" + current.getDown().getCord());}
                else System.out.println("Inside push down is null");
            }
        }
    }

    public Room pop() {
        // TODO Auto-generated method stub
        System.out.println("I have Popped");
        return theStack[--tos];
    }

    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return tos == 0;
    }

    public void push(Room item) {
        System.out.println("I have pushed");
        if (isFull()) {
            System.out.println("The stack is full!");
        }
        else if(item == null){
            System.out.println("you are pushing a null object");
        }
        else 
            System.out.println("stuff added");
        theStack[tos++] = item;
    }

    public boolean isFull() {
        return tos == theStack.length-1;
    }
 }

Answer 1

I haven't really gone through your code line by line but here's a solution: (I wrote a similar program for finding Djikstra's shortest path in a graph)

Make an attribute called PREVIOUS in your room object. Every time you go to a 'next room', make sure you change your next room's PREVIOUS attribute to the room you came from.

When you reach your destination: Start with your destination's PREVIOUS and traverse back through the rooms until you hit a room with no PREVIOUS, which will be your source (start) room. i.e. go to the PREVIOUS room, add it to the stack, go to its PREVIOUS and repeat the process until you hit your starting room.

This should work because: If you go through a path of rooms and you hit a dead-end you will back track and start going through a new path. Eventually you will recursively over-write the PREVIOUS attribute for each room in your new path (every time). When you hit your destination, you will have the most updated (correct) PREVIOUS attribute in every room in your current (correct) path. So traverse back and add the PREVIOUS of each room to a stack or a queue or (whatever you want) as you go. This should give you your path.