Maze generation: Difference between revisions
Content added Content deleted
(Improved D version) |
(→{{header|C}}: replaced long and unreadable code.) |
||
Line 294: | Line 294: | ||
=={{header|C}}== |
=={{header|C}}== |
||
C99. |
|||
{{libheader|GLib|2.26}} |
|||
<lang C>#include <stdio.h> |
|||
{{trans|Python}} |
|||
(The code has no proper error handling) |
|||
<lang c>#include <stdio.h> |
|||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <stdbool.h> |
|||
#include <time.h> |
|||
enum { NORTH, EAST, WEST, SOUTH, |
|||
#include <glib.h> |
|||
USED = 1 << 4 |
|||
}; |
|||
typedef struct cell_t *cell; |
|||
struct cell_t { |
|||
int conn; /* or'd flags: 4 directions, and USED */ |
|||
cell c[4]; /* direction to neighbors */ |
|||
}; |
|||
#define can_go(c, i) (c->c[i] && !(c->c[i]->conn & USED)) |
|||
const int w = 11; |
|||
void walk(cell c) |
|||
const int h = 8; |
|||
size_t randrange(int max) |
|||
{ |
{ |
||
c->conn |= USED; |
|||
return rand() % (max + 1); // basically the wrong (and lazy) way |
|||
while (1) { |
|||
} |
|||
for (int i = 0, a = 0; i < 4; i++) { |
|||
a += can_go(c, i); |
|||
if (i == 3 && !a) return; |
|||
} |
|||
int d; |
|||
do { d = rand() % 4; } while (!can_go(c, d)); |
|||
c->conn |= (1 << d); |
|||
int choice(GArray *a) |
|||
c->c[d]->conn |= (1 << (3 - d)); |
|||
{ |
|||
int i = randrange(a->len > 0 ? a->len - 1 : 0); |
|||
int v = g_array_index(a, int, i); |
|||
return v; |
|||
} |
|||
#define BOUND(A, V, E) do { \ |
|||
if ( (V) < 0 ) V = cells->len + V; \ |
|||
A = E; \ |
|||
} while(0); |
|||
#define PREP(T, V) do { \ |
|||
if (T == NULL) T = malloc(sizeof(int)); \ |
|||
if ( (V) < 0 ) *T = (cells->len + (V)); \ |
|||
else *T = V; \ |
|||
} while(0); |
|||
GArray *get_candidate_neighbors(GPtrArray *cells, int i, int width, int height) |
|||
{ |
|||
int n, s, e, w, *t = NULL; |
|||
GArray *neighbors = g_array_new(FALSE, TRUE, sizeof(int)); |
|||
GArray *an, *as, *ae, *aw; |
|||
if (neighbors == NULL) return NULL; |
|||
n = i - width; |
|||
s = i + width; |
|||
e = i + 1; |
|||
w = i - 1; |
|||
if (n >= 0) { |
|||
BOUND(an, n, g_ptr_array_index(cells, n)); |
|||
if ( an == NULL || an->len == 0 ) { |
|||
PREP(t, n); |
|||
neighbors = g_array_append_vals(neighbors, t, 1); |
|||
} |
|||
} |
|||
if (s < (width * height) ) { |
|||
BOUND(as, s, g_ptr_array_index(cells, s)); |
|||
if ( as == NULL || as->len == 0 ) { |
|||
PREP(t, s); |
|||
neighbors = g_array_append_vals(neighbors, t, 1); |
|||
} |
|||
} |
|||
if ( (e/width) == (i/width) ) { |
|||
BOUND(ae, e, g_ptr_array_index(cells, e)); |
|||
if ( ae == NULL || ae->len == 0 ) { |
|||
PREP(t, e); |
|||
neighbors = g_array_append_vals(neighbors, t, 1); |
|||
} |
|||
} |
|||
if ( (w/width) == (i/width) ) { |
|||
BOUND(aw, w, g_ptr_array_index(cells, w)); |
|||
if ( aw == NULL || aw->len == 0 ) { |
|||
PREP(t, w); |
|||
neighbors = g_array_append_vals(neighbors, t, 1); |
|||
} |
|||
} |
|||
free(t); |
|||
walk(c->c[d]); |
|||
return neighbors; |
|||
} |
|||
} |
} |
||
#define for_i for(int i = 0; i <= y; i++) |
|||
// if version libglib < 2.28 |
|||
#define for_j for(int j = 0; j <= x; j++) |
|||
void lfunc(gpointer d, gpointer ff) |
|||
#define goes(dir) (cells[i][j].conn & (1 << dir)) |
|||
void make_maze(int y, int x) |
|||
{ |
{ |
||
struct cell_t cells[y][x]; |
|||
void (*ffunc)(gpointer) = ff; |
|||
x--; y--; |
|||
ffunc(d); |
|||
} |
|||
for_i for_j { |
|||
void g_list_free_full(GList *list, void (*ffunc)(gpointer)) |
|||
cell c = &cells[i][j]; |
|||
{ |
|||
c->conn = 0; |
|||
g_list_foreach(list, lfunc, (gpointer)ffunc); |
|||
c->c[NORTH] = i > 0 ? &cells[i - 1][ j ] : 0; |
|||
g_list_free(list); |
|||
c->c[SOUTH] = i < y ? &cells[i + 1][ j ] : 0; |
|||
return; |
|||
c->c[WEST] = j > 0 ? &cells[ i ][j - 1] : 0; |
|||
} |
|||
c->c[EAST] = j < x ? &cells[ i ][j + 1] : 0; |
|||
// ---------- |
|||
} |
|||
walk(&cells[0][0]); |
|||
for_j { printf("+---"); } |
|||
int *dress_int(int v) |
|||
printf("+\n"); |
|||
{ |
|||
int *r = malloc(sizeof(int)); |
|||
if (r != NULL) *r = v; |
|||
return r; |
|||
} |
|||
for_i { |
|||
GPtrArray *makeMaze(const int width, const int height) |
|||
for_j { printf(j > 0 && goes(WEST) ? " " : "| "); } |
|||
{ |
|||
printf("|\n"); |
|||
GPtrArray *cells; |
|||
int i; |
|||
int total_cells = width * height; |
|||
cells = g_ptr_array_new(); if (cells == NULL) return NULL; |
|||
for(i = 0; i < total_cells; i++) { |
|||
GArray *o = g_array_new(FALSE, TRUE, sizeof(int)); if (o == NULL) return NULL; |
|||
g_ptr_array_add(cells, o); |
|||
} |
|||
int cur_cell = randrange(total_cells); |
|||
int visited = 1; |
|||
GList *cellstack = NULL; |
|||
while(visited < total_cells) { |
|||
GArray *neighbors = get_candidate_neighbors(cells, cur_cell, width, height); |
|||
if (neighbors->len > 0) { |
|||
int new = choice(neighbors); |
|||
g_array_append_val(g_ptr_array_index(cells, cur_cell), new); |
|||
g_array_append_val(g_ptr_array_index(cells, new), cur_cell); |
|||
cellstack = g_list_prepend(cellstack, dress_int(cur_cell)); |
|||
cur_cell = new; |
|||
visited++; |
|||
} else { |
|||
gpointer d = cellstack->data; |
|||
if (d != NULL) { |
|||
cur_cell = *((int *)d); |
|||
free(d); |
|||
} |
|||
cellstack = g_list_delete_link(cellstack, cellstack); |
|||
} |
|||
} |
|||
g_list_free_full(cellstack, free); |
|||
for_j { printf(i < y && goes(SOUTH) ? "+ " : "+---"); } |
|||
return cells; |
|||
printf("+\n"); |
|||
} |
|||
} |
} |
||
int main() |
|||
bool isin(int v, GArray *a) |
|||
{ |
{ |
||
//srand(time(0)); |
|||
int i; |
|||
make_maze(8, 10); |
|||
}</lang>Output<lang>+---+---+---+---+---+---+---+---+---+---+ |
|||
if (a == NULL) return false; |
|||
| | | |
|||
+ +---+ + +---+---+---+---+---+ + |
|||
for(i = 0; i < a->len; i++) { |
|||
| | | | | | | |
|||
if (g_array_index(a, int, i) == v) return true; |
|||
+---+ +---+ +---+ + + + + + |
|||
} |
|||
| | | | | | | | |
|||
return false; |
|||
+ +---+ +---+ + + +---+ + + |
|||
} |
|||
| | | | | | | |
|||
+ +---+---+ +---+---+---+ + + + |
|||
void showMaze(GPtrArray *cells, int width, int height) |
|||
| | | | | | | |
|||
{ |
|||
+ + + +---+ + +---+---+ + + |
|||
int i; |
|||
| | | | | | | |
|||
+ + +---+ +---+ + +---+---+ + |
|||
GString *s1 = g_string_new(NULL); |
|||
| | | | | | | |
|||
GString *s2 = g_string_new(NULL); |
|||
+ +---+---+---+ + +---+ +---+---+ |
|||
| | | |
|||
for(i = 0; i < (width*height); i++) { |
|||
+---+---+---+---+---+---+---+---+---+---+</lang> |
|||
if ( i % width == 0 ) { |
|||
puts(s1->str); |
|||
puts(s2->str); |
|||
s1 = g_string_assign(s1, "+"); |
|||
s2 = g_string_assign(s2, "|"); |
|||
} |
|||
if ( isin(i - width, g_ptr_array_index(cells, i)) ) { |
|||
s1 = g_string_append(s1, " +"); |
|||
} else s1 = g_string_append(s1, "--+"); |
|||
if ( isin(i + 1, g_ptr_array_index(cells, i)) ) { |
|||
s2 = g_string_append(s2, " "); |
|||
} else s2 = g_string_append(s2, " |"); |
|||
} |
|||
printf("+"); |
|||
for(i = 0; i < width; i++) printf("--+"); |
|||
printf("\n"); |
|||
g_string_free(s1, TRUE); |
|||
g_string_free(s2, TRUE); |
|||
} |
|||
void free_maze_slice(gpointer a, gpointer nil) |
|||
{ |
|||
GArray *aa = (GArray *)a; |
|||
if (a != NULL) g_array_free(aa, TRUE); |
|||
} |
|||
int main(int argc, char **argv) |
|||
{ |
|||
GPtrArray *maze; |
|||
srand(time(NULL)); |
|||
maze = makeMaze(w, h); |
|||
showMaze(maze, w, h); |
|||
g_ptr_array_foreach(maze, free_maze_slice, NULL); |
|||
return EXIT_SUCCESS; |
|||
}</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |