Finding the "missing link" in a maze solving lab

[Curious Gorge]

Hey so I am trying to finish up a lab that I did not finish during a class this summer. The goal is to have the computer navigate an ASCII maze on its own. We use left/right hand rule to find our way through the maze. IE. you have your hands out to your side and if it is open we take a turn down that hallway. We leave breadcrumbs behind us to mark our taken path. In this version of the lab we are to have it recall its path between different trail runs, and use the best path to find the exit.

So far it successfully finds the finish point after some wrong turns and backtracking. There is a slight but difficult problem that needs solving to finish this first stage.

Here I will describe how I go about solving the maze and storing the path in memory.

I have a Linked List for X/Y coordinate pairs (contained inside a class called PathElement). At each turn (including turning down hallways that have already been tracked over once) I store that coordinate in to the list.

The slight but difficult problem to solve occurs in maze1. A few turns prior to finding the finish line, there is an intersection. Because it is an intersection it does not get stored in the path list. It is the quintessential "missing link". I have managed to separate the path elements in the list to different lists, one for paths that have been tracked over once, and the other for paths that have been tracked over more than once.

That part was sort of simple.

This "missing link" has been difficult to figure out how to store in the path list.

As I write this I'm thinking maybe if all adjacent array elements are "open" (ie. open or a breadcrumb) I could just store it in the list. That seems simplest.

But I will provide some illustrations just for good measure

Best Path

The red being the path which has only been tracked over once. Every right angle in both of these pictures is a PathElement node because it gets stored when the computer makes a turn.

Worst Path

The worst path photo changes colors every time it begins backtracking. The blue square is where the first photo's path ends, and the worst path begings. The purple is the terminal path.

I just need an easier way to find that intersection just south of the F circled in black. It does not currently findable in my list because even though it is a turn, it only shows up once (after making the green turn headed west it does not make a turn coming back instead taking the purple path straight through it).

[rproffitt]

I don't see any code so you may be working on getting that here. Read https://www.daniweb.com/programming/threads/435023/read-this-before-posting-a-question so you know what works best here.

This sounds similar to https://www.cs.bu.edu/teaching/alg/maze/
And a Wikipedia on this subject. https://en.wikipedia.org/wiki/Maze_solving_algorithm
And prior discussions with https://www.google.com/search?q=computer+navigate+an+ASCII+maze+on+its+own.

[Curious Gorge]

Just a question, but did you read my question?

I already have managed to solve the maze. I do not need a suggestion on which algorithm to use. The problem is finding that missing intersection coordinate to complete the best path.

I just need a simpler way to solve that.

It was not mentioned in my original post how I was trying to solve it.

I was trying to take the end of the best path, and move outward from its position in the ASCII maze until either hitting a wall or the finish.

IE. if in first image, "Best Path" I started there at the end of the red trail. Then if I tried going to the right and found a wall; I would then traverse left down the hall. If at some point I reach an open path (not a breadcrumb) I would head down that hallway again, until I reach a wall or the finish point.

Then I would take the coordinate of that position and add it to my best path list.

The problem with this solution is that it is very complicated. Its also difficult to debug. I've been bogged down trying to come up with a decent implementation all day.

I do not need code. I don't need algorithms. I need a general depiction of how one might find that intersection to store it in my path.

I'm just asking how you would solve this if you had this problem. I need advice on how to solve this. Not code. I prefer to do my coding on my own because I feel I am capable enough given a proper description.

[rproffitt]

I read it but this is a well beaten topic. There are 8 methods alone in the Wiki article so you pick the method you want and code accordingly.

[JamesCherrill]

rproffitt: Sorry, but it does look to me like you have missed Gorge's point. He has got a working algorithm, but has a specific problem with intersections that have 4 (or more?) exits. Sorry if I have misunderstood your replies.

To me it looks like an artifact of the details of the implementation code, but without seeing the code and spending a lot of time I can't suggest anything specific. This Java exercise is typically most easily solved with a simple recursive exhaustive search, which would not have Gorge's problem (as I understand it).

[AssertNull]

