Maze generation: Difference between revisions

Content added Content deleted
(→‎{{header|C}}: reimplemented)
(→‎{{header|C}}: cleanup)
Line 303: Line 303:
enum { U = 1, D = 2, L = 4, R = 8, WALL = 16, V = 32 };
enum { U = 1, D = 2, L = 4, R = 8, WALL = 16, V = 32 };


wchar_t *grids = L""
wchar_t *grids = L" "
" "
" ╵╷│╼┘┐┤╺└┌├─┴┬┼"
" ╵╷│╼┘┐┤╺└┌├─┴┬┼"
" ┆┆┆┄╯╮ ┄╰╭ ┄ "
" ┆┆┆┄╯╮ ┄╰╭ ┄ "
" ┆ ╯╮ ╰╭ ┄ "
" ┆ ╯╮ ╰╭ ┄ ";
;


int irand(int n)
int irand(int n)
Line 325: Line 323:
x[i] = x[i - 1] + w;
x[i] = x[i - 1] + w;
return x;
return x;
⚫
}

⚫
cell ** new_maze(int w, int h)
⚫
{
⚫
int i, j;
⚫
cell **m = array2(2 * w + 1, 2 * h + 1);
⚫
FOR(i, 2*h) FOR(j, 2*w) m[i][j] = U|D|L|R|WALL;

⚫
FOR(i, h) FOR(j, w) {
⚫
if (i && j) m[2*i - 1][2*j - 1] = 0;
⚫
if (i) m[2*i - 1][2*j] = U|D|WALL;
⚫
if (j) m[2*i][2*j - 1] = L|R|WALL;
⚫
}
⚫
FOR(i, 2*h) m[i][0] &= ~L, m[i][2*w] &= ~R;
⚫
FOR(j, 2*w) m[0][j] &= ~U, m[2*h][j] &= ~D;

⚫
return m;
}
}


Line 353: Line 334:
if (c == ' ' && DOUBLE_SPACE) c = L'　';
if (c == ' ' && DOUBLE_SPACE) c = L'　';
color = m[i][j] & V;
color = m[i][j] & V;

printf("%s%lc%s", color ? "\033[31m":"", c,
printf("%s%lc%s", color ? "\033[31m":"", c,
color ? "\033[m":"");
color ? "\033[m":"");
Line 384: Line 366:
continue;
continue;


visited = j;
/* tear down the wall */
/* tear down the wall */
switch(d[i]) {
switch(d[i]) {
Line 404: Line 385:
break;
break;
}
}

if (visited + 1 == w*h) break;
if ((visited = j) + 1 == w*h) break;
}
}
return visited;
return visited;
⚫
}

⚫
cell ** new_maze(int w, int h)
⚫
{
⚫
int i, j;
⚫
cell **m = array2(2 * w + 1, 2 * h + 1);
⚫
FOR(i, 2*h) FOR(j, 2*w) m[i][j] = U|D|L|R|WALL;

⚫
FOR(i, h) FOR(j, w) {
⚫
if (i && j) m[2*i-1][2*j-1] = 0;
⚫
if (i) m[2*i-1][2*j] = U|D|WALL;
⚫
if (j) m[2*i][2*j-1] = L|R|WALL;
⚫
}
⚫
FOR(i, 2*h) m[i][0] &= ~L, m[i][2*w] &= ~R;
⚫
FOR(j, 2*w) m[0][j] &= ~U, m[2*h][j] &= ~D;

⚫
build(m, 1, 1, w, h, 0);
⚫
FOR(i, 2*h) FOR(j, 2*w) m[i][j] &= ~V;

⚫
return m;
}
}


