Random Dungeon Generator for a Roguelike

dungeon.c

/**
 *    **Random Dungeon Generator**
 *
 * A random dungeon generator for a Roguelike game.
 *
 * It is based on the "Rogue" algorithm, as described by Mark Damon Hughes
 * [Game Design: Article 07: Roguelike Dungeon Generation][algorithm], but with
 * some modifications.
 *
 * The basic algorithm is this:
 *
 * 1. Divide the map into a grid of `GRID_W` × `GRID_H` cells. Each cell will contain a room. The cells are
 *    marked as un_d_connected initially.
 * 2. Choose a random cell as the starting room; set it as the _current room_.
 * 3. While the _current room_ has un_d_connected neighbour cells,
 *    * mark the _current room_ as _d_connected,
 *    * set its _number_ to the number of rooms added so far,
 *    * mark it as a _path_ room, and
 *    * choose one of those un_d_connected neighbours at random and _d_connect it to the _current room_,
 *    * set the new room to the _current room_.
 * 4. Iteration stops when the current room reached a dead end.
 *    * The last room you added is labelled the end room.
 *    * You should now have a fairly long path from the start room to the end room.
 *    * The number of rooms added up to now is referred to as the _distance_:
 *      * If the distance is too short, it might be too easy for the adventurer to get from the start
 *        to the end, so the implementation has the option to go back to step 2
 * 5. Color the rooms: All the __d_connected_ rooms whose _number_ is less than $\frac{distance}{2}$ is
 *    colored blue, all the other rooms colored red.
 *    * Mark the _d_connection between the last blue room and the first red room as a door.
 * 6. While there are un_d_connected rooms on the grid:
 *    * choose a random un_d_connected room and _d_connect it to one of its _d_connected neighbours.
 *    * (If a room doesn't have _d_connected neighbours you can just retry with a different room;
 *      you'll _d_connect all of them eventually)
 *    * Mark the room as _d_connected. Give it the same _color_ as the neighbour you're _d_connecting it too.
 *    * The room is also marked as an _extra_ room.
 * 7. Add some random _d_connections between the rooms
 *    * Choose a room at random and _d_connect it to a random neighbour if they don't have a _d_connection yet.
 *    * If the two rooms have different colors, mark the _d_connection between them as a door...
 *    * ...unless the rooms are start/end rooms - we don't want a door directly to one of these rooms because
 *      it might make the map a bit too easy to solve.
 * 8. Some of the rooms are marked as _gone_ rooms - they will consist of just corridors, for effect.
 *    * The start room and end room cannot be gone rooms.
 *    * Rooms with only one exit can't be gone rooms either (they would just be corridors leading nowhere).
 * 9. Each room is given a random position and width/height to occupy within its cell on the grid.
 *
 * So when the algorithm is done, you can place the player in the room marked as the start room and place a key
 * in any of the blue rooms and you'll be guaranteed that the player will be able to find a key to open the
 * door in one of the accessible rooms. You'll also be guaranteed that the player will have to pass through
 * a door to reach the end room that will be in a room colored red.
 *
 * Of course, the _door_ and the _key_ doesn't have to be an actual door and key. The _door_ could be any obstacle
 * blocking the hero, like a river of lava, and the _key_ would be some means to overcome that obstacle, like a
 * lever to lower a d_drawbridge over the lava.
 *
 * All rooms marked as _path_ rooms will be guaranteed to lie on a path from the start room to the end room,
 * although other paths may exist thanks to the random _d_connections.
 *
 * The rooms marked as _extra_ rooms may be used for some additional purposes. For example, if an extra room has
 * only one corridor _d_connecting it to the rest of the maze, then it could be turned into a secret room by hiding
 * said corridor.
 *
 * You could put tougher _boss_ monsters and/or better treasure in rooms colored 1, so that the flow is that the
 * player starts in the blue area, fights a couple of easier enemies, find the key, go through the door to
 * the red area, encounter a boss, loot some treasure and reach the exit.
 *
 * This online tool [svg-path-editor](https://yqnn.github.io/svg-path-editor/) helped me create the SVG paths.
 *
 * https://dysonlogos.blog/2013/12/23/the-key-to-all-this-madness/
 * https://watabou.itch.io/one-page-dungeon
 *
 * [algorithm]: https://web.archive.org/web/20131025132021/http://kuoi.org/~kamikaze/GameDesign/art07_rogue_dungeon.php
 */

#ifndef DUNGEON_H
#define DUNGEON_H

#define D_GRID_W 			5
#define D_GRID_H 			3

#define D_MAX_ROOM_SIZE		4
#define D_MIN_ROOM_SIZE		3

#define D_MIN_DISTANCE		7

#define D_SECRET_PROB		50

#define D_MAX_GONE_ROOMS 	2
#define D_MIN_GONE_ROOMS	1

#define D_COLOR_BLUE		0
#define D_COLOR_RED			1

#define D_FLAG_START_ROOM	0x01
#define D_FLAG_END_ROOM		0x02
#define D_FLAG_PATH_ROOM	0x04
#define D_FLAG_XTRA_ROOM	0x08
#define D_FLAG_GONE_ROOM	0x10
#define D_FLAG_SECRET_ROOM	0x20

#define D_NORTH				0x01
#define D_SOUTH				0x02
#define D_EAST				0x04
#define D_WEST				0x08

#define D_ORIENT_EW			(D_EAST | D_WEST)
#define D_ORIENT_NS			(D_NORTH | D_SOUTH)

#define D_TILE_EMPTY		' '
#define D_TILE_WALL			'#'
#define D_TILE_FLOOR		'.'
#define D_TILE_FLOOR_EDGE	','
#define D_TILE_CORRIDOR		'`'
#define D_TILE_CROSSING		'+'
#define D_TILE_ENTRANCE		'@'
#define D_TILE_EXIT			'$'
#define D_TILE_LOCKED_DOOR	'D'
#define D_TILE_THRESHOLD	't'
#define D_TILE_SECRET		's'

/* Choose a random number in [0,N) */
#ifndef D_RAND
#  define D_RAND(N)  ((rand() >> 8) % (N))
#endif

typedef struct {
	short x, y;
} D_Point;

typedef struct {
	char _d_connected;
	char color;
	unsigned char flags;
	char visited;

	short x, y, w, h;
} D_Room;

/* Connections between the rooms. An edge p,q means that
there's a corridor between rooms[p] and rooms[q] */
typedef struct {
	short p, q;
	char door, direction, offset;
	short index;

	short x, y, w, h;
} D_Edge;

typedef struct {

	/* These fields are used for configuration */

	short grid_w, grid_h;

	short min_room_size, max_room_size;

	short min_distance;

	short secret_prob;

	short min_gone_rooms, max_gone_rooms;

	/* These fields are computed; don't mess with them: */

	short map_w, map_h;

	D_Room *rooms;
	short n_rooms;

	char *map;

	D_Edge *edges;
	short n_edges, max_edges;

	short start_room, end_room;

	/* Temporary indexes */
	short *cells;

} D_Dungeon;


void d_init(D_Dungeon *M);

void d_deinit(D_Dungeon *M);

int d_generate(D_Dungeon *D);

int d_is_wall(D_Dungeon *M, int x, int y);

int d_is_floor(D_Dungeon *M, int x, int y);

void d_set_tile(D_Dungeon *M, int x, int y, char tile);

char d_get_tile(D_Dungeon *M, int x, int y);

D_Room *d_room_at(D_Dungeon *M, int x, int y);
D_Edge *d_corridor_at(D_Dungeon *M, int x, int y);

D_Room *d_random_room(D_Dungeon *M);

int d_random_wall(D_Dungeon *M, D_Room *room, D_Point *p);

void d_draw(D_Dungeon *M, FILE *f);

#ifdef DUNGEON_IMPLEMENTATION

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

void d_init(D_Dungeon *M) {
	M->grid_w = D_GRID_W;
	M->grid_h = D_GRID_H;

	M->min_room_size = D_MIN_ROOM_SIZE;
	M->max_room_size = D_MAX_ROOM_SIZE;

	M->min_distance = D_MIN_DISTANCE;

	M->secret_prob = D_SECRET_PROB;

	M->min_gone_rooms = D_MIN_GONE_ROOMS;
	M->max_gone_rooms = D_MAX_GONE_ROOMS;

	M->rooms = NULL;
	M->map = NULL;
	M->edges = NULL;
	M->cells = NULL;
}

void d_deinit(D_Dungeon *M) {
	if(M->rooms)
		free(M->rooms);
	M->rooms = NULL;

	if(M->map)
		free(M->map);
	M->map = NULL;

	if(M->edges)
		free(M->edges);
	M->edges = NULL;

	if(M->cells)
		free(M->cells);
	M->cells = NULL;
}

static void _d_reset_generator(D_Dungeon *M) {
	int i;

	memset(M->rooms, 0, M->n_rooms * sizeof *M->rooms);

	for(i = 0; i < M->map_w * M->map_h; i++) {
		M->map[i] = ' ';
	}

	M->n_edges = 0;
	memset(M->edges, 0, M->max_edges * sizeof *M->edges);
}