Ah, mazes. Love 'em. I read your posts a few times and I sort of get what you're going for, but not entirely. I'm a little confused about the dilemma of "finding" an intersection. If you have a choice of going straight, left, or right, you've "found" an intersection. "Found" is in quotes here because it's really just stumbling across an intersection noticing that there are no walls, and saying "I'm now at an intersection".

As for the linked list, I'm having a bit of trouble visualizing how that would work. I always did it with a 2-D array. For the bread crumbs I would initialize everything to 0, then increment my current location every time I took a step. For a known dead end, I'd flag it with a negative number, which I would treat exactly like a wall.

Algorithm-wise, when confronted with a new intersection, you appear to be choosing to go straight. It seems easier and more trouble-free to go right if you reach an intersection if it has not already been tried. I'll reiterate that I don't understand about "finding" an intersection.

[Curious Gorge]

Ok so now we're rolling!

This is my code.

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

import java.util.Random;
import java.util.Scanner;
import java.util.LinkedList;
import java.io.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.swing.*;

/**
 *
 * @author hunterl
 */
public class Maze extends JFrame {

    private static final int MAX_WIDTH = 255;
    private static final int MAX_HEIGHT = 255;
/*@author CuriousGorge */
    private static LinkedList<PathElement> path = new LinkedList<PathElement>();
    private static DataManager pathDatafile = new DataManager();
    private static PathElement elem1 = null;
    private static int pathSize = -1;
    private static boolean bestPathFound = false, atStart = true;
/*@author CuriousGorge end of [code section]*/
    private char[][] maze = new char[MAX_HEIGHT][MAX_WIDTH];

    private Random random = new Random();
    private JPanel mazePanel = new JPanel();
    private int width = 0;
    private int height = 0;
    private boolean step = false;

    private boolean timerFired = false;
    private Timer timer;
    private final int TIMER_DELAY = 200;

    private final int SPRITE_WIDTH = 25;
    private final int SPRITE_HEIGHT = 25;

    private BufferedImage mazeImage;
    private ImageIcon ground = new ImageIcon("sprites/ground.png");
    private ImageIcon wall1 = new ImageIcon("sprites/cactus.png");
    private ImageIcon wall2 = new ImageIcon("sprites/rock.png");
    private ImageIcon finish = new ImageIcon("sprites/well.png");
    private ImageIcon south1 = new ImageIcon("sprites/cowboy-forward-1.png");
    private ImageIcon south2 = new ImageIcon("sprites/cowboy-forward-2.png");
    private ImageIcon north1 = new ImageIcon("sprites/cowboy-back-1.png");
    private ImageIcon north2 = new ImageIcon("sprites/cowboy-back-2.png");
    private ImageIcon west1 = new ImageIcon("sprites/cowboy-left-1.png");
    private ImageIcon west2 = new ImageIcon("sprites/cowboy-left-2.png");
    private ImageIcon east1 = new ImageIcon("sprites/cowboy-right-1.png");
    private ImageIcon east2 = new ImageIcon("sprites/cowboy-right-2.png");

    private long startTime;
    private long currentTime;

    /**
     * Constructor for class Maze. Opens a text file containing the maze, then
     * attempts to solve it.
     *
     * @param fname
     *            String value containing the filename of the maze to open.
     */
    public Maze(String fname) {
        pathDatafile = new DataManager();
        if (pathDatafile.open("paths_for_" + fname, (char) 255)) // If the file was opened, not created
        {
            initPathsList(); // Means we have traversed the maze at least once. Make sure to initialize the
                                // path list
        }
        openMaze(fname);
        mazeImage = printMaze();

        timer = new Timer(TIMER_DELAY, new TimerHandler()); // setup a Timer to slow the animation down.
        timer.start();

        addWindowListener(new WindowHandler()); // listen for window event windowClosing

        setTitle("Cowboy Maze");
        setSize(width * SPRITE_WIDTH + 10, height * SPRITE_HEIGHT + 30);
        setVisible(true);

        add(mazePanel);
        setContentPane(mazePanel);

        solveMaze();
    }

    /**
     * Called from the operating system. If no command line arguments are supplied,
     * the method displays an error message and exits. Otherwise, a new instance of
     * Maze() is created with the supplied filename from the command line.
     *
     * @param args[]
     *            Command line arguments, the first of which should be the filename
     *            to open.
     */

