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

BackTracking in a maze

post #1 of 8
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


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 8
Wut.

Royal Navy Fermi Folder 24/7. Join us @ 37726 ! =~)
post #3 of 8
after your
Code:
getMove()
method checks each direction it will only EVER pick the first valid move.

My suggested fix is this:

make a new struct object like this:
Code:
class move {
    public int row;
    public int col;
    public move(int row, int col){
        this.row = row;
        this.col = col;
    }
}
Store valid moves in a Stack of move's like this:
Code:
Stack moves = new Stack();
if(inBounds((currentMove.getrPos() - 1), (currentMove.getcPos() + 0)) == true)
                {
                        if(mat[currentMove.getrPos() - 1][currentMove.getcPos() + 0] == 'O')
                        {
                                canmove = true;
                                moves.push(new move(currentMove.getrPos() - 1, currentMove.getcPos() + 0));
                        }
                }

make
Code:
getMove()
return that stack of valid moves.....

Then change the
Code:
solveMaze()
method to be a recursive method. Which makes the first valid move until it either finds the exit, or runs out of moves then it returns with a success or fail. When it returns from a move execute the next move in the current stack....... you understand now?
 
Tragbar
(14 items)
 
 
CPUMotherboardGraphicsRAM
Ryzen 1800X Asus Crosshair VI Hero Nvidia Geforce Titan X F4-3600C15D-16GTZ 
Hard DriveHard DriveHard DriveHard Drive
Combined: 6.13 TB of space Samsung SSD 960 EVO 500GB Crucial_CT1050MX300SSD1 M4-CT128M4SSD2 
CoolingCoolingCoolingCooling
EK-Supremacy EVO White Edition PrimoChill PrimoFlex Advanced LRT EK-RES X4 250 (R2.0) Reservoir EK-CoolStream XE 360 
CoolingCoolingCoolingOS
EK-Vardar F4-120ER (2200rpm)  EK-Ekoolant EVO Liquid Coolant EK-XTOP Revo D5 PWM Pump Windows 10 Pro 
MonitorKeyboardPowerCase
Asus VG278H Ducky YOTG Keyboard Corsair AX1200 Corsair Obsidian 800D 
MouseAudioAudioAudio
Logitech G700s Schiit Gungnir Multibit Schiit Mjolnir 2 Schiit LISST 
Audio
Audeze LCD 2 - pre fazor 
CPUMotherboardGraphicsRAM
intel i7 4770K ASRock Z87E-ITX Nvidia Geforce GTX Titan X GSkill F3-2400C10D-16GTX R 
Hard DriveOptical DriveCoolingOS
Samsung 840 Pro 512GB Silverstone 12.7mm Slot Load Blu-Ray Burner Noctua NH-L12 Windows 8 Pro 
MonitorCaseAudioAudio
LG PA75U Slim LED Projector Silverstone SG08 Schiit Bifrost Schiit Asgard 2 
AudioOther
AKG Q701 Headphones Pelican 1510 Green Case  
  hide details  
Reply
 
