Maze generation: Difference between revisions
Content added Content deleted
imported>Mike632t |
imported>BlueWren |
||
Line 1,551: | Line 1,551: | ||
│ │ ╰┄┄┄╯│ ╰┄┄┄┄┄┄┄╯│ ╰┄┄│ |
│ │ ╰┄┄┄╯│ ╰┄┄┄┄┄┄┄╯│ ╰┄┄│ |
||
└─────┴───────┴───────────┴─────┘</pre> |
└─────┴───────┴───────────┴─────┘</pre> |
||
/* ---------------------------------------------------------- */ |
|||
/* I include the following alternative, it may be of interest */ |
|||
/* ---------------------------------------------------------- */ |
|||
/* in file define’s.h */ |
|||
/* I came to ansi-C after Algol-60 etc and these five pretend to be language tokens */ |
|||
/* I do like ansi-C but the syntax is really rather 'scruffy' */ |
|||
#define then |
|||
#define endif |
|||
#define endwhile |
|||
#define endfor |
|||
#define endswitch |
|||
#ifndef BOOL |
|||
#define BOOL int |
|||
#define TRUE 1 |
|||
#define FALSE 0 |
|||
#endif |
|||
#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 before a 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 |
|||
ansi-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 involve 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()' */ |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |