Random Dungeon Generator
In many RPG games, including rogue-like games, diablo-like games and some MMORPG, random dungeon is one of the important elements. There are many random dungeon generating algorithm.
My algorithm is inspired by recursive spanning tree. But here are some specific points: Whether to generate the new branch of every direction is according to the possibility defined by developer(Higher possibility will make the structure slenderer, and lower possibility will make it have more branches). And in 2D space (same in 3D space), we also need to detect if there is available space for new branch. If the number of nodes reach the max limit, the recursive function will stop generate new branch and return. Or when the recursive function finished, the number of nodes is still less than minimal limit, we will choose a random node to execute the recursion again.
The advantage of this algorithm is that we can store the depth(how far to the start node) of every node when generating them. And it can gives the game designer the information of playing progress to design resources and challenges.
The demo and the code(C#) are down below.
Demo link: https://lsqyzyx.itch.io/dungeon-generator
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Tilemaps;
public class DGsim : MonoBehaviour
{
public Tilemap tilemap;
public Tile tileDefualt;
public int amountOfCornerTypes;
public int amountOfEdgeTypes;
public int amountOfCenterTypes;
public int maxDepth;
public int maxAmountOfRooms;
public int minAmountOfRooms;
public float spawnPossiblity;
public float colorS = 1f;
public float colorV = 1f;
public GameObject minimapLine;
public float delay;
public Vector2 offset;
private Dictionary<Vector2Int, Room> Rooms = new Dictionary<Vector2Int, Room>();
private List<Vector2Int> positions = new List<Vector2Int>();
private List<Vector2Int> maxDepthPositions = new List<Vector2Int>();
private int amountOfRooms = 0;
private int theMaxDepth = 0;
private GameObject line;
private class Room
{
public bool b;//If there is a node at bottom
public bool r;//If there is a node at right
public bool t;//If there is a node at top
public bool l;//If there is a node at left
public int d;//Depth(how far to the start node)
public List<int> tp;//Room type(Topography information)
public List<int> e;//Enemy information
public Color c;//Color information
public Room(bool b = false, bool r = false, bool t = false, bool l = false, int d = 0, List<int> tp = null)
{
this.b = b;
this.r = r;
this.t = t;
this.l = l;
this.d = d;
this.tp = tp;
}
}
bool Spawn(Vector2Int newRoom, int depth, int parentsDirect)
{
bool ifGen;
if (depth == 0)
{
ifGen = true;
}
else
{
float rd = UnityEngine.Random.Range(0f, 1f);
if (rd <= spawnPossiblity) ifGen = true;
else ifGen = false;
}
if (ifGen && depth <= maxDepth && amountOfRooms < maxAmountOfRooms && !Rooms.ContainsKey(newRoom))
{
amountOfRooms += 1;
if (depth >= theMaxDepth) theMaxDepth = depth;
List<int> roomTp = new List<int>();
for (int i = 0; i < 4; i++) roomTp.Add(UnityEngine.Random.Range(0, amountOfCornerTypes));
for (int i = 0; i < 4; i++) roomTp.Add(UnityEngine.Random.Range(0, amountOfEdgeTypes));
roomTp.Add(UnityEngine.Random.Range(0, amountOfCenterTypes));//set room type
Rooms.Add(newRoom, new Room(d: depth, tp: roomTp));
float H = UnityEngine.Random.Range(0f, 1f);
Color color = Color.HSVToRGB(H, colorS, colorV, true);
Rooms[newRoom].c = color;//set random color
tilemap.SetTile(new Vector3Int(newRoom.x, newRoom.y, 0), tileDefualt);
tileDefualt.color = Rooms[newRoom].c;
positions.Add(newRoom);
Rooms[newRoom].b = Spawn(new Vector2Int(newRoom.x, newRoom.y - 1), Rooms[newRoom].d + 1, 2);
if (Rooms[newRoom].b)
{
line = Instantiate(minimapLine, transform.position, transform.rotation);
line.GetComponent<LineRenderer>().SetPosition(0, new Vector3(newRoom.x + offset.x, newRoom.y + offset.y, 0));
line.GetComponent<LineRenderer>().SetPosition(1, new Vector3(newRoom.x + offset.x, newRoom.y - 1 + offset.y, 0));
line.GetComponent<DestroyLine>().destroyable = true;
}
Rooms[newRoom].r = Spawn(new Vector2Int(newRoom.x + 1, newRoom.y), Rooms[newRoom].d + 1, 3);
if (Rooms[newRoom].r)
{
line = Instantiate(minimapLine, transform.position, transform.rotation);
line.GetComponent<LineRenderer>().SetPosition(0, new Vector3(newRoom.x + offset.x, newRoom.y + offset.y, 0));
line.GetComponent<LineRenderer>().SetPosition(1, new Vector3(newRoom.x + 1 + offset.x, newRoom.y + offset.y, 0));
line.GetComponent<DestroyLine>().destroyable = true;
}
Rooms[newRoom].t = Spawn(new Vector2Int(newRoom.x, newRoom.y + 1), Rooms[newRoom].d + 1, 0);
if (Rooms[newRoom].t)
{
line = Instantiate(minimapLine, transform.position, transform.rotation);
line.GetComponent<LineRenderer>().SetPosition(0, new Vector3(newRoom.x + offset.x, newRoom.y + offset.y, 0));
line.GetComponent<LineRenderer>().SetPosition(1, new Vector3(newRoom.x + offset.x, newRoom.y + 1 + offset.y, 0));
line.GetComponent<DestroyLine>().destroyable = true;
}
Rooms[newRoom].l = Spawn(new Vector2Int(newRoom.x - 1, newRoom.y), Rooms[newRoom].d + 1, 1);
if (Rooms[newRoom].l)
{
line = Instantiate(minimapLine, transform.position, transform.rotation);
line.GetComponent<LineRenderer>().SetPosition(0, new Vector3(newRoom.x + offset.x, newRoom.y + offset.y, 0));
line.GetComponent<LineRenderer>().SetPosition(1, new Vector3(newRoom.x - 1 + offset.x, newRoom.y + offset.y, 0));
line.GetComponent<DestroyLine>().destroyable = true;
}
switch (parentsDirect)
{
case 0: Rooms[newRoom].b = true; break;
case 1: Rooms[newRoom].r = true; break;
case 2: Rooms[newRoom].t = true; break;
case 3: Rooms[newRoom].l = true; break;
default: break;
}
return true;
}
else
{
return false;
}
}
public void Gen()
{
Spawn(new Vector2Int(0, 0), 0, -1);
int c = 0;
while (amountOfRooms < minAmountOfRooms)
{
int n = UnityEngine.Random.Range(0, amountOfRooms);
Rooms[positions[n]].b = Spawn(new Vector2Int(positions[n].x, positions[n].y - 1), Rooms[positions[n]].d + 1, 2);
if (Rooms[positions[n]].b)
{
line = Instantiate(minimapLine, transform.position, transform.rotation);
line.GetComponent<LineRenderer>().SetPosition(0, new Vector3(positions[n].x + offset.x, positions[n].y + offset.y, 0));
line.GetComponent<LineRenderer>().SetPosition(1, new Vector3(positions[n].x + offset.x, positions[n].y - 1 + offset.y, 0));
line.GetComponent<DestroyLine>().destroyable = true;
}
Rooms[positions[n]].r = Spawn(new Vector2Int(positions[n].x + 1, positions[n].y), Rooms[positions[n]].d + 1, 3);
if (Rooms[positions[n]].r)
{
line = Instantiate(minimapLine, transform.position, transform.rotation);
line.GetComponent<LineRenderer>().SetPosition(0, new Vector3(positions[n].x + offset.x, positions[n].y + offset.y, 0));
line.GetComponent<LineRenderer>().SetPosition(1, new Vector3(positions[n].x + 1 + offset.x, positions[n].y + offset.y, 0));
line.GetComponent<DestroyLine>().destroyable = true;
}
Rooms[positions[n]].t = Spawn(new Vector2Int(positions[n].x, positions[n].y + 1), Rooms[positions[n]].d + 1, 0);
if (Rooms[positions[n]].t)
{
line = Instantiate(minimapLine, transform.position, transform.rotation);
line.GetComponent<LineRenderer>().SetPosition(0, new Vector3(positions[n].x + offset.x, positions[n].y + offset.y, 0));
line.GetComponent<LineRenderer>().SetPosition(1, new Vector3(positions[n].x + offset.x, positions[n].y + 1 + offset.y, 0));
line.GetComponent<DestroyLine>().destroyable = true;
}
Rooms[positions[n]].l = Spawn(new Vector2Int(positions[n].x - 1, positions[n].y), Rooms[positions[n]].d + 1, 1);
if (Rooms[positions[n]].l)
{
line = Instantiate(minimapLine, transform.position, transform.rotation);
line.GetComponent<LineRenderer>().SetPosition(0, new Vector3(positions[n].x + offset.x, positions[n].y + offset.y, 0));
line.GetComponent<LineRenderer>().SetPosition(1, new Vector3(positions[n].x - 1 + offset.x, positions[n].y + offset.y, 0));
line.GetComponent<DestroyLine>().destroyable = true;
}
c++;
if (c > 1000) break;
}
}
void Start()
{
Gen();
}
public void ReGen()
{
tilemap.ClearAllTiles();
Rooms = new Dictionary<Vector2Int, Room>();
positions = new List<Vector2Int>();
maxDepthPositions = new List<Vector2Int>();
amountOfRooms = 0;
theMaxDepth = 0;
Gen();
}
}