Tragbar
(14 items)
 
 
CPUMotherboardGraphicsRAM
Ryzen 1800X Asus Crosshair VI Hero Nvidia Geforce Titan X F4-3600C15D-16GTZ 
Hard DriveHard DriveHard DriveHard Drive
Combined: 6.13 TB of space Samsung SSD 960 EVO 500GB Crucial_CT1050MX300SSD1 M4-CT128M4SSD2 
CoolingCoolingCoolingCooling
EK-Supremacy EVO White Edition PrimoChill PrimoFlex Advanced LRT EK-RES X4 250 (R2.0) Reservoir EK-CoolStream XE 360 
CoolingCoolingCoolingOS
EK-Vardar F4-120ER (2200rpm)  EK-Ekoolant EVO Liquid Coolant EK-XTOP Revo D5 PWM Pump Windows 10 Pro 
MonitorKeyboardPowerCase
Asus VG278H Ducky YOTG Keyboard Corsair AX1200 Corsair Obsidian 800D 
MouseAudioAudioAudio
Logitech G700s Schiit Gungnir Multibit Schiit Mjolnir 2 Schiit LISST 
Audio
Audeze LCD 2 - pre fazor 
CPUMotherboardGraphicsRAM
intel i7 4770K ASRock Z87E-ITX Nvidia Geforce GTX Titan X GSkill F3-2400C10D-16GTX R 
Hard DriveOptical DriveCoolingOS
Samsung 840 Pro 512GB Silverstone 12.7mm Slot Load Blu-Ray Burner Noctua NH-L12 Windows 8 Pro 
MonitorCaseAudioAudio
LG PA75U Slim LED Projector Silverstone SG08 Schiit Bifrost Schiit Asgard 2 
AudioOther
AKG Q701 Headphones Pelican 1510 Green Case  
  hide details  
Reply
post #4 of 8
Dunno if it's too late, but...

We can definitely make backtracking work.
Code:
private boolean getMove() throws IOException

should become
Code:
private boolean getMove(String toCheck) throws IOException

the first time you run getMove, you will be checking for the normal "0". When that fails - you don't find any possible paths - your solveMaze should call getMove again, but with the parameter "."

Every time you move in a position after looking for ".", you should place a different symbol in the position you came from, as a marker that you've been there before and that path leads to a dead end.
Code:
public void solveMaze() throws IOException
{
      System.out.println("\n>>>>>   WORKING  ....  SOLVING MAZE   <<<<<\n");

      while(!solutionFound) //where solution found checks for a valid solution
      {
            mat[currentMove.getrPos()][currentMove.getcPos()] 
            if(getMove("O"))
                  visitStack.push(currentMove);
            else if(getMove("."))
            {
                  visitStack.push(currentMove);
                  replaceLastSpot(currentMove.getrPos(), currentMove.getcPos()) //this replaces the spot you came from with a marker showing not to return
            }
           
      }
}

This will require you to change your getMove function so that it checks against what parameter you pass it, but this should fix your issue. The code should be mostly correct redface.gif

If you really wanted to impress everyone, I would keep a queue of the correct moves to reach the end, so that you can repeat the maze after "learning it"! thumb.gif
Edited by ColSanderz - 2/17/12 at 11:37pm
Flash Penguin
(20 items)
 
Audio Stuffs
(9 items)
 
FileSerpent
(10 items)
 
CPUMotherboardGraphicsGraphics
Xeon W3520 EVGA X58 Classified GTX 275 GTX 275 
GraphicsRAMHard DriveHard Drive
GT 640 G.Skill Trident 1710 Mhz @ 6.7.6.18 Vertex 2 Seagate 1tb 7200.12 
Optical DriveCoolingCoolingCooling
LG Multi-DVD Writer Apogee XT Bitspower mobo and mosfet blocks for EVGA e760 Feser 360 and Feser 240 
OSMonitorKeyboardPower
Win7 x86-64 3x LG W2353V 23" 1080p G15 Gaming Keyboard (V1) [BFG] ES-800 
CaseMouseMouse PadAudio
Antec 1200 LED/Window/HDD rack Modded Logitech G700 An old mousepad (shows a computer with ISA slots) Asus Essence ST 
AudioAudioAudioAudio
Rega Saturn-R CDP/DAC Rega Elicit-R Integrated Amplifier Vandersteen Audio Treo Four-Way, Ported Floor-S... Rega RP8 w/ Exact2 cartridge 
AudioAudioAudioAudio
Cambridge Audio Stream Magic 6 Network Player Beyerdynamic Tesla T1 Headphones reterminated t... Sennheiser HDVA 600 Rega DAC 
Audio
Nordost QB4 w/ Nordost Heimdall Norse 2 Mains C... 
CPUMotherboardRAMHard Drive
Xeon E3-1240 V3 ASROCK E3C226D2I 2x8GB 1333 Kingston Unbuffered ECC 2x WD Black 500 GB in Raid 1 
Hard DriveCoolingOSPower
8x WD Red 3TB in Raid 10 Noctua NH-U9B Windows Server 2012 x64 Seasonic SS-400FL2 400w 
CaseOther
iStarUSA S-917 Adaptec 8885 Raid Controller 
  hide details  
Reply
Flash Penguin
(20 items)
 
Audio Stuffs
(9 items)
 
FileSerpent
(10 items)
 
CPUMotherboardGraphicsGraphics
Xeon W3520 EVGA X58 Classified GTX 275 GTX 275 
GraphicsRAMHard DriveHard Drive
GT 640 G.Skill Trident 1710 Mhz @ 6.7.6.18 Vertex 2 Seagate 1tb 7200.12 
Optical DriveCoolingCoolingCooling
LG Multi-DVD Writer Apogee XT Bitspower mobo and mosfet blocks for EVGA e760 Feser 360 and Feser 240 
OSMonitorKeyboardPower
Win7 x86-64 3x LG W2353V 23" 1080p G15 Gaming Keyboard (V1) [BFG] ES-800 
CaseMouseMouse PadAudio
Antec 1200 LED/Window/HDD rack Modded Logitech G700 An old mousepad (shows a computer with ISA slots) Asus Essence ST 
AudioAudioAudioAudio
Rega Saturn-R CDP/DAC Rega Elicit-R Integrated Amplifier Vandersteen Audio Treo Four-Way, Ported Floor-S... Rega RP8 w/ Exact2 cartridge 
AudioAudioAudioAudio
Cambridge Audio Stream Magic 6 Network Player Beyerdynamic Tesla T1 Headphones reterminated t... Sennheiser HDVA 600 Rega DAC 
Audio
Nordost QB4 w/ Nordost Heimdall Norse 2 Mains C... 
CPUMotherboardRAMHard Drive
Xeon E3-1240 V3 ASROCK E3C226D2I 2x8GB 1333 Kingston Unbuffered ECC 2x WD Black 500 GB in Raid 1 
Hard DriveCoolingOSPower
8x WD Red 3TB in Raid 10 Noctua NH-U9B Windows Server 2012 x64 Seasonic SS-400FL2 400w 
CaseOther
iStarUSA S-917 Adaptec 8885 Raid Controller 
  hide details  
Reply
post #5 of 8
Thread Starter 
thank you for your reply ColSanderz.

I think I understand the logic you talked about, but I have some questions:
1. what is this for mat[currentMove.getrPos()][currentMove.getcPos()]
2. Do I have to create a new method for replaceLastSpot(currentMove.getrPos(), currentMove.getcPos()) and if so how do I have to write it
3. Did you mean the getMove() method in while(!solutionFound) or another one
4. you said that I have to change the getMove() function so that it checks against what parameter you pass it, can you show how to do this

I know my questions seem simple but I am new in programming

thanks,
Mahdi
post #6 of 8
Quote:
Originally Posted by skoon View Post

thank you for your reply ColSanderz.
I think I understand the logic you talked about, but I have some questions:
1. what is this for mat[currentMove.getrPos()][currentMove.getcPos()]
2. Do I have to create a new method for replaceLastSpot(currentMove.getrPos(), currentMove.getcPos()) and if so how do I have to write it
3. Did you mean the getMove() method in while(!solutionFound) or another one
4. you said that I have to change the getMove() function so that it checks against what parameter you pass it, can you show how to do this
I know my questions seem simple but I am new in programming
thanks,
Mahdi


1. Oh sorry, that doesn't need to be there.

2. Yes you will. So, you have int cPos/rPos. Those should be responsible for holding the current position in the maze. Your getMove already creates temporary x/y variables and adds the new coordinates to your Coord variable, which is good! all you should have to do now is have it set the symbol defined by cPos/rPos (in your maze) to that symbol I talked about, then change it (cPos/rPos) to the current position by grabbing the most recent entry in your coord stack. Rince and repeat. (hopefully that made sense)