    public static void initPathsList() {
        if (pathDatafile.fileSize() != 0) {
            bestPathFound = true;

            int y = -1, x = -1;

            do { // So long as we still have something to get
                /* Read a pair of path element data */
                y = pathDatafile.readInteger();
                x = pathDatafile.readInteger();
                if (y != -1 && x != -1) {
                    path.add(new PathElement(y, x));
                }
            } while (!pathDatafile.isAtEOF());
            pathSize = path.size();
            pathDatafile.reset();
            System.out.println("Done reading file.");
        }
    }

    public static void main(String[] args) {

        if (args.length > 0) {

            new Maze(args[0]);

        } else {
            System.out.println();
            System.out.println("Usage: java Maze <filename>.");
            System.out.println("Maximum Maze size:" + MAX_WIDTH + " x " + MAX_HEIGHT + ".");
            System.out.println();
            System.exit(1);
        }
    }

    /**
     * Finds the starting location and passes it to the recursive algorithm solve(x,
     * y, facing). The starting location should be the only '.' on the outer wall of
     * the maze.
     */
    public void solveMaze() {
        boolean startFound = false;
        if (!startFound) {
            for (int i = 0; i < width; i++) { // look for the starting location on the top and bottom walls of the Maze.
                if (maze[0][i] == '.') {
                    preSolve(i, 0, "south");
                    startFound = true;
                } else if (maze[height - 1][i] == '.') {
                    preSolve(i, height - 1, "north");
                    startFound = true;
                }
            }
        }
        if (!startFound) {
            for (int i = 0; i < height; i++) { // look for the starting location on the left and right walls of the
                                                // Maze.
                if (maze[i][0] == '.') {
                    preSolve(0, i, "east");
                    startFound = true;
                } else if (maze[i][width - 1] == '.') {
                    preSolve(width - 1, i, "west");
                    startFound = true;
                }
            }
        }
        if (!startFound) {
            System.out.println("Start not found!");
        }
    }

    public void preSolve(int x, int y, String facing) {
        // Graphics2D g2 = (Graphics2D)mazePanel.getGraphics();
        // g2.drawImage(mazeImage, null, 0, 0);
        // g2.drawImage(printGuy(facing), x*SPRITE_WIDTH, y*SPRITE_HEIGHT, null, null);
        Scanner input = new Scanner(System.in);
        System.out.println("Press 1 to start");
        input.nextLine();
        startTime = System.currentTimeMillis();
        solve(y, x, -1, facing, null);
    }