static int _d_init_generator(D_Dungeon *M) {

	M->map_w = M->grid_w * (M->max_room_size + 1) + 1;
	M->map_h = M->grid_h * (M->max_room_size + 1) + 1;

	M->n_rooms = M->grid_w * M->grid_h;

	M->rooms = malloc(M->n_rooms * sizeof *M->rooms);
	if(!M->rooms) {
		return 0;
	}

	M->map = malloc(M->map_w * M->map_h * sizeof *M->map);
	if(!M->map) {
		free(M->rooms);
		return 0;
	}

	/* Maximum number of edges in a M*N rooms graph is 2MN-M-N */
	M->max_edges = (2 * M->grid_w * M->grid_h) - M->grid_w - M->grid_h;
	M->edges = malloc(M->max_edges * sizeof *M->edges);
	if(!M->edges) {
		free(M->rooms);
		free(M->map);
		return 0;
	}

	return 1;
}

static int _d_grid_index(D_Dungeon *M, int row, int col) {
	if(row < 0 || row >= M->grid_h) return -1;
	if(col < 0 || col >= M->grid_w) return -1;
	return row * M->grid_w + col;
}

static int _d_get_unconnected(D_Dungeon *M) {
	int i, n = 0;
	assert(M->cells);
	for(i = 0; i < M->n_rooms; i++) {
		if(!M->rooms[i]._d_connected) {
			M->cells[n++] = i;
		}
	}
	return n;
}

static int _d_get_unconnected_neighbors(D_Dungeon *M, int gi, int n[4]) {
	int j = 0, i, count;
	int row = gi / M->grid_w;
	int col = gi % M->grid_w;

	i = _d_grid_index(M, row-1, col);
	if(i >= 0 && !M->rooms[i]._d_connected)
		n[j++] = i;
	i = _d_grid_index(M, row+1, col);
	if(i >= 0 && !M->rooms[i]._d_connected)
		n[j++] = i;
	i = _d_grid_index(M, row, col-1);
	if(i >= 0 && !M->rooms[i]._d_connected)
		n[j++] = i;
	i = _d_grid_index(M, row, col+1);
	if(i >= 0 && !M->rooms[i]._d_connected)
		n[j++] = i;

	count = j;
	while(j < 4) n[j++] = -1;
	return count;
}

static int _d_get_connected_neighbors(D_Dungeon *M, int gi, int n[4]) {
	int j = 0, i, count;
	int row = gi / M->grid_w;
	int col = gi % M->grid_w;

	i = _d_grid_index(M, row-1, col);
	if(i >= 0 && M->rooms[i]._d_connected)
		n[j++] = i;
	i = _d_grid_index(M, row+1, col);
	if(i >= 0 && M->rooms[i]._d_connected)
		n[j++] = i;
	i = _d_grid_index(M, row, col-1);
	if(i >= 0 && M->rooms[i]._d_connected)
		n[j++] = i;
	i = _d_grid_index(M, row, col+1);
	if(i >= 0 && M->rooms[i]._d_connected)
		n[j++] = i;

	count = j;
	while(j < 4) n[j++] = -1;
	return count;
}

static D_Edge *_d_get_edge(D_Dungeon *M, int p, int q) {
	int i;
	for(i = 0; i < M->n_edges; i++) {
		D_Edge *e = &M->edges[i];
		if((e->p == p && e->q == q) || (e->p == q && e->q == p))
			return e;
	}
	return NULL;
}

static D_Edge *_d_connect(D_Dungeon *M, int from, int to) {
	D_Edge *e;
	assert(!_d_get_edge(M, from, to));
	assert(M->n_edges < M->max_edges);
	e = &M->edges[M->n_edges];

	e->index = M->n_edges;
	e->p = from;
	e->q = to;

	M->n_edges++;
	return e;
}

static int _d_count_exits(D_Dungeon *M, int room) {
	int i, c = 0;
	for(i = 0; i < M->n_edges; i++) {
		if(M->edges[i].p == room || M->edges[i].q == room)
			c++;
	}
	return c;
}

static int _d_layout(D_Dungeon *M) {
	int count;
	int neighbours[4];

	int curr, next, split, c, attempts = 0;
	D_Edge *edge;

	if(!_d_init_generator(M))
		return 0;

	M->cells = calloc(M->n_rooms, sizeof *M->cells);
	if(!M->cells)
		return 0;

	do {
		_d_reset_generator(M);

		count = 0;

		curr = D_RAND(M->n_rooms);
		M->start_room = curr;
		for(;;) {
			M->cells[count++] = curr;

			M->rooms[curr]._d_connected = 1;
			M->rooms[curr].flags |= D_FLAG_PATH_ROOM;
			c = _d_get_unconnected_neighbors(M, curr, neighbours);
			if(!c) {
				M->end_room = curr;
				break;
			}

			next = neighbours[D_RAND(c)];

			_d_connect(M, curr, next);
			curr = next;
		}
	} while (count < M->min_distance  && ++attempts < 10);

	/* Color the first half of the rooms BLUE and the
	second half of the rooms RED. We put a locked door
	between the BLUE and RED rooms. */
	split = count / 2;
	curr = M->cells[split];
	next = M->cells[split+1];
	assert(curr >= 0 && next >= 0);
	edge = _d_get_edge(M, curr, next);
	assert(edge != NULL);
	edge->door = 1;

	for(c = 0; c < count; c++) {
		int i = M->cells[c];
		D_Room *r = &M->rooms[i];
		if(c <= split)
			r->color = D_COLOR_BLUE;
		else
			r->color = D_COLOR_RED;
	}

#if 1
	/* Connect all the un_d_connected rooms... */
	attempts = 0;
	for(;;) {
		c = _d_get_unconnected(M);
		if(!c) break;
		curr = M->cells[ D_RAND(c) ];

		c = _d_get_connected_neighbors(M, curr, neighbours);
		if(!c) continue;
		next = neighbours[ D_RAND(c) ];

		_d_connect(M, curr, next);
		M->rooms[curr]._d_connected = 1;

		/* Give it the same color */
		M->rooms[curr].color = M->rooms[next].color;

		/* Mark it as an "Extra D_Room". You might want to
		use the knowledge to use the knowledge later to
		hide a treasure there, or make it a secret room */
		M->rooms[curr].flags |= D_FLAG_XTRA_ROOM;
	}
#endif

#if 1
	/* Count the number of blue rooms */
	for(curr = 0, c = 0; curr < M->n_rooms; curr++) {
		if(M->rooms[curr].color == D_COLOR_BLUE)
			c++;
	}
	/* If there are more Red rooms (`n_rooms - c`) than blue rooms (`c`),
	swap everything around */
	if(M->n_rooms - c > c) {
		int t = M->start_room;
		M->start_room = M->end_room;
		M->end_room = t;
		for(curr = 0, c = 0; curr < M->n_rooms; curr++) {
			if(M->rooms[curr].color == D_COLOR_BLUE)
				M->rooms[curr].color = D_COLOR_RED;
			else
				M->rooms[curr].color = D_COLOR_BLUE;
		}
	}
#endif

	M->rooms[M->start_room].flags |= D_FLAG_START_ROOM;
	M->rooms[M->end_room].flags |= D_FLAG_END_ROOM;

#if 1
	count = D_RAND((M->grid_w + M->grid_h + 1)/2) + 1;
	while(count > 0) {
		int row, col, door;
		curr = D_RAND(M->n_rooms);
		row = curr / M->grid_w;
		col = curr % M->grid_w;

		if(++attempts > M->n_rooms) {
			/* Too many attempts - bail out
			Since I made it possible to add a door
			between rooms with different colors, I
			don't think this would be a problem */
			break;
		}

		/* Find candidate neighbours */
		c = 0;
		next = _d_grid_index(M, row-1, col);
		if(next >= 0 && !_d_get_edge(M, curr, next))
			neighbours[c++] = next;
		next = _d_grid_index(M, row+1, col);
		if(next >= 0 && !_d_get_edge(M, curr, next))
			neighbours[c++] = next;
		next = _d_grid_index(M, row, col-1);
		if(next >= 0 && !_d_get_edge(M, curr, next))
			neighbours[c++] = next;
		next = _d_grid_index(M, row, col+1);
		if(next >= 0 && !_d_get_edge(M, curr, next))
			neighbours[c++] = next;
		if(c == 0) {
			continue;
		}

		next = neighbours[ D_RAND(c) ];

		/* If the two rooms have different colors, put a locked door between them */
		door = M->rooms[curr].color != M->rooms[next].color;
		if(door) {
			if(M->rooms[curr].flags & (D_FLAG_START_ROOM | D_FLAG_END_ROOM)
				|| M->rooms[next].flags & (D_FLAG_START_ROOM | D_FLAG_END_ROOM)) {
				/* don't put the door in the start/end room - it might make the
				map too easy (as I found through experimentation) */
				continue;
			}
		}

		edge = _d_connect(M, curr, next);
		edge->door = door;
		count--;
	}
#endif

#if 1
	/* Make gone rooms */
	count = D_RAND(M->max_gone_rooms - M->min_gone_rooms + 1) + M->min_gone_rooms;
	attempts = 0;
	while(count > 0) {
		if(++attempts > 10) break;

		curr = D_RAND(M->n_rooms);

		if(_d_count_exits(M, curr) < 2)
			continue;
		if(M->rooms[curr].flags & (D_FLAG_GONE_ROOM | D_FLAG_START_ROOM | D_FLAG_END_ROOM))
			continue;

		M->rooms[curr].flags |= D_FLAG_GONE_ROOM;

		count--;
	}
#endif

	for(curr = 0; curr < M->n_rooms; curr++) {
		D_Room *room = &M->rooms[curr];

		int row = curr / M->grid_w;
		int col = curr % M->grid_w;

		if(M->rooms[curr].flags & D_FLAG_GONE_ROOM) {

			room->w = 1;
			room->h = 1;
			room->x = col * (M->max_room_size + 1) + 1 + M->max_room_size/2;
			room->y = row * (M->max_room_size + 1) + 1 + M->max_room_size/2;

		} else {
			room->w = D_RAND(M->max_room_size - M->min_room_size + 1) + M->min_room_size;
			room->h = D_RAND(M->max_room_size - M->min_room_size + 1) + M->min_room_size;

			room->x = col * (M->max_room_size + 1) + 1 + (M->max_room_size - room->w + 1)/2;
			room->y = row * (M->max_room_size + 1) + 1 + (M->max_room_size - room->h + 1)/2;
		}
	}

	/* Shift the edges up/down or left/right a bit */
	for(curr = 0; curr < M->n_edges; curr++) {
		M->edges[curr].offset = D_RAND(3)-1;
	}

	free(M->cells);
	M->cells = NULL;

	return 1;
}