I think you're going to run into a problem with your current program, because it's going to insert the coord into the stack whether or not it's the correct way. If you run into a dead end (which is bound to happen), and you have to backtrack, you will have to delete the most most recent entry into the stack until you get to a position/coordinate that provides you with another route to take.

You can actually fit it in this function still....
Code:
public void solveMaze() throws IOException
{
      System.out.println("\n>>>>>   WORKING  ....  SOLVING MAZE   <<<<<\n");

      while(!solutionFound) /*where solution found checks for a valid solution*/
      {
            if(getMove("O"))
                  visitStack.push(currentMove);
            else if(getMove("."))
            {
                  visitStack.push(currentMove);
                  /*replaceLastSpot(currentMove.getrPos(), currentMove.getcPos()) /*this replaces the spot you came from with a marker showing not to return*/
                 mat[cPos][rPos]  = "+" //this is the symbol I used in my maze (back in the day lol)
                 /*after this, simply set the cPos and rPos to the current position*/
                                   
            }
            rPos = visitstack.peek().getY() //or X, whichever it is
            cPos = visitstack.peek().getX() //or Y whichever it is
            /*may have to check the exact syntax on these last two lines. I know .peek is right, but not 100% if it's .getX/.getY etc.*/
           
      }
}

Like I said, this code above should be mostly correct. You may have to change the syntax slightly

3. What I meant by !solutionFound, is that the loop would continue - finding a viable path to the end - until the end is actually found. Unfortunately, I'm unsure how you will determine that. Inside the while(!solutionFound) statement, it calls getMove twice - once for finding a path with 'O', and the next with '.' If the first if fails, the second should always pass until it reaches spot where another 'O' exists.

4. nice and simple smile.gif
Code:
private boolean getMove(char toCheck) throws IOException //change it from a string to char. didn't realize your 2d array was a char array
        {
                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]) = toCheck) //either this or .equals(toCheck) not sure which will work better of the top of my head
                        {
                                canmove = true;

                                tempRow = currentMove.getrPos() - 1;
                                tempCol = currentMove.getcPos() + 0;
                        }
                }
/* more code here blah blah */

}

I hope I was helpful enough, atleast to give you some insight on how to complete your program! If it's not due too soon (later this week, like wed-fri), send me a PM, and I'll be more than happy to give you a more thorough answer to help you complete your program thumb.gif
Flash Penguin
(20 items)
 
Audio Stuffs
(9 items)
 
FileSerpent
(10 items)
 
CPUMotherboardGraphicsGraphics
Xeon W3520 EVGA X58 Classified GTX 275 GTX 275 
GraphicsRAMHard DriveHard Drive
GT 640 G.Skill Trident 1710 Mhz @ 6.7.6.18 Vertex 2 Seagate 1tb 7200.12 
Optical DriveCoolingCoolingCooling
LG Multi-DVD Writer Apogee XT Bitspower mobo and mosfet blocks for EVGA e760 Feser 360 and Feser 240 
OSMonitorKeyboardPower
Win7 x86-64 3x LG W2353V 23" 1080p G15 Gaming Keyboard (V1) [BFG] ES-800 
CaseMouseMouse PadAudio
Antec 1200 LED/Window/HDD rack Modded Logitech G700 An old mousepad (shows a computer with ISA slots) Asus Essence ST 
AudioAudioAudioAudio
Rega Saturn-R CDP/DAC Rega Elicit-R Integrated Amplifier Vandersteen Audio Treo Four-Way, Ported Floor-S... Rega RP8 w/ Exact2 cartridge 
AudioAudioAudioAudio
Cambridge Audio Stream Magic 6 Network Player Beyerdynamic Tesla T1 Headphones reterminated t... Sennheiser HDVA 600 Rega DAC 
Audio
Nordost QB4 w/ Nordost Heimdall Norse 2 Mains C... 
CPUMotherboardRAMHard Drive
Xeon E3-1240 V3 ASROCK E3C226D2I 2x8GB 1333 Kingston Unbuffered ECC 2x WD Black 500 GB in Raid 1 
Hard DriveCoolingOSPower
8x WD Red 3TB in Raid 10 Noctua NH-U9B Windows Server 2012 x64 Seasonic SS-400FL2 400w 
CaseOther
iStarUSA S-917 Adaptec 8885 Raid Controller 
  hide details  
