|
=={{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 <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}}==
|