From 0f5e0c8d912dcdfe01d6a2bc693ef98eda82c336 Mon Sep 17 00:00:00 2001
From: davidovski <david@sendula.com>
Date: Wed, 28 Jul 2021 18:00:42 +0100
Subject: added mst to calculate corridors
---
src/main.c | 233 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
1 file 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();
--
cgit v1.2.1