Rosetta Code

Maze generation: Difference between revisions

Page Discussion

Maze generation (view source)

Revision as of 03:07, 23 August 2011

269 bytes added ,  12 years ago
→‎{{header|C}}: refactor
(Added second Python version)
(→‎{{header|C}}: refactor)
Line 300:
 
#define DOUBLE_SPACE 1
 
typedef unsigned char cell;
enum { U = 1, D = 2, L = 4, R = 8, WALLV = 16, V = 32 };
 
wchar_t *gridsglyph[] = L" "
L"　│││─┘┐┤─└┌├─┴┬┼　┆┆┆┄╯╮ ┄╰╭ ┄";
" ┴┬│┤┘┐┤├└┌├─┴┬┼"
" ┆┆┆┄╯╮ ┄╰╭ ┄ "
" ┆ ╯╮ ╰╭ ┄ ";
 
int irand(int n)
Line 316 ⟶ 315:
 
#define FOR(i, h) for(i = 0; i <= h; i++)
cell **array2grid(int w, int h)
{
int i, j;
cell **x = malloc(sizeof(cell*) * h + h * w);
x[0] = (cell*)(x + h);
FOR(i, h - 1) x[i + 1] = x[i] + w;
FOR(i, h-1) FOR(j, w-1) x[i][j] = 0;
return x;
}
 
