Random Dungeon generator - help please

[Andr0id]

I am having trouble getting my random dungeon generator working properly. I will try to explain how I WANT my algorithm to work, however i don't think it's working correctly. Or maybe its a flaw in the whole idea I'm not sure.

Step one: randomly choose map size between maximum size constant and min size constant
step two: assign the map values (size) to a new room structure
Step three: fill whole map with a specific tile type (for example stone)
Step four: clean up map array to remove any junk data (map array isn't dynamic yet so it might have unused tiles, so I need to make them blank so the map looks nicer)
Step five: find the center of the current map
step 6: generate a predefined number of random room width/height values and store in array
step 7: assign element 0 in room array to the room at the center of the map
step 8-1: begin a for loop lasting number of rooms iterations beginning at the second element in the room list.
step 8-2:generate random x,y values for the element currently being indexed by the for loop between 1 and the map width/height.
step 8-3: check if the number of placed rooms is above 0
else: currently still placing the first room (this is not the room at the center of the map)
in order to correctly place the room two checks need to be made. First check if the total area of the room is contained within the map. Then check if the current room intersects any previously placed rooms (in this instance there is only one other room the center room).
step 8-4: The index of the for loop is now on room 2, generate new x,y for this element. check the current room against all previously placed rooms and see if A: the current room intersects any previously placed rooms B: that the current rooms area is contained within the map. If either check fails then generate new x,y values for the current element and start over.

continue this process until all the rooms that can fit within the map without intersecting have been flagged as placed

step 9: actually update the map array from the room array.

step 10: write the map array to a file so it can be seen.

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

const int max_x = 500;
const int max_y = 500;
const char stone = '#';
const char dirt = '_';
const int wall_width = 1;
const int wall_height = 1;
const char staricase_up = 'U';
const char staricase_down = 'D';
const int MAXROOMS = 200;

struct ROOM{
	int x, y;
	int width, height;
	int room_id;
	bool placed;
};

ROOM gen_room()
{
	int x, y, width, height;
	width = ((int)(rand()%25)+5);
	height = ((int)(rand()%25)+5);
	x = y = 0;
	ROOM room;
	room.x = x;
	room.y = y;
	room.width = width;
	room.height = height;
	room.placed = false;
	return room;
}

bool valueInRange(int value, int min, int max);

bool valueInRangeEx(int value, int min, int max);

bool rectOverlap(ROOM A, ROOM B);

bool rectContains(ROOM A, ROOM B);

void generate_map2();

void update_map_file(FILE * pFile, char _map[][max_y]);

void place_all_rooms(int map_width, int map_height, char _map[][max_y], int number_of_rooms, ROOM list[], FILE *pFile);

int main()
{
	generate_map2();
	return 0;
}

void generate_map2()
{
	int number_of_rooms = 0;
	int m_width, m_height;
	int m_centre_x;
	int m_centre_y;
	int placed_rooms = 0;
	bool increase_placed_rooms_flag = false;
	char map[max_x][max_y];
	int room_id_count = 0;
	FILE *pFile = NULL;

	ROOM map_room;

	srand((unsigned int)time(NULL)); // sead for random room gen

	ROOM room_list[MAXROOMS];

	number_of_rooms = MAXROOMS;

	//randomly choose a map size if the user hasent chosen one
	m_width = (rand() % 499)+50;
	m_height = (rand() % 499)+50;

	int total_map_area = m_width*m_height;

	map_room.x = 0;
	map_room.y = 0;
	map_room.width = m_width;
	map_room.height = m_height;

	//make map, then fill the map with stone
	
	for(int x = 0; x<m_width; x++)
	{
		for(int y = 0; y<m_height; y++)
		{
			map[x][y] = stone;
		}
	}

	//clean up map
	for(int x = 0; x<max_x; x++)
	{
		for(int y = 0; y<max_y; y++)
		{
			if(map[x][y] != '#')
			{
				map[x][y] = ' ';
			}
		}
	}

	//find center of the map
	m_centre_x = m_width/2;
	m_centre_y = m_height/2;

	for(int i = 1; i<number_of_rooms; i++)
	{
		room_list[i] = gen_room();
	}

	room_list[0].height = 10;
	room_list[0].width = 10;
	room_list[0].x = m_centre_x - (int)room_list[0].width/2;
	room_list[0].y = m_centre_y - (int)room_list[0].width/2;
	room_list[0].placed = true;

	for(int i = 1; i<number_of_rooms;)
	{
		room_list[i].x = (int)(rand() % m_width) + 1;
		room_list[i].y = (int)(rand() % m_height) + 1;

		if(placed_rooms > 0)
		{
			for(int j = 1; j <= placed_rooms; j++)
			{
				if(rectOverlap(room_list[i], room_list[i-j]) == false)
				{
					if((rectContains(map_room, room_list[i]) == true))
					{
						increase_placed_rooms_flag = true;
						
					}
				}
			}
			if(increase_placed_rooms_flag == true)
			{
				placed_rooms++;
				increase_placed_rooms_flag = false;
				room_list[i].placed = true;
				i++;
			}
		}
		else
		{
			if(rectOverlap(room_list[0], room_list[i]) == false)
			{
				if(rectContains(map_room, room_list[i]) == true)
				{
					placed_rooms++;
					room_list[i].placed = true;
					i++;
				}
			}
		}
	}

	place_all_rooms(m_width, m_height, map, number_of_rooms, room_list, pFile);

	update_map_file(pFile, map);
}

bool valueInRange(int value, int min, int max)
{ 
	return (value >= min) && (value <= max); 
}

bool valueInRangeEx(int value, int min, int max)
{ 
	return (value > min) && (value < max); 
}

bool rectOverlap(ROOM A, ROOM B)
{
    bool xOverlap = valueInRangeEx(A.x, B.x, B.x + B.width+2) ||
                    valueInRangeEx(B.x, A.x, A.x + A.width+2);

    bool yOverlap = valueInRangeEx(A.y, B.y, B.y + B.height+2) ||
                    valueInRangeEx(B.y, A.y, A.y + B.height+2);

    return xOverlap && yOverlap;
}

bool rectContains(ROOM A, ROOM B)
{
	bool containsX = valueInRange(B.x, A.x, A.x + A.width) && valueInRange(B.x + B.width, A.x, A.x + A.width);
	bool containsY = valueInRange(B.y, A.y, A.y + A.height) && valueInRange(B.y + B.height, A.y, A.y + A.height);

	return containsX && containsY;
}

void place_all_rooms(int map_width, int map_height, char _map[][max_y], int number_of_rooms, ROOM list[], FILE *pFile)
{
			for(int z = 0; z < number_of_rooms; z++)
			{
				if((list[z].placed == true))
				{
					for(int room_x = 1; room_x<=list[z].width; room_x++)
					{
						for(int room_y = 1; room_y<=list[z].height; room_y++)
						{
							_map[list[z].x + room_x][list[z].y + room_y] = dirt;
							//update_map_file(pFile, _map);
						}
					}
				}
			}
}

void update_map_file(FILE * pFile, char _map[][max_y])
{
	pFile = fopen ("mymap.txt","w");

	for(int y = 0; y < max_y; y++)
	{
		for(int x = 0; x < max_x; x++)
		{
			fputc(_map[x][y], pFile);
		}
		fputs("\n", pFile); 
	}

	fclose(pFile);
}

this code doesn't do exactly what I want, however it is close. If you compile it it will generate a map but the rooms still intersect and sometimes are not contained in the map. I know there are some memory leaks in here so if someone could help me with that too I would be very grateful.

I don't expect anyone to code this whole thing for me and i don't want anyone to. A few hints or tips or small fixes would be fine.

This build produces a map similar to this

######################################
######################################
######################################
##_________###########################
##_________###########################
##_________________###################
##_________________###################
##_________________###################
##_________________#####____________##
########################____________##
########################____________##
########################____________##
######################################
######################################

see how the two rectangle rooms on the left over lap, what I want is a min spacing between each room to be one character width

like this
Code:

######################################
#___________________#________________#
#___________________#________________#
#___________________#________________#
#___________________#________________#
#___________________#________________#
#___________________#________________#
#___________________#________________#
#___________________#________________#
######################################

simple example but you can see what i mean.

thanks in advance for any help.

[novacain]

You are not reseting the 'increase_placed_rooms_flag' if the new room fails the test.

This means if the new room does not intersect with ANY of the already placed rooms AND is within the board, the new room is placed.