Just a simple maze generator

gistfile1.cpp

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

typedef struct {
	unsigned int x;
	unsigned int y;
} Coordinate;

class Dungeon {
	unsigned int _width;
	unsigned int _height;

	unsigned char *_data;

	public:
		void generate(int, int);
		void write(const char* filename);
};

#define QUEUE_SIZE 1024
#define CELL_MARKED 1
#define CELL_FLOOR 128
#define CELL_WALL 0

void Dungeon::generate(int w, int h) {
	Coordinate *queue = new Coordinate[w*h];
	unsigned int load = 0;
	unsigned char *d = new unsigned char[w*h];

	// data is not meant to be NULL, and is correct size and all stuff ...

	// Fill with walls.
	memset(d, 0, sizeof(char)*w*h);

	// Seed the maze with a point inside the border walls.
	queue[0].x = ( rand() % (w-2) ) + 1;
	queue[0].y = ( rand() % (h-2) ) + 1;
	load = 1;

	// Initialize so that borders are marked walls.
	for(int i = 0; i < w; ++i) {
		d[i] = d[i + (w*(h-1))] = CELL_MARKED;
	}
	for(int i = 0; i < h; ++i) {
		d[i*w] = d[(i*w)+(w-1)] = CELL_MARKED;
	}

	// As long as there's a wall in the list.
	while(load != 0) {
		unsigned int candidate = rand()%load;
		Coordinate *c = queue + candidate;
		unsigned int x = c->x;
		unsigned int y = c->y;
		unsigned int pos = (y * w) + x;
		// First, remove from the queue.
		memcpy(c, queue + load, sizeof(Coordinate));
		--load;
		// Mark the current cell.
		*(d + pos) = CELL_MARKED + CELL_FLOOR;
		// Add the surrounding
		// ## Unroll the whole double loop ? ... why not ...
		// When marking the wall, we're sure that we won't propagate
		// outside the maze as the border walls are already marked.
		unsigned int tmp;
		Coordinate *target;
		unsigned char *mark;

		target = queue + load;
		tmp = pos - w - 1; // (-1, -1)
		target->x = x - 1;
		target->y = y - 1;
		mark = d + tmp;
		load += ( (*mark) ^ 1 ) & 1; // If marked, it won't increment.
		*mark |= 1; // Mark the wall as visited.

		// Hence, if not marked, the end of the queue will be overwritten.
		target = queue + load;
		++tmp; // (0, -1)
		target->x = x;
		target->y = y - 1;
		load += ( (*mark) ^ 1 ) & 1;
		*mark |= 1;

		target = queue + load;
		++tmp; // (1, -1)
		target->x = x + 1;
		target->y = y - 1;
		load += ( (*mark) ^ 1 ) & 1;
		*mark |= 1;

		target = queue + load;
		tmp = pos - 1; // (-1, 0)
		target->x = x - 1;
		target->y = y;
		load += ( (*mark) ^ 1 ) & 1;
		*mark |= 1;

		target = queue + load;
		tmp = pos + 1; // (1, 0)
		target->x = x + 1;
		target->y = y;
		load += ( (*mark) ^ 1 ) & 1;
		*mark |= 1;

		target = queue + load;
		tmp = pos + w - 1; // (-1, 1)
		target->x = x - 1;
		target->y = y + 1;
		mark = d + tmp;
		load += ( (*mark) ^ 1 ) & 1;
		*mark |= 1;

		target = queue + load;
		++tmp; // (0, 1)
		target->x = x;
		target->y = y + 1;
		load += ( (*mark) ^ 1 ) & 1;
		*mark |= 1;

		target = queue + load;
		++tmp; // (1, 1)
		target->x = x + 1;
		target->y = y + 1;
		load += ( (*mark) ^ 1 ) & 1;
		*mark |= 1;
	}

	delete []queue;
	_width = w;
	_height = h;
	_data = d;

	// Done ! .... Wait ... no if ?? only one level loops ?
}

void Dungeon::write(const char* filename)
{
	FILE *out;
	out = fopen(filename, "wb");

	fprintf(out, "P5\n#\n%d %d\n255\n", _width, _height);
	fwrite(_data, 1, _width*_height, out);

	fclose(out);
}

int main()
{
	Dungeon donj;

	donj.generate(128, 128);

	donj.write("maze.pgm");

	return 0;
}