    /**
     * Recursive algorithm to solve a Maze. Places a X at locations already visited.
     * This algorithm is very inefficient, it follows the right hand wall and will
     * never find the end if the path leads it in a circle.
     *
     * @param x
     *            int value of the current X location in the Maze.
     * @param y
     *            int value of the current Y location in the Maze.
     * @param facing
     *            String value holding one of four cardinal directions determined by
     *            the current direction facing.
     */
    private void solve(int y, int x, int steps, String facing, PathElement elem2) { // @hunterl I changed the order of
                                                                                    // the x,y
        // arguments to solve(), was expecting a
        // different order than your original. Also added 'int steps' argument
        Graphics2D g2 = (Graphics2D) mazePanel.getGraphics(); // don't mess with the next

        while (!timerFired) { // wait for the timer.
            try {
                Thread.sleep(10);
            } catch (Exception e) {
            }
        }
        timerFired = false;
        currentTime = System.currentTimeMillis();
        if ((currentTime - startTime) > 5000000) {
            closingMethod();
        }

        // Do not mess with the above part of this method
        // Below is where you put your solution to solving the maze.
        if (maze[y][x] != 'F') { // this is if it doesn't find the finish on a turn.........
            g2.drawImage(mazeImage, null, 0, 0);
            g2.drawImage(printGuy(facing), x * SPRITE_WIDTH, y * SPRITE_HEIGHT, null, null);
            mazePanel.setSize(width * SPRITE_WIDTH + 10, height * SPRITE_HEIGHT + 30);
            maze[y][x] = 'X'; // mark this spot as visited. This is how you can keep track of where you've
                                // been.
 /*@author CuriousGorge */
            if (bestPathFound) { // we have found the optimal path
                // Follow path to Finish point

                if (path.size() > 1) { // If we have nodes left to remove
                    if(elem2 == null)
                    {
                        if (path.size() - 1 == 0) // If one remaining
                        {
                            elem1 = elem2;
                            elem2 = path.removeFirst(); // Remove it and save it into elem2
                        } else if (path.size() == pathSize) // If first run
                        {
                            elem1 = path.removeFirst();
                            elem2 = path.removeFirst();
                        } else {
                            elem2 = path.removeFirst(); // Remove an element from the bestPath list because we need a new
                            // node to find the finish point
                            elem1 = path.getFirst(); // Get next node but don't remove it yet
                        }
                    }

                    if (facing.equals("east") || facing.equals("west")) // If moving horizontally
                    {
                        steps = Math.abs(elem2.getY() - elem1.getY()); // Then the next step must be on the vertical
                                                                        // because we stored all elements as turns.
                    } else if (facing.equals("north") || facing.equals("south")) {
                        steps = Math.abs(elem2.getX() - elem1.getX());
                    }

                }
                followPath(y, x, steps, facing, elem2);
            } else if (!bestPathFound) { // We do not have the optimal path

                findPath(y, x, facing);
            }
             /*@author CuriousGorge end of [code section]*/
        } else

        {
            System.out.println("Found the finish!");

            // don't mess with the following 4 lines, but you can add stuff below that if
            // you need.
            currentTime = System.currentTimeMillis();
            long endTime = currentTime - startTime;
            long finalTime = endTime / 1000;
            System.out.println("Final Time = " + finalTime);
            printPath();
        }
    }
 /*@author CuriousGorge [custom helper methods] */
    private void followPath(int y, int x, int distance, String facingStr, PathElement elem) {
        String leftStr, rightStr;
        int horizontal = 0, vertical = 0, dirHorizontal = elem1.getY() - elem.getY(),
                dirVertical = elem1.getX() - elem.getX();

        if (facingStr.equals("east")) {
            leftStr = "north";
            rightStr = "south";
            horizontal = +1;
        } else if (facingStr.equals("north")) {
            leftStr = "west";
            rightStr = "east";
            vertical = -1;
        } else if (facingStr.equals("west")) {
            leftStr = "south";
            rightStr = "north";
            horizontal = +1;
        } else {
            leftStr = "east";
            rightStr = "west";
            vertical = +1;
        }

        if (distance >= 1) { // If distance remains to next turn
            solve(y + vertical, x + horizontal, distance - 1, facingStr, elem); // Take a step
        } else { // Otherwise make a turn
            if (dirHorizontal != 0) {
                if (dirHorizontal > 0) {
                    solve(y, x, 0, leftStr, null); // Turn left
                } else if (dirHorizontal < 0) {
                    solve(y, x, 0, rightStr, null); // Otherwise turn right
                }
            } else if (dirVertical != 0) {
                if (dirVertical > 0) {
                    solve(y, x, 0, leftStr, null); // Turn left
                } else if (dirVertical < 0) {
                    solve(y, x, 0, rightStr, null); // Otherwise turn right
                }
            }
        }
    }

    @SuppressWarnings("rawtypes")
    private void findPath(int y, int x, String fwdStr) // Purpose is to make decisions given an input
                                                        // (duh)-- reduces code duplication!!!
    {
        char fwd, left, right; // Store chars for each 'hand'
        int horizontal = 0, vertical = 0;
        String leftStr, rightStr;
        if (fwdStr.equals("east")) {
            fwd = maze[y][x + 1];
            left = maze[y - 1][x];
            right = maze[y + 1][x];
            horizontal = 1;
            leftStr = "north";
            rightStr = "south";

        } else if (fwdStr.equals("north")) {
            fwd = maze[y - 1][x];
            left = maze[y][x - 1];
            right = maze[y][x + 1];
            vertical = -1;
            leftStr = "west";
            rightStr = "east";

        } else if (fwdStr.equals("west")) {
            fwd = maze[y][x - 1];
            left = maze[y + 1][x];
            right = maze[y - 1][x];
            horizontal = -1;
            leftStr = "south";
            rightStr = "north";

        } else {
            fwd = maze[y + 1][x];
            left = maze[y][x + 1];
            right = maze[y][x - 1];
            vertical = 1;
            leftStr = "east";
            rightStr = "west";

        }

        switch (fwd) {
        case '.':
            // Go forward
            if (left == 'X' && right == 'X') // If at intersection (CANNOT BE GUARANTEED TO HAPPEN BEFORE FINISH)
                path.add(new PathElement(y, x));

            solve(y + vertical, x + horizontal, -1, fwdStr, null);
            break;
        case 'F':
            path.add(new PathElement(y, x));
            findShortestPath();
            solve(y + vertical, x + horizontal, -1, fwdStr, null);
            break;

        case 'X': // If already been here
        case '%': // and/or if forward is a wall
        case '#': // and/or if forward is a wall

            if (fwd == 'X' && left != '.' && right != '.') { // If fwd is a breadcrumb and left and right are not walls
                // Go forward
                solve(y + vertical, x + horizontal, -1, fwdStr, null);
            } else {
                // OLD VARS: PathElement tmp1 = null, tmp2 = null;
                path.add(new PathElement(y, x));
                if (left == '.') // Left has not been taken but is open
                {
                    solve(y, x, -1, leftStr, null);
                } else if (left == 'X') // Left has been taken but is open
                {
                    /*
                     * OLD CODE: tmp1 = bestPath.getLast(); tmp2 = fromOldBestPath.getLast();
                     * 
                     * if(tmp1.getX() != tmp2.getX() || tmp1.getY() != tmp2.getY()) {
                     * fromOldBestPath.add(bestPath.removeLast()); }
                     */
                    solve(y, x, -1, leftStr, null);

                } else if (right == '.') // Right has not been taken
                {
                    solve(y, x, -1, rightStr, null);
                } else if (right == 'X') // Right has been taken but is open
                {
                    solve(y, x, -1, rightStr, null);

                } else { // Dead end
                    if (left == '%' || left == '#') // left hand is not open case
                    {
                        {
                            if (right == '%' || right == '#') // Right hand is not open case
                            {
                                // Turn around (total left rotation)
                                solve(y, x, -1, leftStr, null);
                            }
                        }
                    }
                }
            }
            break;
        default:
            break;
        }
    }

    private void findShortestPath() {
        /*
         * The last element in path is the finish point coordinate. The next is crucial
         * for connecting the best path to that last element.
         */
        @SuppressWarnings("rawtypes")
        PathElement end = path.removeLast(), tmp1 = null, tmp2 = null, intersection = path.removeLast();
        @SuppressWarnings("rawtypes")
        LinkedList<PathElement> bestPath = new LinkedList<PathElement>();

        // Sort out the duplicate path parts
        while (true) { // While true
            tmp1 = path.removeFirst(); // Remove the first few elements
            if (path.contains(tmp1)) // If the given element still exists within the path, it is a duplicate and we
                                        // have the end of the best path (or beginning of the doubled back path)
            {
                break;
            } else // If not in the best path, add the removed element to the optimal path
            {
                bestPath.add(tmp1);
            }
        }

        bestPath.add(intersection); // This part was originally missing in maze1 with this implementation. I've
                                    // since added code within findPath() to add the correct element.
        bestPath.add(end); // Tack the finish point data on the end.

        path = bestPath;

        System.out.println("Showing best path elements:");
        for (int c = 0; c < path.size(); c++) {
            tmp2 = path.get(c);
            System.out.println("[ x:" + tmp2.getX() + " , y:" + tmp2.getY() + " ]");
        }

        /*
         * OLD DEBUG CODE: System.out.println("Elements belonging to worst path:"); do {
         * tmp1 = path.removeFirst(); System.out.println("[ x:" + tmp1.getX() + " , y:"
         * + tmp1.getY() + " ]"); } while (!path.isEmpty());
         */

    }

    private void printPath() {

        while (!path.isEmpty()) {
            PathElement e = path.removeFirst();
            System.out.println("(x=" + e.getX() + "   y=" + e.getY() + ")");
            pathDatafile.write("" + e.getY());
            pathDatafile.write("" + e.getX());
        }
        pathDatafile.saveAndClose();

        System.out.println("Done.");
    }

