diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | README.md | 3 | ||||
| -rw-r--r-- | src/const.h | 4 | ||||
| -rw-r--r-- | src/main.c | 64 | ||||
| -rw-r--r-- | src/mst.c | 57 | ||||
| -rw-r--r-- | src/mst.h | 4 |
6 files changed, 79 insertions, 55 deletions
@@ -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} @@ -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 @@ -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]); + |