fixed mst calculations

6 files changed, 79 insertions, 55 deletions

diff --git a/Makefile b/Makefile
index 9f508fc..92a2629 100644
--- a/Makefile
+++ b/Makefile
@@ -8,7 +8,7 @@ install: ${PROG}
 	cp ${PROG} ~/.local/bin/
 
 build: src/main.c
-	${CC} src/main.c -o ${PROG} ${FLAGS}
+	${CC} src/main.c src/mst.c -o ${PROG} ${FLAGS}
 
 build-osx: ${PROG}
 	clang -framework CoreVideo -framework IOKit -framework Cocoa -framework GLUT -framework OpenGL libraylib.a ${PROG}.c -o ${PROG}
diff --git a/README.md b/README.md
index 38d9435..f3700bf 100644
--- a/README.md
+++ b/README.md
@@ -1,3 +1,6 @@
 # Procedural Generated Dungeon
 
 
+https://www.gamasutra.com/blogs/AAdonaac/20150903/252889/Procedural_Dungeon_Generation_Algorithm.php
+https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
+https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
diff --git a/src/const.h b/src/const.h
new file mode 100644
index 0000000..068a36d
--- /dev/null
+++ b/src/const.h
@@ -0,0 +1,4 @@
+
+#define ROOM_COUNT 6
+#define MAX_SIZE 100
+#define MIN_SIZE 35
diff --git a/src/main.c b/src/main.c
index 41093ba..3c2ee14 100644
--- a/src/main.c
+++ b/src/main.c
@@ -1,18 +1,17 @@
 #include "raylib.h"
-#include "limits.h"
 #include "stdlib.h"
 #include "stdio.h"
 #include "math.h"
 #include "time.h"
 
-#define ROOM_COUNT 6
+#include "mst.h"
+#include "const.h"
+
 const int screenWidth = 800;
 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;
@@ -27,7 +26,7 @@ typedef struct R {
 Room rooms[ROOM_COUNT];
 
 // define each corridor as a branch between a room and its "parent"
-int parentRooms[ROOM_COUNT];
+int *parentRooms;
 
 // extend build in C random function to return a value from 0.0d to 1.0d
 double randomDouble() {
@@ -49,8 +48,8 @@ void positionRooms() {
 
 		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);
+		int w = MIN_SIZE + randomDouble() * (MAX_SIZE-MIN_SIZE);
+		int h = MIN_SIZE + randomDouble() * (MAX_SIZE-MIN_SIZE);
 
 		rooms[i] = (Room){x, y, w, h};
 	}
@@ -118,50 +117,6 @@ 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
@@ -177,14 +132,15 @@ void mapCorridors() {
 	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));
+			int dx = (nodes[i].x - nodes[j].x);
+			int dy = (nodes[i].y - nodes[j].y);
+			int distanceSquared = dx*dx + dy*dy;
 			graph[i][j] = distanceSquared;
 		}
 	}
 
 
-	primMST(graph);
-
+	parentRooms = primMST(graph);
 }
 
 
diff --git a/src/mst.c b/src/mst.c
new file mode 100644
index 0000000..f090dd5
--- /dev/null
+++ b/src/mst.c
@@ -0,0 +1,57 @@
+#include "stdio.h"
+#include "limits.h"
+#include "stdbool.h"
+
+#include "const.h"
+
+// Prim's minimum spanning tree algorithm
+// graph: adjacency matrix representation of the nodes/rooms
+int* primMST(int graph[ROOM_COUNT][ROOM_COUNT]) {
+
+	// create the array of parents to be returned
+	static int parentRooms[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];
+			}
+		}
+	}
+	
+	return parentRooms;
+
+}
+
diff --git a/src/mst.h b/src/mst.h
new file mode 100644
index 0000000..e005fee
--- /dev/null
+++ b/src/mst.h
@@ -0,0 +1,4 @@
+#include "const.h"
+
+int* primMST(int graph[ROOM_COUNT][ROOM_COUNT]);
+