Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Help : BackTracking in a maze
New Posts  All Forums:Forum Nav:

Help : BackTracking in a maze

post #1 of 2
Thread Starter 
Hello every body

I'm creating a program that generates a random maze depending on the starting point you enter and then solves it. My problem is that even thought there is a solution to the maze, it returns that there is no solution to the maze.

I tried to do BackTracking in the getMove() method but it didn't work

this is my code
Code:
// Lab29ast.java
// This is the student version of the Lab29a assignment.  Complete this file as is.


import java.io.*;
import java.util.*;
import java.util.ArrayList;

public class lab29a
{
        public static void main(String args[]) throws IOException
        {
                System.out.println("\nLab 29a \n");
                BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
                System.out.print("Enter random starting seed  ===>>  ");
                int seed = Integer.parseInt(input.readLine());

                Maze maze = new Maze(seed);
                maze.displayMaze();
                maze.solveMaze();
                maze.displayMaze();
                maze.mazeSolution();
        }
}

class Coord     // Coord is a class that stores a single maze location.
{
        private int rPos;
        private int cPos;
        public Coord (int r, int c)             { rPos = r; cPos = c; }
        public boolean isFree()                 { return (rPos == 0 && cPos == 0); }
        public void setPos(int r, int c)        { rPos+= r; cPos+= c; }
        public int getrPos()                    { return  rPos;   }
        public int getcPos()                    { return  cPos;   }
}

class Maze
{
        private char mat[][];        // 2d character array that stores the maze display
        private Coord currentMove;   // object that stores current maze position
        private MyStack visitStack;  // stack that stores location that have been visited

        // constructor which generates the random maze, random starting location
        // and initializes Maze class values.  If the random value equals 0 the maze
        // store an 'X' otherwise it store an 'O' in the maze.
        public Maze(int seed)
        {
                Random random = new Random(seed);
                int startRow, startCol;
                mat = new char[12][12];
                for (int r = 0; r < 12; r++)
                        for (int c = 0; c < 12; c++)
                        {
                                if (r == 0 || c == 0 || r == 11 || c == 11)
                                        mat[r][c] = 'X';
                                else
                                {
                                        int rndInt = random.nextInt(2);
                                        if (rndInt == 0)
                                                mat[r][c] = 'X';
                                        else
                                                mat[r][c] = 'O';
                                }
                        }
                mat[0][0] = 'O';
                startRow = random.nextInt(12);
                startCol = 11;
                mat[startRow][startCol] = '.';
                visitStack = new  MyStack();
                currentMove = new Coord(startRow,startCol);
                visitStack.push(currentMove);
        }

        // displays the current maze configuration
        void displayMaze() throws IOException
        {
                System.out.println("\nRANDOM MAZE DISPLAY\n");
                for (int r = 0; r < 12; r++)
                {
                        for (int c = 0; c < 12; c++)
                                System.out.print(mat[r][c] + "  ");
                        System.out.println();
                }
                System.out.println();
                pause();
        }

        // This method solves the maze with private helper method <getMove>.
        // A loop is needed to repeat getting new moves until either a maze solution
        // is found or it is determined that there is no way out off the maze.
        public void solveMaze() throws IOException
        {
                System.out.println("\n>>>>>   WORKING  ....  SOLVING MAZE   <<<<<\n");

                while(getMove())
                {
                        mat[currentMove.getrPos()][currentMove.getcPos()] = '.';
                        //System.out.println("1");
                        visitStack.push(currentMove);
                        //System.out.println("2");

                }
        }

        // Short method to display the result of the maze solution
        public void mazeSolution()
        {
                if (currentMove.isFree())
                        System.out.println("\nTHE MAZE HAS A SOLUTION.\n");
                else
                        System.out.println("\nTHE MAZE HAS NO SOLUTION.\n");
        }

        // This method determines if a coordinate position is inbounds or not
        private boolean inBounds(int r, int c)
        {
                boolean inBound = false;

                if(r >= 0 && c >= 0)
                {
                        if((r + 1 ) < mat.length && (c + 1) < mat[0].length)
                                inBound = true;
                }

                return inBound;
        }

