-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary-tree.c
64 lines (52 loc) · 1.59 KB
/
binary-tree.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// Copyright (C) 2023 <[email protected]>
//
// This program is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License version 2 as published by
// the Free Software Foundation.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
// more details.
//
// You should have received a copy of the GNU General Public License along
// with this program; if not, write to the Free Software Foundation, Inc., 59
// Temple Place, Suite 330, Boston, MA 02111-1307 USA
#include <stdlib.h>
#include "maze.h"
#define LEN(arr) (sizeof(arr)/sizeof(arr[0]))
static int
random_comparer(const void *p0, const void *p1)
{
(void) p0; (void) p1;
return rand() % 2 == 0 ? -1 : 1;
}
static void
shuffle(void *arr, size_t n, size_t size)
{
qsort(arr, n, size, random_comparer);
}
extern void
maze_binary_tree(maze_t *m, int w, int h, int seed)
{
size_t i;
int x, y, nx, ny;
maze_wall_t *home, bias[2];
bias[0] = MAZE_WALL_EAST;
bias[1] = MAZE_WALL_NORTH;
maze_init(m, "binary_tree", w, h, seed);
for (y = 0; y < m->height; ++y) {
for (x = 0; x < m->width; ++x) {
shuffle(bias, LEN(bias), sizeof(bias[0]));
home = maze_get(m, x, y);
for (i = 0; i < LEN(bias); ++i) {
nx = x + MAZE_WALL_OFFSET_X(bias[i]);
ny = y + MAZE_WALL_OFFSET_Y(bias[i]);
if ((*home & bias[i]) && maze_get(m, nx, ny)) {
maze_remove_wall(m, x, y, bias[i]);
break;
}
}
}
}
}