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

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.

I suggest a depth-first search of the board to find previous answers to the question

I suggest "right-hand rule",

I suggest recursion
I had the same problem in my first c++ course last semester.

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.

Looking at your codes will give me some idea

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.

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.

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?

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.

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.

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.

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.

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.