        // This method checks eight possible positions in a counter-clock wise manner
        // starting with the (-1,0) position.  If a position is found the method returns
        // true and the currentMove coordinates are altered to the new position
        private boolean getMove() throws IOException
        {
                boolean canmove = false;
                int tempRow = currentMove.getrPos();
                int tempCol = currentMove.getcPos();

                if(inBounds((currentMove.getrPos() - 1), (currentMove.getcPos() + 0)) == true)
                {
                        if(mat[currentMove.getrPos() - 1][currentMove.getcPos() + 0] == 'O')
                        {
                                canmove = true;

                                tempRow = currentMove.getrPos() - 1;
                                tempCol = currentMove.getcPos() + 0;
                        }
                }

                else if(inBounds((currentMove.getrPos() -1), (currentMove.getcPos() +1)) == true)
                {
                        if(mat[currentMove.getrPos() - 1][currentMove.getcPos() + 1] == 'O')
                        {
                                canmove = true;

                                tempRow = currentMove.getrPos() - 1;
                                tempCol = currentMove.getcPos() + 1;
                        }
                }

                else if(inBounds((currentMove.getrPos() + 0), (currentMove.getcPos() + 1)) == true)
                {
                        if(mat[currentMove.getrPos() + 0][currentMove.getcPos() + 1] == 'O')
                        {
                                canmove = true;

                                tempRow = currentMove.getrPos() + 0;
                                tempCol = currentMove.getcPos() + 1;
                        }
                }

                else if(inBounds((currentMove.getrPos() + 1), (currentMove.getcPos() + 1)) == true)
                {
                        if(mat[currentMove.getrPos() + 1][currentMove.getcPos() + 1] == 'O')
                        {
                                canmove = true;

                                tempRow = currentMove.getrPos() + 1;
                                tempCol = currentMove.getcPos() + 1;
                        }
                }

                else if(inBounds((currentMove.getrPos() + 1), (currentMove.getcPos() + 0)) == true)
                {
                        if(mat[currentMove.getrPos() + 1][currentMove.getcPos() + 0] == 'O')
                        {
                                canmove = true;

                                tempRow = currentMove.getrPos() + 1;
                                tempCol = currentMove.getcPos() + 0;
                        }
                }

                else if(inBounds((currentMove.getrPos() + 1), (currentMove.getcPos() - 1)) == true)
                {
                        if(mat[currentMove.getrPos() + 1][currentMove.getcPos() - 1] == 'O')
                        {
                                canmove = true;

                                tempRow = currentMove.getrPos() + 1;
                                tempCol = currentMove.getcPos() - 1;
                        }
                }

                else if(inBounds((currentMove.getrPos() + 0), (currentMove.getcPos() - 1)) == true)
                {
                        if(mat[currentMove.getrPos() + 0][currentMove.getcPos() - 1] == 'O')
                        {
                                canmove = true;

                                tempRow = currentMove.getrPos() + 0;
                                tempCol = currentMove.getcPos() - 1;
                        }
                }

                else if(inBounds((currentMove.getrPos() - 1), (currentMove.getcPos() - 1)) == true)
                {
                        if(mat[currentMove.getrPos() - 1][currentMove.getcPos() - 1] == 'O')
                        {
                                canmove = true;

                                tempRow = currentMove.getrPos() - 1;
                                tempCol = currentMove.getcPos() - 1;
                        }
                }

                if(canmove == true)                                //BackTracking
                {
                        currentMove = new Coord(tempRow, tempCol);
                        //System.out.println(currentMove + " push");
                }
                else
                {
                        currentMove = (Coord)visitStack.pop();
                    //System.out.println(currentMove + " pop");
                }

//              if(visitStack.isEmpty())
//                      canmove = false;
//              else
//                      canmove = true;

                return canmove;
        }

        private void pause() throws IOException
        {
                BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
                String dummy;
                System.out.print("\nPress <Enter> to continue  ===>>  ");
                dummy = input.readLine();
        }
}

class MyStack<E>
{
        private ArrayList<E> data;        // stores stack data

        public MyStack()
        // Initializes an empty array object 
        {
                data = new ArrayList<E>();
        }

        public boolean isEmpty()
        // Returns true if data is empty, false otherwise
        {
                return data.size() == 0;
        }

        public void push (E x)
        // Adds variable x to the top of the stack
        {
                 data.add(x);
        }

        public E pop()
        // Returns and removes the top element from the stack
        {
                if(!data.isEmpty())
                        return data.remove((data.size())-1);

                System.out.println("stack empty ...  fool!");

                return null;
        }

        public E peek()
        // Returns the top element from the stack without removal
        {
                return (E)data.get((data.size())-1);
        }
}


this is my output

X - SOLID WALL (no passage allowed)

O - PATH (passage allowed)

. - TRAVELED (path traveled to find the exit)
Code:
Enter random starting seed  ===>>  25

RANDOM MAZE DISPLAY

O  X  X  X  X  X  X  X  X  X  X  X
X  O  O  X  O  O  X  X  X  X  X  X
X  O  O  X  O  X  O  X  O  O  O  X
X  X  X  O  O  X  X  O  O  O  X  X
X  X  X  X  O  O  O  O  O  X  O  X
X  X  X  X  O  O  O  X  X  X  X  X
X  O  X  O  X  X  O  X  O  X  O  X
X  X  X  X  X  O  O  X  X  X  O  X
X  X  X  O  O  X  X  O  O  X  O  X
X  O  X  X  O  O  O  X  O  O  O  X
X  X  X  X  X  O  O  X  O  X  O  .
X  X  X  X  X  X  X  X  X  X  X  X


