Skip to content

Instantly share code, notes, and snippets.

@thoraxe
Created November 26, 2023 17:00
Show Gist options
  • Save thoraxe/7af9d792d5c098a203a99f912f88c200 to your computer and use it in GitHub Desktop.
Save thoraxe/7af9d792d5c098a203a99f912f88c200 to your computer and use it in GitHub Desktop.
using Godot;
using System;
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Linq;
[Tool]
public partial class dun_gen : Node3D
{
// dungeon generator
bool _start = false;
[Export]
public bool Start {
get { return _start; }
set {
_start = value;
Generate(_start);
}
}
GridMap _gridMap;
// dungeon parameters
int _borderSize = 20;
[Export]
public int BorderSize {
get { return _borderSize; }
set {
_borderSize = value;
// don't run when we're inside the game, but only in the editor
if (Engine.IsEditorHint()) VisualizeBorder(_borderSize);
}
}
[Export]
public int MinRoomSize = 2;
[Export]
public int MaxRoomSize = 4;
[Export]
public int NumRooms = 4;
[Export]
public int RoomMargin = 1;
[Export]
public int MaxRoomRecursionDepth = 15;
// store the room information
List<List<Vector3>> _roomTiles;
List<Vector3> _roomPositions;
// specifically an array and not a list because of the delaunay triangulation function
Vector2[] _roomPositionsV2;
// spanning trees and graphs
AStar2D _delaunayTraingulation;
AStar2D _minSpanningTree;
void Generate(bool status)
{
GD.Print("generating: " + status);
VisualizeBorder(BorderSize);
// clear out the list storage and graphs/trees
_roomTiles = new List<List<Vector3>>{};
_roomPositions = new List<Vector3>{};
_delaunayTraingulation = new AStar2D();
_minSpanningTree = new AStar2D();
for (int room = 0; room < NumRooms; room++) MakeRoom(MaxRoomRecursionDepth);
// now that we know how many rooms and positions there are, we can properly initialize the vector2 array
_roomPositionsV2 = new Vector2[_roomPositions.Count];
// TODO: refactor into function
// convert the vector3 list of the room positions into a vector2 list
for (int i = 0; i < _roomPositions.Count; i++)
{
Vector2 positionV2 = new Vector2(_roomPositions[i].X, _roomPositions[i].Z);
GD.Print("room " + i + " pos: " + positionV2);
// store the current room position in the vector2 array
_roomPositionsV2[i] = positionV2;
// add the room position as a point in the delaunay traingulation and the minimum spanning tree
_delaunayTraingulation.AddPoint(_delaunayTraingulation.GetAvailablePointId(), positionV2);
_minSpanningTree.AddPoint(_minSpanningTree.GetAvailablePointId(), positionV2);
}
// do the delaunay triangulation
Queue<int> delaunayPoints = new Queue<int>(Geometry2D.TriangulateDelaunay(_roomPositionsV2));
GD.Print();
GD.Print("delaunay points: " + delaunayPoints.Count);
int numTriangles = delaunayPoints.Count / 3;
GD.Print("num triangles: " + numTriangles);
// TODO: refactor into function
// manually connect the points on the delaunay graph
// the returned queue of stuff is actually each point on the triangle in order
// since triangles have 3 points, each set of 3 points will be a complete triangle
// first, iterate over each triangle
for (int i = 0; i < numTriangles; i++)
{
// grab the first three points
int p1 = delaunayPoints.Dequeue();
int p2 = delaunayPoints.Dequeue();
int p3 = delaunayPoints.Dequeue();
GD.Print("Triangle #" + i + " points: 1: " + p1 + " 2: " + p2 + " 3: " + p3);
// connect each point of the triangle on the delaunay graph
_delaunayTraingulation.ConnectPoints(p1,p2);
_delaunayTraingulation.ConnectPoints(p2,p3);
_delaunayTraingulation.ConnectPoints(p1,p3);
}
// make a temporary list of visited points, which is the integer index of the point in the graph
List<long> visitedPoints = new List<long>{};
// add a random point from the delaunay graph to the visited points list
Random rnd = new Random();
int rp = rnd.Next() % _roomPositions.Count;
GD.Print("Chosen point: " + rp);
visitedPoints.Add(rp);
// iterate until the size of the visited points list is the size of the minimum spanning tree
// in other words, until all points are visited
// in the first iteration, the visited points list has one item, and the minimum spanning tree has all the
// points in the graph
while (visitedPoints.Count < _minSpanningTree.GetPointCount())
{
GD.Print("points list is smaller, so iterating");
// recalculate possible connections candidates
List<List<long>> possibleConnections = new List<List<long>>{};
foreach (long visitedPoint in visitedPoints)
{
GD.Print("current visited point: " + visitedPoint);
// look at connections in the delaunay graph
foreach (long connectionPoint in _delaunayTraingulation.GetPointConnections(visitedPoint))
{
// if the visited point is not already in the visited points list, add it
if (!visitedPoints.Contains(connectionPoint))
{
List<long> connectionPair = new List<long>{visitedPoint, connectionPoint};
// add the connection to the list of possible connections
GD.Print("Adding connection pair: " + connectionPair.ToString());
possibleConnections.Add(connectionPair);
}
}
// choose another random connection from the list of possible connections
List<long> connection = possibleConnections[rnd.Next() % possibleConnections.Count];
// loop through all possible connections
// compare length to currently selected connection (random)
// if the new connection is shorter, replace the selected connection with the new one
GD.Print("Looping through possible connections to find shortest path");
foreach (List<long> possibleConnection in possibleConnections)
{
// calculate the distance between possible connection points
float newDistance = _roomPositionsV2[possibleConnection[0]].DistanceSquaredTo(_roomPositionsV2[possibleConnection[1]]);
float selectedDistance = _roomPositionsV2[connection[0]].DistanceSquaredTo(_roomPositionsV2[connection[1]]);
// if the new distance is less than the currently selected connection's distance, replace with the new connection
if (newDistance < selectedDistance)
{
GD.Print(newDistance + " is shorter than " + selectedDistance + " so choosing " + connection.ToString());
connection = possibleConnection;
}
}
GD.Print("shortest connection:" + connection.ToString());
// connection now is the shortest one
// add the connection's second point to the visited points array
visitedPoints.Add(connection[1]);
// connect the two points in the minimum spanning tree
_minSpanningTree.ConnectPoints(connection[0], connection[1]);
// disconnect the two points in the delaunay graph
_delaunayTraingulation.DisconnectPoints(connection[0], connection[1]);
}
}
}
void MakeRoom(int RecursionDepth)
{
// check if we are below max recursion depth
if (!(RecursionDepth > 0)) return;
// get a random room width x height
Random rnd = new Random();
int width = (rnd.Next() % (MaxRoomSize - MinRoomSize)) + MinRoomSize;
int height = (rnd.Next() % (MaxRoomSize - MinRoomSize)) + MinRoomSize;
// get a random position for the room
Vector3I startPos = new Vector3I
{
X = rnd.Next() % (BorderSize - width + 1),
Z = rnd.Next() % (BorderSize - height + 1)
};
// check if a room already exists where we have tried to start a new room
// if it does, recursively try again until the max recursion depth, before aborting
for (int row = RoomMargin * -1; row < height + RoomMargin; row++)
{
for (int col = RoomMargin * -1; col < width + RoomMargin; col++)
{
if (_gridMap.GetCellItem(new Vector3I(startPos.X + col, 0, startPos.Z + row)) == 0)
{
// there's already a room tile here, so try again
MakeRoom(RecursionDepth - 1);
return;
}
}
}
List<Vector3> roomInfo = new List<Vector3>{};
// make the room similar to making the border
for (int row = 0; row < height; row++)
{
for (int col = 0; col < width; col++)
{
Vector3I position = new Vector3I(startPos.X + col, 0, startPos.Z + row);
_gridMap.SetCellItem(position, 0);
// build the list of room position information
roomInfo.Add(position);
}
}
// put the room position information list into the list of tiles
_roomTiles.Add(roomInfo);
// calculate the center position of the room
float avgX = startPos.X + (width / 2);
float avgZ = startPos.Z + (height / 2);
Vector3 centerPos = new Vector3(avgX, 0, avgZ);
// TODO: should probably just convert this to the vector2 when we create it
_roomPositions.Add(centerPos);
}
void VisualizeBorder(int BorderSize)
{
// just in case we didn't already fetch it somewhere
_gridMap = GetNode<GridMap>("GridMap");
GD.Print("border size: " + BorderSize);
_gridMap.Clear();
for (int i = -1; i < BorderSize + 1; i++)
{
// north border
_gridMap.SetCellItem(new Vector3I(i, 0, -1), 3);
// south border
_gridMap.SetCellItem(new Vector3I(i, 0, BorderSize), 3);
// east border
_gridMap.SetCellItem(new Vector3I(BorderSize, 0, i), 3);
// west border
_gridMap.SetCellItem(new Vector3I(-1, 0, i), 3);
}
}
// Called when the node enters the scene tree for the first time.
public override void _Ready()
{
_gridMap = GetNode<GridMap>("GridMap");
Generate(true);
}
// Called every frame. 'delta' is the elapsed time since the previous frame.
public override void _Process(double delta)
{
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment