RealDev

So, today, I took a break from studying, and decided to try working on my own random dungeon generation. My goal was simple. Create 3 random rooms, and connect them. My limitations were also simple, do it in C++, do it will minimal algorithmic implementation (as in A* and the likes thereof). The end result I am quite happy with:

The first steps are quite easy, as part of the required code, I figured a Rectangle object would make sense to have (for simpler storage of the 3 rooms I generated), and as part of this implementation I build two helper functions, one to check if a point is in a rectangle, and another to check if two rectangles intersect. I also build a function that returns a random integer of a certain max value "Next":

struct Rectangle
{
public:
	int X, Y, W, H;
};

bool Inside(Rectangle *rect, int x, int y)
{
	return (x >= rect->X && 
		    x <= rect->X + rect->W && 
		    y >= rect->Y && 
		    y <= rect->Y + rect->H);
}

bool Intersects(Rectangle *rect1, Rectangle *rect2)
{
	return (rect1->X < rect2->X + rect2->W && 
	        rect1->X + rect1->W > rect2->X &&
		rect1->Y < rect2->Y + rect2->H && 
		rect1->Y + rect1->H > rect2->Y); 
}

int Next(int max)
{
	return rand() % max;
}

My algorithm for the generation worked in a simple manner. First, create 3 rooms (of size 32, 16 and 8 respectively) in my map (a 2D integer array), making sure when they are created that they do not intersect with any of the rooms created before the one currently being made.

		int map[64][64];

		int x, y;

		//first rectangle
		Rectangle r1;
		x = Next(64);
		y = Next(64);
		r1.X = x - 16;
		r1.Y = y - 16;
		r1.H = 32;
		r1.W = 32;

		//second rectangle
		Rectangle r2;
		r2.X = r1.X + 1;
		r2.Y = r1.Y + 1;
		r2.W = 16;
		r2.H = 16;
		//make sure that there is no intersection with r1
		while (Intersects(&r1,&r2))
		{
			r2.X = Next(64) - 8;
			r2.Y = Next(64) - 8;
		}

		//third triangle
		Rectangle r3;
		r3.X = r1.X + 1;
		r3.Y = r1.Y + 1;
		r3.W = 8;
		r3.H = 8;
		//make sure there is no intersection with r1 or r2
		while (Intersects(&r1,&r3) || Intersects(&r2,&r3))
		{
			r3.X = Next(64) - 4;
			r3.Y = Next(64) - 4;
		}

So far, so good, the next step is to fill my map in the areas inside the rectangles with the value 1. This is quite a trivial step. Next, I had to build paths between rectangle 1, and rectangle 2, then do the same between rectangle 2 and 3. I swapped the up-across from 1-to-2 to across-up from 2-to-3 (so the paths would follow different bends):

		int sm_x, lg_x;
		if ((r1.X + r1.W/2)<(r2.X + r2.W/2))
		{
			sm_x = (r1.X + r1.W/2);
			lg_x = (r2.X + r2.W/2);
		}
		else
		{
			sm_x = (r2.X + r2.W/2);
			lg_x = (r1.X + r1.W/2);
		}
		for (int i = sm_x - 1; i < lg_x + 1; i++)
		{
			map[i][r1.Y + r1.W/2 + 1] = 1;
			map[i][r1.Y + r1.W/2 - 1] = 1;
			map[i][r1.Y + r1.W/2] = 1;
		}
                [...]

		int lg_y, sm_y;
		if ((r1.Y + r1.H/2)<(r2.Y + r2.H/2))
		{
			sm_y = (r1.Y + r1.H/2);
			lg_y = (r2.Y + r2.H/2);
		}
		else
		{
			sm_y = (r2.Y + r2.H/2);
			lg_y = (r1.Y + r1.H/2);
		}
		for (int j = sm_y - 1; j < lg_y + 1; j++)
		{
			map[r2.X + r2.W/2 + 1][j] = 1;
			map[r2.X + r2.W/2 - 1][j] = 1;
			map[r2.X + r2.W/2][j] = 1;
		}
                [...]

Finally, do what you want with the map. This isn't the greatest algorithm or method by far, but if you made it more generic using arrays/lists you could easily generate quite complex and diverse maps. I hope this was at least of some minor interest to you.

The full code is available on my GitHub, and you can continue following my experimentation with the same code in my next post.