Just a simple maze generator

gistfile1.cpp

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);
};

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


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) {
		// TODO
	}
	for(int i = 0; i < h; ++i) {
		// TODO
	}

	// 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 ); // 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 );
		*mark |= 1;

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

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

		target = queue + load;
		tmp = pos + 1; // (1, 0)
		target->x = x + 1;
		target->y = y;
		load += ~( (*mark) & 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 );
		*mark |= 1;

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

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

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

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