dungeon.cpp

#include <stdint.h>
#include <stdlib.h>

#include "character.h"
#include "dungeon.h"
#include "util.h"

void init_dungeon(dungeon_t *d) {
	int i, j;
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			d->characters[i][j] = NULL;
		}
	}
}

void gen_random_dungeon(dungeon_t* d) {
	init_dungeon_hardness(d);
	
	// Generate rooms
	generate_rooms(d);
	
	// Generate corridors
	generate_corridors(d);
	
	// Generate player position
	// Pick a random room
	int r = randrange(0, d->room_count-1);
	d->player_pos.x = randrange(d->room_list[r].x, d->room_list[r].x + d->room_list[r].w - 1);
	d->player_pos.y = randrange(d->room_list[r].y, d->room_list[r].y + d->room_list[r].h - 1);
	
	// Generate stairs
	generate_stairs(d);
	
	// Create the pc in the character array
	d->characters[d->player_pos.y][d->player_pos.x] = generate_pc(d->player_pos.x, d->player_pos.y);
}

void gen_monsters(dungeon_t *d, int nummon) {
	int open_cells = 0;
	int i, j, k;
	
	// Count the open cells
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			if (d->hardness[i][j] == 0 && d->characters[i][j] == NULL) {
				open_cells++;
			}
		}
	}
	
	// Record the positions of the open cells
	position_t *monster_positions = malloc(open_cells * sizeof(position_t));
	k = 0;
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			if (d->hardness[i][j] == 0 && d->characters[i][j] == NULL) {
				monster_positions[k].x = j;
				monster_positions[k].y = i;
				k++;
			}
		}
	}
	
	// Shuffle the list of open cells
	for (i = 0; i < open_cells; i++) {
		int swap_index = rand() % open_cells;
		position_t tmp = monster_positions[i];
		monster_positions[i] = monster_positions[swap_index];
		monster_positions[swap_index] = tmp;
	}
	
	// Create the monsters
	for (i = 0; i < nummon && i < open_cells; i++) {
		int x = monster_positions[i].x;
		int y = monster_positions[i].y;
		d->characters[y][x] = generate_monster(x, y);
	}
	
	free(monster_positions);
}

void init_turn_heap(dungeon_t *d, heap_t *h) {
	int i, j;
	
	init_character_turn_heap(h);
	
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			if (d->characters[i][j]) {
				heap_insert(h, d->characters[i][j]);
			}
		}
	}
}

void free_dungeon(dungeon_t* d) {
	int i, j;
	
	free(d->room_list);
	free(d->upstair_list);
	free(d->downstair_list);
	
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			if (d->characters[i][j]) {
				if (d->characters[i][j]->player) {
					free(d->characters[i][j]->player);
				}
				if (d->characters[i][j]->monster) {
					free(d->characters[i][j]->monster);
				}
				free(d->characters[i][j]);
			}
		}
	}
}

void init_dungeon_hardness(dungeon_t* d) {
	int i, j;
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			if (i == 0 || i == (MAP_HEIGHT - 1) || j == 0 || j == (MAP_WIDTH - 1)) {
				d->hardness[i][j] = 255;
			} else {
				d->hardness[i][j] = randrange(1, 254);
			}
		}
	}
}

void generate_stairs(dungeon_t* d) {
	int found_pos, i, j;
	
	// Up stairs
	int num_up_stairs = randrange(1, 2);
	d->upstair_count = num_up_stairs;
	d->upstair_list = malloc(num_up_stairs * sizeof(position_t));
	
	for (i = 0; i < num_up_stairs; i++) {
		found_pos = 0;
		while (!found_pos) {
			int x = randrange(1, MAP_WIDTH-2);
			int y = randrange(1, MAP_HEIGHT-2);

			if (d->hardness[y][x] == 0) {
				// This is an open space, let's see if it is already a stair
				int valid = 1;
				for (j = 0; j < i; j++) {
					if (d->upstair_list[j].x == x && d->upstair_list[j].y == y) {
						valid = 0;
					}
				}
				
				if (x == d->player_pos.x && y == d->player_pos.y) {
					valid = 0;
				}
				
				// If not valid, keep trying
				if (!valid) continue;
				
				d->upstair_list[i].x = x;
				d->upstair_list[i].y = y;
				found_pos = 1;
			}
		}
	}
		
	// Down stairs
	int num_down_stairs = randrange(1, 2);
	d->downstair_count = num_down_stairs;
	d->downstair_list = malloc(num_down_stairs * sizeof(position_t));
	
	for (i = 0; i < num_down_stairs; i++) {
		found_pos = 0;
		while (!found_pos) {
			int x = randrange(1, MAP_WIDTH-2);
			int y = randrange(1, MAP_HEIGHT-2);

			if (d->hardness[y][x] == 0) {
				// This is an open space, let's see if it is already a stair
				// Have to check both up stairs and down stairs now
				int valid = 1;
				for (j = 0; j < d->upstair_count; j++) {
					if (d->upstair_list[j].x == x && d->upstair_list[j].y == y) {
						valid = 0;
					}
				}
				
				for (j = 0; j < i; j++) {
					if (d->downstair_list[j].x == x && d->downstair_list[j].y == y) {
						valid = 0;
					}
				}
				
				if (x == d->player_pos.x && y == d->player_pos.y) {
					valid = 0;
				}
				
				// If not valid, keep trying
				if (!valid) continue;
				
				d->downstair_list[i].x = x;
				d->downstair_list[i].y = y;
				found_pos = 1;
			}
		}
	}
}

void generate_corridors(dungeon_t* d) {
	int i, j;
	
	int* connected = malloc(d->room_count * sizeof(int));
	for (i = 0; i < d->room_count; i++) {
		connected[i] = 0;
	}
	
	connected[0] = 1;
	
	while(1) {
		// Check if all the rooms are connected
		int flag = 1;
		for (i = 0; i < d->room_count; i++) {
			if (!connected[i]) flag = 0;
		}
		if (flag) break;
		
		// Find the closest connected/disconnected pair of rooms
		int minDistFact = 10000;
		int room1 = 0;
		int room2 = 0;
		for (i = 0; i < d->room_count; i++) {
			if (connected[i]) continue;
			for (j = 0; j < d->room_count; j++) {
				if (!connected[j]) continue;
				
				// Compare distance, no need to square root since we
				// don't care about the actual distance
				int xFact = d->room_list[j].x - d->room_list[i].x;
				int yFact = d->room_list[j].y - d->room_list[i].y;
				int distFact = xFact * xFact + yFact * yFact;
				if (distFact < minDistFact) {
					minDistFact = distFact;
					room1 = i; //disconnected room
					room2 = j; //connected room
				}
			}
		}
		
		// Connect the rooms with corridors
		connect_rooms(d, room1, room2);
		connected[room1] = 1;
	}
	
	free(connected);
}

void connect_rooms(dungeon_t* d, int room1, int room2) {
	int i;
	
	// Start position
	int currX = randrange(d->room_list[room1].x, d->room_list[room1].x + d->room_list[room1].w - 1);
	int currY = randrange(d->room_list[room1].y, d->room_list[room1].y + d->room_list[room1].h - 1);

	// End position
	int targetX	= randrange(d->room_list[room2].x, d->room_list[room2].x + d->room_list[room2].w - 1);
	int targetY = randrange(d->room_list[room2].y, d->room_list[room2].y + d->room_list[room2].h - 1);

	while(1) {
		// Where we need to travel to get there
		int dx = targetX - currX;
		int dy = targetY - currY;

		// Select which direction and how far to go
		if (randchance(0.5)) {
			dx = 0;
			dy = sign(dy) * randrange(0, abs(dy)/2+1);
		} else {
			dy = 0;
			dx = sign(dx) * randrange(0, abs(dx)/2+1);
		}

		// Number of iterations in this leg of the corridor
		int dist = abs(dx + dy);

		// Draw each cell along the way, avoiding rooms
		// If we cross an existing corridor, exit - it is connected
		for (i = 0; i < dist; i++) {
			currX += sign(dx);
			currY += sign(dy);
			
			d->hardness[currY][currX] = 0;
		}

		// Once we have reached our target, exit
		if (currX == targetX && currY == targetY) {
			return;
		}
	}
}

void generate_rooms(dungeon_t* d) {
	int i, j, k;
	
	int room_eligible[MAP_HEIGHT][MAP_WIDTH];
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			room_eligible[i][j] = !(i == 0 || i == (MAP_HEIGHT-1) || j == 0 || j == (MAP_WIDTH-1));
		}
	}
	
	// Choose how many rooms to make
	int rooms_to_make = randrange(MIN_ROOMS, MAX_ROOMS);
	
	// Initialize the dungeon with that information
	d->room_count = rooms_to_make;
	d->room_list = malloc(rooms_to_make * sizeof(room_t));
	
	for (k = 0; k < rooms_to_make; k++) {
		int foundRoom = 0;
		int x, y, w, h;
		
		// Until we have found a valid position for the room
		while(!foundRoom) {
			// Generate random parameters for the room
			w = randrange(4, 10);
			h = randrange(3, 8);
			x = randrange(1, MAP_WIDTH - w);
			y = randrange(1, MAP_HEIGHT - h);
			
			// Assume that this is good
			foundRoom = 1;
			
			// Check every cell in the new room to see if it is eligible
			// If not, set the flag to false so we will try again
			for (i = y; i < y+h; i++) {
				for (j = x; j < x+w; j++) {
					if (!room_eligible[i][j]) foundRoom = 0;
				}
			}
		}
		
		// Save the parameters of the room in the array
		d->room_list[k].x = x;
		d->room_list[k].y = y;
		d->room_list[k].w = w;
		d->room_list[k].h = h;
		
		// Mark this room and the border around it as ineligible for room placement
		for (i = y-1; i < y+h+1; i++) {
			for (j = x-1; j < x+w+1; j++) {
				room_eligible[i][j] = 0;
			}
		}
		
		// Mark the cells in the map as room cells
		for (i = y; i < y+h; i++) {
			for (j = x; j < x+w; j++) {
				d->hardness[i][j] = 0;
			}
		}
	}
}