path: root/src/maze.c

/*
 * 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 <SDL.h>
#include <stdlib.h>
#include "maze.h"

struct mf_maze {
	int           w;
	int           h;
	int           show_all;
	unsigned int *walls;
	unsigned int *show;
	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)));
}

void
mf_maze_reveal_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->show[i / (sizeof(*m->show)*8)] |= 1 << (i % (sizeof(*m->show)*8));
}

static int
_mf_maze_revealed_wall(struct mf_maze *m, int x, int y, int dx, int dy)
{
	int i;

	if (m->show_all) {
		return 1;
	}

	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->show[i / (sizeof(*m->show)*8)]
		& 1 << (i % (sizeof(*m->show)*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, int show_all)
{
	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->show = calloc(
			(w * h * 2 + sizeof(*m->show)*8 - 1) /
				(sizeof(*m->show)*8),
			sizeof(*m->show));
	if (m->show == NULL) {
		free(m->walls);
		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->show);
		free(m->walls);
		free(m);
		return NULL;
	}

	/* Initialize parameters */
	m->w        = w;
	m->h        = h;
	m->show_all = show_all;

	/* 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;
}

static int
_mf_maze_draw_line(SDL_Renderer *renderer, int x, int y, int w, int h, int cw)
{
	SDL_Rect rect;

	rect.x = x * cw - 1;
	rect.y = y * cw - 1;
	rect.w = w * cw + 2;
	rect.h = h * cw + 2;
	if (SDL_RenderFillRect(renderer, &rect) < 0) {
		SDL_LogError(SDL_LOG_CATEGORY_APPLICATION,
				"Couldn't render maze: %s", SDL_GetError());
		return -1;
	}

	return 0;
}

int
mf_maze_render(struct mf_maze *m, SDL_Renderer *r, SDL_Color *color, int cw)
{
	int e;
	int x;
	int y;

	e = 0;

	if (SDL_SetRenderDrawColor(r,
				color->r, color->g, color->b, color->a) < 0) {
		SDL_LogError(SDL_LOG_CATEGORY_APPLICATION,
				"Couldn't render maze: %s", SDL_GetError());
		e = -1;
	}

	if (
			_mf_maze_draw_line(r, 0,    0,    m->w, 0,    cw) < 0 ||
			_mf_maze_draw_line(r, 0,    m->h, m->w, 0,    cw) < 0 ||
			_mf_maze_draw_line(r, 0,    0,    0,    m->h, cw) < 0 ||
			_mf_maze_draw_line(r, m->w, 0,    0,    m->h, cw) < 0) {
		e = -1;
	}

	for (y = 0; y < m->h; ++y) {
		for (x = 0; x < m->w; ++x) {
			if (y < m->h - 1 && mf_maze_is_wall(m, x, y, 0, 1) &&
					_mf_maze_revealed_wall(m, x, y, 0, 1)) {
				/* Draw h line */
				if (_mf_maze_draw_line(r, x  , y+1,
							1, 0, cw) < 0) {
					e = -1;
				}
			}
			if (x < m->w - 1 && mf_maze_is_wall(m, x, y, 1, 0) &&
					_mf_maze_revealed_wall(m, x, y, 1, 0)) {
				/* Draw v line */
				if (_mf_maze_draw_line(r, x+1, y  ,
							0, 1, cw) < 0) {
					e = -1;
				}
			}
		}
	}

	return e;
}

void
mf_maze_destroy(struct mf_maze **m_p)
{
	struct mf_maze *m;

	if (m_p == NULL || *m_p == NULL) {
		return;
	}
	m = *m_p;

	if (m->walls != NULL) {
		free(m->walls);
	}
	if (m->show != NULL) {
		free(m->show);
	}
	free(m);
	m = NULL;
}