// Generate a pac-man style maze.
// Code is written in a style that should make it trivial to convert to Scratch,
// i.e. no functions, no local variables, while loops instead of for loops, no <=, >=, or !=,
// and all arrays are 1 dimensional, based at 1. (So the C implementation never accesses element 0)
#include <stdio.h>
#include <stdlib.h> // malloc, random, EXIT_SUCCESS
#define repeat_until(x) while (!(x))
// Constants:
int TARGET_HEIGHT, TARGET_WIDTH, TILE_DIMENSION, MIDDLE, WIDTH, HEIGHT, TETRIS_WIDTH, PACWIDTH, PACHEIGHT, MAZE_HEIGHT, LINE_WIDTH, LINEHEIGHT, TRUE, FALSE;
// Scalars:
int this_row, this_len, next_tile, first_tile, last_tile, dead_block, row, col, t, i, j, nibble, bit, k, iterate, paths, c, breakflag, left, right, returnval, f1;
// Const arrays:
#define TILEMAX 32
unsigned int tile[TILEMAX] = {
0,
142, 3208, 1100, 226, 46, 3140, 2188, 232, 79, 35976, 19524, 242,
47, 19524, 35016, 244, 1252, 1252, 78, 2248, 1220, 228, 140, 200,
196, 76, 14, 2184, 12, 136, 204,
};
#ifdef DEBUG
static char tc[]=" 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz~!@#$%^&*()_+`-={}|[]\\:\";'<>,./";
#endif /* DEBUG */
// Arrays:
long *tetris;
int *maze;
char *line;
#define FLOOR(x) (x) // a hint for Scratch translation
int pick_random_int_between(int low, int high) { // calls to this also map to a Scratch primitive
return low + random()%(high-low+1);
}
void place_tile(int tileno, int r, int c)
{
t = tile[tileno+1];
next_tile += 1;
row = 0;;
repeat_until (!(row < 4)) {
nibble = t % 16;
t = FLOOR(t / 16);
col = 0;
repeat_until (!(col < 4)) {
bit = (nibble > 7);
nibble = (nibble+nibble) % 16;
if (bit) tetris[((col+c)*TETRIS_WIDTH) + (row+r) + 1] = next_tile;
col += 1;
}
row += 1;
}
}
void can_place(int tileno, int r, int c)
{
t = tile[tileno+1];
returnval = TRUE;
row = 0;
repeat_until (!(row < 4 && returnval)) {
nibble = t % 16;
t = FLOOR(t / 16);
col = 0;
repeat_until (!(col < 4 && returnval)) {
bit = (nibble > 7);
nibble = (nibble+nibble) % 16;
if (bit &&
( (!(tetris[((col+c)*TETRIS_WIDTH) + (row+r) + 1] == 0))
|| ((row+r) > (HEIGHT-1))
|| ((c+col) > (WIDTH-1))
)
) {
returnval = FALSE;
}
col += 1;
}
row += 1;
}
}
void debug(void) {
#ifdef DEBUG
i = HEIGHT-1;
repeat_until (!(i+1 > 0)) {
j = 0;
repeat_until (!(j < WIDTH)) {
putchar(tc[1+tetris[((j)*TETRIS_WIDTH) + (i) + 1]]);
j += 1;
}
putchar('\n');
i -= 1;
}
putchar('\n');
#endif /* DEBUG */
}
void drop(int tileno, int r, int c)
{
can_place(tileno, r, c); f1 = returnval;
can_place(tileno, r-1, c);
if (f1 && (r==0 || !returnval)) {
place_tile(tileno, r, c);
} else {
if (r>0) drop(tileno, r-1, c);
}
}
void play_tetris(void) {
next_tile = 0; // used by 'place_tile' called from 'drop'
i = 0;
repeat_until (!(i < WIDTH)) {
j = 0;
repeat_until (!(j < HEIGHT+TILE_DIMENSION+1)) {
tetris[((i)*TETRIS_WIDTH) + (j) + 1] = 0;
j += 1;
}
i += 1;
}
drop(30, HEIGHT+1, FLOOR(WIDTH / 2)); // jail. Should also handle tunnels here.
i = 0;
repeat_until (!(i < 1000)) {
drop(pick_random_int_between(first_tile, last_tile-1), HEIGHT, pick_random_int_between(0,WIDTH-1));
i += 1;
}
}
void add(int this, int next) {
line[((this_row)*LINE_WIDTH) + (this_len) + 1]= this;
this_len += 1;
line[((this_row)*LINE_WIDTH) + (this_len) + 1]= next;
this_len += 1;
line[((this_row)*LINE_WIDTH) + (this_len) + 1]= '\0';
}
void init_row(void) {
this_row = -1;
this_len = 0;
}
void next_row(void) {
this_row += 1;
line[((this_row)*LINE_WIDTH) + (0) + 1] = ' ';
line[((this_row)*LINE_WIDTH) + (1) + 1] = '\0';
this_len = 1;
}
void convert_to_maze(void) {
row = 1;
j = 0;
repeat_until (!(j < WIDTH)) {
col = 1;
i = HEIGHT-1;
repeat_until (!(i+1 > 0)) {
maze[((col)*MAZE_HEIGHT ) + (row) + 1] = tetris[((j)*TETRIS_WIDTH) + (i) + 1];
if (maze[((col)*MAZE_HEIGHT ) + (row) + 1] == 0) maze[((col)*MAZE_HEIGHT ) + (row) + 1] = dead_block;
col += 1;
i -= 1;
}
i = 1;
repeat_until (!(i < HEIGHT)) {
maze[((col)*MAZE_HEIGHT ) + (row) + 1] = tetris[((j)*TETRIS_WIDTH) + (i) + 1];
if (maze[((col)*MAZE_HEIGHT ) + (row) + 1] == 0) maze[((col)*MAZE_HEIGHT ) + (row) + 1] = dead_block;
col += 1;
i += 1;
}
row += 1;
j += 1;
}
}
void debug_maze(void) {
#ifdef DEBUG
i = PACHEIGHT-2;
repeat_until (!(i > 0)) {
j = 1;
repeat_until (!(j < PACWIDTH-1)) {
putchar(tc[1+maze[((j)*MAZE_HEIGHT ) + (i) + 1]]);
j += 1;
}
putchar('\n');
i -= 1;
}
putchar('\n');
#endif /* DEBUG */
}
void cell(int above_below, int i, int j) {
// This is messy but I don't have the time to work it out properly and
// do a neater implementation. Sorry. There's a minor bug that is
// worked around by 'trim_junk()'
if (above_below < 0) {
if ((i+1 == PACWIDTH) && (j+1 == PACHEIGHT)) {
add('#', ' ');
} else {
if (!(maze[((i)*MAZE_HEIGHT ) + (j-1) + 1] == maze[((i)*MAZE_HEIGHT ) + (j) + 1])) {
if ((maze[((i)*MAZE_HEIGHT ) + (j-1) + 1] == 0) && (maze[((i)*MAZE_HEIGHT ) + (j) + 1] == dead_block)) {
if ((maze[((i)*MAZE_HEIGHT ) + (j) + 1] == dead_block) && (maze[((i-1)*MAZE_HEIGHT ) + (j) + 1] == 0)) {
add(' ', ' ');
} else {
add('#', ' ');
}
} else {
if ((maze[((i)*MAZE_HEIGHT ) + (j) + 1] == 0) && (maze[((i)*MAZE_HEIGHT ) + (j-1) + 1] == dead_block)) {
if ((maze[((i-1)*MAZE_HEIGHT ) + (j-1) + 1] == dead_block) || (maze[((i)*MAZE_HEIGHT ) + (j-1) + 1] == 0)) {
add(' ', ' ');
} else {
if ((maze[((i-1)*MAZE_HEIGHT ) + (j-1) + 1] == 0) && (maze[((i-1)*MAZE_HEIGHT ) + (j) + 1] == 0)) {
add(' ', ' ');
} else {
add('#', ' ');
}
}
} else {
add('#', '#');
}
}
} else {
if ((!(maze[((i-1)*MAZE_HEIGHT ) + (j) + 1] == maze[((i)*MAZE_HEIGHT ) + (j) + 1]))) {
if ((maze[((i)*MAZE_HEIGHT ) + (j) + 1] == dead_block) && (maze[((i-1)*MAZE_HEIGHT ) + (j) + 1] == 0)) {
add(' ', ' ');
} else {
add('#', ' ');
}
} else {
if ( (maze[((i)*MAZE_HEIGHT ) + (j) + 1] == maze[((i)*MAZE_HEIGHT ) + (j-1) + 1])
&& (!(maze[((i-1)*MAZE_HEIGHT ) + (j-1) + 1] == maze[((i)*MAZE_HEIGHT ) + (j) + 1]))) {
add('#', ' ');
} else {
add(' ', ' ');
}
}
}
}
} else if (above_below == 0) {
if (!(maze[((i-1)*MAZE_HEIGHT ) + (j) + 1] == maze[((i)*MAZE_HEIGHT ) + (j) + 1])) {
if ((maze[((i)*MAZE_HEIGHT ) + (j) + 1] == dead_block) && (maze[((i-1)*MAZE_HEIGHT ) + (j) + 1] == 0)) {
add(' ', ' ');
} else {
add('#', ' ');
}
} else {
add(' ', ' ');
}
}
}
void symmetry(int i) {
right = MIDDLE;
left = right;
repeat_until (!(left+1 > 0)) {
line[((i)*LINE_WIDTH) + (right) + 1] = line[((i)*LINE_WIDTH) + (left) + 1];
right += 1;
left -= 1;
}
line[((i)*LINE_WIDTH) + (right) + 1] = '\0'; // end of line
}
void gen_text_maze(void) {
init_row();
i = PACHEIGHT-1;
repeat_until (!(i > 0)) {
k = 0;
repeat_until (!(k+1 > -1)) {
next_row();
j = 1;
repeat_until (!(j < PACWIDTH)) {
cell(k,j,i);
j += 1;
}
k -= 1;
}
i -= 1;
}
i = 0;
repeat_until (!(i < TARGET_WIDTH+1)) {
line[((TARGET_HEIGHT+1)*LINE_WIDTH) + (i) + 1] = ' ';
i += 1;
}
line[((TARGET_HEIGHT+1)*LINE_WIDTH) + (TARGET_WIDTH+1) + 1] = '\0';
i = 0;
repeat_until (!(i < PACHEIGHT*2 )) {
symmetry(i);
i += 1;
}
}
void trim_central_column(void) {
// Trim any central '#'s that don't connect above or below (OK if connecting to left and right)
iterate = 0;
repeat_until (!(iterate < PACHEIGHT*2-1)) {
i = 1;
repeat_until (!(i < PACHEIGHT*2-1)) {
if ( line[((i)*LINE_WIDTH) + (MIDDLE) + 1] == '#'
&& line[((i)*LINE_WIDTH) + (MIDDLE-1) + 1] != '#'
&& ( (!(line[((i-1)*LINE_WIDTH) + (MIDDLE) + 1] == '#'))
|| (!(line[((i+1)*LINE_WIDTH) + (MIDDLE) + 1] == '#'))
)
) {
line[((i)*LINE_WIDTH) + (MIDDLE) + 1] = ' ';
}
i += 1;
}
iterate += 1;
}
}
void too_narrow(void) {
// Reject any that don't have >= 3 #'s on any col. Should we check rows as well?
i = 1;
paths = 4;
repeat_until (!(i < (PACHEIGHT-1)*2 && paths > 3)) {
#ifdef DEBUG
fprintf(stdout, "%03d: ", i);
#endif /* DEBUG */
paths = 0;
j = 1;
repeat_until (!(j < 1+TARGET_WIDTH)) {
#ifdef DEBUG
putchar(line[((i)*LINE_WIDTH) + (j) + 1]);
#endif /* DEBUG */
if (line[((i)*LINE_WIDTH) + (j) + 1] > ' ') paths += 1; // # or @ etc
j += 1;
}
#ifdef DEBUG
putchar('\n');
#endif /* DEBUG */
i += 1;
}
returnval = (paths < 4);
}
void wide_path(void) {
// Reject if there is a path all the way across
returnval = FALSE;
i = 1;
repeat_until (!(i < 1+TARGET_HEIGHT)) {
paths = 0;
j = 1;
repeat_until (!(j < 1+TARGET_WIDTH)) {
if (line[((i)*LINE_WIDTH) + (j) + 1] != ' ') paths += 1; // # or @ etc
j += 1;
}
if (paths == TARGET_WIDTH) returnval = TRUE;
i += 1;
}
if (!returnval) {
// or all the way from top to bottom
j = 1;
repeat_until (!(j < 1+TARGET_WIDTH)) {
paths = 0;
i = 1;
repeat_until (!(i < 1+TARGET_HEIGHT)) {
if (line[((i)*LINE_WIDTH) + (j) + 1] != ' ') paths += 1; // # or @ etc
i += 1;
}
if (paths == TARGET_HEIGHT) returnval = TRUE;
j += 1;
}
if (!returnval) {
// Reject if too many paths joining left to right
paths = 0;
i = 1;
repeat_until (!(i < TARGET_HEIGHT)) {
// check the logic of this, since I had got the 'too narrow' test wrong, and it's similar
if (line[((i)*LINE_WIDTH) + (MIDDLE) + 1] != ' ' && line[((i)*LINE_WIDTH) + (MIDDLE-1) + 1] != ' ') paths += 1; // # or @ etc
i += 1;
}
if (paths > 5) returnval = TRUE;
}
}
}
void small_loops(void) {
// Reject squares (small loops):
returnval = FALSE;
i = 2;
repeat_until (!(i < PACHEIGHT*2-2)) {
j = 1;
repeat_until (!(j < 1+TARGET_WIDTH)) {
if (line[((i)*LINE_WIDTH) + (j) + 1] == ' ') {
if (line[((i-1)*LINE_WIDTH) + (j-1) + 1] == '#') {
if (line[((i-1)*LINE_WIDTH) + (j) + 1] == '#') {
if (line[((i-1)*LINE_WIDTH) + (j+1) + 1] == '#') {
if (line[((i)*LINE_WIDTH) + (j-1) + 1] == '#') {
if (line[((i)*LINE_WIDTH) + (j+1) + 1] == '#') {
if (line[((i+1)*LINE_WIDTH) + (j-1) + 1] == '#') {
if (line[((i+1)*LINE_WIDTH) + (j) + 1] == '#') {
if (line[((i+1)*LINE_WIDTH) + (j+1) + 1] == '#') {
returnval = TRUE;
#ifdef DEBUG
//fprintf(stdout, "too small\n");
#endif
}
}
}
}
}
}
}
}
}
j += 1;
}
i += 1;
}
}
void trim_junk(void) {
i = 2;
repeat_until (!(i < PACHEIGHT*2-2)) {
j = 1;
repeat_until (!(j < 1+TARGET_WIDTH)) {
if (line[((i)*LINE_WIDTH) + (j) + 1] == '#') {
if (line[((i-1)*LINE_WIDTH) + (j-1) + 1] == ' ') {
if (line[((i-1)*LINE_WIDTH) + (j) + 1] == ' ') {
if (line[((i-1)*LINE_WIDTH) + (j+1) + 1] == ' ') {
if (line[((i)*LINE_WIDTH) + (j-1) + 1] == ' ') {
if (line[((i)*LINE_WIDTH) + (j+1) + 1] == ' ') {
if (line[((i+1)*LINE_WIDTH) + (j-1) + 1] == ' ') {
if (line[((i+1)*LINE_WIDTH) + (j) + 1] == ' ') {
if (line[((i+1)*LINE_WIDTH) + (j+1) + 1] == ' ') {
line[((i)*LINE_WIDTH) + (j) + 1] = ' ';
}
}
}
}
}
}
}
}
}
j += 1;
}
i += 1;
}
}
void bad_spawn_point(void) {
// While we're at it, set up the jail exit
breakflag = FALSE;
i = FLOOR(TARGET_HEIGHT / 2);
repeat_until (!((i > 0) && !breakflag)) {
if (line[((i)*LINE_WIDTH) + (MIDDLE) + 1] == '#') {
line[((i+1)*LINE_WIDTH) + (MIDDLE) + 1] = 'V'; // or maybe place this on the line above?
if (line[((i-1)*LINE_WIDTH) + (MIDDLE) + 1] == '#') returnval = TRUE;
breakflag = TRUE;
}
i -= 1;
}
if (!returnval) {
// must spawn below jail
breakflag = FALSE;
returnval = FALSE;
i = FLOOR(TARGET_HEIGHT / 2)+4;
repeat_until (!((i < (PACHEIGHT-1)*2) && !breakflag)) {
if (line[((i)*LINE_WIDTH) + (MIDDLE) + 1] == '#') {
line[((i)*LINE_WIDTH) + (MIDDLE) + 1] = '@';
if (line[((i-1)*LINE_WIDTH) + (MIDDLE) + 1] == '#') returnval = TRUE;
if (line[((i+1)*LINE_WIDTH) + (MIDDLE) + 1] == '#') returnval = TRUE;
breakflag = TRUE;
}
i += 1;
}
if (!returnval) {
// don't spawn on bottom line
returnval = TRUE;
i = i+1;
repeat_until (!(i < (PACHEIGHT-1)*2)) {
if (line[((i)*LINE_WIDTH) + (MIDDLE) + 1] == '#') returnval = FALSE;
i += 1;
}
}
}
}
void draw_maze(void) {
printf(" 01234567890123456789012345\n");
i = 0;
repeat_until (!(i < PACHEIGHT*2-1)) {
printf("%03d: |%s| ", i, &line[((i)*LINE_WIDTH) + (0) + 1]); // has to be handled differently in Scratch anyway
j = 0;
repeat_until (!(j < 1+TARGET_WIDTH)) {
c = line[((i)*LINE_WIDTH) + (j) + 1];
putchar(c);
if (c == ' ') {
putchar(c);
} else {
c = line[((i)*LINE_WIDTH) + (j+1) + 1];
if (c == ' ') {
putchar(c);
} else {
putchar('#'); // hack for spawn point
}
}
j += 1;
}
putchar('\n');
i += 1;
}
putchar('\n');
}
void try_one(void)
{
play_tetris();
debug();
convert_to_maze();
debug_maze();
gen_text_maze();
trim_junk();
trim_central_column();
}
int main(int argc, char **argv)
{
FALSE = (0==1);
TRUE = (0==0);
// Constants:
TARGET_HEIGHT = 19;
TARGET_WIDTH = 25;
TILE_DIMENSION = 4;
MIDDLE = FLOOR((TARGET_WIDTH+1) / 2);
WIDTH = FLOOR(TARGET_HEIGHT / 2);
HEIGHT = FLOOR(TARGET_WIDTH / 4);
TETRIS_WIDTH = (HEIGHT+TILE_DIMENSION+1);
PACWIDTH = (HEIGHT*2+1);
PACHEIGHT = (WIDTH+2);
MAZE_HEIGHT = (PACHEIGHT+TILE_DIMENSION);
LINE_WIDTH = (PACWIDTH*6+1);
LINEHEIGHT = (PACHEIGHT*2+1);
// Arrays:
tetris = (long *)malloc(sizeof(long) * (WIDTH * TETRIS_WIDTH + 1)); // 0,0 at bottom left, 8,19 at top right
maze = (int *)malloc(sizeof(int) * ((PACWIDTH+TILE_DIMENSION)*MAZE_HEIGHT + 1));
line = (char *)malloc(sizeof(char) * ((LINEHEIGHT * LINE_WIDTH) + 1)); // slop is to allow for stretched image
//#ifdef DEBUG
srand((unsigned int)time(NULL)); // New maze every second!
//#endif
first_tile = 0;
last_tile = TILEMAX;
dead_block = last_tile+1;
// Generating is cheap so we can afford to generate and reject any completed mazes that have problems
returnval = TRUE;
repeat_until (!(returnval)) { // while something is bad about this try
try_one();
too_narrow();
if (!returnval) {
wide_path();
if (!returnval) {
small_loops();
if (!returnval) {
bad_spawn_point();
}
}
}
}
draw_maze();
return (EXIT_SUCCESS);
}