diff options
| -rw-r--r-- | src/local.mk | 3 | ||||
| -rw-r--r-- | src/maze.c | 186 | ||||
| -rw-r--r-- | src/maze.h | 38 |
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_ */ |