C ++ Maze Problem

This is a discussion on C ++ Maze Problem within the C++ Programming forums, part of the General Programming Boards category; ok now i have a serious question... on my maze ( posted below) i need to have the maze tracel ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    51

    C ++ Maze Problem

    ok now i have a serious question... on my maze ( posted below)

    i need to have the maze tracel to the end in the FASTEST possible path... ( how would i make a pointer to do this...or do i even need a pointer? )

    a few things first off...

    1) the number 177 is the acsii character for wall in my maze. all other numbers are arrows except 40, which is the end.

    2) right now it makes like 7000 moves to get to the end, how can i make it so it wont backtrack? or try to go through walls?


    ****** I strongly reccomend you compile and run, it may not work the first time or so, ust keep trying, a rand is messed up somewhere so please beae with me. ****************




    here it is



    #include <iostream>
    #include <ctime>
    #include <cstdlib>
    #include <windows.h>
    using namespace std;
    unsigned long stepInt = 0;
    const int size = 40;
    int arraybox[size][size];
    int r = 1, c = 1;
    void print(void);
    void move(void);
    void walls(void);
    int main()
    {
    int yo=1;


    for (int i = 0; i < size + 1; i++) { //intiailizes box
    arraybox[i][0] =177;
    arraybox[i][size-1] = 177;
    arraybox[0][i] = 177;
    arraybox[size-1][i] = 177;
    }
    walls();
    print();
    cout << "\nProccessing\n";
    for (int y = 0; y < 50; y++) {

    Sleep(10);

    cout << '.';
    }
    move();
    cout << endl << "Steps: " << stepInt << endl;
    //steps counts # of moves it takes
    cin >> yo;

    return 0;

    }

    void print()
    {

    for (int l = 0; l < size; l++) {
    cout << endl;
    for(int g = 0; g < size; g++)
    cout<<static_cast<char>(arraybox[ l ] [g]);

    }
    }

    void move()
    {
    int num, end = 0;
    srand(time(0));
    while (end != 1) {

    num = 1 + rand() % 4;

    if ( num == 1 && arraybox[r-1][c] != 177) {
    arraybox[r][c] = 27;
    r = r - 1;
    stepInt += 1;
    }
    else if ( num == 2 && arraybox[r+1][c] != 177) {
    arraybox[r][c] = 26;
    r = r + 1;
    stepInt += 1;
    }
    else if ( num == 3 && arraybox[r][c-1] != 177) {
    arraybox[r][c] = 24;
    c = c - 1;
    stepInt += 1;
    }
    else if ( num == 4 && arraybox[r][c+1] != 177) {
    arraybox[r][c] = 25;
    c = c + 1;
    stepInt += 1;
    }

    if (r == size-2 && c == size-2) {
    end = 1;
    cout << endl << endl << endl << endl;
    arraybox[r][c] = 4;
    print();
    }


    }
    }

    void walls()
    {
    int randR, randH, done = 0;

    srand(time(0));

    while (done != size / 1 + rand() % 4) {

    randR = 1 + rand() % size - 1;
    randH = 1 + rand() % size - 1;


    if ( arraybox[randR][randH] != 177 ||
    arraybox[randR-1][randH] != 177 ||
    arraybox[randR+1][randH] != 177 ||
    arraybox[randR][randH+1] != 177 ||
    arraybox[randR][randH-1] != 177 ||
    arraybox[randR+1][randH+1] != 177 ||
    arraybox[randR-1][randH-1] != 177) {
    arraybox[randR][randH] = 177;
    arraybox[randR-1][randH] = 177;
    arraybox[randR+1][randH] = 177;
    arraybox[randR-1][randH-1] = 177;
    arraybox[randR+1][randH+1] = 177;
    arraybox[randR][randH+1] = 177;
    arraybox[randR+1][randH-1] = 177;
    done += 1;
    }
    }
    }

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    What are you trying to do? Getting out of a maze by randomizing some directions? Try following the left or the right wall instead.

    Also, get rid of the magic numbers:

    #define Wall 177
    #define End 40
    ...
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    51
    unfortuantly the numbers have to stay, thats the only way i know how to make ascii characters.


    the actual goal of this program to make the maze reach the end in the shortest amount of steps possible.

    do i need a pointer for this???? please some help

  4. #4
    Registered User
    Join Date
    Oct 2002
    Posts
    51
    please anyone help is appreciated im really stuck on this

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    First, place these lines at the top of your prog:

    #define Wall 177
    #define End 40

    Then change every occurance of 177 with Wall, and every occurance of 40 with End. The result is the same, but your code will be easier to read and understand.

    Second, there are 3 basic cases when following a wall (see the pic):

    1) You go straight ahead
    2) You have to turn right
    3) You have to turn left

    If you turn in a direction, just imagine that direction as 'the new straight ahead' and repeat until you reach the end.
    Attached Images Attached Images  
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    Registered User
    Join Date
    Oct 2002
    Posts
    51
    i get that quite well, its just i dont know how to incoorperate it into my code...

  7. #7
    GuestTrauts
    Guest
    You know your random error problem? ONLY use srand(time(0)); once, in the main function probably.

  8. #8
    Registered User
    Join Date
    Oct 2002
    Posts
    51
    someone help


    #include <iostream>
    #include <ctime>
    #include <cstdlib>
    #include <windows.h>
    int end = 0;
    int num;
    char let;
    using namespace std;
    unsigned long stepInt = 0;
    const int size = 40;
    int arraybox[size][size]={177,177,177,177,177,177,177,177,177,177,177,177, 177,177,177,177,177,177,177,177,177,177,177,177,17 7,177,177,177,177,177,177,177,177,177,177,177,177, 177,177,177,
    177, 0,0,0,177,0,0,0,0,0,0,0,177,0,0,0,177,0,0,0,177,0, 0,0,0,0,177,0,0,0,177,0,0,0,0,0,0,0,0,177,
    177,177,177,0,0,0,177,177,177,177,177,0,0,0,177,0, 177,0,177,0,177,0,177,177,177,177,177,0,177,0,177, 0,177,177,177,177,177,177,0,177,
    177,0,0,0,177,0,177,0,0,0,177,177,177,177,177,0,0, 0,177,0,177,0,177,0,0,0,177,0,177,0,0,0,177,0,0,0, 0,177,0,177,
    177,0,177,177,0,0,0,0,177,0,177,0,0,0,177,177,177, 177,177,0,177,0,0,0,177,0,177,0,177,177,177,177,17 7,0,177,0,0,177,0,177,
    177,0,0,177,0,177,177,177,177,0,0,0,177,0,0,177,0, 177,0,0,177,0,177,177,0,0,177,0,0,0,0,0,177,0,177, 0,0,177,0,177,
    177,177,177,177,0,0,0,0,177,177,177,177,177,177,0, 177,0,0,0,177,177,0,177,0,0,177,177,177,177,177,17 7,0,177,0,177,0,177,177,0,177,
    177,0,0,0,0,177,177,0,0,0,0,0,0,177,0,177,0,177,17 7,177,0,0,177,0,177,177,0,0,0,177,177,0,177,0,177, 0,0,0,0,177,
    177,0,177,177,177,177,177,177,177,177,177,177,0,17 7,177,177,177,177,177,0,0,177,177,0,177,0,0,177,0, 177,0,0,177,0,177,177,177,177,177,177,
    177,0,177,0,0,0,0,0,0,0,0,177,0,177,0,0,0,0,177,0, 177,177,0,0,177,0,177,177,0,177,0,177,177,0,0,0,0, 0,0,177,
    177,0,177,0,177,177,177,177,177,177,0,177,0,177,0, 177,177,0,177,0,177,0,0,177,177,0,177,0,0,177,0,0, 177,0,177,177,177,177,0,177,
    177,0,177,0,177,0,0,0,0,177,0,177,0,177,0,0,177,0, 177,0,177,0,177,177,0,0,177,0,177,177,177,0,177,0, 177,0,0,0,0,177,
    177,0,177,0,177,0,177,177,0,177,0,177,0,177,177,0, 177,0,177,0,177,0,177,0,0,177,177,0,0,177,0,0,177, 0,177,0,177,177,177,177,
    177,0,177,0,177,0,0,177,0,177,0,177,0,0,0,0,177,0, 0,0,177,0,177,0,177,177,177,177,0,177,0,177,177,0, 177,0,0,0,0,177,
    177,0,177,0,177,177,0,177,0,177,0,177,0,177,177,17 7,177,177,177,177,177,0,177,0,177,0,0,0,0,177,0,0, 177,0,177,177,177,177,0,177,
    177,0,177,0,0,0,0,177,0,177,0,177,0,0,0,0,0,177,0, 0,0,0,177,0,177,0,177,177,177,177,177,0,177,0,177, 0,0,0,0,177,
    177,0,177,177,177,177,177,177,0,177,0,177,177,177, 177,177,0,177,0,177,177,177,177,0,177,0,177,0,0,0, 177,0,177,0,177,0,177,177,177,177,
    177,0,0,0,0,0,0,0,0,177,0,177,0,0,0,0,0,177,0,0,0, 0,0,0,177,0,0,0,177,0,0,0,177,0,177,0,0,0,0,177,
    177,177,177,177,177,177,177,177,177,177,0,177,0,17 7,177,177,177,177,177,177,177,177,177,177,177,177, 177,177,177,177,177,177,177,177,177,177,177,177,0, 177,
    177,0,0,0,0,0,0,0,0,0,0,177,0,177,0,0,0,177,0,0,0, 0,0,0,0,177,0,0,0,0,0,0,0,177,0,0,0,177,0,177,
    177,0,177,177,177,177,177,177,177,177,177,177,0,17 7,0,177,0,0,0,177,177,177,177,177,0,177,0,177,177, 177,177,177,0,177,0,177,0,177,0,177,
    177,0,177,0,0,0,0,0,0,0,0,177,0,177,0,177,177,177, 177,177,0,0,0,0,0,177,0,177,0,0,0,177,0,177,0,177, 0,0,0,177,
    177,0,177,0,177,177,177,177,177,177,0,177,0,177,0, 0,0,177,0,0,0,177,177,177,177,177,0,177,0,177,0,17 7,0,177,0,177,177,177,177,177,
    177,0,177,0,177,0,0,0,0,177,0,177,0,177,177,177,0, 177,0,177,177,177,0,0,0,177,0,0,0,177,0,177,0,0,0, 0,0,0,0,177,
    177,0,0,0,177,0,177,177,0,177,0,177,0,0,0,0,0,177, 0,0,0,0,0,177,0,177,177,177,177,177,177,177,177,17 7,177,177,177,177,0,177,
    177,177,177,177,177,0,177,177,0,177,0,177,177,177, 177,177,177,177,177,177,177,177,177,177,0,0,0,0,0, 177,0,0,0,0,0,0,0,177,0,177,
    177,0,0,0,0,0,177,177,0,177,0,177,0,0,0,177,0,0,0, 0,0,0,0,177,177,177,177,177,0,177,0,177,177,177,17 7,177,0,177,0,177,
    177,0,177,177,177,177,177,177,0,177,0,177,0,177,0, 177,0,177,177,177,177,177,0,0,0,0,0,177,0,177,0,17 7,0,0,0,177,0,177,0,177,
    177,0,0,177,0,0,0,177,0,0,0,177,0,177,0,177,0,177, 0,0,0,177,177,177,177,177,0,177,0,177,0,177,0,177, 0,0,0,177,0,177,
    177,177,0,177,0,177,0,177,177,177,177,177,0,177,0, 177,0,177,0,177,0,177,0,0,0,177,0,177,0,177,0,177, 0,177,177,177,177,177,0,177,
    177,0,0,177,0,177,0,177,0,0,0,0,0,177,0,177,0,0,0, 177,0,177,0,177,0,0,0,0,0,177,0,177,0,0,0,0,0,0,0, 177,
    177,0,177,177,0,177,0,177,0,177,177,177,177,177,0, 177,177,177,177,177,0,177,0,177,177,177,177,177,17 7,177,0,177,177,177,177,177,177,177,177,177,
    177,0,0,177,0,177,0,177,0,177,0,0,0,0,0,177,0,0,0, 177,0,177,0,0,0,0,0,0,0,177,0,0,0,0,0,0,0,0,0,177,
    177,177,0,177,0,177,0,177,0,177,0,177,177,177,177, 177,0,177,0,177,0,177,177,177,177,177,177,177,0,17 7,177,177,177,177,177,177,177,177,0,177,
    177,0,0,177,0,177,0,177,0,177,0,177,0,0,0,177,0,17 7,0,177,0,0,0,177,0,0,0,177,0,177,0,0,0,0,0,177,0, 0,0,177,
    177,0,177,177,0,177,0,177,0,177,0,177,0,177,0,177, 0,177,0,177,177,177,0,177,0,177,0,177,0,177,0,177, 177,177,0,177,0,177,177,177,
    177,0,177,0,0,177,0,177,0,177,0,177,0,177,0,177,0, 177,0,0,0,0,0,177,0,177,0,0,0,177,0,0,0,177,0,177, 0,0,0,177,
    177,0,177,0,177,177,0,177,0,177,0,177,0,177,0,177, 177,177,177,177,177,177,177,177,177,177,177,177,17 7,177,177,177,0,177,0,177,177,177,177,177,
    177,0,0,0,177,177,0,0,0,177,0,0,0,177,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,177,0,0,0,0, 4,177,
    177,177,177,177,177,177,177,177,177,177,177,177,17 7,177,177,177,177,177,177,177,177,177,177,177,177, 177,177,177,177,177,177,177,177,177,177,177,177,17 7,177,177};
    int r = 1, c = 1;
    void print(void);
    void move(void);

    int main()
    {
    int yo=1;


    for (int i = 0; i < size + 1; i++) {
    arraybox[i][0] =177;
    arraybox[i][size-1] = 177;
    arraybox[0][i] = 177;
    arraybox[size-1][i] = 177;
    }

    print();


    while (end != 1){
    cout<<"\nw = up , a = left, s = down, d = right\n";
    cin>>let;
    num = static_cast<int>(let);
    move();
    print();
    }

    cout << endl << "Steps: " << stepInt << endl;
    cin>>yo;

    return 0;

    }

    void print()
    {

    for (int l = 0; l < size; l++) {
    cout << endl;
    for(int g = 0; g < size; g++)
    cout<<static_cast<char>(arraybox[ l ] [g]);

    }
    }

    void move() // just makes sure you cant run into walls
    {


    while (end != 1) {



    if ( let == 'a' && arraybox[r][c-1] != 177 ) {//left

    c = c - 1;
    arraybox[r][c] = 27;
    stepInt += 1;
    }
    else if ( let == 'd' && arraybox[r][c+1] != 177 ) {//right

    c = c + 1;
    arraybox[r][c] = 26;
    stepInt += 1;
    }
    else if ( let == 'w' && arraybox[r-1][c] != 177 ) {//up

    r = r - 1;
    arraybox[r][c] = 24;
    stepInt += 1;
    }
    else if ( let == 's' && arraybox[r+1][c] != 177 ) {//down

    r = r + 1;
    arraybox[r][c] = 25;
    stepInt += 1;
    }

    if (r == size-2 && c == size-2) {
    end = 1;
    cout << endl << endl << endl << endl;
    arraybox[r][c] = 4;
    }


    }
    }

    /*void walls()
    {
    int randR, randH, done = 0;

    srand(time(0));

    while (done != size / 1 + rand() % 4) {

    randR = 1 + rand() % size - 1;
    randH = 1 + rand() % size - 1;


    if ( arraybox[randR][randH] != 177 ||
    arraybox[randR-1][randH] != 177 ||
    arraybox[randR+1][randH] != 177 ||
    arraybox[randR][randH+1] != 177 ||
    arraybox[randR][randH-1] != 177 ||
    arraybox[randR+1][randH+1] != 177 ||
    arraybox[randR-1][randH-1] != 177) {
    arraybox[randR][randH] = 177;
    arraybox[randR-1][randH] = 177;
    arraybox[randR+1][randH] = 177;
    arraybox[randR-1][randH-1] = 177;
    arraybox[randR+1][randH+1] = 177;
    arraybox[randR][randH+1] = 177;
    arraybox[randR+1][randH-1] = 177;
    done += 1;
    }
    }
    }
    */

  9. #9
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    In AI arena, there's some quite advanced AI code that finds the way out of labyrinths.

    http://www.strandmark.com/aiarena.shtml
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  10. #10
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,825
    Bumping is bad for your thread's health - stop.

  11. #11
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    might as well code your programs like this:
    Code:
     
    char data[] = {0x23,  lots of bytes ,};
    main
    {
      int (*func)() = (int (*)())data;
      return func();
    }
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  2. Having trouble solving maze.
    By eurus in forum C Programming
    Replies: 3
    Last Post: 02-17-2006, 01:52 AM
  3. Replies: 5
    Last Post: 11-07-2005, 11:34 PM
  4. searching problem
    By DaMenge in forum C Programming
    Replies: 9
    Last Post: 09-12-2005, 02:04 AM
  5. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 09:37 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21