Thread: noobie maze program

Im working on a maze solving program and i'm a little lost. It should just follow the maze walls to the right and find the exit using: west=0, north=1,east=2,south=3.

The '.' represent open spaces in the maze, and the '#' represent walls.

I have the maze and i have it printing but i am not sure how to do a solving function. I have searched but everything i found just confuses me and i cant figure out how to implement it in my program . Please help


code

Code:

#include <stdio.h>
#include <string.h>

 
 
void display( char maze[12][12],int row, int column )
{
int i,j;
for( i = 0; i<12; i++)
{
for( j = 0; j<12; j++)
{
printf( "%c", maze[i][j]);
}
printf("\n");
}





int main()
{
int row = 2;
int column = 0;
int direction; 
char maze[12][12] = {'#','#','#','#','#','#','#','#','#','#','#','#',
	             '#','.','.','.','#','.','.','.','.','.','.','#',
	             'x','.','#','.','#','.','#','#','#','#','.','#',
	             '#','#','#','.','#','.','.','.','.','#','.','#',
	             '#','.','.','.','.','#','#','#','.','#','.','.',
	             '#','#','#','#','.','#','.','#','.','#','.','#',
	             '#','.','.','#','.','#','.','#','.','#','.','#',
	             '#','#','.','#','.','#','.','#','.','#','.','#',
	             '#','.','.','.','.','.','.','.','.','#','.','#',
	             '#','#','#','#','#','#','.','#','#','#','.','#',
	             '#','.','.','.','.','.','.','#','.','.','.','#',
	             '#','#','#','#','#','#','#','#','#','#','#','#',};


 


return 0;

      
}

I've been working on a little maze solving program of my own, I'm at work so I don't have any code to show but you have looked at the A* path finding algorythm at all? Here's a good link ..

http://www.policyalmanac.org/games/aStarTutorial.htm

If you need any more help, I'll see what I can do.

One way would be to always try the same direction in every room until you hit a wall. Then try another direction until you hit a wall. If you reach a dead-end back up until you reach a room with a direction you haven't tried. This is pretty easy to implement with a recursive function, but some people might argue that a recursive solution isn't the best.

So the algorithm might look something like:
- if no wall to the east, enter the room to the east and loop, otherwise go back to the last room
- if no wall to the north, enter the room to the north and loop, otherwise go back to the last room
- if no wall to the west, enter the room to the west and loop, otherwise go back to the last room
- if no wall to the south, enter the room to the south and loop, otherwise go back to the last room
- else, nowhere to go, return to last room

The reason recursive functions work so well here is because it's easy to get back to the last room by just returning. Instead of looping at each step you just call your recursive function with the new room coordinates.

This doesn't exactly meet your requirements, but here's a simple maze program I wrote to help someone else on this board:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

unsigned char **maze = NULL;
int dimx, dimy;
int curx, cury;
int goalx, goaly;

char *dirs = NULL;
int curdir;

void read_file(void)
{
  char *vals = "0123456789ABCDEF";
  char buf[4096];
  FILE *fp;
  int i, j;

  if(!(fp = fopen("maze.txt", "r")))
  {
    puts("Couldn't open maze.txt for reading!");
    exit(EXIT_FAILURE);
  }

  fgets(buf, sizeof(buf), fp);
  sscanf(buf, "%d %d", &dimx, &dimy);
  fgets(buf, sizeof(buf), fp);
  sscanf(buf, "%d %d", &curx, &cury);
  fgets(buf, sizeof(buf), fp);
  sscanf(buf, "%d %d", &goalx, &goaly);

  printf("Maze is %d by %d. Attempt to go from %d,%d to %d,%d\n",
    dimx, dimy, cury, curx, goaly, goalx);

  if(!(maze = malloc(sizeof(char *) * dimy)))
  {
    puts("Memory allocation error!");
    exit(EXIT_FAILURE);
  }

  for(i = 0;i < dimy;++i)
  {
    if(!(maze[i] = malloc(dimx)))
    {
      puts("Memory allocation error!");
      exit(EXIT_FAILURE);
    }

    fgets(buf, sizeof(buf), fp);

    for(j = 0;j < dimx;++j)
      maze[i][j] = strchr(vals, buf[j]) - vals;
  }

  fclose(fp);
}

void print_maze(void)
{
  int i, j;

  for(i = 0;i < dimy;++i)
  {
    for(j = 0;j < dimx;++j)
      printf("%X ", maze[i][j]);
    putchar('\n');
  }
}

int try_coord(int y, int x)
{
  unsigned char val = maze[y][x];

  maze[y][x] |= CHECKED;

  if(y == goaly && x == goalx)
    return 1;

  if(!(val & W_NORTH) && !(maze[y - 1][x] & CHECKED))
    if(try_coord(y - 1, x))
    {
      dirs[curdir++] = 'N';
      return 1;
    }
  if(!(val & W_SOUTH) && !(maze[y + 1][x] & CHECKED))
    if(try_coord(y + 1, x))
    {
      dirs[curdir++] = 'S';
      return 1;
    }
  if(!(val & W_EAST) && !(maze[y][x + 1] & CHECKED))
    if(try_coord(y, x + 1))
    {
      dirs[curdir++] = 'E';
      return 1;
    }
  if(!(val & W_WEST) && !(maze[y][x - 1] & CHECKED))
    if(try_coord(y, x - 1))
    {
      dirs[curdir++] = 'W';
      return 1;
    }

  return 0;
}

void print_solution(void)
{
  puts("\nSolution:");
  while(--curdir > -1)
    printf("%c ", dirs[curdir]);
  putchar('\n');
}

int main(void)
{
  read_file();

  if(!(dirs = calloc(1, dimx * dimy)))
  {
    puts("Memory allocation error!");
    return 0;
  }
  curdir = 0;

  print_maze();

  if(!try_coord(cury, curx))
    puts("No solution found");
  else
    print_solution();

  return EXIT_SUCCESS;
}

maze.txt looks like:

Code:

5 5
0 4
4 1
DC8AB
575CB
4A15F
5C169
776A3

Hopefully the try_coord() function will help you. That's where the whole solution-finding happens.

Originally Posted by gunder

I've been working on a little maze solving program of my own, I'm at work so I don't have any code to show but you have looked at the A* path finding algorythm at all? Here's a good link ..

http://www.policyalmanac.org/games/aStarTutorial.htm

If you need any more help, I'll see what I can do.

wow A* seems interesting but i dont have enough time to dive into it at the moment. Everyone keeps telling me this is easy, but im not getting anywhere. Im having trouble assigning directions to number like i want 0,1,2,3, and following the right wall....not real sure how to go about it. I havent learned stacks yet, so i kinda want to avoid them right now.

I came across this but i am not sure how to utilize and adjust it for my program, any ideas?

Code:

if( north != been_there_done_that )
    recursive( here->north );
if( east != been_there_done_that )
    recursive( here->east );
if( south != been_there_done_that )
    recursive( here->south );
if( west != been_there_done_that )
    recursive( here->west );
return at_a_dead_end;

eh, i figured it out. yay for me. If anyone wants me to post the final code i will. it now displays the graph after each move and counts the total number of times moved north south east and west.