From ba5f8f180155888d1aee3507c3fe25109e58abb1 Mon Sep 17 00:00:00 2001
From: P. J. McDermott <pj@pehjota.net>
Date: Mon, 02 Aug 2021 00:00:29 -0400
Subject: maze: New functions
---
(limited to 'src')
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_ */
--
cgit v0.9.1