Maze Program, Any ideas

This is a discussion on Maze Program, Any ideas within the C++ Programming forums, part of the General Programming Boards category; OK i have a project due for my CS class in a week or so and i decided to come ...

  1. #1
    Registered User
    Join Date
    Nov 2003
    Posts
    3

    Maze Program, Any ideas

    OK i have a project due for my CS class in a week or so and i decided to come on here and see if anyone has ideas for how i should do this program. I have to open a file that has a 20x20 maze with "o" for the path, "x" for the walls, and i start and end at two different letters. an example would be

    xxxxxxxxooooooxxxxxx
    xxoooooooxxxxoooxxxx
    xxxxxxxxoxxxxxxxxxxx

    THen the program has to create another file that has the directions through the maze.

    Im having problems storing the individual characters in an array, im using a 2-dimensional one and im wondering if im going at that the wrong way. Im also wondering if anyone would help with ideas on how i would go at parts of the maze where there are multiple directions to go. Thanks for the help in advance

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    What kind of problems are you having with storing them? A two dimensional array should work fine.

    As for solving it, do a search for breadth first search (or BFS for short) which will solve a maze like this easily and give you the shortest route as well.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,761
    I suggest a depth-first search of the board to find previous answers to the question
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    I suggest "right-hand rule",

  5. #5
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    I suggest recursion
    I had the same problem in my first c++ course last semester.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  6. #6
    Registered User
    Join Date
    Nov 2003
    Posts
    3
    Ive been testing to see if the maze was actually loaded in the array by printing out random parts of the array, but all i end up getting is blank space. any ideas on why thats happening.

  7. #7
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    Looking at your codes will give me some idea

  8. #8
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Originally posted by alphaoide
    I suggest "right-hand rule",
    I think I'm thinking along the same lines. If you are walking through a maze, you can find you're way out by just keeping your right hand on the wall to your right. Keep walking around like that and you'll eventually find your way out. That won't find the shortest path like a BFS algorithm, but I think it might be easier to understand and implement.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  9. #9
    Registered User
    Join Date
    Nov 2003
    Posts
    3
    Our instructions forthe program are to find the shortest path so, i guess its going to be a BFS instead of the right-hand rule.

  10. #10
    Registered User
    Join Date
    Nov 2003
    Posts
    168
    Maybe when "drawing" the maze, you should add which type each room is - i.e. a type one room is a room which has a way back and forth, and a type 4 room is a room where you can go back, forth, left and right. This room ofcourse links to type one room. But a type 2 room can only go left and forth. Got it?
    -Felix
    Rots Soft
    If the facts don't fit the theory, change the facts.
    Albert Einstein (1879 - 1955)

  11. #11
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Yeah, we don't have any idea why your two-dimensional array doesn't work unless we see the code. Could you post it?

    On a sidenote, right hand rule doesn't always work if where you want to get to is in the middle of the maze. In this case it is possible to loop around the exit indefinately.

  12. #12
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    Originally posted by Felix
    Maybe when "drawing" the maze, you should add which type each room is - i.e. a type one room is a room which has a way back and forth, and a type 4 room is a room where you can go back, forth, left and right. This room ofcourse links to type one room. But a type 2 room can only go left and forth. Got it?
    probably not...because I'm sure that the maze that this will be graded on will be different then he has supplied right now to make the program....this is actually a very trivial program. Recursively step through the array, keeping track of the position that you are at....each time check for walls on all sides. If you encounter a dead end, go of the stack. Also keep track of the directions by printing them into an array.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  13. #13
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    That doesn't necessarily give the shortest distance though.

    [edit] Unless its a perfect maze where there is one and one way to get from any one spot to another. If this is the case then the stack method would give shortest distance.
    Last edited by PJYelton; 11-13-2003 at 12:10 PM.

  14. #14
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    Originally posted by PJYelton
    That doesn't necessarily give the shortest distance though.

    [edit] Unless its a perfect maze where there is one and one way to get from any one spot to another. If this is the case then the stack method would give shortest distance.
    You're right...I was thinking of a maze with one way in and one way out.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  15. #15
    Wen Resu
    Join Date
    May 2003
    Posts
    219
    made a similar program, cause i was bored.
    Heres best i can tell you. load the maze int othe array like you have been. when doing this find your start and end points, store them somewere.
    NOw as said use recursion.
    as an example
    this is assuming x is a wall o is a empty spot
    using F as the finished spot locator
    the 2d array is built as havign top right corner of the map as 0,0
    Code:
    void search(int x, int y, unsigned char dir) { // x y coords to check and direction you are coming from
    if map[x][y] =  120 { // 120 is  ascii code for x
        return;
    }
    if map[x][y] = 111 { // 111 is ascii code for o
    // check up
    search(x, y - 1, d);
    // check down
    search(x, y + 1, u);
    // check left
    search(x -1, y, r);
    //check right
    search(x+1, y, l);
    // if you get here then all suround spots are xs
    return
    }
    Ok a note about this code
    its just an idea
    your gona need to use loc to make sure your not checking the direction you were just coming from.
    gona let you figure otu rest if yo uened help post some code.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Issue with program that's calling a function and has a loop
    By tigerfansince84 in forum C++ Programming
    Replies: 9
    Last Post: 11-12-2008, 01:38 PM
  2. insufficient memory for tsr
    By manmohan in forum C Programming
    Replies: 8
    Last Post: 01-02-2004, 09:48 AM
  3. Date program starts DOS's date
    By jrahhali in forum C++ Programming
    Replies: 1
    Last Post: 11-24-2003, 05:23 PM
  4. Program Idea's
    By devour89 in forum C++ Programming
    Replies: 11
    Last Post: 12-04-2002, 04:57 AM
  5. Program ideas...
    By code987 in forum C++ Programming
    Replies: 3
    Last Post: 11-18-2002, 11:41 PM

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