dungen.cs

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)
	{
	}
}