-
Notifications
You must be signed in to change notification settings - Fork 0
/
recursive-backtracking.c
66 lines (56 loc) · 1.7 KB
/
recursive-backtracking.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
65
66
// Copyright (C) 2023 <alpheratz99@protonmail.com>
//
// 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 <string.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);
}
static void
backtrack(maze_t *m, int x, int y)
{
size_t i;
int nx, ny;
maze_wall_t *nbor, walls[4];
walls[0] = MAZE_WALL_NORTH;
walls[1] = MAZE_WALL_WEST;
walls[2] = MAZE_WALL_SOUTH;
walls[3] = MAZE_WALL_EAST;
shuffle(walls, LEN(walls), sizeof(walls[0]));
for (i = 0; i < LEN(walls); ++i) {
nx = x + MAZE_WALL_OFFSET_X(walls[i]);
ny = y + MAZE_WALL_OFFSET_Y(walls[i]);
if ((nbor = maze_get(m, nx, ny))
&& *nbor == MAZE_WALL_ALL) {
maze_remove_wall(m, x, y, walls[i]);
backtrack(m, nx, ny);
}
}
}
extern void
maze_recursive_backtracking(maze_t *m, int w, int h, int seed)
{
maze_init(m, "recursive_backtracking", w, h, seed);
backtrack(m, rand()%m->width, rand()%m->height);
}