Random Dungeon generator - help please

This is a discussion on Random Dungeon generator - help please within the C++ Programming forums, part of the General Programming Boards category; I am having trouble getting my random dungeon generator working properly. I will try to explain how I WANT my ...

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    3

    Question Random Dungeon generator - help please

    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.

    Code:
    #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


    Code:
    ######################################
    ######################################
    ######################################
    ##_________###########################
    ##_________###########################
    ##_________________###################
    ##_________________###################
    ##_________________###################
    ##_________________#####____________##
    ########################____________##
    ########################____________##
    ########################____________##
    ######################################
    ######################################
    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:
    Code:
    ######################################
    #___________________#________________#
    #___________________#________________#
    #___________________#________________#
    #___________________#________________#
    #___________________#________________#
    #___________________#________________#
    #___________________#________________#
    #___________________#________________#
    ######################################
    simple example but you can see what i mean.

    thanks in advance for any help.

  2. #2
    train spotter
    Join Date
    Aug 2001
    Location
    near a computer
    Posts
    3,859
    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.
    "Man alone suffers so excruciatingly in the world that he was compelled to invent laughter."
    Friedrich Nietzsche

    "I spent a lot of my money on booze, birds and fast cars......the rest I squandered."
    George Best

    "If you are going through hell....keep going."
    Winston Churchill

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need a random number generator thats not compleatly random
    By thedodgeruk in forum C++ Programming
    Replies: 1
    Last Post: 06-05-2011, 06:48 AM
  2. Random Generator
    By jpjpolski in forum C Programming
    Replies: 4
    Last Post: 05-29-2011, 12:56 AM
  3. Random generator 0 1
    By Dedalus in forum C Programming
    Replies: 3
    Last Post: 06-30-2009, 08:44 AM
  4. Random Name Generator
    By jdinger in forum C++ Programming
    Replies: 6
    Last Post: 04-11-2002, 11:36 AM
  5. Random dungeon generator...
    By blackwyvern in forum Game Programming
    Replies: 2
    Last Post: 03-23-2002, 10:56 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21