     /*@author CuriousGorge [end of code section]*/

    /**
     * Opens a text file containing a maze and stores the data in the 2D char array
     * maze[][].
     *
     * @param fname
     *            String value containing the file name of the maze to open.
     */
    public void openMaze(String fname) {
        String in = "";
        int i = 0;
        try {
            Scanner sc = new Scanner(new File(fname));
            while (sc.hasNext()) {
                in = sc.nextLine();
                in = trimWhitespace(in);
                if (in.length() <= MAX_WIDTH && i < MAX_HEIGHT) {
                    for (int j = 0; j < in.length(); j++) {
                        if (in.charAt(j) == '#') { // if this spot is a wall, randomize the wall peice to display
                            if (random.nextInt(2) == 0) {
                                maze[i][j] = '#';
                            } else {
                                maze[i][j] = '%';
                            }
                        } else {
                            maze[i][j] = in.charAt(j);
                        }
                    }
                } else {
                    System.out.println("Maximum maze size exceeded: (" + MAX_WIDTH + " x " + MAX_HEIGHT + ")!");
                    System.exit(1);
                }
                i++;
            }
            width = in.length();
            height = i;
            System.out.println("(" + width + " x " + height + ") maze opened.");
            System.out.println();
            sc.close();
        } catch (FileNotFoundException e) {
            System.err.println("File not found: " + e);
        }
    }

    /**
     * Removes white space from the supplied string and returns the trimmed String.
     *
     * @param s
     *            String value to strip white space from.
     * @return String stripped of white space.
     */
    public String trimWhitespace(String s) {
        String newString = "";
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != ' ') {
                newString += s.charAt(i);
            }
        }
        return newString;
    }

    /**
     * Returns the sprite facing the direction supplied.
     *
     * @param facing
     *            String value containing 1 of 4 cardinal directions to make the
     *            sprite face.
     * @return Image of the sprite facing the proper direction.
     */
    private Image printGuy(String facing) {
        if (facing.equals("south")) { // draw sprite facing south
            if (step) {
                step = false;
                return south1.getImage();
            } else {
                step = true;
                return south2.getImage();
            }
        } else if (facing.equals("north")) { // draw sprite facing north
            if (step) {
                step = false;
                return north1.getImage();
            } else {
                step = true;
                return north2.getImage();
            }
        } else if (facing.equals("east")) { // draw sprite facing east
            if (step) {
                step = false;
                return east1.getImage();
            } else {
                step = true;
                return east2.getImage();
            }
        } else if (facing.equals("west")) { // draw sprite facing west
            if (step) {
                step = false;
                return west1.getImage();
            } else {
                step = true;
                return west2.getImage();
            }
        }
        return null;
    }

    /**
     * Prints the Maze using sprites.
     *
     * @return BufferedImage rendition of the maze.
     */
    public BufferedImage printMaze() {
        BufferedImage mi = new BufferedImage(width * SPRITE_WIDTH, height * SPRITE_HEIGHT, BufferedImage.TYPE_INT_ARGB);
        Graphics g2 = mi.createGraphics();

        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (maze[i][j] == '#') { // draw wall
                    g2.drawImage(wall1.getImage(), j * SPRITE_WIDTH, i * SPRITE_HEIGHT, null, null);
                } else if (maze[i][j] == '%') { // draw wall
                    g2.drawImage(wall2.getImage(), j * SPRITE_WIDTH, i * SPRITE_HEIGHT, null, null);
                } else if (maze[i][j] == '.' || maze[i][j] == 'X') { // draw ground
                    g2.drawImage(ground.getImage(), j * SPRITE_WIDTH, i * SPRITE_HEIGHT, null, null);
                } else if (maze[i][j] == 'F') { // draw finish
                    g2.drawImage(finish.getImage(), j * SPRITE_WIDTH, i * SPRITE_HEIGHT, null, null);
                }
            }
        }
        return mi;
    }

    public void closingMethod() {

        long endTime = currentTime - startTime;
        long finalTime = endTime / 100;
        System.out.println("Final Time = " + ((double) finalTime / (double) 10));
        System.exit(0);

    }

    /**
     * Handles the Timer, updates the boolean timerFired every time the Timer ticks.
     * Used to slow the animation down.
     */
    private class TimerHandler implements ActionListener {

        public void actionPerformed(ActionEvent e) {
            timerFired = true;
        }
    }

    /**
     * Catch the windowClosing event and exit gracefully.
     */
    private class WindowHandler extends WindowAdapter {

        public void windowClosing(WindowEvent e) {
            removeAll();
            closingMethod();
            System.exit(0);
        }
    }

}

