maze: New functions

3 files changed, 226 insertions, 1 deletions

diff --git a/src/local.mk b/src/local.mk
index 84fefc6..4414cdc 100644
--- a/src/local.mk
+++ b/src/local.mk
@@ -1,3 +1,4 @@
 mazefight_SOURCES += \
 	%reldir%/defs.h \
-	%reldir%/main.c
+	%reldir%/main.c \
+	%reldir%/maze.c
diff --git a/src/maze.c b/src/maze.c
new file mode 100644
index 0000000..cfa010b
--- /dev/null
+++ b/src/maze.c
@@ -0,0 +1,186 @@
+/*
+ * Copyright (C) 2021  P. J. McDermott
+ *
+ * This file is part of Maze Fight
+ *
+ * Maze Fight is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Maze Fight 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 Maze Fight.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdlib.h>
+#include "maze.h"
+
+struct mf_maze {
+	int           w;
+	int           h;
+	unsigned int *walls;
+	unsigned int *visited;
+};
+
+/*
+ * Black magic follows
+ */
+
+void
+mf_maze_rm_wall(struct mf_maze *m, int x, int y, int dx, int dy)
+{
+	int i;
+
+	if (x + dx < 0 || x + dx >= m->w || y + dy < 0 || y + dy >= m->h) {
+		return;
+	}
+
+	if (dx < 0) --x;
+	if (dy < 0) --y;
+	i = y * m->w + x;
+	i *= 2;
+	if (dx == 0) ++i;  /* Moving vertically */
+
+	m->walls[i / (sizeof(*m->walls)*8)] |= 1 << (i % (sizeof(*m->walls)*8));
+}
+
+int
+mf_maze_is_wall(struct mf_maze *m, int x, int y, int dx, int dy)
+{
+	int i;
+
+	if (x + dx < 0 || x + dx >= m->w || y + dy < 0 || y + dy >= m->h) {
+		return 1;
+	}
+
+	if (dx < 0) --x;
+	if (dy < 0) --y;
+	i = y * m->w + x;
+	i *= 2;
+	if (dx == 0) ++i;  /* Moving vertically */
+
+	return !(m->walls[i / (sizeof(*m->walls)*8)]
+		& 1 << (i % (sizeof(*m->walls)*8)));
+}
+
+static void
+_mf_maze_visit(struct mf_maze *m, int x, int y)
+{
+	int i;
+
+	++x, ++y;  /* Coordinates start from -1 (edges) */
+	i = y * (m->w+2) + x;
+	m->visited[i / (sizeof(*m->visited)*8)] |=
+		1 << (i % (sizeof(*m->visited)*8));
+}
+
+static int
+_mf_maze_is_visited(struct mf_maze *m, int x, int y)
+{
+	int i;
+
+	++x, ++y;  /* Coordinates start from -1 (edges) */
+	i = y * (m->w+2) + x;
+	return m->visited[i / (sizeof(*m->visited)*8)]
+		& 1 << (i % (sizeof(*m->visited)*8));
+}
+
+/*
+ * End of black magic
+ */
+
+static void
+_mf_maze_carve(struct mf_maze *m, int x, int y)
+{
+	int dirs[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
+	int i;
+	int j;
+	int t_x;
+	int t_y;
+
+	/* Shuffle directions */
+	for (i = 0; i < 4; ++i) {
+		j = rand() / (RAND_MAX / (i+1));
+		t_x        = dirs[i][0];
+		t_y        = dirs[i][1];
+		dirs[i][0] = dirs[j][0];
+		dirs[i][1] = dirs[j][1];
+		dirs[j][0] = t_x;
+		dirs[j][1] = t_y;
+	}
+
+	/* You are here */
+	_mf_maze_visit(m, x, y);
+
+	/* Carve passages */
+	for (i = 0; i < 4; ++i) {
+		if (!_mf_maze_is_visited(m, x + dirs[i][0], y + dirs[i][1])) {
+			mf_maze_rm_wall(m, x, y, dirs[i][0], dirs[i][1]);
+			_mf_maze_carve(m, x + dirs[i][0], y + dirs[i][1]);
+		}
+	}
+}
+
+struct mf_maze *
+mf_maze_new(int s, int w, int h)
+{
+	struct mf_maze *m;
+	int             x;
+	int             y;
+
+	/* Allocate everything */
+	m = calloc(1, sizeof(*m));
+	if (m == NULL) {
+		return NULL;
+	}
+	m->walls = calloc(
+			(w * h * 2 + sizeof(*m->walls)*8 - 1) /
+				(sizeof(*m->walls)*8),
+			sizeof(*m->walls));
+	if (m->walls == NULL) {
+		free(m);
+		return NULL;
+	}
+	m->visited = calloc(
+			((w+2) * (h+2) + sizeof(*m->visited)*8 - 1) /
+				(sizeof(*m->visited)*8),
+			sizeof(*m->visited));
+	if (m->visited == NULL) {
+		free(m->walls);
+		free(m);
+		return NULL;
+	}
+
+	/* Initialize parameters */
+	m->w = w;
+	m->h = h;
+
+	/* Mark edges as visited */
+	for (x = -1; x <= w; ++x) {
+		_mf_maze_visit(m, x, -1);  /* Top */
+		_mf_maze_visit(m, x,  h);  /* Bottom */
+	}
+	for (y = 0; y < h; ++y) {
+		_mf_maze_visit(m, -1, y);  /* Left */
+		_mf_maze_visit(m,  w, y);  /* Right */
+	}
+
+	/* Carve passages */
+	srand(s);
+	_mf_maze_carve(m, 0, 0);
+
+	free(m->visited);
+	return m;
+}
+
+void
+mf_maze_free(struct mf_maze *m)
+{
+	free(m->walls);
+	free(m);
+}
diff --git a/src/maze.h b/src/maze.h
new file mode 100644
index 0000000..1f22702
--- /dev/null
+++ b/src/maze.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2021  P. J. McDermott
+ *
+ * This file is part of Maze Fight
+ *
+ * Maze Fight is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Maze Fight 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 Maze Fight.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef MF_MAZE_H_
+#define MF_MAZE_H_
+
+struct mf_maze;
+
+void
+mf_maze_rm_wall(struct mf_maze *m, int x, int y, int dx, int dy);
+
+int
+mf_maze_is_wall(struct mf_maze *m, int x, int y, int dx, int dy)
+	__attribute__((__pure__));
+
+struct mf_maze *
+mf_maze_new(int s, int w, int h);
+
+void
+mf_maze_free(struct mf_maze *m);
+
+#endif  /* MF_MAZE_H_ */