Java Maze Explorer Using Stacks

Question

NOT ASKING FOR CODE

I just want to make it clear I DO NOT want anyone to give me the code to solve this, I want to write it myself so I actually learn something.

NOT ASKING FOR CODE

Okay , so I need to create a class that will take a txt file that has a maze consisting of ('W' = WALL, 'S' = START, 'O' = TRAVERSABLE SPACE, 'F' = FINISH) and return a boolean true/false on whether or not the maze is solvable using stacks and/or queues.

I'm in the early stages right now, so here what I was thinking...

Could I somehow create a 2-dimensional array that would assign "coordinates" to each character in the maze? And then just go through every letter and "explode" to check in all four directions whether it can continue that way? Once the location has been explored, it will be added to a stack so it will not be explored anymore.

Would something like this work? And how can I create a 2D array?

EDIT:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;
import java.awt.Point;


public class MazeExplorer {
    public static int x;
    public static int y;

    final int mazeHeight = 12;
    final int mazeWidth = 58;
    public static char[][] mazeLocationPoints = new char[12][58];






    public static void main(String[] args) throws FileNotFoundException{

        File f = new File("Maze1.txt");
        Scanner sc = new Scanner(f);
        String mazeString = new Scanner( f ).useDelimiter("\\A").next();

        Stack<Point> points = new Stack<>();
        while(sc.hasNextLine()){
            mazeLocationPoints[][] = sc.nextLine().toCharArray();
            points.push(mazeLocations);


        }

    }

}

Answer 1

You should treat each Point as a Node that keeps track of its ancestor and children. A child is added to the list if it is not the current nodes parent and its value == 'O' Start by adding your starting node to the Queue. Pop it out and mark it visited. Add all of its children to the Queue pop them out and mark them visited. Repeat this proccess until your Queue is empty or you have found a Node whose value is 'F'

Children can be found by considering its neighboring indices and evaluating three things:

1. Is this neighboring index the parent? If yes, do not add to children
2. Are the neighboring indices within the bounds of the maze? To avoid ArrayIndexOutofBounds exceptions

3. Does the value at this node equal 'O' or 'F'. If 'O' add to children list and to queue. If 'F' you are finished.

   public class Point {
     int i;
     int j;
     char value;
     Point parent;
     ArrayList<Point> children;
   
     public static final maze[][];
   
     public Point(int i, int j, char val) {
       this.i = i;
       this.j = j;
       this.val = val
       parent = null;
       children = new ArrayList<Point>();
     }
   
     public void generateChildren() {
       if (i + 1 <= mazeHeight && j + 1 <= mazeWidth) {
         if (maze[i+1][j+1] == 'O') {
           if (!maze[i+1][j+1].equals[this.parent]) {
             Point child = new Child(i+1, j+1, 'O');
             child.parent = this;
             children.add(child);
           }
         }
       }
       // ADD LOGIC FOR OTHER CASES i -1 j -1 etc ...  
     }
   }
   

Something like this. Start my making a new Point with your Start and add it to the queue then generate its children get the children back and add them to the queue. Add logic to check if equals 'F'

Answer 2

So just to come back to this. If you don't know the size of the maze to begin with I wouldn't use a 2D array. Arrays are fixed size in Java and cannot be expanded without doing expensive operations. Alternatively you could allocate your 2D array to be larger than the maze and just fill in what you have. If you know the size then you are golden in terms of array usage.

I would suggest using an ArrayList> (or use String instead of Character if that is easier for you) to maintain your maze. This way you can build your maze very easily without knowing the sizes to begin with and have an easy time printing it.

As for the maze traversal, you will need to record the starting point and then search for the ending point. There are several choices of algorithms (some are much better than others) but if your teacher wants you to use a stack he probably wants you to use depth first search since this is the standard stack based search algorithm. Wikipedia has a great article on how it is performed.

You will also need to use a Map to maintain the locations in the maze you have already searched. Alternatively you could modify the maze itself and fill in W's after you have visited an O but this might get a bit tricky since it introduces a couple edge cases to worry about.

The end case is either you visit the F and win or your stack empties entirely and you then know the F is unreachable (since by that point you would have visited every single reachable node from the S).