Little help with a maze problem. I dont think one of my loops terminates!!

Hey. I'm working on a project which i have posted different parts about. What it does, is the program inputs a notepad file which holds a binary map made of 0s and 1s. The 0s are traversible and the 1s are walls. My map looks like this :

Code:

---

1111111111
1011111111
1000011111
1011011111
1011000001
1111011011
1110011011
1110111011
1111111001
1111111111

---

My program takes that data and puts it into a 2d matrix. Then, it initializes a start position 1,1 being the upper left 0. It then scans to its right, left, up and down and decides if there is an opening. If there is, it sets that decision to the value 1. I then generate a random number between 1 and 4. If the decision is available and the random number cooresponding to that decision is generated, then xpos and ypos adjust accordingly. The process stops when xpos and ypos both equal 9, the bottom right 0 of the map. Here is the code. I think i may have two problems. 1. i think that a loop may not be acting right but i just cant figure it out. and 2. maybe i dont have the coordinants numbered right, like 9,9 doesnt coorespond to the bottom left 0. Take a look and let me know if you have any thoughts.

Code:

---


#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <time.h>
using namespace std;
//
//
//
void printmatrix(char print[10][10]){
    for (int i=0;i<10;i++){
        for(int k=0;k<10;k++){
        cout<<print[i][k];
        }
    cout <<"\n";}
}
int main(int argc, char** argv) {
   
    //start copying file to a 2d array
   
    string rowbuild;
    char maze[10][10];
    int rownum=0;
    //begin file io
    ifstream mazefile ("maze.txt");
    while(rownum<10){
      getline(mazefile,rowbuild);
      for(int n=0;n<10;n++){
          maze[rownum][n]=rowbuild[n];}
      rownum++;
      }
    printmatrix(maze);
   
    cout << maze[1][1];
    int xpos=1;            //provides lateral position init at 1
    int ypos=1;            //provides vertical position init at 1
   
    while (xpos!=9&&ypos!=9){
                //provides random decision point
    int dec1=0;
    int dec2=0;
    int dec3=0;
    int dec4=0;
    int foundmatch=0;
 
    //this snippet generates the possible decisions
   
    if (maze[xpos+1][ypos]==0){
        dec1=1;
    }
    if(maze[xpos-1][ypos]==0){
        dec2=1;
    }
    if(maze[xpos][ypos+1]==0){
    dec3=1;
    }
    if(maze[xpos][ypos-1]){
        dec4=1;
    }
   
    //end getting number of decisions
   
    do{
    int dectake;
    srand ( time(NULL) );
    dectake= rand() % 4 + 1;
   
    if(dectake==1&&dec1==1){
        foundmatch=1;
        xpos++;
    }
    if(dectake==2&&dec2==1){
        foundmatch=1;
        xpos--;
    }
    if(dectake==3&&dec3==1){
        foundmatch=1;
        ypos++;
    }
    if(dectake==4&&dec4==1){
        foundmatch=1;
        ypos--;
    }
    } while (foundmatch!=1);
   
   
    }
   
    cout << "I made it to the end of the maze!";
    return (EXIT_SUCCESS);
}

---

Thanks. Im pretty new to c++ so its good to have a place where i can learn. Sometimes, books just dont address such specific issues.

The thing to do in these situation is step through your code in the debugger and what what it's doing. It should be pretty easy to see where it's acting differently than your expectations.

yea, all my debugger says is

User process Running or somethign like that.

Create a breakpoint right after it prints the file. Then you can single step thru the program to see if there is a loop going on. Put another one right before a statement you think may be causing problems.

hm. ok. thanks.

Quote:

---

maybe i dont have the coordinants numbered right, like 9,9 doesnt coorespond to the bottom left 0. Take a look and let me know if you have any thoughts.

---

I assume you mean bottom right, as there is no 0 in the bottom left area

If i am not mistaken, your indexes are off

_ 0123456789
0 1111111111
1 1011111111
2 1000011111
3 1011011111
4 1011000001
5 1111011011
6 1110011011
7 1110111011
8 1111111001
9 1111111111 <-- 9,9

Hello Dwellerofholes,

I'm a beginner myself but I'll try my best to help.

first off,
I like your way of creating things.
however,
I believe this is a good case study of how program logic can baffle programmers more than writing correct codes.

Logic issue No.1:

Code:

---

if (maze[xpos+1][ypos]==0){
        dec1=1;
    }
// skip...
if(dectake==1&&dec1==1){
        foundmatch=1;
        xpos++;
    }

---

