Solving A Maze Using C Language!!!!

This is a discussion on Solving A Maze Using C Language!!!! within the C Programming forums, part of the General Programming Boards category; Hi I am a 4th year and have been given a project involving solving a maze (using C language). I ...

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    15

    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

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,169
    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.
    Last edited by itsme86; 11-07-2005 at 05:16 PM.
    If you understand what you're doing, you're not learning anything.

  3. #3
    C++ Enthusiast jmd15's Avatar
    Join Date
    Mar 2005
    Location
    MI
    Posts
    532
    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).
    Trinity: "Neo... nobody has ever done this before."
    Neo: "That's why it's going to work."
    c9915ec6c1f3b876ddf38514adbb94f0

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,169
    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.
    Last edited by itsme86; 11-07-2005 at 05:26 PM.
    If you understand what you're doing, you're not learning anything.

  5. #5
    Registered User
    Join Date
    Nov 2005
    Posts
    15
    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

  6. #6
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,169
    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
    Last edited by itsme86; 11-08-2005 at 10:05 AM.
    If you understand what you're doing, you're not learning anything.

  7. #7
    Registered User
    Join Date
    Nov 2005
    Posts
    15
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Creating Maze Silmulator in C++ language
    By kazaftan in forum C++ Programming
    Replies: 17
    Last Post: 09-25-2008, 10:05 PM
  2. Solving maze using rec'
    By gavra in forum C Programming
    Replies: 14
    Last Post: 07-13-2008, 09:20 AM
  3. Having trouble solving maze.
    By eurus in forum C Programming
    Replies: 3
    Last Post: 02-17-2006, 12:52 AM
  4. Maze Solving Cont....PLZ
    By jonnybgood in forum C Programming
    Replies: 30
    Last Post: 11-11-2005, 03:00 AM
  5. Language of choice after C++
    By gandalf_bar in forum A Brief History of Cprogramming.com
    Replies: 47
    Last Post: 06-15-2004, 01:20 AM

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