Reply
Flash Penguin
(20 items)
 
Audio Stuffs
(9 items)
 
FileSerpent
(10 items)
 
CPUMotherboardGraphicsGraphics
Xeon W3520 EVGA X58 Classified GTX 275 GTX 275 
GraphicsRAMHard DriveHard Drive
GT 640 G.Skill Trident 1710 Mhz @ 6.7.6.18 Vertex 2 Seagate 1tb 7200.12 
Optical DriveCoolingCoolingCooling
LG Multi-DVD Writer Apogee XT Bitspower mobo and mosfet blocks for EVGA e760 Feser 360 and Feser 240 
OSMonitorKeyboardPower
Win7 x86-64 3x LG W2353V 23" 1080p G15 Gaming Keyboard (V1) [BFG] ES-800 
CaseMouseMouse PadAudio
Antec 1200 LED/Window/HDD rack Modded Logitech G700 An old mousepad (shows a computer with ISA slots) Asus Essence ST 
AudioAudioAudioAudio
Rega Saturn-R CDP/DAC Rega Elicit-R Integrated Amplifier Vandersteen Audio Treo Four-Way, Ported Floor-S... Rega RP8 w/ Exact2 cartridge 
AudioAudioAudioAudio
Cambridge Audio Stream Magic 6 Network Player Beyerdynamic Tesla T1 Headphones reterminated t... Sennheiser HDVA 600 Rega DAC 
Audio
Nordost QB4 w/ Nordost Heimdall Norse 2 Mains C... 
CPUMotherboardRAMHard Drive
Xeon E3-1240 V3 ASROCK E3C226D2I 2x8GB 1333 Kingston Unbuffered ECC 2x WD Black 500 GB in Raid 1 
Hard DriveCoolingOSPower
8x WD Red 3TB in Raid 10 Noctua NH-U9B Windows Server 2012 x64 Seasonic SS-400FL2 400w 
CaseOther
iStarUSA S-917 Adaptec 8885 Raid Controller 
  hide details  
Reply
post #7 of 8
Thread Starter 
Quote:
Originally Posted by ColSanderz View Post

1. Oh sorry, that doesn't need to be there.
2. Yes you will. So, you have int cPos/rPos. Those should be responsible for holding the current position in the maze. Your getMove already creates temporary x/y variables and adds the new coordinates to your Coord variable, which is good! all you should have to do now is have it set the symbol defined by cPos/rPos (in your maze) to that symbol I talked about, then change it (cPos/rPos) to the current position by grabbing the most recent entry in your coord stack. Rince and repeat. (hopefully that made sense)
I think you're going to run into a problem with your current program, because it's going to insert the coord into the stack whether or not it's the correct way. If you run into a dead end (which is bound to happen), and you have to backtrack, you will have to delete the most most recent entry into the stack until you get to a position/coordinate that provides you with another route to take.
You can actually fit it in this function still....
Code:
public void solveMaze() throws IOException
{
      System.out.println("\n>>>>>   WORKING  ....  SOLVING MAZE   <<<<<\n");
      while(!solutionFound) /*where solution found checks for a valid solution*/
      {
            if(getMove("O"))
                  visitStack.push(currentMove);
            else if(getMove("."))
            {
                  visitStack.push(currentMove);
                  /*replaceLastSpot(currentMove.getrPos(), currentMove.getcPos()) /*this replaces the spot you came from with a marker showing not to return*/
                 mat[cPos][rPos]  = "+" //this is the symbol I used in my maze (back in the day lol)
                 /*after this, simply set the cPos and rPos to the current position*/
                                   
            }
            rPos = visitstack.peek().getY() //or X, whichever it is
            cPos = visitstack.peek().getX() //or Y whichever it is
            /*may have to check the exact syntax on these last two lines. I know .peek is right, but not 100% if it's .getX/.getY etc.*/
           
      }
}
Like I said, this code above should be mostly correct. You may have to change the syntax slightly
3. What I meant by !solutionFound, is that the loop would continue - finding a viable path to the end - until the end is actually found. Unfortunately, I'm unsure how you will determine that. Inside the while(!solutionFound) statement, it calls getMove twice - once for finding a path with 'O', and the next with '.' If the first if fails, the second should always pass until it reaches spot where another 'O' exists.
4. nice and simple smile.gif
Code:
private boolean getMove(char toCheck) throws IOException //change it from a string to char. didn't realize your 2d array was a char array
        {
                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]) = toCheck) //either this or .equals(toCheck) not sure which will work better of the top of my head
                        {
                                canmove = true;
                                tempRow = currentMove.getrPos() - 1;
                                tempCol = currentMove.getcPos() + 0;
                        }
                }
/* more code here blah blah */
}
I hope I was helpful enough, atleast to give you some insight on how to complete your program! If it's not due too soon (later this week, like wed-fri), send me a PM, and I'll be more than happy to give you a more thorough answer to help you complete your program thumb.gif


for these two lines rPos = visitstack.peek().getY() //or X, whichever it is
cPos = visitstack.peek().getX() //or Y whichever it is

I don't understand how visitstack.peek() and getrPos() can be togather, because visitstack.peek() is from the stack and getrPos() is from the Coord class

I adjusted the code you posted for the solvemaze() method to this
Code:
public void solveMaze() throws IOException
        {
                System.out.println("\n>>>>>   WORKING  ....  SOLVING MAZE   <<<<<\n");

                while(getMove('.')) // I'm not sure about this condition 
                {
                        if(getMove('O'))
                                visitStack.push(currentMove);
                        else if(getMove('.'))
            {
                                visitStack.push(currentMove);

                                mat[currentMove.getrPos()][currentMove.getcPos()]  = '+'; 
                        }

                        currentMove.setPos(currentMove.getrPos(), currentMove.getcPos());
                }
        }

and for the changes in the getMove() method I still don't understand what to write

also that you mentioned the due date. It 's due Wednesday .

thanks,
Mahdi
post #8 of 8
For your getMove() you are simply adding a parameter, char toCheck,
Code:
private boolean getMove(char toCheck) throws IOException

Within your getMove function, you have nested if statements that check each direction from the x,y coordinate that you're currently at. Instead of
Code:
if(mat[currentMove.getrPos() - 1][currentMove.getcPos() + 1] == 'O')

you're going to check if the position is equal to the toCheck parameter that you passed to it from solveMaze()
Code:
if(mat[currentMove.getrPos() - 1][currentMove.getcPos() + 1] == toCheck)

/*that...or...this....   */

if(mat[currentMove.getrPos() - 1][currentMove.getcPos() + 1].equals(toCheck))

you're simply replacing 'O' with toCheck in each case.






concerning the stack and coord class. Your stack is a arraylist of coord's, right? You're essentially creating an array of objects - the coord class that you defined.

It's my fault for not looking at your code more closely (as I have my own projects and stuff at work I'm working on.

.peek().getrPos() should work, but you will probably have to cast it, since java would not know that the arraylist/stack is a coord...so...
Code:
((Coord)visitstack.peek()).getcPos()

/* ...and... */

((Coord)visitstack.peek()).getrPos()

Flash Penguin
(20 items)
 
Audio Stuffs
(9 items)
 