increasing xpos moves up and down, not from left to right.
(perhaps you're confused because x-axis runs horizontal)
I believe choosing distinctive variables names can clear things up.

Logic issue No.2:
Only two(possibly three)things can happen in your maze(event of zero and one).
but the game you're conjuring up in your mind has more than two events.
something must move(1), pathway(2), non-pathway(3),
starting point(4), end point(5).
as you can see,
the map had issues to begin with, not your code.

Logic issue No3:
the flow of the program has a problem.
you're writing codes based on the outcome before any actions can happen,
because you're changing xpos/ypos before you cast
random decision.
this is the major reason why your app just hangs,
because outcome(which supposed to terminate loop and end game)
was not based on the probabilities but rather than fixed end.

taking a closer look again at the code,

Code:

---

if (maze[xpos+1][ypos]==0){
        dec1=1;
    }

---

shows you what I mean.
unless your first move is anything but down, your loop will never terminate.
even if we get lucky and pass the first move,
we still have almost infinite probabilities of getting stuck.

plus what other guys had said so far.

so something like this should work..(hopefully)

Code:

---

#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <time.h>

// OO: letter o's(open path), XX: maze walls
#define OO 0
#define XX 1
#define WIDE 10
#define TALL 10
#define ENDPOINT 99

using namespace std;
/*
void printmatrix(char print[10][10]){
    for (int i=0;i<10;i++){
        for(int k=0;k<10;k++){
        cout<<print[i][k];
        }
    cout <<"\n";}
}
*/

int main() {
   
    //start copying file to a 2d array
    int maze[TALL][WIDE] = {
        {XX, XX, XX, XX, XX, XX, XX, XX, XX, XX}, 
        {XX, OO, XX, XX, XX, XX, XX, XX, XX, XX},
        {XX, OO, OO, OO, OO, XX, XX, XX, XX, XX},
        {XX, OO, XX, XX, OO, XX, XX, XX, XX, XX},
        {XX, OO, XX, XX, OO, OO, OO, OO, OO, XX},
        {XX, XX, XX, XX, OO, XX, XX, OO, XX, XX},
        {XX, XX, XX, OO, OO, XX, XX, OO, XX, XX},
        {XX, XX, XX, OO, XX, XX, XX, OO, XX, XX},
        {XX, XX, XX, XX, XX, XX, XX, OO, ENDPOINT, XX},
        {XX, XX, XX, XX, XX, XX, XX, XX, XX, XX}
        };
         
    #ifdef MAZEFILE
    int rownum=0;
    //begin file io
    ifstream mazefile ("maze.txt");
    while(rownum<10){
      getline(mazefile,rowbuild);
      for(int n=0;n<10;n++){
          maze[rownum][n]=rowbuild[n];}
      rownum++;
      }
    printmatrix(maze);
    #endif
   
    srand ( time(NULL) );
   
 
    int dectake(0);
    int xpos=1;            //provides lateral position init at 1
    int ypos=1;
   
    int currentXPos(1);
    int currentYPos(1);
    int i(0);              // number of turns(or guesses) used
    short endFlag(1);
       
   
    // intro
    cout << "==================================" << endl;
    cout << "\tThe MAZE" << endl;
    cout << "==================================" << endl;
   
   
    // Place a player
    xpos = currentXPos;
    ypos = currentYPos;
   
    do
    {
    // guess where to go before you make a move
    dectake= rand() % 4 + 1;
   
    // show probabilities
    switch(dectake)
    {
                 
        case 1:
        ++ypos;
        cout<<"Moving right..." << endl;
           
            // did we reach the end?
            if(maze[xpos][ypos] == ENDPOINT)
            {
              cout << "Gratz! You are finally out of the maze!" << endl;
              endFlag = 0;
              break;
                     
            // if not, can we at least move?
            } else if (maze[xpos][ypos]==0){
                cout << "That was a lucky guess! " << endl;
                currentYPos = ypos;
                break;

            } else {
                  cout << "You ran into a wall" << endl;
                  --ypos; // go back if blocked
                  currentYPos = ypos;
                  break;         
                  }     
                  break;
           
        case 2:
        --ypos;
        cout<<"Moving left..." << endl;
     
        if(maze[xpos][ypos] == ENDPOINT)
            {
              cout << "Gratz! You are finally out of the maze!" << endl;
              endFlag = 0;
              break;
             
             
        } else if (maze[xpos][ypos]==0){
                cout << "That was a lucky guess! " << endl;
                currentYPos = ypos;
                break;           
            } else {
                  cout << "You ran into a wall" << endl;
                    ++ypos;
                    currentYPos = ypos;
                    break;           
                  }     
                  break;
      case 3:
      ++xpos;
      cout<<"Moving down..." << endl;             
      if(maze[xpos][ypos] == ENDPOINT)
            {
              cout << "Gratz! You are finally out of the maze!" << endl;
              endFlag = 0;
              break;
               
        } else if (maze[xpos][ypos]==0){
                cout << "That was a lucky guess! " << endl;
                currentXPos  = xpos;
                break;
            } else {
                  cout << "You ran into a wall" << endl;
                  --xpos;
                  currentXPos = xpos;
                  break;
                  }     
                  break;
        case 4:
        --xpos;
        cout<<"Moving up..." << endl;
        if(maze[xpos][ypos] == ENDPOINT)
            {
              cout << "Gratz! You are finally out of the maze!" << endl;                           
              endFlag = 0;
              break;
     
        } else if (maze[xpos][ypos]==0){
                cout << "That was a lucky guess! " << endl;
                currentYPos = xpos;
                break;
            } else {
                  cout << "You ran into a wall" << endl;
                  ++xpos;
                  currentXPos = xpos;
                  break;
                  }
                  break;
        default:
              ; // do nothing
              break;     
       
    } // end switch
   
    ++i;
    } while(endFlag != 0);
   
    // display game results
    cout << "You took " << i << " guess to escape the maze" << endl;
   
    if(i == 14) // shortcut
        cout << "PERFECT SCORE " << endl;
       
   
   
    return 0;
}

---

you can turn on/off fileIO for yourself.
I disabled it to make sure no errors were involved with fstream obj. for testing purposes.

I think it's a good idea to use int maze[] rather than char type.

my best score was 47 guess lol

hope it didn't sound like I'm criticizing you, no I'm not~
thanks~ :)

