Solving A Maze Using C Language!!!!

Hi
I am a 4th year and have been given a project involving solving a maze (using C language). I have never done C before although i have done about 6 months of JAVA.

Any help to the following would be greatly appreciated.
Here is the layout which we were given.

We get given an input file which is layed out as follows:

20 20 (this is the size of the maze, 20x20)
4 7 (this is the starting point of the maze)
7 20 (this is the end point of the maze)
5 7 2 9 4 6 .......
4 6 8 6 8 9 ........(20 rows of numbers and 20 columns of numbers giving each sqaure of the maze the info it needs)

so 6 would be 0 1 1 0 in binary which would mean the north direction hasnt got a wall, West has a wall, South has a wall and East hasnt got a wall.

We have to get to the end in the quickest route possible.

I have come up only with this so far... i have no idea how to implement it...

say function checksquare(grid reference)
if grid reference has been looked at, go back
for each square connected to this one
if connectdsquare = = endsquare, maze has been solved
else checksquare(connectedsquare)
end for
end function


i have no idea how to implement this!!!!
any help would be so greatly appreciated


thanks

jonny

What if north, south, and west all have walls. Does the input file have 14 or E? I only see single-digit numbers in your example file is the reason I ask.

So does it give you coordinates? If so then why not make a 2D array and fill it with a certain character, say 'E' for empty. Then take all the coordinates and put the character 'F' in that spot in the array. Then when checking just plug your coordinates(your current location in the maze added with whatever amount you are moving in a certain direction) into the array and if it returns an E then that spot is empty, if it returns an F that spot is taken(a wall).

The 2D array is a good idea. You could make each element a bitfield. Say:

Code:

---

#define W_EAST  0x1
#define W_SOUTH 0x2
#define W_WEST  0x4
#define W_NORTH 0x8
#define CHECKED 0x10

---

Then, while reading the text file you just do array[row][column] = input_num;

Then start at the starting coordinates and move in all the possible directions. Something like:

Code:

---

void function(int cur_row, int cur_column)
{
  array[cur_row][cur_column] |= CHECKED;

  if(!(array[cur_row][cur_column] & N_WALL) && !(array[cur_row - 1][cur_column] & CHECKED))
    function(cur_row - 1, cur_column);

/* Same if(), but for the other 3 directions */
}

---

Do that for each direction and if the if() matches then call the function again recursively on the new row/column.

Then you also just need to check if the cur_row and cur_column match the destination coordinates.

Note: The CHECKED bit is only necessary if your maze can have more than one way to get to the same coordinate.

to answer your first question, yes 14 would mean north, west and south have walls.

Im not 100% sure on what exactly the code example you gave does. Could you possibly exaplin it in more detail (ie: what each line of code does).

I appreciate all the help.

thanks

Imagine an 8-bit bitfield. While reading the input file you set each coordinate in the 2-d array to the value for that coordinate in the input field. So let's say maze[0][0] is 6. The maze[0][0] bitfield would look like 00000110.

So when you get ready to process coordinate 0,0 you grab that number and try going in each direction. The code example I gave is just a way of finding out if there's a wall in the direction you're trying to go. The & operator is bitwise AND. So let's say you try going east first. East is defined as 0x1. So you do maze[0][0] & W_EAST which is the same as:

00000110 (6) &
00000001 (1)
---------------
00000000 (0)

Since the result is 0 there's no wall to the east so you can go that way. If you tried south (defined as 0x2) you'd be doing:

00000110 (6) &
00000010 (2)
---------------
00000010 (2)

Since the answer isn't 0 there's a wall there so you can't go that way. So you have 4 if()s, one that tests each direction W_EAST (0x1), W_SOUTH (0x2), W_WEST (0x4), W_NORTH (0x8).

Hopefully that clears up some of it, but if you need more information on bitwise operators then check this out: http://www.eskimo.com/~scs/cclass/int/sx4ab.html

ok cool..that makes perfect sense...
there is another problem that i have been trying to work out..
after i have worked out whether there is a wall in a certain coordinate how do i tell the program to move there and start on the next coordinates (trying all 4 sides)
Once it has has managed to get to the end coordinate, i need it to save the route it took to an array. I also have to get it to find the shortest route.
I though for the shortest route i could just compare array lengths and print out the shortests one (or is there a better way (im sure there is))

thanks, a lot...your help is awesome