FileSerpent
(10 items)
 
CPUMotherboardGraphicsGraphics
Xeon W3520 EVGA X58 Classified GTX 275 GTX 275 
GraphicsRAMHard DriveHard Drive
GT 640 G.Skill Trident 1710 Mhz @ 6.7.6.18 Vertex 2 Seagate 1tb 7200.12 
Optical DriveCoolingCoolingCooling
LG Multi-DVD Writer Apogee XT Bitspower mobo and mosfet blocks for EVGA e760 Feser 360 and Feser 240 
OSMonitorKeyboardPower
Win7 x86-64 3x LG W2353V 23" 1080p G15 Gaming Keyboard (V1) [BFG] ES-800 
CaseMouseMouse PadAudio
Antec 1200 LED/Window/HDD rack Modded Logitech G700 An old mousepad (shows a computer with ISA slots) Asus Essence ST 
AudioAudioAudioAudio
Rega Saturn-R CDP/DAC Rega Elicit-R Integrated Amplifier Vandersteen Audio Treo Four-Way, Ported Floor-S... Rega RP8 w/ Exact2 cartridge 
AudioAudioAudioAudio
Cambridge Audio Stream Magic 6 Network Player Beyerdynamic Tesla T1 Headphones reterminated t... Sennheiser HDVA 600 Rega DAC 
Audio
Nordost QB4 w/ Nordost Heimdall Norse 2 Mains C... 
CPUMotherboardRAMHard Drive
Xeon E3-1240 V3 ASROCK E3C226D2I 2x8GB 1333 Kingston Unbuffered ECC 2x WD Black 500 GB in Raid 1 
Hard DriveCoolingOSPower
8x WD Red 3TB in Raid 10 Noctua NH-U9B Windows Server 2012 x64 Seasonic SS-400FL2 400w 
CaseOther
iStarUSA S-917 Adaptec 8885 Raid Controller 
  hide details  
Reply
Flash Penguin
(20 items)
 
Audio Stuffs
(9 items)
 
FileSerpent
(10 items)
 
CPUMotherboardGraphicsGraphics
Xeon W3520 EVGA X58 Classified GTX 275 GTX 275 
GraphicsRAMHard DriveHard Drive
GT 640 G.Skill Trident 1710 Mhz @ 6.7.6.18 Vertex 2 Seagate 1tb 7200.12 
Optical DriveCoolingCoolingCooling
LG Multi-DVD Writer Apogee XT Bitspower mobo and mosfet blocks for EVGA e760 Feser 360 and Feser 240 
OSMonitorKeyboardPower
Win7 x86-64 3x LG W2353V 23" 1080p G15 Gaming Keyboard (V1) [BFG] ES-800 
CaseMouseMouse PadAudio
Antec 1200 LED/Window/HDD rack Modded Logitech G700 An old mousepad (shows a computer with ISA slots) Asus Essence ST 
AudioAudioAudioAudio
Rega Saturn-R CDP/DAC Rega Elicit-R Integrated Amplifier Vandersteen Audio Treo Four-Way, Ported Floor-S... Rega RP8 w/ Exact2 cartridge 
AudioAudioAudioAudio
Cambridge Audio Stream Magic 6 Network Player Beyerdynamic Tesla T1 Headphones reterminated t... Sennheiser HDVA 600 Rega DAC 
Audio
Nordost QB4 w/ Nordost Heimdall Norse 2 Mains C... 
CPUMotherboardRAMHard Drive
Xeon E3-1240 V3 ASROCK E3C226D2I 2x8GB 1333 Kingston Unbuffered ECC 2x WD Black 500 GB in Raid 1 
Hard DriveCoolingOSPower
8x WD Red 3TB in Raid 10 Noctua NH-U9B Windows Server 2012 x64 Seasonic SS-400FL2 400w 
CaseOther
iStarUSA S-917 Adaptec 8885 Raid Controller 
  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 › BackTracking in a maze