Line 420: Line 422:
FOR(i, 4) {
FOR(i, 4) {
switch(i) {
switch(i) {
case 0: if (x <= 1 || (m[y][x-1] & (U|D))) continue; break;
case 0: if ( x <= 1 || (m[y][x-1] & (U|D))) continue;
break;
⚫
case 1: if (x+1 >= 2*w || (m[y][x+1] & (U|D))) continue; break;
case 2: if (y <= 1 || (m[y-1][x] & (L|R))) continue; break;
case 1: if (x+1 >= 2*w || (m[y][x+1] & (U|D))) continue;
break;
case 3: if (y+1 >= 2*h || (m[y+1][x] & (L|R))) continue; break;
case 2: if ( y <= 1 || (m[y-1][x] & (L|R))) continue;
break;
⚫
case 3: if (y+1 >= 2*h || (m[y+1][x] & (L|R))) continue;
break;
case 4: m[y][x] &= ~V; return 0;
case 4: m[y][x] &= ~V; return 0;
}
}
Line 432: Line 438:


switch(i) {
switch(i) {
case 0: m[y][ x ] |= V|L;
case 0: m[y][ x ] |= V|L; m[y][x-1] |= V|L|R; m[y][x-2] |= V|R;
m[y][x-1] |= V|L|R;
m[y][x-2] |= V|R;
break;
break;
case 1: m[y][ x ] |= V|R;
case 1: m[y][ x ] |= V|R; m[y][x+1] |= V|L|R; m[y][x+2] |= V|L;
m[y][x+1] |= V|L|R;
m[y][x+2] |= V|L;
break;
break;
case 2: m[ y ][x] |= V|U;
case 2: m[ y ][x] |= V|U; m[y-1][x] |= V|D|U; m[y-2][x] |= V|D;
m[y-1][x] |= V|D|U;
m[y-2][x] |= V|D;
break;
break;
case 3: m[ y ][x] |= V|D;
case 3: m[ y ][x] |= V|D; m[y+1][x] |= V|D|U; m[y+2][x] |= V|U;
m[y+1][x] |= V|D|U;
m[y+2][x] |= V|U;
break;
break;
}
}
Line 455: Line 453:
{
{
setlocale(LC_CTYPE, "");
setlocale(LC_CTYPE, "");
srand(time(0));


int w = atoi(v[1]), h = atoi(v[2]), i, j;
int w = atoi(v[1]), h = atoi(v[2]);
cell **m = new_maze(w, h);
cell **m = new_maze(w, h);
⚫
build(m, 1, 1, w, h, 0);


⚫
FOR(i, 2*h) FOR(j, 2*w) m[i][j] &= ~V;
solve(m, w, h, 1, 1, 2*w - 1, 2 * h - 1);
solve(m, w, h, 1, 1, 2*w - 1, 2 * h - 1);


show_maze(m, w, h);
show_maze(m, w, h);


/* free(m) */
return 0;
return 0;
}</lang>Running:<lang>┌─────┬───┬─────┬───────┬─────────┐
}</lang>output<lang>% ./a.out 17 8
│┄┄┄┄╮│╭┄╮│　　╭┄╮│╭┄┄┄┄┄╮│　　　　╭┄┄┄╮│
┌─┬───────┬─────┬─────┬───┬───────┐
├───╼┆│┆╷┆├─╼┆╷┆│┆┌─┬─╼┆│　╺─┐┆┌─┐┆│
⚫
│┆│　　╭┄┄┄╮│　　╭┄╮│　　　　　│　　　│　　　　　　　│
│╭┄┄┄╯│┆│┆│╭┄╯│┆│┆│　│╭┄╯│　　　│┆│　│┆│
│┆│　╷┆╺─┐┆└─╼┆╷┆└───┐　│　╷　│　┌─┬─╼　│
│┆┌───┘┆│┆│┆┌─┘┆│┆│　│┆┌─┘　┌─┘┆│　╵┆│
│┆│　│╰┄╮│╰┄┄┄╯│╰┄┄┄╮│　│　│　│　│　│　　　│
│┆│╭┄┄┄╯│┆│┆│╭┄╯│┆│　│┆│　　　│╭┄╯│╭┄╯│
│┆└─┴─╼┆├─────┴───┐┆│　╵　│　╵　╵　│　╺─┤
│┆╵┆┌───┤┆╵┆│┆╺─┘┆│　│┆└───┤┆┌─┘┆╺─┤
⚫
│╰┄┄┄┄┄╯│　　　　　　　　　│┆│　　　│　　　　　│　　　│
│╰┄╯│　　　│╰┄╯│╰┄┄┄╯│　│╰┄┄┄╮│┆│　　╰┄╮│
├─────┬─┘　╺─────┐　│┆├───┴─┬───┼─╼　│
├───┘　╷　├───┼─────┤　└───┐┆│┆└─┬─┐┆│
│　　　　　│　　　　　　　　　│　│┆│╭┄┄┄╮│　　　│　　　│
├─╼　╷　│　╺─────┐　└─┤┆│┆┌─┐┆│　╷　│　╷　│
│　　　　　│　│　　　│　　　　　│　　　　　│┆│╰┄╮│　│┆│
│　┌───┘　└─╼　│　╺─┐　╵　┌─╼　│┆└─┐┆│　╵┆│
│　　　│　│　　　　　　　│　　　│┆│┆│　│┆│　│　│　│　│
│　╺─┴─┴─┐　┌───┴─╼　│┆╵┆│　╵┆│　│　╵　│　│
│　│　　　　　　　　　│　　　│　　　│　　　│╰┄╮│┆│╭┄╯│
│　├───┐　┌───┴─╼　├───┘　╷　└─┐┆╵┆│┆┌─┤
│　　　　　　　│　│　　　　　　　│╰┄╯│╭┄╯│　│　　　│　│
⚫
│　│　　　│　│　　　　　　　│　　　　　│　　　│╰┄╯│┆│　│
│　╺─┬─┐　╵　│　╺─────┴───┤┆╺─┤　└───┴─┤
│　╵　╷　└─┘　╺─────┤　╺───┴───┴───┘┆╵　│
│　　　│　│　　　│　　　　　　　　　　　│╰┄╮│　　　　　　　│
⚫
│　　　│　　　　　　　　　　　│　　　　　　　　　　　　　　╰┄┄│
├─╼　╵　└───┴─────────┐　└─╼┆└─────╼　│
└───┴───────────┴─────────────────┘</lang>
│　　　　　　　　　　　　　　　　　　　│　　　　╰┄┄┄┄┄┄┄┄│
└───────────────────┴─────────────┘</lang>


=={{header|D}}==
=={{header|D}}==
Retrieved from "https://rosettacode.org/wiki/Maze_generation"