int d_is_wall(D_Dungeon *M, int x, int y) {
	char t;
	if(x < 0 || x >= M->map_w || y < 0 || y >= M->map_h)
		return 1;
	t = M->map[ y * M->map_w + x ];
	return t == D_TILE_EMPTY || t == D_TILE_WALL;
}

int d_is_floor(D_Dungeon *M, int x, int y) {
	char t;
	if(x < 0 || x >= M->map_w || y < 0 || y >= M->map_h)
		return 0;
	t = M->map[ y * M->map_w + x ];
	return t == D_TILE_FLOOR_EDGE || t == D_TILE_FLOOR;
}

static int _d_is_tile(D_Dungeon *M, int x, int y, char tile) {
	if(x < 0 || x >= M->map_w || y < 0 || y >= M->map_h)
		return 0;
	return (M->map[ y * M->map_w + x ] == tile);
}

void d_set_tile(D_Dungeon *M, int x, int y, char tile) {
	if(x < 0 || x >= M->map_w || y < 0 || y >= M->map_h)
		return;
	M->map[ y * M->map_w + x ] = tile;
}

char d_get_tile(D_Dungeon *M, int x, int y) {
	if(x < 0 || x >= M->map_w || y < 0 || y >= M->map_h)
		return D_TILE_EMPTY;
	return M->map[ y * M->map_w + x ];
}

static int _d_has_neighbour(D_Dungeon *M, int x, int y, char tile) {
	return (_d_is_tile(M, x - 1, y, tile) ||
			_d_is_tile(M, x + 1, y, tile) ||
			_d_is_tile(M, x, y - 1, tile) ||
			_d_is_tile(M, x, y + 1, tile));
}

int d_random_wall(D_Dungeon *M, D_Room *room, D_Point *p) {
	int attempts = 0, x, y;
	do {
		switch(D_RAND(4)) {
		case 0:
			x = room->x - 1;
			y = room->y + D_RAND(room->h);
			if(d_is_floor(M, x + 1, y) && d_is_wall(M, x - 1, y) && d_is_wall(M, x, y - 1) && d_is_wall(M, x, y + 1)) {
				p->x = x; p->y = y;
				return 1;
			}
			break;
		case 1:
			x = room->x + room->w;
			y = room->y + D_RAND(room->h);
			if(d_is_floor(M, x - 1, y) && d_is_wall(M, x + 1, y) && d_is_wall(M, x, y - 1) && d_is_wall(M, x, y + 1)) {
				p->x = x; p->y = y;
				return 1;
			}
			break;
		case 2:
			x = room->x + D_RAND(room->w);
			y = room->y - 1;
			if(d_is_floor(M, x, y + 1) && d_is_wall(M, x, y - 1) && d_is_wall(M, x - 1, y) && d_is_wall(M, x + 1, y)) {
				p->x = x; p->y = y;
				return 1;
			}
			break;
		case 3:
			x = room->x + D_RAND(room->w);
			y = room->y + room->h;
			if(d_is_floor(M, x, y - 1) && d_is_wall(M, x, y + 1) && d_is_wall(M, x - 1, y) && d_is_wall(M, x + 1, y)) {
				p->x = x; p->y = y;
				return 1;
			}
			break;
		}
	} while(++attempts < 8);
	return 0;
}

static int _d_edge_direction(int p, int q) {
	if(q < p) {
		if(q == p - 1) {
			return D_WEST;
		} else {
			return D_NORTH;
		}
	} else {
		if(q == p + 1) {
			return D_EAST;
		} else {
			return D_SOUTH;
		}
	}
}

static const char *_d_dir_name(int dir) {
	switch(dir) {
		case D_NORTH: return "North";
		case D_SOUTH: return "South";
		case D_EAST: return "East";
		case D_WEST: return "West";
	}
	return "";
}

static int _d_traverse_room(D_Dungeon *M, int idx, int prev) {
	int i, e = 0, exits[4];
	D_Edge *edges[4];
	D_Point exit_points[4];
	D_Room *room = &M->rooms[idx];

	if(room->visited) return 0;
	room->visited = 1;
	printf("Room %d:\n", idx);

	for(i = 0; i < M->n_edges; i++) {
		if(M->edges[i].p == idx) {
			assert(e < 4);
			exits[e] = M->edges[i].q;
			edges[e] = &M->edges[i];
			e++;
		} else if(M->edges[i].q == idx) {
			assert(e < 4);
			exits[e] = M->edges[i].p;
			edges[e] = &M->edges[i];
			e++;
		}
	}

	for(i = 0; i < e; i++) {
		int dir = _d_edge_direction(idx, exits[i]);
		printf(" * %s %d %c\n", _d_dir_name(dir), exits[i], exits[i]==prev?'*':' ');
		switch(dir) {
			case D_NORTH:
				exit_points[i].x = edges[i]->x;
				exit_points[i].y = edges[i]->y + edges[i]->h - 1;
				break;
			case D_SOUTH:
				exit_points[i].x = edges[i]->x;
				exit_points[i].y = edges[i]->y;
				break;
			case D_WEST:
				exit_points[i].x = edges[i]->x + edges[i]->w - 1;
				exit_points[i].y = edges[i]->y;
				break;
			case D_EAST:
				exit_points[i].x = edges[i]->x;
				exit_points[i].y = edges[i]->y;
				break;
		}
	}

	for(i = 0; i < e; i++) {
		int s;
		if(exits[i] == prev) continue;
		s = _d_traverse_room(M, exits[i], idx);
		if(s == 1 && !(room->flags & D_FLAG_GONE_ROOM) && (M->rooms[ exits[i] ].flags & D_FLAG_XTRA_ROOM)) {
			if(D_RAND(100) > M->secret_prob) continue;
			M->rooms[ exits[i] ].flags |= D_FLAG_SECRET_ROOM;
			d_set_tile(M, exit_points[i].x, exit_points[i].y, D_TILE_SECRET);
		}
	}

	return e;
}

