Thread: Maze Solving Cont....PLZ

(maze[xstart][ystart] & W_NORTH)

what do you suppose you are doing with that? Does that solve any task you had in mind? Maybe its there for looks?

Oh I just thought of a useful bit of information I learned with I was 15 going through a huge bush maze in a girls pants. If you always turn right, the end will be near. Use that information to your advantage my friend.

You will want to set up movement checks. If you want to move a direction, see if that wall is closed or not, then see if that direction is in bounds of the array. If it is, then do the move.


Quzah.

Originally Posted by jonnybgood

i thought it would tell me whether there is a wall or not..
i thought it did the following
say maze[xstart][ystart] is 6
in binary this is 0 1 1 0
i want to & this with 1 0 0 0 (north wall)
then the result of this will be 0 0 0 0 which will tell ne that there isnt a wall at north so i can do something like move to maze[xstart][ystart+1] and do the loops again.

how would i go about the above

what I meant was...its not doing a damn thing. perhaps putting it in an if statement would get you the results..

Code:

if( whatever & 6 )
{
   // DO SOMETHING
}

Code:

(maze[xstart][ystart] & W_NORTH)

& is an operator...like +. You wouldn't have a line of code like:

Code:

4 + 3;

would you? I mean...it's doing nothing. It's adding the numbers and the result is just left in limbo. You need to use the result somewhere, somehow.

Here's a generic solve-the-maze type program that mostly follows your guidelines. The input file is a bit different (it's in hex), but maybe it will help. Let me know if you have any questions about it at all because understanding is the most important thing:

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;
}

Running it I get:

Code:

Maze is 5 by 5. Attempt to go from 4,0 to 1,4
D C 8 A B
5 7 5 C B
4 A 1 5 F
5 C 1 6 9
7 7 6 A 3

Solution:
N N E E S S E E N W N N E

I didn't free the memory I allocated which makes me a bad person. Don't follow that bad example

Where do you check if there's a wall in the way? It's possible to have two adjacent cells that you can enter, but not necessarily directly from one to the other.