voidint show_mazerand_neighbor(cell **mc, int w, int h, int x, int y, int *x2, int *y2) {
int d, ofx[] = {1, -1, 0, 0}, ofy[] = {0, 0, -1, 1};
{
int i, j, colorcnt = 0;
FOR(d, 3) {
wchar_t c;
j = x + ofx[d], i = y + ofy[d];
FOR(i, 2 * h) {
if (j < 0 || j >= w || i < 0 || i >= h || (c[i][j] & V))
FOR(j, 2 * w) {
continue;
c = grids[ m[i][j] ];
if (c!irand(++cnt)) *x2 == ' ' && DOUBLE_SPACE)j, c*y2 = L'　'i;
}
color = m[i][j] & V;
return cnt;
}
 
int build(cell **c, int w, int h, int x, int y, int avail) {
printf("%s%lc%s", color ? "\033[31m":"", c,
int x2, y2;
color ? "\033[m":"");
c[y][x] |= V;
}
 
putchar('\n');
while (avail) {
if (!rand_neighbor(c, w, h, x, y, &x2, &y2)) break;
if (x2 > x) c[y][x] |= R, c[y][x2] |= L; else
if (x2 < x) c[y][x] |= L, c[y][x2] |= R; else
if (y2 > y) c[y][x] |= D, c[y2][x] |= U; else
if (y2 < y) c[y][x] |= U, c[y2][x] |= D;
 
avail = build(c, w, h, x2, y2, avail - 1);
}
 
return avail;
}
 
voidcell** shufflemake_maze(int *xw, int lh)
{
cell **cells = grid(w, h);
int t, i;
build(cells, w, h, 0, 0, w * h - 1);
while (--l)
return cells;
if ((i = irand(l+1)) != l)
t = x[l], x[l] = x[i], x[i] = t;
}
 
int dirs[][2]walk(cell =**c, {cell {-2**s, 0},int {2w, 0}int h, {0int x, -2}int y, {0int x2, 2}int };y2)
int build(cell **m, int x, int y, int w, int h, int visited)
{
int i, j, d, dirs[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
if (x < 0 || x >= 2*w || y < 0 || y >= 2*h || (m[y][x] & V))
return 0;
 
ms[y][x] |= V;
if (y == y2 && x == x2) return 1;
 
FOR(d, 3) {
int i, j, d[] = {0, 1, 2, 3};
if (!(c[y][x] & (1 << d))) continue;
shuffle(d, 4);
i = y + dirs[d][1];
j = x + dirs[d][0];
 
for if (i =< 0; || i >= h || j < 4;0 i++|| j >= w) {continue;
if (!(j = build(m, x + dirs[ds[i]][0j], y& +V) dirs[d[i]][1],continue;
w, h, visited + 1)))
continue;
 
if (walk(c, s, w, h, j, i, x2, y2)) break;
/* tear down the wall */
}
switch(d[i]) {
case 0: m[y-1][x-1] &= ~D;
m[ y ][x-1] &= ~(U|D);
m[y+1][x-1] &= ~U;
break;
case 1: m[y-1][x+1] &= ~D;
m[ y ][x+1] &= ~(U|D);
m[y+1][x+1] &= ~U;
break;
case 2: m[y-1][x-1] &= ~R;
m[y-1][ x ] &= ~(L|R);
m[y-1][x+1] &= ~L;
break;
case 3: m[y+1][x-1] &= ~R;
m[y+1][ x ] &= ~(L|R);
m[y+1][x+1] &= ~L;
break;
}
 
if ((visitedd <= j) + 1 == w*h3) break;{
s[y][x] |= (1 << d);
if (d <= 1) s[i][j] |= 1 << (1 - d);
else s[i][j] |= 1 << (5 - d);
return 1;
}
return visited0;
}
 
void show_maze(cell **c, cell **s, new_maze(int w, int h)
{
int i, j, x, y;
cell **mtile = array2grid(2 * w + 1, 2 * h + 1);
FOR(i, 2*h) FOR(j, 2*w) m[i][j] = U|D|L|R|WALL;
 
FOR(i, 2*h) FOR(j, 2*w) {
if (tile[i][j] &&= ((j&1) m[2*? 0 : (U|D)) | ((i-&1][2*j-1]) =? 0 : (L|R));
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;
 
buildFOR(mi, 1,2*h) 1tile[i][0] &= ~L, tile[i][2*w,] h,&= 0)~R;
FOR(ij, 2*hw) FOR(tile[0][j] &= ~U, tile[2*w) m[ih][j] &= ~VD;
 
FOR(i, h-1) FOR(j, w-1) {
return m;
y = 2 * i + 1, x = 2 * j + 1;
}
 
int solve(cell **m, int w, int h, int x, int y, int ex, int ey)
{
int i;
if (x < 0 || x >= 2*w || y < 0 || y >= 2*h || (m[y][x] & V))
return 0;
 
m if (c[yi][xj] |=& R) V;{
tile[y-1][x+1] &= ~D;
if (x == ex && y == ey) return 1;
tile[ y ][x+1] = 0;
 
tile[y+1][x+1] &= ~U;
FOR(i, 4) {
switch(i) {
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 3: if (y+1 >= 2*h || (m[y+1][x] & (L|R))) continue;
break;
case 4: m[y][x] &= ~V; return 0;
}
if (c[i][j] & D) {
tile[y+1][x-1] &= ~R;
tile[y+1][ x ] = 0;
tile[y+1][x+1] &= ~L;
}
if(!s) continue;
 
if (solve(m, w, h, x + dirstile[iy][0x], y += dirss[i][1j], ex, ey));
if (s[i][j] & U) tile[y-1][ x ] |= V|D;
break;
if (s[i][j] & D) tile[y+1][ x ] |= V|U;
if (s[i][j] & L) tile[ y ][x-1] |= V|R;
if (s[i][j] & R) tile[ y ][x+1] |= V|L;
}
 
switchFOR(i, 2*h) {
FOR(j, 2*w)
case 0: m[y][ x ] |= V|L; m[y][x-1] |= V|L|R; m[y][x-2] |= V|R;
printf((tile[i][j] & V) ? "\033[31m%lc\033[m" : "%lc",
break;
glyph[ tile[i][j] ]);
case 1: m[y][ x ] |= V|R; m[y][x+1] |= V|L|R; m[y][x+2] |= V|L;
putchar('\n');
break;
case 2: m[ y ][x] |= V|U; m[y-1][x] |= V|D|U; m[y-2][x] |= V|D;
break;
case 3: m[ y ][x] |= V|D; m[y+1][x] |= V|D|U; m[y+2][x] |= V|U;
break;
}
free(tile);
return 1;
}
 
int main(int c, char *v[])
{
cell **solu, **maze;
int w = 0, h = 0;
 
setlocale(LC_CTYPE, "");
if (!DOUBLE_SPACE) glyph[0] = glyph[16] = L' ';
 
int w = 0, h = 0;
if (c > 2) w = atoi(v[1]), h = atoi(v[2]);
if (w <= 0) w = 1116;
if (h <= 0) h = 8;
 
cell **mmaze = new_mazemake_maze(w, h);
solve(m,solu w,= h, 1, 1, 2*grid(w - 1, 2 * h - 1);
show_mazewalk(mmaze, solu, w, h, 0, 0, w-1, h-1);
show_maze(maze, solu, w, h);
 
/* free(mmaze); free(solu); */
return 0;
}</lang>output<lang>┌─┬───────┬───────┬─────────────┐
}</lang>sample output:<lang>┌─┬─────┬─────┬───────┐
│┆││┆│╭┄┄┄┄┄╮│　　╭┄╮│　　　　　│　　　　　　　　　　　　　│
│┆└─┤┆┬┆││┆│┆────┐┆└───┐　┬│　┬　┴│　┌───┐　│──────┤
│╰┄┄┄╯│┆││┆│╰┄┄┄╮│╰┄┄┄╮│　│　│　│　　　│　　　│　　　　│
│┆└─┐　│┆└───┐┆└─┤　│　│　│　└─────┐　│
├─────┤┆└─┤　├───┘　┬　└─┤
││╰┄╮│　│╰┄┄┄╮│╰┄╮│　│　│　│　│╰┄╮│　│　　　　　│　　　│
├─┐┆│　└─┬──┆├─┐┆│　│　│　│　│　┌───┤　│
│　┌─┤　└─┐┆│　┴　┌───┼─┤　│
│　│　│┆│　　　│╭┄╯│　│┆│　　　│╭┄╮│╭┄╮││　│　│　│╭┄╮│　│
│　│┆├──　│┆──┤　│┆│　──┴─┘　├─┘┆│┆│　│
│　└─┬───┤┆│　├─┤┆┬┆┴┆┬┆│
│　│┆│　　　│╰┄╮│╭┄╯│　　　　　　　│╭┄╯│╰┄╮│
│　　　│╭┄╮│┆│　　　│┆│╰┄╯│┆│
│　│┆└─┬─┴──┆│┆┌─┴───┬───┘┆┌─┴──┆│
├─┤　│┆┬┆┴┆├─┤　│┆└───┤┆│
│　│╰┄╮│╭┄┄┄╯│┆│　　╭┄╮│╭┄┄┄╯│╭┄┄┄╯│
│　　　│┆│╰┄╯│　　　│╰┄┄┄╮│┆│
│　└─┐┆│┆┌───┤┆└─┐┆│┆│┆────┤┆┌───┤
│　┬　│┆└─┬─┴─┬─┴───┤┆│┆│
│　　　│╰┄╯│　　　│╰┄╮│┆│┆│╰┄┄┄╮│┆│　　　│
│　│　│╰┄╮│╭┄╮│╭┄┄┄┄┄╯│┆│
│　│　└───┘　│　└──┆│┆│┆└────┆│┆└──　│
│　└─┴─┤┆┴┆┬┆┴┆┌─────┘┆│
│　│　　　　　╰┄╯│╰┄╯│　　│　　　　┆│╰┄╯│╰┄┄┄┄┄╯│╰┄┄┄┄│
└─┴───────┴───────┴───────┴─────┘</lang>
└─────────┴───┴───────┘</lang>
 
=={{header|D}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/167422"