Press <Enter> to continue  ===>>

>>>>>   WORKING  ....  SOLVING MAZE   <<<<<


RANDOM MAZE DISPLAY

O  X  X  X  X  X  X  X  X  X  X  X
X  O  O  X  O  O  X  X  X  X  X  X
X  O  O  X  O  X  O  X  O  O  O  X
X  X  X  O  O  X  X  O  O  O  X  X
X  X  X  X  O  O  O  O  O  X  O  X
X  X  X  X  O  O  O  X  X  X  X  X
X  O  X  O  X  X  O  X  O  X  .  X
X  X  X  X  X  O  O  X  X  X  .  X
X  X  X  O  O  X  X  O  O  X  .  X
X  O  X  X  O  O  O  X  O  O  .  X
X  X  X  X  X  O  O  X  O  X  .  .
X  X  X  X  X  X  X  X  X  X  X  X


Press <Enter> to continue  ===>>

THE MAZE HAS NO SOLUTION.

Press any key to continue...

this is what should the output be
Code:
Enter random starting seed ===>> 25

RANDOM MAZE DISPLAY

O X X X X X X X X X X X
X O O X O O X X X X X X
X O O X O X O X O O O X
X X X O O X X O O O X X
X X X X O O O O O X O X
X X X X O O O X X X X X
X O X O X X O X O X O X
X X X X X O O X X X O X
X X X O O X X O O X O X
X O X X O O O X O O O X
X X X X X O O X O X O .
X X X X X X X X X X X X

Press <Enter> to continue ===>>

>>>>> WORKING .... SOLVING MAZE <<<<<

RANDOM MAZE DISPLAY

. X X X X X X X X X X X
X . . X . . X X X X X X
X . . X . X . X . . . X
X X X . . X X . . . X X
X X X X . . . . . X . X
X X X X . . . X X X X X
X O X O X X . X O X . X
X X X X X . O X X X . X
X X X O . X X . . X . X
X O X X . . . X . . . X
X X X X X . . X . X . .
X X X X X X X X X X X X

Press <Enter> to continue ===>>

THE MAZE HAS A SOLUTION.

please help me for I need to know how to fix the program very quickly

I would appreciate any answer or comment

thank you in advance
post #2 of 2
i dont know squat about code, but how about using the right wall or left wall method (stick to either one and you will eventually find your way out)
    
CPUMotherboardGraphicsGraphics
phenom ii x6 1100t gigabyte ga990fxa ud5 gigabyte 480gtx gigabyte 480gtx 
GraphicsRAMHard DriveHard Drive
evga 480gtx corsair vengence ddr3 1600 ocz agility 3 sdd ocz agility 3 sdd 
Hard DriveOptical DriveCoolingCooling
maxtor hdd asus blu-ray reader/burner xspc ex360 rad (x2)  swiftec mcp655 pump w/bitspower pump kit and v2... 
CoolingCoolingCoolingCooling
laing d5 pump w/bitspower pump kit and v2 pump top heatkiller cpu block koolance nv480gtx full vga blocks ek northbridge block 
CoolingCoolingOSMonitor
lamptron fc5 bitspower 150 black ice reservoir vista ultimate 64 bit asus s248h-p hdmi led 
MonitorMonitorKeyboardPower
acer x183h acer x183h corsair k60 mechanical silverstone strider 1000 silver 
CaseMouseMouse PadAudio
corsair 500r corsair m60 func 1030 archetype creative x-fi xtreme gamer 
  hide details  
Reply
    
CPUMotherboardGraphicsGraphics
phenom ii x6 1100t gigabyte ga990fxa ud5 gigabyte 480gtx gigabyte 480gtx 
GraphicsRAMHard DriveHard Drive
evga 480gtx corsair vengence ddr3 1600 ocz agility 3 sdd ocz agility 3 sdd 
Hard DriveOptical DriveCoolingCooling
maxtor hdd asus blu-ray reader/burner xspc ex360 rad (x2)  swiftec mcp655 pump w/bitspower pump kit and v2... 
CoolingCoolingCoolingCooling
laing d5 pump w/bitspower pump kit and v2 pump top heatkiller cpu block koolance nv480gtx full vga blocks ek northbridge block 
CoolingCoolingOSMonitor
lamptron fc5 bitspower 150 black ice reservoir vista ultimate 64 bit asus s248h-p hdmi led 
MonitorMonitorKeyboardPower
acer x183h acer x183h corsair k60 mechanical silverstone strider 1000 silver 
CaseMouseMouse PadAudio
corsair 500r corsair m60 func 1030 archetype creative x-fi xtreme gamer 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Help : BackTracking in a maze