added mst to calculate corridors

1 files changed, 230 insertions, 3 deletions

diff --git a/src/main.c b/src/main.c
index 73ec76c..41093ba 100644
--- a/src/main.c
+++ b/src/main.c
@@ -1,19 +1,246 @@
 #include "raylib.h"
+#include "limits.h"
+#include "stdlib.h"
+#include "stdio.h"
+#include "math.h"
+#include "time.h"
 
+#define ROOM_COUNT 6
 const int screenWidth = 800;
-const int screenHeight = 450;
+const int screenHeight = 800;
+const int seed = 123456781;
+
+const int radius = 20;
+const int maxSize = 100;
+const int minSize = 35;
+
+typedef struct R {
+	int x;
+	int y;
+	int w;
+	int h;
+} Room;
+
+// In this example, the idea is that rooms will be made up of tiles in a game
+// 1 pixel/unit in this algorithm is intended to 
+
+Room rooms[ROOM_COUNT];
+
+// define each corridor as a branch between a room and its "parent"
+int parentRooms[ROOM_COUNT];
+
+// extend build in C random function to return a value from 0.0d to 1.0d
+double randomDouble() {
+	return rand() / (double)(RAND_MAX);
+}
+
+
+// Randomly position rooms around the map, spanning around a circular space
+void positionRooms() {
+	for (int i = 0; i < ROOM_COUNT; i++) {
+		double t = 2 * PI * randomDouble();
+		double u = 2 * randomDouble();
+		double r;
+		if (u > 1) {
+			r = 2-u;
+		} else {
+			r = u;
+		}
+
+		int x = (screenWidth/2) + radius*r*cos(t);
+		int y = (screenHeight/2) + radius*r*sin(t);
+		int w = minSize + randomDouble() * (maxSize-minSize);
+		int h = minSize + randomDouble() * (maxSize-minSize);
+
+		rooms[i] = (Room){x, y, w, h};
+	}
+} 
+
+// Determine if two rooms are colliding with each other or not.
+// true: colliding
+// false: not colliding
+bool areColliding(Room a, Room b) {
+	bool h1 = (b.x < a.x+a.w);
+	bool h2 = (b.x+b.w > a.x);
+
+	bool v1 = (b.y < a.y+a.h);
+	bool v2 = (b.y+b.h > a.y);
+
+	return h1 && h2 && v1 && v2;
+}
+
+
+void separateRooms() {
+
+	// Move the rooms away from each other until there are no collisions left
+	bool d = true;
+	while (d) {
+		// set d to false. If no rooms are moved, then we are done with this
+		d = false;
+
+		// iterate through all rooms and check if all other rooms are colliding with each room
+		for (int i = 0; i < ROOM_COUNT; i++) {
+			for (int j = 0; j < ROOM_COUNT; j++) {
+				// only check if they are different rooms
+				if (j != i) {
+					// only move it if they are colliding
+					if (areColliding(rooms[i], rooms[j])) {
+						d = true;
+						Room *room1 = &rooms[i];
+						Room *room2 = &rooms[j];
+						
+						// calculate the difference in centers of the two rooms
+						int c1x = room1->x + (room1->w/2);
+						int c1y = room1->y + (room1->h/2);
+
+						int c2x = room2->x + (room2->w/2);
+						int c2y = room2->y + (room2->h/2);
+
+						int dx = c1x - c2x;
+						int dy = c1y - c2y;
+
+						// move the current room away from the other room by the difference of centers + half the width of the room
+						room1->x += dx;
+						room1->y += dy; 
+						
+						room1->x += (abs(dx)/dx) * (room1->w/2);
+						room1->y += (abs(dy)/dy) * (room1->h/2);
+
+					}
+				}
+			}
+		}
+	}
+}
+
+// function to get the center of each room as a Vector2 point.
+Vector2 getCenter(Room *room) {
+	return (Vector2){room->x+(room->w/2), room->y+(room->h/2)};
+}
+
+// Prim's minimum spanning tree algorithm
+void primMST(int graph[ROOM_COUNT][ROOM_COUNT]) {
+
+	int key[ROOM_COUNT];
+	bool mstSet[ROOM_COUNT];
+
+	// all keys should start as infinite
+	for (int i = 0; i < ROOM_COUNT; i++) {
+		key[i] = INT_MAX;
+		mstSet[i] = false;
+	}
+
+	// always start with the first vertext int MST
+	// making the key 0, so that its always picked first
+	key[0] = 0;
+	parentRooms[0] = -1; // the first node has no parent
+
+	for (int c = 0; c < ROOM_COUNT - 1; c++) {
+
+		// pick the minimum key from the set of nodes that are not yet included
+		int min = INT_MAX;
+		int min_index;
+
+		for (int v = 0; v < ROOM_COUNT; v++) {
+			if (mstSet[v] == false && key[v] < min) {
+				min = key[v];
+				min_index = v;
+			}
+		}
+		printf("min index is %d\n", min_index);	
+		// add the picked node to the set
+		mstSet[min_index] = true;
+
+		// Update key values and parent index
+
+		for (int v = 0; v < ROOM_COUNT; v++) {
+			if (graph[min_index][v] && mstSet[v] == false && graph[min_index][v] < key[v]) {
+				parentRooms[v] = min_index;
+				key[v] = graph[min_index][v];
+			}
+		}
+	}
+
+}
+
+void mapCorridors() {
+	// Make things easier for us by working with only the center points of each room
+	Vector2 nodes[ROOM_COUNT];
+	for (int i = 0; i < ROOM_COUNT; i++) {
+		nodes[i] = getCenter(&rooms[i]);
+	}
+
+	// Map the rooms points into an adjacency matrix  
+	int graph[ROOM_COUNT][ROOM_COUNT];
+	
+
+	for (int i = 0; i < ROOM_COUNT; i++) {
+		for (int j = 0; j < ROOM_COUNT; j++) {
+			// we only really need to compare distances between nodes, so to save time, we will leave distances squared
+			int distanceSquared = floor((nodes[i].x - nodes[j].x) + (nodes[i].y - nodes[j].y));
+			graph[i][j] = distanceSquared;
+		}
+	}
+
+
+	primMST(graph);
+
+}
+
+
+void createCorridors() {
+
+}
+
+void generateRooms() {
+	positionRooms();
+	separateRooms();
+	mapCorridors();
+	
+}
+
 
 int main(void) {
+	srand(time(NULL));
+
+	generateRooms();
+
 	InitWindow(screenWidth, screenHeight, "dungeon generation");
-	SetTargetFPS(60);
+	SetTargetFPS(20);
 
 	while (!WindowShouldClose()) {
 		
 		BeginDrawing();
 		ClearBackground(GRAY);
 
-		EndDrawing();
+		for (int i = 0; i < ROOM_COUNT; i++) {
+			for (int j = 0; j < ROOM_COUNT; j++) {
+				Vector2 a = getCenter(&rooms[i]);
+				Vector2 b = getCenter(&rooms[j]);
+
+				DrawLine(a.x, a.y, b.x, b.y, RED);
+			}
+		}
+
+		for (int i = 0; i < ROOM_COUNT; i++) {
+			Color c;
+			if (i == 0) c = BLACK;
+			else	    c = LIGHTGRAY;
+			DrawRectangleLines(rooms[i].x, rooms[i].y, rooms[i].w, rooms[i].h, c); 
+			
+			int p = parentRooms[i];
 
+			if (p > -1 && p < ROOM_COUNT) {
+				Vector2 a = getCenter(&rooms[i]);
+				Vector2 b = getCenter(&rooms[p]);
+
+				DrawLine(a.x, a.y, b.x, b.y, GREEN);
+			}
+		}
+
+	
+
+		EndDrawing();
 	}
 
 	CloseWindow();