To find my code changes (the other author being my professor, hunterl) please do a look through (or ctrl+F search) for the string "@author CuriousGorge". I have surrounded all relevant code with that string and indicators to show the beginning and end.

It is not the best commented code, but I tried to explain the more esoteric parts of it.

[Curious Gorge]

Hold up. I forgot. I managed to get it to add that intersection (with one extra PathElement data piece in my path list) so on the first run this will find the finish point (with some backtracking) and store the complete best path in to the text file.

I've found the current problem to be with the second run. It reads the data in the text file properly, storing the data in to that same path list.

However when it runs some hinky stuff happens. For some reason when followPath() gets called it gets the wrong distance and walks right through a wall while headed north.

I believe this is because of the way I remove and peek the next first piece of data in the list. I'm still working to solve that. In essence, the problem has changed some.

[AssertNull]

DataManager and PathElement classes? Any input files needed? Sprites? Just zip it up and attach it. The problem with these kinds of assignments and posting it on a forum is that we can't compile and run it without all those other classes. Sometimes we don't need to and the problem just sticks out.

The second problem is, and I don't know far along you are in your Java education (the following comment might be something you get to later) is that you have a whole bunch of GUI and timing code intermingled with your maze solving code. Preferably you have them as independent as possible. Thus the maze and maze solving code wouldn't have anything to do with the code displaying the maze or reading in the maze.

I'm seeing a lot of maze[y][x] code as opposed to maze[x][y]. If it represents the (x,y) coordinates, the reverse order makes it confusing compared to what everyone expects to see (x represents horizontal, y represents vertical, and x comes before y).

I frankly see this as an algorithm problem, not a coding problem, like you said, which means that you want to explain in detailed English precisely what your algorithm is. Key word is "precisely". As precise as possible because this is a very precise process and you need to be able to detect all deviations from your algorithm immediately. You're on the right track as far as drawing and posting those mazes with the colored lines. You just need a few more of them and to make them a little more detailed. Keep in mind that we aren't familiar with the project. All we see is what you show us.

That's actually a GOOD thing for you as far as learning to program. One of the largest pitfalls when debugging is the "You know what I mean" pitfall, or rather the "I know what I mean" pitfall. We're so wrapped up in our own logic and what's "obvious" that bugs can slip by. Thus if you detail what is "obvious", on paper, then follow it painstakingly, you often find out that it's NOT obvious or that you're actually not following your own directions. And if you are, writing down the exact steps will clarify it to yourself.

Regarding commenting, you need to comment what is not obvious. For example, you check for 'X'. What does X represent? A wall? An empty space? A breadcrumb? it's very hard to follow the algorithm not knowing what X represents. I found it by looking at printMaze. X appears to be an empty spot and a hashhtag (#) appears to be a wall. Not obvious at all. I assume a dot is a breadcrumb?

You should create some constant character values. Assign WALL to equal #, then use WALL, not # in your code. Makes it way more obvious to follow the logic.

Definitely change the [y][x] array code to [x][y]. Go with convention. People are used to seeing (x,y) coordinates. Unless there is a very good reason not to, go with that.

[JamesCherrill]

I've found the current problem to be with the second run

That's a very common problem. Trying to re-use existing objects and data structures for new run ... it's easy to miss re-initialising or clearing one variable that screws up the second run. (Even easier to miss when you add something to the code later!)

Simple answer is don't do it. package your code with a class whose constructor takes a data file and instantiates/executes whatever is needed. For the next data file simply create a new instance with all new variables and data structures, and allow the old stuff to be garbage collected.