Sandbox: Difference between revisions

#define MAZE_SIZE_X 16

#define MAZE_SIZE_Y 16

/* in file GlobalDefs.h */

unsigned char box[MAZE_SIZE_X+1][MAZE_SIZE_Y+1];

int allowed[4];

int x_[4] = { 0, 1, 0, -1 };

int y_[4] = { 1, 0, -1, 0 };

/* in file DesignMaze.c */

/* This produces an enclosed rectangular maze. There will only be one path between any (x1,y1) and

(x2,y2). The code to add doors is not included here */

/* When I write code for me I put an explanation beforea function to remind me what I was thinking at the time – I have retained those explanations to self here */

/* Also note at the end of the path_check() function the return relies on the weak type checking of

ansii-C and (int)TRUE == 1 */

/* By making the recursive functions static, this is a hint to the compiler to simplify the stack code

instructions as the compiler knows everything that it needs from the current source file and does

not need to involver the linker.

Implementation specific #pragma could also be used */

/**************************************************************************/

/* */

/* The maze is made up of a set of boxes (it is a rectangular maze). */

/* Each box has a description of the four sides, each side can be :- */

/* (a) a solid wall */

/* (b) a gap */

/* (c) a door */

/* */

/* A side has an opening bit set for gaps and doors, this makes the */

/* movement checking easier. */

/* */

/* For any opening there are four bits corresponding to the four sides:- */

/* Bit 0 is set if Northwards movement is allowed */

/* Bit 1 is set if Eastwards movement is allowed */

/* Bit 2 is set if Southwards movement is allowed */

/* Bit 3 is set if Westwards movement is allowed */

/* */

/* For a door there are four bits corresponding to the four sides:- */

/* Bit 4 is set if North has a door, unset if North has a gap */

/* Bit 5 is set if East has a door, unset if East has a gap */

/* Bit 6 is set if South has a door, unset if South has a gap */

/* Bit 7 is set if West has a door, unset if West has a gap */

/* */

/**************************************************************************/

/**************************************************************************/

/********************************** path_check ****************************/

/**************************************************************************/

/* */

/* This sets: */

/* allowed[0] to TRUE if a path could be extended to the 'North' */

/* allowed[1] to TRUE if a path could be extended to the 'East' */

/* allowed[2] to TRUE if a path could be extended to the 'South' */

/* allowed[3] to TRUE if a path could be extended to the 'West' */

/* */

/* A path could be extended in a given direction if it does not go */

/* beyond the edge of the maze (there are no gaps in the surrounding */

/* walls), or the adjacent box has not already been visited */

/* (i.e. it contains 0). */

/* */

/* It also returns non-zero if there is at least one potential path */

/* which can be extended. */

/* */

/**************************************************************************/

static int path_check(int x, int y)

{

if ( y > (MAZE_SIZE_Y-1) )

then { allowed[0] = FALSE; }

else { allowed[0] = (box[x ][y+1] == 0) ? TRUE : FALSE; }

endif

if ( x > (MAZE_SIZE_X-1) )

then { allowed[1] = FALSE; }

else { allowed[1] = (box[x+1][y ] == 0) ? TRUE : FALSE; }

endif

if ( y < 2 )

then { allowed[2] = FALSE; }

else { allowed[2] = (box[x ][y-1] == 0) ? TRUE : FALSE; }

endif

if ( x < 2 )

then { allowed[3] = FALSE; }

else { allowed[3] = (box[x-1][y ] == 0) ? TRUE : FALSE; }

endif

return (allowed[0]+allowed[1]+allowed[2]+allowed[3]);

} /* end of 'path_check' */

/**************************************************************************/

/********************************** design_maze ***************************/

/**************************************************************************/

/* */

/* This is a recursive routine to produce a random rectangular maze */

/* with only one route between any two points. */

/* For each box reached, a 'wall' is knocked through to an adjacent */

/* box if that box has not previously been reached (i.e. no walls */

/* knocked out). */

/* For the adjacent box the adjacent wall is also knocked out. */

/* Then the routine is called again from the adjacent box. */

/* If there are no adjacent boxes which have not already been reached */

/* then the routine returns to the previous call. */

/* */

/**************************************************************************/

static void design_maze(int x, int y)

{

int direction;

while ( path_check(x,y) > 0)

{

do { direction = rand()%4; } while ( allowed[direction]==FALSE );

box[x ][y ] |= (1 << direction );

box[x+x_[direction]][y+y_[direction]] |= (1 << ((direction+2) % 4) );

design_maze( x+x_[direction] , y+y_[direction] );

} endwhile

} /* end of 'design_maze()' */