static void _d_postprocess(D_Dungeon *M) {
	int i, j, start, placed;
	D_Room *room;
	D_Edge *edge;
	D_Point point;

	for(j = 0; j < M->grid_h; j++) {
		for(i = 0; i < M->grid_w; i++) {
			D_Room *room = &M->rooms[_d_grid_index(M, j, i)];
			int p, q;

			if(!room->_d_connected || (room->flags & D_FLAG_GONE_ROOM)) {
				d_set_tile(M, room->x, room->y, D_TILE_CROSSING);
				continue;
			}

			for(p = 0; p < room->w; p++) {
				for(q = 0; q < room->h; q++) {
					d_set_tile(M, room->x + p, room->y + q, D_TILE_FLOOR);
				}
			}
		}
	}

	/* Draw all the edges, computing their bounding boxes in the process */
	for(i = 1; i < M->n_rooms; i++) {
		int row = i / M->grid_w;
		int col = i % M->grid_w;

		int x = col * (M->max_room_size + 1) + 1 + (M->max_room_size)/2;
		int y = row * (M->max_room_size + 1) + 1 + (M->max_room_size)/2;

		if(col > 0) {
			int left = i - 1;
			int maxx, minx, tx = x;

			edge = _d_get_edge(M, i, left);
			if(edge) {
				edge->direction = D_ORIENT_EW;
				if((M->rooms[i].flags & D_FLAG_GONE_ROOM) || (M->rooms[left].flags & D_FLAG_GONE_ROOM))
					edge->y = y;
				else
					edge->y = y + edge->offset;

				start = edge->y * M->map_w + x;

				edge->h = 1;
				maxx = x - (M->max_room_size + 1);
				minx = x;

				for(j = 0; j <= M->max_room_size + 1; j++, tx--) {
					if(M->map[ start - j ] != D_TILE_EMPTY)
						continue;

					if(tx < minx)
						minx = tx;
					if(tx > maxx)
						maxx = tx;

					if(edge->door && j == M->max_room_size/2 + 1)
						M->map[ start - j ] = D_TILE_LOCKED_DOOR;
					else
						M->map[ start - j ] = D_TILE_CORRIDOR;
				}

				edge->x = minx;
				edge->w = maxx - minx + 1;
			}
		}
		if(row > 0) {
			int up = i - M->grid_w;
			int maxy, miny, ty = y;

			edge = _d_get_edge(M, i, up);
			if(edge) {
				edge->direction = D_ORIENT_NS;
				if((M->rooms[i].flags & D_FLAG_GONE_ROOM) || (M->rooms[up].flags & D_FLAG_GONE_ROOM))
					edge->x = x;
				else
					edge->x = x + edge->offset;

				start = y * M->map_w + edge->x;

				edge->w = 1;
				maxy = y - (M->max_room_size + 1);
				miny = y;

				for(j = 0; j <= M->max_room_size; j++, ty--) {
					if(M->map[start - j * M->map_w] != D_TILE_EMPTY)
						continue;

					if(ty < miny)
						miny = ty;
					if(ty > maxy)
						maxy = ty;

					if(edge->door && j == M->max_room_size/2 + 1)
						M->map[ start - j * M->map_w ] = D_TILE_LOCKED_DOOR;
					else
						M->map[ start - j * M->map_w ] = D_TILE_CORRIDOR;
				}

				edge->y = miny;
				edge->h = maxy - miny + 1;
			}
		}
	}
	
	for(j = 0; j < M->map_h; j++) {
		for(i = 0; i < M->map_w; i++) {
			if(d_is_wall(M, i, j) && (
				!d_is_wall(M, i - 1, j) ||
				!d_is_wall(M, i + 1, j) ||
				!d_is_wall(M, i, j - 1) ||
				!d_is_wall(M, i, j + 1) ||
				/* Diagonal checks only makes it look nice in ASCII: */
				!d_is_wall(M, i - 1, j - 1) ||
				!d_is_wall(M, i + 1, j - 1) ||
				!d_is_wall(M, i - 1, j + 1) ||
				!d_is_wall(M, i + 1, j + 1)
			)) {
				d_set_tile(M, i, j, D_TILE_WALL);
			}

			if(_d_is_tile(M, i, j, D_TILE_CORRIDOR) && _d_has_neighbour(M, i, j, D_TILE_FLOOR)) {
				D_Edge * e = d_corridor_at(M, i, j);
				if(!e->door)
					d_set_tile(M, i, j, D_TILE_THRESHOLD);
			}
		}
	}
	
	/* Place the dungeon entrance and exit */
	room = &M->rooms[M->start_room];
	placed = d_random_wall(M, room, &point);
	if(placed) {
		d_set_tile(M, point.x, point.y, D_TILE_ENTRANCE);
	} else {
		/* Ugly, but better than nothing */
		d_set_tile(M, room->x + room->w/2, room->y + room->h/2, D_TILE_ENTRANCE);
	}

	room = &M->rooms[M->end_room];
	placed = d_random_wall(M, room, &point);
	if(placed) {
		d_set_tile(M, point.x, point.y, D_TILE_EXIT);
	} else {
		d_set_tile(M, room->x + room->w/2, room->y + room->h/2, D_TILE_EXIT);
	}

	for(j = 0; j < M->map_h; j++) {
		for(i = 0; i < M->map_w; i++) {
			if(_d_is_tile(M, i, j, D_TILE_FLOOR) && _d_has_neighbour(M, i, j, D_TILE_WALL) &&
			!(_d_has_neighbour(M, i, j, D_TILE_THRESHOLD) 
				|| _d_has_neighbour(M, i, j, D_TILE_CORRIDOR) 
				|| _d_has_neighbour(M, i, j, D_TILE_LOCKED_DOOR) 
				|| _d_has_neighbour(M, i, j, D_TILE_ENTRANCE) 
				|| _d_has_neighbour(M, i, j, D_TILE_EXIT) 
				|| _d_has_neighbour(M, i, j, D_TILE_SECRET)))
				M->map[ j * M->map_w + i ] = D_TILE_FLOOR_EDGE;
		}
	}

	_d_traverse_room(M, M->start_room, -1);
}

int d_generate(D_Dungeon *D) {
	if(!_d_layout(D))
		return 0;
	_d_postprocess(D);
	return 1;
}

D_Room *d_room_at(D_Dungeon *M, int x, int y) {
	int col = (x - 1) / (M->max_room_size + 1);
	int row = (y - 1) / (M->max_room_size + 1);
	int i = _d_grid_index(M, row, col);
	D_Room *r = &M->rooms[i];
	if(x >= r->x && x < r->x + r->w && y >= r->y && y < r->y + r->h)
		return r;
	return NULL;
}

D_Edge *d_corridor_at(D_Dungeon *M, int x, int y) {
	int i;
	for(i = 0; i < M->n_edges; i++) {
		D_Edge *e = &M->edges[i];
		if(x >= e->x && x < e->x + e->w && y >= e->y && y < e->y + e->h)
			return e;
	}
	return NULL;
}

D_Room *d_random_room(D_Dungeon *M) {
	D_Room *r;
	do {
		r = &M->rooms[D_RAND(M->n_rooms)];
	} while(r->flags & D_FLAG_GONE_ROOM);
	return r;
}

void d_draw(D_Dungeon *M, FILE *f) {
	int i, j;
	for(j = 0; j < M->map_h; j++) {
		for(i = 0; i < M->map_w; i++) {
			putc(d_get_tile(M, i, j), f);
		}
		putc('\n', f);
	}
}

#endif /* DUNGEON_IMPLEMENTATION */
#endif /* DUNGEON_H */

main.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define DUNGEON_IMPLEMENTATION
#include "dungeon.c"

#define POISSON_IMPLEMENTATION
#include "poisson.c"

static float frand() {
	return ((float)rand())/RAND_MAX;
}

static int wall_constraint(struct poisson *P, float x, float y) {
	D_Dungeon *M = P->data;
	float fx, fy;
	int mx, my;

	(void)P;

	x /= 10.0;
	y /= 10.0;

	mx = (int)x;
	my = (int)y;

	fx = x - mx;
	fy = y - my;

	if(!d_is_wall(M, mx, my)) return 1;

	if(fx < 0.3 && !d_is_wall(M, mx - 1, my)) return 1;
	if(fx > 0.7 && !d_is_wall(M, mx + 1, my)) return 1;
	if(fy < 0.3 && !d_is_wall(M, mx, my - 1)) return 1;
	if(fy > 0.7 && !d_is_wall(M, mx, my + 1)) return 1;

	return 0;
}

static void drawSvg(D_Dungeon *M, FILE *f) {
	int i, j;
	struct poisson P;
	D_Room *r;

	poisson_init(&P);
	P.r = 2.75;
	P.w = (M->map_w+1) * 10;
	P.h = (M->map_h+1) * 10;
	P.x0.y = (M->rooms[0].y + M->rooms[0].h/2) * 10;
	P.x0.x = (M->rooms[0].x + M->rooms[0].w/2) * 10;
	P.constraint = wall_constraint;
	P.data = M;

	if(!poisson_plot(&P)) {
		fprintf(stderr, "Couldn't do Poisson Disk thing :(\n");
		/* return; */
	}

	fprintf(f, "<svg viewBox=\"0 0 %d %d\" xmlns=\"http://www.w3.org/2000/svg\">\n", M->map_w * 10, M->map_h * 10);

	fprintf(f, " <defs>\n");
	fprintf(f, " <symbol id=\"floor\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <rect x=\"-0.2\" y=\"-0.2\" width=\"10.4\" height=\"10.4\" fill=\"#FFF\"/>\n");
	fprintf(f, " </symbol>\n");

	fprintf(f, " <symbol id=\"wall-l\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 0 0 C 0.2 2.5, -0.2 7.5, 0 10\" stroke=\"black\" fill=\"none\" stroke-width=\"0.5\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " <symbol id=\"wall-r\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 10 0 C 10.2 2.5, 9.8 7.5, 10 10\" stroke=\"black\" fill=\"none\" stroke-width=\"0.5\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " <symbol id=\"wall-t\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 0 0 C 2.5 0.2, 7.5 -0.2, 10 0\" stroke=\"black\" fill=\"none\" stroke-width=\"0.5\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " <symbol id=\"wall-b\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 0 10 C 2.5 10.2, 7.5 9.8, 10 10\" stroke=\"black\" fill=\"none\" stroke-width=\"0.5\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");

	fprintf(f, " <symbol id=\"floor-r1\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 10 0 C 10.2 2.5, 9.8 7.5, 10 10\" stroke=\"black\" fill=\"none\" stroke-width=\"0.125\"  stroke-dasharray=\"0.3 1.5 1 2.5 0.4 2\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " <symbol id=\"floor-r2\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 10 0 C 10.2 2.5, 9.8 7.5, 10 10\" stroke=\"black\" fill=\"none\" stroke-width=\"0.125\"  stroke-dasharray=\"0.7 2.5 0.7 1.5 0.5 2\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " <symbol id=\"floor-r3\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 10 0 C 10.2 2.5, 9.8 7.5, 10 10\" stroke=\"black\" fill=\"none\" stroke-width=\"0.125\"  stroke-dasharray=\"0.7 1.5 0.7 1 0.5 2\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " <symbol id=\"floor-b1\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 0 10 C 2.5 10.2, 7.5 9.8, 10 10\" stroke=\"black\" fill=\"none\" stroke-width=\"0.125\"  stroke-dasharray=\"0.3 1.5 1 2.5 0.4 2\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " <symbol id=\"floor-b2\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 0 10 C 2.5 10.2, 7.5 9.8, 10 10\" stroke=\"black\" fill=\"none\" stroke-width=\"0.125\"  stroke-dasharray=\"0.7 2.5 0.7 1.5 0.5 2\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " <symbol id=\"floor-b3\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 0 10 C 2.5 10.2, 7.5 9.8, 10 10\" stroke=\"black\" fill=\"none\" stroke-width=\"0.125\"  stroke-dasharray=\"0.7 1.5 0.7 1 0.5 2\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");

	fprintf(f, " <symbol id=\"blobs\" width=\"6\" height=\"6\" viewBox=\"-3 -3 6 6\" x=\"-3\" y=\"-3\">\n");
	fprintf(f, "  <path d=\"M -0.01 -2.88 C -0.86 -2.92 -1.02 -2.89 -2.22 -2.13 C -2.58 -1.96 -2.83 -1.13 -2.89 -0.08 C -3 0.63 -2.61 1.18 -2.2 2.01 C -1.66 2.77 -0.59 2.73 -0.01 2.73 C 0.69 2.8 1.79 2.73 2.17 2.47 C 2.84 2.24 2.86 0.82 2.85 -0.05 C 2.83 -0.68 2.78 -2.05 2.29 -2.1 C 1.6 -2.31 1.21 -2.92 0 -2.89\"\n");
	fprintf(f, "  fill=\"#EEE\" stroke=\"none\"/>\n");
	fprintf(f, " </symbol>\n\n");
	fprintf(f, "\n");
	
	fprintf(f, " <symbol id=\"strokes\" width=\"4\" height=\"4\" viewBox=\"-2 -2 4 4\" x=\"-2\" y=\"-2\">\n");
	fprintf(f, "  <path d=\"M-1.5,-1.5 C -1.75,-0.5 -1.25,0.5 -1.5,1.5 M0,-1.75 C -0.2,-0.5 0.2,0.5 0,1.5   M1.5,-1.5 C 1.75,-0.5 1.25,0.5 1.5,1.5\"\n");
	fprintf(f, "  fill=\"none\" stroke=\"black\" stroke-width=\"0.25\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n\n");
	fprintf(f, "\n");
	fprintf(f, " <symbol id=\"stone1\" width=\"2\" height=\"2\" viewBox=\"-1 -1 2 2\" x=\"-1\" y=\"-1\">\n");
	fprintf(f, "  <path d=\"M -0.66 -0.7 Q -0.96 -0.45 -0.88 0.17 Q -0.9 0.4 -0.5 0.63 Q 0.065 0.87 0.44 0.76 C 0.9 0.56 1 -0.78 0.59 -0.8 C 0.15 -0.87 -0.54 -1.01 -0.66 -0.7 Z\" \n");
	fprintf(f, "   fill=\"white\" stroke=\"black\" stroke-width=\"0.25\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol> \n");
	fprintf(f, "\n");
	fprintf(f, " <symbol id=\"stone2\" width=\"2\" height=\"2\" viewBox=\"-1 -1 2 2\" x=\"-1\" y=\"-1\">\n");
	fprintf(f, "  <path d=\"M -0.34 -0.79 Q -0.69 -0.53 -0.73 -0.29 Q -0.73 -0.05 -0.47 0.14 Q -0.33 0.37 0.05 0.33 C 0.53 -0.05 0.62 -0.41 0.16 -0.65 C 0.15 -0.87 -0.23 -0.92 -0.34 -0.79 Z M 0.61 0.22 C 0.44 0.12 0.22 0.28 0.24 0.56 C 0.29 0.88 0.56 0.84 0.69 0.69 C 0.7333 0.5667 0.7767 0.4433 0.61 0.22\" \n");
	fprintf(f, "   fill=\"white\" stroke=\"black\" stroke-width=\"0.25\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, "\n");
	fprintf(f, " <symbol id=\"stone3\" width=\"2\" height=\"2\" viewBox=\"-1 -1 2 2\" x=\"-1\" y=\"-1\">\n");
	fprintf(f, "  <path d=\"M -0.57 -0.41 Q -0.89 -0.15 -0.88 0.17 Q -0.77 0.57 -0.27 0.47 Q 0.28 0.58 0.46 0.37 C 0.62 0.23 0.73 -0.1 0.46 -0.41 C 0.28 -0.64 -0.15 -0.85 -0.56 -0.41\" \n");
	fprintf(f, "   fill=\"white\" stroke=\"black\" stroke-width=\"0.25\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, "\n");
	fprintf(f, " <symbol id=\"door-floor\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 0 0 L 3 0 L 3 1.3 L 7 1.3 L 7 0.01 L 10 0 L 10 10 L 7 10 L 7 8.7 L 3 8.7 L 3 10 L 0 10 Z\" \n");
	fprintf(f, "   fill=\"white\" stroke=\"none\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, "\n");
	fprintf(f, " <symbol id=\"doorway-floor\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 2 0 L 2 2 L 0 2 L 0 10 L 10 10 L 10 2 L 8 2 L 8 0 Z \" \n");
	fprintf(f, "   fill=\"white\" stroke=\"none\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " <symbol id=\"doorway\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 0 0 C 0.46 0.07 0.77 -0.07 2 0 C 2.07 0.27 1.92 0.43 2 2 C 1.43 1.92 1.21 2.03 0 2 C 0.07 2.9 -0.14 4.05 0 10 M 10 10 C 9.83 3.45 10.1 2.91 10 2 C 8.64 1.87 8.51 2.03 8 2 C 8.12 0.62 7.93 0.33 8 0 C 9.21 -0.07 9.31 0.07 10 0 \" \n");
	fprintf(f, "   fill=\"none\" stroke=\"black\" stroke-width=\"0.5\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " <symbol id=\"secret-door\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 0 0 C 0.46 0.07 0.77 -0.07 2 0 C 2.07 0.27 1.92 0.43 2 2 C 1.43 1.92 1.21 2.03 0 2 C 0.07 2.9 -0.14 4.05 0 10 M 10 10 C 9.83 3.45 10.1 2.91 10 2 C 8.64 1.87 8.51 2.03 8 2 C 8.12 0.62 7.93 0.33 8 0 C 9.21 -0.07 9.31 0.07 10 0 M 2 1 C 5 -2 5 4 8 1\" \n");
	fprintf(f, "   fill=\"none\" stroke=\"black\" stroke-width=\"0.5\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, "\n");
	fprintf(f, " <symbol id=\"door\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 0 0 C 2.1 0.17 2.53 0.12 2.94 0.03 C 2.99 0.51 3.02 0.87 2.99 1.36 C 4.16 1.3 6.05 1.35 7 1.39 C 7.03 0.84 7.01 0.42 6.96 0.04 C 8.22 -0.08 8.95 0.12 10 0 M 10 10 C 7.94 9.96 7.31 9.96 6.93 9.98 C 6.85 9.36 6.83 8.95 6.9 8.51 C 5.04 8.48 4.29 8.53 3.01 8.58 C 3.04 8.93 3.12 9.47 3.09 10.04 C 2.76 10.08 1.26 9.82 0 10 M 3.59 1.35 C 3.58 5.91 3.67 7.09 3.66 8.51 M 6.52 8.46 C 6.51 6.54 6.33 3.25 6.31 1.38 M 3.64 5.09 C 5.1 5.07 5.36 5.12 6.44 5.06\" \n");
	fprintf(f, "   fill=\"none\" stroke=\"black\" stroke-width=\"0.5\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol> \n");
	fprintf(f, "\n");
	fprintf(f, " <symbol id=\"stairs\" width=\"12\" height=\"12\" viewBox=\"-6 -6 12 12\">\n");
	fprintf(f, "  <path d=\"M -3.86 -3.8 C -1.31 -3.77 1.61 -3.67 4.23 -3.7 M -1.67 3.19 C -0.45 3.16 0.75 3.19 1.68 3.29 M -3.16 -1.39 C -0.9433 -1.4667 1.0133 -1.4733 3.35 -1.51 M -2.43 0.97 C -0.97 0.86 1.05 0.89 2.45 0.91\" \n");
	fprintf(f, "   fill=\"none\" stroke=\"black\" stroke-width=\"0.5\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, "\n");
	fprintf(f, " <symbol id=\"cobwebs\" width=\"12\" height=\"12\" viewBox=\"-6 -6 12 12\">\n");
	fprintf(f, "  <path d=\"M -5 -5 M -5 -5 M -5 -5 C -4.51 -3.32 -3.86 -1.71 -3.37 -0.02 M -5 -5 C -4.01 -3.48 -2.8 -2.01 -1.95 -0.71 M -5 -5 C -3.43 -4.04 -2 -2.8 -0.77 -1.97 M -5 -5 C -3.35 -4.62 -1.78 -4.05 -0.21 -3.61 M -4.98 -0.56 C -4.74 -1.19 -4.33 -1.57 -3.75 -1.19 C -3.6 -1.75 -3.37 -1.9 -2.76 -1.85 C -2.79 -2.55 -2.42 -2.69 -1.94 -2.85 C -2 -3.4 -1.72 -3.76 -1.03 -3.86 C -1.5 -4.44 -1.38 -4.78 -0.92 -4.99 M -5.04 -2.65 C -4.85 -3.12 -4.62 -3.12 -4.29 -2.83 C -4.22 -3.16 -4.08 -3.4 -3.69 -3.14 C -3.63 -3.6 -3.49 -3.75 -3.14 -3.76 C -3.3 -4.11 -3.19 -4.34 -2.85 -4.4 C -3.07 -4.72 -3.05 -4.9 -2.67 -5.01\" \n");
	fprintf(f, "   fill=\"none\" stroke=\"black\" stroke-width=\"0.25\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, "\n");
	fprintf(f, " <symbol id=\"statue\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 1.58 4.88 C 1.39 3.5 3.32 1.79 5.08 2.06 C 6.56 2.23 7.33 3.04 7.7 4.69 C 7.58 8.01 5.18 7.56 4.9 7.64 C 3.9 7.53 2.22 7.34 1.95 5\" \n");
	fprintf(f, "   fill=\"none\" stroke=\"black\" stroke-width=\"0.5\" stroke-linecap=\"round\"/>\n");
	fprintf(f, "  <path d=\"M 5.01 2 c -0.55 0.38 -0.62 1.84 -0.87 1.83 C 3.19 3.88 1.83 3.76 1.73 3.93 C 1.69 4.36 3.69 5.04 3.48 5.24 C 3.61 5.49 2.87 7.18 3.09 7.37 C 3.67 7.55 4.64 5.92 4.88 5.94 C 5.09 5.7 6.56 7.31 6.8 7.2 C 6.99 6.95 6.14 5.28 6.38 5.2 C 6.66 4.79 7.33 4.5 7.61 3.9 C 7.46 3.82 5.72 4.09 5.68 3.86 C 5.39 3.5 5.26 1.81 5.02 2\" \n");
	fprintf(f, "   stroke=\"none\" fill=\"black\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, "\n");
	
	
	fprintf(f, " <symbol id=\"crack-t\" width=\"12\" height=\"12\" viewBox=\"-1 -1 12 12\">\n");
	fprintf(f, "  <path d=\"M 4.19 0 C 2.91 1.02 2.79 0.98 2.2 1.49 C 3.22 1.93 3.67 2.25 4.48 2.83 C 4.1 3.17 2.56 3.98 2.6 4.1 C 3.51 6.25 4.04 7.15 4.13 7.04 C 3.84 5.84 3.42 4.98 3.19 4.17 C 4.13 3.65 4.85 3.12 5.26 2.9 C 4.84 2.37 4.35 1.85 3.71 1.36 C 3.87 1.15 5.49 0.46 6.19 0\" \n");
	fprintf(f, "  fill=\"black\" stroke=\"none\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, "\n");
	fprintf(f, " <symbol id=\"pillar\" width=\"10\" height=\"10\" viewBox=\"-3 -3 10 10\" x=\"-3\" y=\"-3\">\n");
	fprintf(f, "  <path d=\"M 0.08 -2.44 C -1.5 -2.35 -1.98 -1.48 -2.19 -0.03 C -2.05 1.32 -1.28 2.02 0.04 2.18 C 1.2 2.07 2.31 1 2.3 0 C 2.16 -1.22 1.65 -2.14 -0.05 -2.3\" \n");
	fprintf(f, "  fill=\"#EEE\" stroke=\"black\" stroke-width=\"0.5\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n");
	fprintf(f, " </defs>\n\n");

	for(i = 0; i < P.n_points; i++) {
		float sx = frand()*0.1 + 0.9;
		float sy = frand()*0.1 + 0.9;
		fprintf(f, " <use href=\"#blobs\" transform=\"translate(%.2f %.2f) rotate(%d) scale(%.2f %.2f)\"/>\n", P.points[i].x, P.points[i].y, ((i*60) + D_RAND(30) - 15)%360, sx, sy);
	}
	for(i = 0; i < P.n_points; i++) {
		float sx = frand()*0.1 + 0.9;
		float sy = frand()*0.1 + 0.9;
		fprintf(f, " <use href=\"#strokes\" transform=\"translate(%.2f %.2f) rotate(%d) scale(%.2f %.2f)\"/>\n", P.points[i].x, P.points[i].y, ((i*60) + D_RAND(30) - 15)%360, sx, sy);
	}
	poisson_done(&P);

	for(j = 0; j < M->map_h; j++) {
		for(i = 0; i < M->map_w; i++) {
			char tile = d_get_tile(M, i,j);
			if(tile == 'D') {
				D_Edge *edge = d_corridor_at(M, i, j);
				assert(edge);
				if(edge->direction == D_ORIENT_EW) {
					fprintf(f, " <use href=\"#door-floor\" transform=\"translate(%d %d)\"/>\n", i * 10, j * 10);
				} else {
					fprintf(f, " <use href=\"#door-floor\" transform=\"translate(%d %d) rotate(90 6 6)\"/>\n", i * 10, j * 10);
				}
			} else if(tile == D_TILE_SECRET){
				int rot = 0, t;
				D_Edge *edge = d_corridor_at(M, i, j);
				assert(edge);
				if(edge->direction == D_ORIENT_EW) {
					if(edge->w == 1) {
						D_Room *r = d_room_at(M, i+1, j);
						assert(r);
						if(r->flags & D_FLAG_SECRET_ROOM)
							rot = -90;
						else
							rot = 90;
					} else if((t = d_get_tile(M, i+1, j)) == D_TILE_FLOOR || t == D_TILE_CROSSING)
						rot = 90;
					else if((t = d_get_tile(M, i-1, j)) == D_TILE_FLOOR || t == D_TILE_CROSSING)
						rot = -90;
				} else {
					if(edge->h == 1) {
						D_Room *r = d_room_at(M, i, j + 1);
						assert(r);
						if(r->flags & D_FLAG_SECRET_ROOM)
							rot = 0;
						else
							rot = 180;
					} else if((t = d_get_tile(M, i, j - 1)) == D_TILE_FLOOR || t == D_TILE_CROSSING)
						rot = 0;
					else if((t = d_get_tile(M, i, j + 1)) == D_TILE_FLOOR || t == D_TILE_CROSSING)
						rot = 180;
				}
				fprintf(f, " <use href=\"#doorway-floor\" transform=\"translate(%d %d) rotate(%d 6 6)\"/>\n", i * 10, j * 10, rot);
			} else if(tile == 't') {
				int rot = 0;
				if(d_get_tile(M, i, j + 1) == D_TILE_FLOOR)
					rot = 180;
				if(d_get_tile(M, i+1, j) == D_TILE_FLOOR)
					rot = 90;
				if(d_get_tile(M, i-1, j) == D_TILE_FLOOR)
					rot = -90;
				fprintf(f, " <use href=\"#doorway-floor\" transform=\"translate(%d %d) rotate(%d 6 6)\"/>\n", i * 10, j * 10, rot);
			} else if(!d_is_wall(M, i,j)) {
				fprintf(f, " <use href=\"#floor\" transform=\"translate(%d %d)\"/>\n", i * 10, j * 10);
			}
		}
	}

	for(j = 0; j < M->map_h; j++) {
		for(i = 0; i <M->map_w; i++) {
			char tile = d_get_tile(M, i,j);
			if(d_is_wall(M, i,j))
				continue;

			fprintf(f, " <g transform=\"translate(%d %d)\">\n", i * 10, j * 10);
			if(tile == '@') {
				int rot = 0, t;
				if((t = d_get_tile(M, i, j + 1)) == D_TILE_FLOOR || t == D_TILE_FLOOR_EDGE) {

					if((t = d_get_tile(M, i+1, j)) == D_TILE_FLOOR || t == D_TILE_FLOOR_EDGE) {
						/* The entrance is a hole in the ceiling */
						fprintf(f, "  <use href=\"#wall-l\"/><use href=\"#wall-r\"/><use href=\"#wall-t\"/>\n");
						rot = 0;
					} else {
						fprintf(f, "  <use href=\"#wall-l\"/><use href=\"#wall-r\"/>\n");
						rot = 0;
					}
				} else if((t = d_get_tile(M, i, j - 1)) == D_TILE_FLOOR || t == D_TILE_FLOOR_EDGE) {
					fprintf(f, "  <use href=\"#wall-l\"/><use href=\"#wall-r\"/>\n");
					rot = 180;
				} else if((t = d_get_tile(M, i + 1, j)) == D_TILE_FLOOR || t == D_TILE_FLOOR_EDGE) {
					fprintf(f, "  <use href=\"#wall-t\"/><use href=\"#wall-b\"/>\n");
					rot = -90;
				} else if((t = d_get_tile(M, i - 1, j)) == D_TILE_FLOOR || t == D_TILE_FLOOR_EDGE) {
					fprintf(f, "  <use href=\"#wall-t\"/><use href=\"#wall-b\"/>\n");
					rot = 90;
				}
				fprintf(f, "  <use href=\"#stairs\" transform=\"rotate(%d 6 6)\"/>\n", rot);
			} else if(tile == '$') {
				int rot = 0, t;
				if((t = d_get_tile(M, i, j + 1)) == D_TILE_FLOOR || t == D_TILE_FLOOR_EDGE) {
					if((t = d_get_tile(M, i+1, j)) == D_TILE_FLOOR || t == D_TILE_FLOOR_EDGE) {
						/* The exit is just a hole in the floor */
						fprintf(f, "  <use href=\"#wall-l\"/><use href=\"#wall-r\"/><use href=\"#wall-b\"/>\n");
						rot = 0;
					} else {
						fprintf(f, "  <use href=\"#wall-l\"/><use href=\"#wall-r\"/>\n");
						rot = 180;
					}
				} else if((t = d_get_tile(M, i, j - 1)) == D_TILE_FLOOR || t == D_TILE_FLOOR_EDGE) {
					fprintf(f, "  <use href=\"#wall-l\"/><use href=\"#wall-r\"/>\n");
					rot = 0;
				} else if((t = d_get_tile(M, i + 1, j)) == D_TILE_FLOOR || t == D_TILE_FLOOR_EDGE) {
					fprintf(f, "  <use href=\"#wall-t\"/><use href=\"#wall-b\"/>\n");
					rot = 90;
				} else if((t = d_get_tile(M, i - 1, j)) == D_TILE_FLOOR || t == D_TILE_FLOOR_EDGE) {
					fprintf(f, "  <use href=\"#wall-t\"/><use href=\"#wall-b\"/>\n");
					rot = -90;
				}
				fprintf(f, "  <use href=\"#stairs\" transform=\"rotate(%d 6 6)\"/>\n", rot);
			} else if(tile == 'S') {
				fprintf(f, "  <use href=\"#statue\" transform=\"rotate(%d 6 6)\"/>\n", D_RAND(360));
			} else if(tile == D_TILE_SECRET) {
				int rot = 0, t;
				D_Edge *edge = d_corridor_at(M, i, j);
				assert(edge);
				if(edge->direction == D_ORIENT_EW) {
					if(edge->w == 1) {
						D_Room *r = d_room_at(M, i+1, j);
						assert(r);
						if(r->flags & D_FLAG_SECRET_ROOM)
							rot = -90;
						else
							rot = 90;
					} else if((t = d_get_tile(M, i+1, j)) == D_TILE_FLOOR || t == D_TILE_CROSSING)
						rot = 90;
					else if((t = d_get_tile(M, i-1, j)) == D_TILE_FLOOR || t == D_TILE_CROSSING)
						rot = -90;
				} else {
					if(edge->h == 1) {
						D_Room *r = d_room_at(M, i, j + 1);
						assert(r);
						if(r->flags & D_FLAG_SECRET_ROOM)
							rot = 0;
						else
							rot = 180;
					} else if((t = d_get_tile(M, i, j - 1)) == D_TILE_FLOOR || t == D_TILE_CROSSING)
						rot = 0;
					else if((t = d_get_tile(M, i, j + 1)) == D_TILE_FLOOR || t == D_TILE_CROSSING)
						rot = 180;
				}
				fprintf(f, " <use href=\"#secret-door\" transform=\"rotate(%d 6 6)\"/>\n", rot);
			} else if(tile == 't') {
				int rot = 0;
				if(d_get_tile(M, i, j + 1) == D_TILE_FLOOR)
					rot = 180;
				if(d_get_tile(M, i + 1, j) == D_TILE_FLOOR)
					rot = 90;
				if(d_get_tile(M, i - 1, j) == D_TILE_FLOOR)
					rot = -90;
				fprintf(f, " <use href=\"#doorway\" transform=\"rotate(%d 6 6)\"/>\n", rot);
			} else if(tile == 'D') {
				D_Edge *edge = d_corridor_at(M, i, j);
				assert(edge);
				if(edge->direction == D_ORIENT_EW) {
					fprintf(f, "  <use href=\"#door\"/>\n");
				} else {
					fprintf(f, "  <use href=\"#door\" transform=\"rotate(90 6 6)\"/>\n");
				}
			} else {
				int r = D_RAND(100);
				if(d_is_wall(M, i - 1, j))
					fprintf(f, "  <use href=\"#wall-l\"/>\n");
				if(d_is_wall(M, i + 1, j))
					fprintf(f, "  <use href=\"#wall-r\"/>\n");
				if(d_is_wall(M, i, j - 1))
					fprintf(f, "  <use href=\"#wall-t\"/>\n");
				if(d_is_wall(M, i, j + 1))
					fprintf(f, "  <use href=\"#wall-b\"/>\n");

				if(r < 4) {
					float sx = frand()*0.1 + 0.9;
					float sy = frand()*0.1 + 0.9;
					fprintf(f, " <use href=\"#stone1\" transform=\"translate(%.2f %.2f) rotate(%d) scale(%.2f %.2f)\"/>\n", frand()*7.0+2.0, frand()*7.0+2.0, D_RAND(360) - 180, sx, sy);
				} else if(r < 8) {
					float sx = frand()*0.1 + 0.9;
					float sy = frand()*0.1 + 0.9;
					fprintf(f, " <use href=\"#stone2\" transform=\"translate(%.2f %.2f) rotate(%d) scale(%.2f %.2f)\"/>\n", frand()*7.0+2.0, frand()*7.0+2.0, D_RAND(360) - 180, sx, sy);
				} else if(r < 12) {
					float sx = frand()*0.1 + 0.9;
					float sy = frand()*0.1 + 0.9;
					fprintf(f, " <use href=\"#stone3\" transform=\"translate(%.2f %.2f) rotate(%d) scale(%.2f %.2f)\"/>\n", frand()*7.0+2.0, frand()*7.0+2.0, D_RAND(360) - 180, sx, sy);
				}

			}
			if(!d_is_wall(M, i + 1, j))
				fprintf(f, "  <use href=\"#floor-r%c\"/>\n",(i+j)%3 + '1');
			if(!d_is_wall(M, i, j + 1))
				fprintf(f, "  <use href=\"#floor-b%c\"/>\n",(i+j)%3 + '1');
			fprintf(f, " </g>\n");
		}
	}

	/* Random cobwebs */
	for(i = 0; i < 3; i++) {
		r = d_random_room(M);
		switch(D_RAND(4)) {
			case 0:
				if(d_get_tile(M, r->x, r->y) == D_TILE_FLOOR_EDGE) {
					fprintf(f, " <use href=\"#cobwebs\" transform=\"translate(%d %d)\"/>\n", r->x * 10, r->y * 10);
					d_set_tile(M, r->x, r->y, 'X');
				} else
					i--;
				break;
			case 1:
				if(d_get_tile(M, r->x + r->w - 1, r->y) == D_TILE_FLOOR_EDGE) {
					fprintf(f, " <use href=\"#cobwebs\" transform=\"translate(%d %d) rotate(90 6 6)\"/>\n", (r->x + r->w - 1) * 10, r->y * 10);
					d_set_tile(M, r->x + r->w - 1, r->y, 'X');
				} else
					i--;
				break;
			case 2:
				if(d_get_tile(M, r->x + r->w - 1, r->y + r->h - 1) == D_TILE_FLOOR_EDGE) {
					fprintf(f, " <use href=\"#cobwebs\" transform=\"translate(%d %d) rotate(180 6 6)\"/>\n", (r->x + r->w - 1) * 10, (r->y + r->h - 1) * 10);
					d_set_tile(M, r->x + r->w - 1, r->y + r->h - 1, 'X');
				} else
					i--;
				break;
			case 3:
				if(d_get_tile(M, r->x, r->y + r->h - 1) == D_TILE_FLOOR_EDGE) {
					fprintf(f, " <use href=\"#cobwebs\" transform=\"translate(%d %d) rotate(-90 6 6)\"/>\n", r->x * 10, (r->y + r->h - 1) * 10);
					d_set_tile(M, r->x, r->y + r->h - 1, 'X');
				}
				else
					i--;
				break;
		}
	}
	
	/* Random cracks */
	for(i = 0; i < 3; i++) {
		r = d_random_room(M);
		switch(D_RAND(4)) {
			case 0:
				j = r->x + D_RAND(r->w);
				if(d_get_tile(M, j, r->y) == D_TILE_FLOOR_EDGE) {
					fprintf(f, " <use href=\"#crack-t\" transform=\"translate(%d %d)\"/>\n", j * 10, r->y * 10);
					d_set_tile(M, j, r->y, 'X');
				} else
					i--;
				break;
			case 1:
				j = r->y + D_RAND(r->h);
				if(d_get_tile(M, r->x + r->w - 1, j) == D_TILE_FLOOR_EDGE) {
					fprintf(f, " <use href=\"#crack-t\" transform=\"translate(%d %d) rotate(90 6 6)\"/>\n", (r->x + r->w - 1) * 10, j * 10);
					d_set_tile(M, r->x + r->w - 1, j, 'X');
				} else
					i--;
				break;
			case 2:
				j = r->x + D_RAND(r->w);
				if(d_get_tile(M, j, r->y + r->h - 1) == D_TILE_FLOOR_EDGE) {
					fprintf(f, " <use href=\"#crack-t\" transform=\"translate(%d %d) rotate(180 6 6)\"/>\n", j * 10, (r->y + r->h - 1) * 10);
					d_set_tile(M, j, r->y + r->h - 1, 'X');
				} else
					i--;
				break;
			case 3:
				j = r->y + D_RAND(r->h);
				if(d_get_tile(M, r->x, j) == D_TILE_FLOOR_EDGE) {
					fprintf(f, " <use href=\"#crack-t\" transform=\"translate(%d %d) rotate(-90 6 6)\"/>\n", r->x * 10, j * 10);
					d_set_tile(M, r->x, j, 'X');
				}
				else
					i--;
				break;
		}
	}
	
	/* Room with pillars */
	do {
		r = d_random_room(M);
	} while(r->flags & (D_FLAG_START_ROOM | D_FLAG_END_ROOM | D_FLAG_GONE_ROOM) || (r->w * r->h < 8));
	for(i = 1; i < r->w; i++) 
		for(j = 1; j < r->h; j++) {
			fprintf(f, " <use href=\"#pillar\" transform=\"translate(%d %d) rotate(%d)\"/>\n", (r->x + i) * 10 + 1, (r->y + j) * 10 + 1, D_RAND(360));
		}

	fprintf(f, "</svg>\n");
}

int main(int argc, char *argv[]) {
	FILE *f;
	int seed;
	D_Dungeon M;

	if(argc > 1)
		seed = atoi(argv[1]);
	else {
		seed = time(NULL);
	}
	srand(seed);

	printf("Seed: %d\n", seed);

	d_init(&M);

	M.grid_w = 4;
	M.grid_h = 4;

	d_generate(&M);

	d_draw(&M, stdout);

	f = fopen("map.svg","w");
	if(f) {
		drawSvg(&M, f);
		fclose(f);
	} else {
		fprintf(stderr, "Unable to save SVG");
	}

	printf("Seed: %d", seed);

	d_deinit(&M);

	return 0;
}

poisson.c

/*
 * Implementation of Poisson Disk Sampling for a series of 2D points.
 *
 * I used this article as reference [Poisson Disk Sampling in Processing][pdsp]
 *
 * [pdsp]: https://sighack.com/post/poisson-disk-sampling-bridsons-algorithm
 */
#ifndef POISSON_H
#define POISSON_H

struct point {
	float x, y;
};

struct poisson;

typedef int (*poisson_constraint)(struct poisson *P, float x, float y);

struct poisson {
	int	k;
	float r;
	int w, h;
	struct point x0;
	short n_points;
	struct point *points;
	void *data;
	poisson_constraint constraint;
};

void poisson_init(struct poisson *P);

int poisson_plot(struct poisson *P);

void poisson_done(struct poisson *P);

#if defined(POISSON_TEST) && !defined(POISSON_IMPLEMENTATION)
# define POISSON_IMPLEMENTATION
#endif

#ifdef POISSON_IMPLEMENTATION

#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <assert.h>

#ifndef P_W0
# define P_W0	100
#endif

#ifndef P_H0
# define P_H0	100
#endif

#ifndef P_R0
# define P_R0	5.0
#endif

#ifndef P_K0
# define P_K0	30
#endif

#define N	2

void poisson_init(struct poisson *P) {
	/* These are set to sensible defaults,
	but you're allowed to change them: */

	P->k = P_K0;
	P->r = P_R0;

	P->w = P_W0;
	P->h = P_H0;

	P->x0.x = rand() % P->w;
	P->x0.y = rand() % P->h;

	P->constraint = NULL;
	P->data = 0;

	/* Don't change these: */
	P->n_points = 0;
	P->points = NULL;
}

void poisson_done(struct poisson *P) {
	if(P->points)
		free(P->points);
	P->points = NULL;
	P->n_points = 0;
}

/* Used internally */
struct generator {
	struct poisson *P;

	short *grid;
	short grid_size, grid_w, grid_h;
	short *active_list;
	short n_active;
	float cell_size;
};

static short _p_insert_point(struct generator *G, float x, float y) {
	short index, gx, gy;

	gx = floor(x/G->cell_size);
	gy = floor(y/G->cell_size);

	index = gy * G->grid_w + gx;
	assert(index < G->grid_size);
	G->grid[index] = G->P->n_points;

	assert(G->P->n_points < G->grid_size);
	index = G->P->n_points++;
	G->P->points[index].x = x;
	G->P->points[index].y = y;

	return index;
}

static float _p_frand() {
	return ((float)rand())/RAND_MAX;
}

#define MAX(a,b) ((a) > (b)? (a) : (b))
#define MIN(a,b) ((a) < (b)? (a) : (b))

static float dist(float x0, float y0, float x1, float y1) {
	float dx = x1 - x0, dy = y1 - y0;
	return sqrt(dx * dx + dy * dy);
}

static int _p_is_valid_point(struct generator *G, float px, float py) {
	short gx, gy, i0, i1, j0, j1, i, j;
	struct poisson *P = G->P;

	if(px < 0 || px >= P->w || py < 0 || py >= P->h) return 0;

	if(P->constraint)
		if(!P->constraint(P, px, py))
			return 0;

	gx = floor(px / G->cell_size);
	gy = floor(py / G->cell_size);

	/* Note to self: I did see some cases where the constraint that no two
	 * points should be closer than R is being violated, and I suspect that
	 * what's happening is that they are just placed so that there ends up
	 * being a empty grid cell between them. This implies some misunderstanding
	 * on my part, but I've decided I can live with it. If you can't live with
	 * it, changing the +/-1s below to +/-2 works around the issue.
	 */
	i0 = MAX(gx - 1, 0);
	i1 = MIN(gx + 1, G->grid_w - 1);
	j0 = MAX(gy - 1, 0);
	j1 = MIN(gy + 1, G->grid_h - 1);

	for(i = i0; i <= i1; i++)
		for(j = j0; j <= j1; j++) {
			short t = G->grid[j * G->grid_w + i];
			if(t >= 0) {
				struct point *q = &G->P->points[t];
				if(dist(px, py, q->x, q->y) < P->r)
					return 0;
			}
		}

	return 1;
}

int poisson_plot(struct poisson *P) {
	short i, k;
	struct generator G;

	G.P = P;

	/* Note to self: I found that if you use `floor()` as in the [pdsp][]
	article, then some of the points end up violating the contstraints */
	G.cell_size = ceil((float)P->r / sqrt(N));

	G.grid_w = ceil((float)P->w / G.cell_size) + 1;
	G.grid_h = ceil((float)P->h / G.cell_size) + 1;
	G.grid_size = G.grid_w * G.grid_h;

	P->n_points = 0;

	G.grid = malloc(G.grid_size * sizeof *G.grid);
	if(!G.grid) {
		fprintf(stderr, "no memory\n");
		return 0;
	}
	for(i = 0; i < G.grid_size; i++)
		G.grid[i] = -1;

	G.active_list = malloc(G.grid_size * sizeof *G.active_list);
	if(!G.active_list) {
		free(G.grid);
		fprintf(stderr, "no memory\n");
		return 0;
	}
	G.n_active = 0;

	P->points = malloc(G.grid_size * sizeof *P->points);
	if(!P->points) {
		free(G.grid);
		free(G.active_list);
		fprintf(stderr, "no memory\n");
		return 0;
	}

	i = _p_insert_point(&G, P->x0.x, P->x0.y);
	G.active_list[G.n_active++] = i;

	while(G.n_active > 0) {
		short ax = rand() % G.n_active;
		short a = G.active_list[ax];
		struct point *p = &P->points[a];

		for(k = 0; k < P->k; k++) {
			float th = ((float)(rand() % 360)) * M_PI / 180;
			float rad = (_p_frand() * 2.0 + 1.0) * P->r;

			float nx = p->x + rad * cos(th);
			float ny = p->y + rad * sin(th);

			if(!_p_is_valid_point(&G, nx, ny))
				continue;

			i = _p_insert_point(&G, nx, ny);
			assert(G.n_active < G.grid_size);
			G.active_list[G.n_active++] = i;
			break;
		}
		if(k == P->k) {
			/* No point found - remove the point from the
			active list by replacing it with the last one in the
			list, and decrementing the counter */
			G.active_list[ax] = G.active_list[--G.n_active];
		}
	}
	free(G.grid);
	free(G.active_list);

	return 1;
}

#endif /* POISSON_IMPLEMENTATION */

#ifdef POISSON_TEST

#include <stdio.h>

static int circle_constraint(struct poisson *P, float x, float y) {
	return dist(P->x0.x, P->x0.y, x, y) < 20;
}

int main(int argc, char* argv[]) {
	FILE *f = stdout;
	int i;

	struct poisson P;

	(void)argc; (void)argv;

	srand(time(NULL));

	poisson_init(&P);
	P.r = 3.0;
	P.x0.x = 50;
	P.x0.y = 60;
	P.constraint = circle_constraint;

	if(!poisson_plot(&P)) {
		return 1;
	}

	fprintf(f, "<svg viewBox=\"0 0 %d %d\" xmlns=\"http://www.w3.org/2000/svg\">\n", P.w, P.h);

#if 0
	fprintf(f, " <symbol id=\"strokes\" width=\"30\" height=\"30\" viewBox=\"-15 -15 30 30\" x=\"-15\" y=\"-15\">\n");
	fprintf(f, "   <circle cx=\"0\" cy=\"0\" r=\"%g\" fill=\"red\" opacity=\"0.1\"/>\n", P_R0);
	fprintf(f, "   <circle cx=\"0\" cy=\"0\" r=\"1\" fill=\"black\"/>\n");
	fprintf(f, " </symbol>\n\n");
#else
	fprintf(f, " <symbol id=\"strokes\" width=\"4\" height=\"4\" viewBox=\"-2 -2 4 4\" x=\"-2\" y=\"-2\">\n");
	fprintf(f, "  <path d=\"M-1.5,-1.5 v3 M0,-1.75 v3.5 M1.5,-1.5 v3\" fill=\"none\" stroke-width=\"0.3\" stroke=\"gray\" stroke-linecap=\"round\"/>\n");
	fprintf(f, " </symbol>\n\n");
#endif


	for(i = 0; i < P.n_points; i++) {
		float sx = _p_frand()*0.1 + 0.9;
		float sy = _p_frand()*0.1 + 0.9;
		fprintf(f, " <use href=\"#strokes\" transform=\"translate(%.2f %.2f) rotate(%d) scale(%.2f %.2f)\"/>\n", P.points[i].x, P.points[i].y, rand()%360 - 180, sx, sy);
	}

	fprintf(f, "</svg>\n");

	poisson_done(&P);

	return 0;
}

#endif /* POISSON_TEST */
#endif /* POISSON_H */