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

#define MAP_WIDTH 80
#define MAP_HEIGHT 21

#define MAX_ROOMS 12
#define MIN_ROOMS 6

#define ROCK 0
#define ROOM 1
#define CORRIDOR 2
#define STAIRS_UP 3
#define STAIRS_DOWN 4

typedef struct {
	int hardness;
	int immutable;
	int type;
} map_cell;

typedef struct {
	int x;
	int y;
	int w;
	int h;
} room;

/**
 * Generate a random number between min and max, inclusive
**/
int randrange(int min, int max);

/**
 * Probability generator
 */
int randchance(double prob);

/**
 * Returns the sign of a number
 * Or zero if the input is zero
 */
int sign(int x);

/**
 * Draw the dungeon
 */
void draw_map(map_cell dungeon[][80]);

/**
 * Generate random rooms in the dungeon, and place them in the provided array.
 * Return the number of rooms actually generated
 */
int generate_rooms(map_cell dungeon[][80], room rooms[MAX_ROOMS]);

/**
 * Generate corridors to connect the rooms
 */
void generate_corridors(map_cell dungeon[][80], room rooms[MAX_ROOMS], int numRooms);

/**
 * Connect the two given rooms by a corridor
 */
void connect_rooms(map_cell dungeon[][80], room rooms[MAX_ROOMS], int room1, int room2);

/**
 * Generate stairs in random positions on rooms or corridors
 */
void generate_stairs(map_cell dungeon[][80]);

/**
 * Update hardness in each cell to reflect whether it is a border cell or an open spce
 */
void update_hardness(map_cell dungeon[][80]);

int main(int argc, char* argv[]) {
	int seed;
	
	// Get the seed from commandline if specified
	if (argc > 1) {
		seed = atoi(argv[1]);
	} else {
		srand(time(NULL));
		seed = rand();
	}
	
	// Print the seed so we can reuse it
	printf("Using Seed: %d\n", seed);
	srand(seed);
	
	// Map initialization
	map_cell dungeon[MAP_HEIGHT][MAP_WIDTH];
	
	int i, j;
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			dungeon[i][j].hardness = randrange(1, 254);
			dungeon[i][j].type = ROCK;
			dungeon[i][j].immutable = (i == 0 || i == (MAP_HEIGHT - 1) || j == 0 || j == (MAP_WIDTH - 1));
		}
	}
	
	// Generate rooms
	room rooms[MAX_ROOMS];
	int room_count = generate_rooms(dungeon, rooms);
	
	// Generate corridors
	generate_corridors(dungeon, rooms, room_count);
	
	// Generate stairs
	generate_stairs(dungeon);
	
	// Update hardness
	update_hardness(dungeon);
	
	draw_map(dungeon);
}

void generate_stairs(map_cell dungeon[][80]) {
	int found_pos, i;
	
	// Up stairs
	for (i = 0; i < randrange(1, 2); i++) {
		found_pos = 0;
		while (!found_pos) {
			int x = randrange(1, MAP_WIDTH-2);
			int y = randrange(1, MAP_HEIGHT-2);

			if (dungeon[y][x].type == ROOM || dungeon[y][x].type == CORRIDOR) {
				dungeon[y][x].type = STAIRS_UP;
				found_pos = 1;
			}
		}
	}
		
	// Down stairs
	for (i = 0; i < randrange(1, 2); i++) {
		found_pos = 0;
		while (!found_pos) {
			int x = randrange(1, MAP_WIDTH-2);
			int y = randrange(1, MAP_HEIGHT-2);

			if (dungeon[y][x].type == ROOM || dungeon[y][x].type == CORRIDOR) {
				dungeon[y][x].type = STAIRS_DOWN;
				found_pos = 1;
			}
		}
	}
}

void update_hardness(map_cell dungeon[][80]) {
	int i, j;
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			if (dungeon[i][j].immutable) {
				dungeon[i][j].hardness = 255;
			} else if (dungeon[i][j].type != ROCK) {
				dungeon[i][j].hardness = 0;
			}
		}
	}
}

void generate_corridors(map_cell dungeon[][80], room rooms[MAX_ROOMS], int numRooms) {
	int i, j;
	
	int connected[MAX_ROOMS];
	for (i = 0; i < MAX_ROOMS; i++) {
		connected[i] = -1;
	}
	
	connected[0] = 0;
	
	while(1) {
		// Check if all the rooms are connected
		int flag = 1;
		for (i = 0; i < numRooms; i++) {
			if (connected[i] < 0) 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 < numRooms; i++) {
			if (connected[i] >= 0) continue;
			for (j = 0; j < numRooms; j++) {
				if (connected[j] < 0) continue;
				
				// Compare distance, no need to square root since we
				// don't care about the actual distance
				int xFact = rooms[j].x - rooms[i].x;
				int yFact = rooms[j].y - rooms[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(dungeon, rooms, room1, room2);
		connected[room1] = room2;
	}
}

void connect_rooms(map_cell dungeon[][80], room rooms[MAX_ROOMS], int room1, int room2) {
	int i;
	
	// Start position
	int currX = randrange(rooms[room1].x, rooms[room1].x + rooms[room1].w - 1);
	int currY = randrange(rooms[room1].y, rooms[room1].y + rooms[room1].h - 1);

	// End position
	int targetX	= randrange(rooms[room2].x, rooms[room2].x + rooms[room2].w - 1);
	int targetY = randrange(rooms[room2].y, rooms[room2].y + rooms[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);

			if (dungeon[currY][currX].type == ROCK) {
				dungeon[currY][currX].type = CORRIDOR;
			}

			else if (dungeon[currY][currX].type == CORRIDOR) {
				return;
			}
		}

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

int generate_rooms(map_cell dungeon[][80], room rooms[MAX_ROOMS]) {
	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);
	
	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
		rooms[k].x = x;
		rooms[k].y = y;
		rooms[k].w = w;
		rooms[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++) {
				dungeon[i][j].type = ROOM;
			}
		}
	}
	
	return rooms_to_make;
}
		

void draw_map(map_cell dungeon[][80]) {
	int i, j;
	for (i = 0; i < MAP_HEIGHT; i++) {
		for (j = 0; j < MAP_WIDTH; j++) {
			if (dungeon[i][j].immutable) {
				if (i == 0 || i == (MAP_HEIGHT - 1)) printf("-");
				else printf("|");
			}
			else if (dungeon[i][j].type == ROCK) printf(" ");
			else if (dungeon[i][j].type == ROOM) printf(".");
			else if (dungeon[i][j].type == CORRIDOR) printf("#");
			else if (dungeon[i][j].type == STAIRS_UP) printf("<");
			else if (dungeon[i][j].type == STAIRS_DOWN) printf(">");
			else printf("!"); // Error- something we didn't expect was in the map
		}
		printf("\n");
	}
}

int randrange(int min, int max) {
	int range = max - min + 1;
	return (rand() % range) + min;
}

int randchance(double prob) {
	int resolution = RAND_MAX;
	return (rand() % resolution) < (prob * resolution);
}

int sign(int x) {
	if (x > 0) return 1;
	if (x < 0) return -1;
	return 0;
}