Yo yo

thanks for the help. I ended up just rewriting it. I found that if i did foundmatch as the endpoint and not for the decision it worked better. So i did my if statements as having 3 conditions instead. also, i realized that if i initialize the rand seed every time, then i will come out with like the same random number for every time. lol. so i changed that so it only seeds when it calls it. um. yea, still random movement and all but it works now. My indexes were wrong at first but i realize that now and yea, i stupidly switched my maze[][] thing. ypos goes first lol. here is the finished code. now im goign to start workign on comparing decisions to a memory matrix so i dont go down bad paths twice! aight

Code:

---

//
// File:  mazerunner.cc
// Author: sheawatson
//
// Created on February 19, 2008, 8:31 PM
//

#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
#include <cstdlib>
#include <time.h>

using namespace std;
//
//
void printmatrix(char print[10][10]){
    for (int i=0;i<10;i++){
        for(int k=0;k<10;k++){
        cout<<print[i][k];
        }
    cout <<"\n";
        }
}

int randomnumbergenerator(){
    //srand((unsigned)time(0));
    /*int random_integer;
    int lowest=1, highest=4;
    int range=(highest-lowest)+1;
    random_integer = lowest+int(range*rand()/(RAND_MAX + 1.0));
    return random_integer;*/
   
    int dectake;
    //srand ( time(NULL) );
    dectake= rand() % 4 + 1;
    return dectake;
}
   
   
int main(int argc, char** argv) {

    //start copying file to a 2d array
   
    string rowbuild;
    char maze[10][10];
    int rownum=0;
   
    //begin file io
    ifstream mazefile;
    mazefile.open ("maze.txt");
    if (mazefile.is_open()) {
   
                while(rownum<10){
                        getline(mazefile,rowbuild);
                        for(int n=0;n<10;n++){
                                maze[rownum][n]=rowbuild[n];
                                }
                        rownum++;
        }
    }
    else{cout << "Couldnt open the maze file!";
    }
    mazefile.close();
   
    printmatrix(maze);
   
    int xpos = 1;
    int ypos = 1;
    int foundmatch = 0;
    int dectake;
    int n = 0;
       
    //provides random decision point
    while (foundmatch == 0){
        cout<< "X coordinate = " << xpos << "    Y coordinate = "<<ypos<< "\n";
                  if(maze[ypos][xpos] == 'F' ){
            foundmatch = 1; 
            }
        else{ 
              n++;
                    dectake = randomnumbergenerator();
                   
                    cout<< dectake<<"  ";
   
                    if((maze[ypos][(xpos+1)]== '0' || maze[ypos][xpos+1] == 'F') && dectake==1){
                xpos++;
                    }
                    if((maze[ypos][(xpos-1)]== '0' || maze[ypos][xpos-1] == 'F') && dectake==2){
                xpos--;
                    }
                    if((maze[(ypos+1)][xpos]== '0' || maze[ypos+1][xpos] == 'F') && dectake==3){
                ypos++;
                    }
                    if((maze[(ypos-1)][xpos]== '0' || maze[ypos-1][xpos] == 'F') && dectake==4){
                ypos--;
                    }
        }             
   
    }
    cout << "\nI only had to loop this many times " << n;
        cout << "\nI made it to the end of the maze!\n";
    return (EXIT_SUCCESS);
    //system ("PAUSE");
}

---

and the finishline of my maze is an F character btw