一. 概述
生成地下城，包含房间和迷宫通路。类似：
- 示例效果一
- 示例效果二
二. 思路
1.生成迷宫通路
- 从房间的边缘坐标XY为奇数的格子生成迷宫，确保房间和迷宫通路之间有间隔墙壁（除了蓝色格子视为墙壁）。
- 迷宫通路生长每次探测两个格子，确保迷宫通路间有间隔墙壁。
2.生成过程
三. 代码示例
位置结构体
public struct Vec2 { public int x; public int y; public Vec2(int x, int y) { this.x = x; this.y = y; } public static Vec2 Zero { get { return new Vec2(0, 0); } } public override bool Equals(object obj) { if (!(obj is Vec2)) return false; var o = (Vec2)obj; return x == o.x && y == o.y; } public override int GetHashCode() { return x.GetHashCode() + y.GetHashCode(); } public static Vec2 operator+ (Vec2 a, Vec2 b) { return new Vec2(a.x + b.x, a.y + b.y); } public static Vec2 operator* (Vec2 a, int n) { return new Vec2(a.x * n, a.y * n); } public static Vec2 operator* (int n, Vec2 a) { return new Vec2(a.x * n, a.y * n); } public static bool operator== (Vec2 a, Vec2 b) { return a.x == b.x && a.y == b.y; } public static bool operator !=(Vec2 a, Vec2 b) { return !(a.x == b.x && a.y == b.y); } } 房间，区域的定义
public struct Region { public int id; public List<Vec2> positions; public Region(int id) { this.id = id; positions = new List<Vec2>(); } } struct Room { public Rect rect; public List<Vec2> borders; public Room(int x, int y, int w, int h) { rect = new Rect(x, y, w, h); borders = new List<Vec2>(); for (int i = x; i <= x + w; i++) for (int j = y; j <= y + h; j++) if (!(i > x && x < x + w && j > y && j < y + h)) borders.Add(new Vec2(i, j)); } } - Room中的格子，计算生成迷宫和尝试连接区域，只需要计算房间边缘的格子即borders。
生成算法上下文
struct Context { public Vec2 size; public int roomCnt; public int windingPct; public int roomSizeOff; public int[,] map; public List<Region> regions; public List<Room> rooms; public int regionIDIdx; } - size 地图的大小，由输入地图大小裁剪成长宽为奇数的大小。
- roomCnt 预期生成地图的数量。
- windingPct 地图的蜿蜒程度最大为100 注意：即使为0，地图的蜿蜒程度一般也会比较大。
- roomSizeOff 房间长或宽的数值正负偏移
- map 记录地图土块的类型索引
- regions 地区列表
- room 房间列表
- 地区ID索引计数
生长方向枚举
public enum EDir { Up = 0, Down = 1, Left = 2, Right = 3, } static Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2> { {EDir.Up, new Vec2(0, 1) }, {EDir.Down, new Vec2(0, -1) }, {EDir.Left, new Vec2(-1, 0) }, {EDir.Right, new Vec2(1, 0) }, }; 初始化上下文&裁剪地图
Context context; public void Init(int w, int h, int roomCnt, int windingPct, int roomSizeOff) { int x = w - w % 2 - 2 - 1; int y = h - h % 2 - 2 - 1; context = new Context() { size = new Vec2(x, y), roomCnt = roomCnt, windingPct = windingPct, roomSizeOff = roomSizeOff, map = new int[x, y], regions = new List<Region>(), rooms = new List<Room>(), regionIDIdx = -1, }; } - 地图的长宽都被裁剪成奇数，并内缩一个单位。
生成地图房间
void GenRooms() { for (int i = 0; i < context.roomCnt;) { var size = R.Range(1, 3 + context.roomSizeOff) * 2 + 1; var off = R.Range(0, 1 + size / 2) * 2; var w = size; var h = size; if (R.Range(0, 2) > 0) w += off; else h += off; var x = R.Range(0, (context.size.x - w) / 2) * 2 ; var y = R.Range(0, (context.size.y - h) / 2) * 2 ; var rect = new Rect(x, y, w, h); bool isOverlap = false; foreach (var room in context.rooms) if (rect.Overlaps(room.rect)) { isOverlap = true; break; } if (isOverlap) continue; ++i; GrowRegion(); for (int m = x; m < x + w; m++) for (int n = y; n < y + h; n++) Carve(m, n); context.rooms.Add(new Room(x, y, w, h)); } } - 根据roomCnt参数生成房间
- 随机生成房间的大小和位置
- 若是新生成的房间和其他的房间重合则重新生成
- 生成房间的位置都是奇数，所以每个房间之上隔一个单位
生成迷宫通路
void GenMaze() { foreach (var room in context.rooms) foreach (var pos in room.borders) if (pos.x % 2 == 0 && pos.y % 2 == 0) GrowMaze(pos); } void GrowMaze(Vec2 pos) { Vec2 forward = Vec2.Zero; var stack = new Stack<Vec2>(); stack.Push(pos); GrowRegion(); bool isStart = true; while (stack.Count > 0) { var p = stack.Pop(); List<Vec2> dirs = new List<Vec2>(); foreach (var pair in dirDict) { var dir = pair.Value; if (CanMazeGrow(p, dir)) dirs.Add(dir); } if (dirs.Count > 0) { if (!(dirs.Contains(forward) && R.Range(0, 100) < context.windingPct)) forward = dirs[R.Range(0, dirs.Count)]; if (isStart) isStart = false; else Carve(p + forward); Carve(p + 2 * forward); stack.Push(p + 2 * forward); } else forward = Vec2.Zero; } TryShrinkRegion(); } bool CanMazeGrow(Vec2 pos, Vec2 dir) { return CanCarve(pos + dir) && CanCarve(pos + 2 * dir); } bool CanCarve(Vec2 pos) { return CanCarve(pos.x, pos.y); } bool CanCarve(int x, int y) { return InMap(x, y) && context.map[x, y] == 0; } bool InMap(Vec2 pos) { return InMap(pos.x, pos.y); } bool InMap(int x, int y) { var size = context.size; return x >= 0 && x < size.x && y >= 0 && y < size.y; } void Carve(Vec2 pos, int ty = 1) { Carve(pos.x, pos.y, ty); } void Carve(int x, int y, int ty = 1) { context.map[x, y] = ty; context.regions[context.regionIDIdx].positions.Add(new Vec2(x, y)); } - 从每个房间的边缘XY为奇数尝试生长迷宫通路
- 递归的生长迷宫向四周探测两个单位，符合条件则向那个方向生长两个单位，直到不能生长
- 若至少生长了一次，则形成一个迷宫通路区域
- 第一次生长时，为了避免后面影响连接的计算，第一次的第一个单位填充被忽略
连接区域
void Connect() { for (int i = 0; i < context.rooms.Count; i++) { context.regions[i].positions.Clear(); foreach (var pos in context.rooms[i].borders) context.regions[i].positions.Add(pos); } Dictionary<int, Region> dict = new Dictionary<int, Region>(); for (int i = 0; i < context.regions.Count; i++) dict[i] = context.regions[i]; var idxs = new List<int>(); while (dict.Count > 1) { idxs.Clear(); foreach (var pair in dict) idxs.Add(pair.Key); var dest = idxs[idxs.Count - 1]; idxs.RemoveAt(idxs.Count - 1); bool isMerge = false; foreach (var idx in idxs) { var connectPos = Vec2.Zero; if (TryConnectRegion(dict[dest], dict[idx], out connectPos)) { GrowRegion(); dict[context.regionIDIdx] = context.regions[context.regionIDIdx]; foreach (var pos in dict[dest].positions) dict[context.regionIDIdx].positions.Add(pos); foreach (var pos in dict[idx].positions) dict[context.regionIDIdx].positions.Add(pos); Carve(connectPos); dict.Remove(dest); dict.Remove(idx); isMerge = true; break; } } if (!isMerge) { Debug.Log("Region Merge Failed!"); return; } } } bool TryConnectRegion(Region a, Region b, out Vec2 connectPos) { for (int i = 0; i < a.positions.Count; i++) { var ap = a.positions[i]; if (ap.x % 2 == 0 && ap.y % 2 == 0) for (int j = 0; j < b.positions.Count; j++) { var bp = b.positions[j]; if (bp.x % 2 == 0 && bp.y % 2 == 0) if (ap.y == bp.y) { if (ap.x - bp.x == 2) { connectPos = ap + new Vec2(-1, 0); return true; } if (ap.x - bp.x == -2) { connectPos = ap + new Vec2(1, 0); return true; } } else if (ap.x == bp.x) { if (ap.y - bp.y == 2) { connectPos = ap + new Vec2(0, -1); return true; } if (ap.y - bp.y == -2) { connectPos = ap + new Vec2(0, 1); return true; } } } } connectPos = Vec2.Zero; return false; } - 递归的对区域进行两两合并
- 两个区域若是各自存在一个格子，若是这两个格子的距离为2个单位则这两个单位可通过Lerp(格子a,格子b，0.5)这个格子连接，这两个区域合并成为一个区域。
- 若是有需要可以判断两个区域中是否有房间，可以把这个格子作为"门"之类的东西。
裁剪迷宫通路
void CutMaze() { var region = context.regions[context.regionIDIdx]; List<Vec2> dirs = new List<Vec2>(); foreach (var pos in region.positions) CutMazeArrangement(pos); } void CutMazeArrangement(Vec2 pos) { if (context.map[pos.x, pos.y] == 0) return; List<Vec2> dirs = new List<Vec2>(); foreach (var pair in dirDict) { var dir = pair.Value; var test = pos + dir; if (!InMap(test)) continue; if (context.map[test.x, test.y] == 1) dirs.Add(test); } if (dirs.Count == 1) { context.map[pos.x, pos.y] = 0; CutMazeArrangement(dirs[0]); } } - 递归的检查所有迷宫通路的格子，若是此格子的连通方向只有一个，则消除此格子。
完整代码
using System.Collections; using System.Collections.Generic; using UnityEngine; using R = UnityEngine.Random; public struct Vec2 { public int x; public int y; public Vec2(int x, int y) { this.x = x; this.y = y; } public static Vec2 Zero { get { return new Vec2(0, 0); } } public override bool Equals(object obj) { if (!(obj is Vec2)) return false; var o = (Vec2)obj; return x == o.x && y == o.y; } public override int GetHashCode() { return x.GetHashCode() + y.GetHashCode(); } public static Vec2 operator+ (Vec2 a, Vec2 b) { return new Vec2(a.x + b.x, a.y + b.y); } public static Vec2 operator* (Vec2 a, int n) { return new Vec2(a.x * n, a.y * n); } public static Vec2 operator* (int n, Vec2 a) { return new Vec2(a.x * n, a.y * n); } public static bool operator== (Vec2 a, Vec2 b) { return a.x == b.x && a.y == b.y; } public static bool operator !=(Vec2 a, Vec2 b) { return !(a.x == b.x && a.y == b.y); } } public enum EDir { Up = 0, Down = 1, Left = 2, Right = 3, } public class DungeonBuild { public struct Region { public int id; public List<Vec2> positions; public Region(int id) { this.id = id; positions = new List<Vec2>(); } } struct Room { public Rect rect; public List<Vec2> borders; public Room(int x, int y, int w, int h) { rect = new Rect(x, y, w, h); borders = new List<Vec2>(); for (int i = x; i <= x + w; i++) for (int j = y; j <= y + h; j++) if (!(i > x && x < x + w && j > y && j < y + h)) borders.Add(new Vec2(i, j)); } } struct Context { public Vec2 size; public int roomCnt; public int windingPct; public int roomSizeOff; public int[,] map; public List<Region> regions; public List<Room> rooms; public int regionIDIdx; } static Dictionary<EDir, Vec2> dirDict = new Dictionary<EDir, Vec2> { {EDir.Up, new Vec2(0, 1) }, {EDir.Down, new Vec2(0, -1) }, {EDir.Left, new Vec2(-1, 0) }, {EDir.Right, new Vec2(1, 0) }, }; Context context; public void Init(int w, int h, int roomCnt, int windingPct, int roomSizeOff) { int x = w - w % 2 - 2 - 1; int y = h - h % 2 - 2 - 1; context = new Context() { size = new Vec2(x, y), roomCnt = roomCnt, windingPct = windingPct, roomSizeOff = roomSizeOff, map = new int[x, y], regions = new List<Region>(), rooms = new List<Room>(), regionIDIdx = -1, }; } public void Build() { GenRooms(); GenMaze(); Connect(); CutMaze(); } public int[,] GetResult() { return context.map; } public Vector2 GetSize() { return new Vector2(context.size.x, context.size.y); } void GrowRegion() { context.regionIDIdx++; context.regions.Add(new Region(context.regionIDIdx)); } void TryShrinkRegion() { if (context.regions[context.regionIDIdx].positions.Count == 0) { context.regions.RemoveAt(context.regionIDIdx); context.regionIDIdx--; } } void GenRooms() { for (int i = 0; i < context.roomCnt;) { var size = R.Range(1, 3 + context.roomSizeOff) * 2 + 1; var off = R.Range(0, 1 + size / 2) * 2; var w = size; var h = size; if (R.Range(0, 2) > 0) w += off; else h += off; var x = R.Range(0, (context.size.x - w) / 2) * 2 ; var y = R.Range(0, (context.size.y - h) / 2) * 2 ; var rect = new Rect(x, y, w, h); bool isOverlap = false; foreach (var room in context.rooms) if (rect.Overlaps(room.rect)) { isOverlap = true; break; } if (isOverlap) continue; ++i; GrowRegion(); for (int m = x; m < x + w; m++) for (int n = y; n < y + h; n++) Carve(m, n); context.rooms.Add(new Room(x, y, w, h)); } } void GenMaze() { foreach (var room in context.rooms) foreach (var pos in room.borders) if (pos.x % 2 == 0 && pos.y % 2 == 0) GrowMaze(pos); } void GrowMaze(Vec2 pos) { Vec2 forward = Vec2.Zero; var stack = new Stack<Vec2>(); stack.Push(pos); GrowRegion(); bool isStart = true; while (stack.Count > 0) { var p = stack.Pop(); List<Vec2> dirs = new List<Vec2>(); foreach (var pair in dirDict) { var dir = pair.Value; if (CanMazeGrow(p, dir)) dirs.Add(dir); } if (dirs.Count > 0) { if (!(dirs.Contains(forward) && R.Range(0, 100) < context.windingPct)) forward = dirs[R.Range(0, dirs.Count)]; if (isStart) isStart = false; else Carve(p + forward); Carve(p + 2 * forward); stack.Push(p + 2 * forward); } else forward = Vec2.Zero; } TryShrinkRegion(); } void Connect() { for (int i = 0; i < context.rooms.Count; i++) { context.regions[i].positions.Clear(); foreach (var pos in context.rooms[i].borders) context.regions[i].positions.Add(pos); } Dictionary<int, Region> dict = new Dictionary<int, Region>(); for (int i = 0; i < context.regions.Count; i++) dict[i] = context.regions[i]; var idxs = new List<int>(); while (dict.Count > 1) { idxs.Clear(); foreach (var pair in dict) idxs.Add(pair.Key); var dest = idxs[idxs.Count - 1]; idxs.RemoveAt(idxs.Count - 1); bool isMerge = false; foreach (var idx in idxs) { var connectPos = Vec2.Zero; if (TryConnectRegion(dict[dest], dict[idx], out connectPos)) { GrowRegion(); dict[context.regionIDIdx] = context.regions[context.regionIDIdx]; foreach (var pos in dict[dest].positions) dict[context.regionIDIdx].positions.Add(pos); foreach (var pos in dict[idx].positions) dict[context.regionIDIdx].positions.Add(pos); Carve(connectPos); dict.Remove(dest); dict.Remove(idx); isMerge = true; break; } } if (!isMerge) { Debug.Log("Region Merge Failed!"); return; } } } bool TryConnectRegion(Region a, Region b, out Vec2 connectPos) { for (int i = 0; i < a.positions.Count; i++) { var ap = a.positions[i]; if (ap.x % 2 == 0 && ap.y % 2 == 0) for (int j = 0; j < b.positions.Count; j++) { var bp = b.positions[j]; if (bp.x % 2 == 0 && bp.y % 2 == 0) if (ap.y == bp.y) { if (ap.x - bp.x == 2) { connectPos = ap + new Vec2(-1, 0); return true; } if (ap.x - bp.x == -2) { connectPos = ap + new Vec2(1, 0); return true; } } else if (ap.x == bp.x) { if (ap.y - bp.y == 2) { connectPos = ap + new Vec2(0, -1); return true; } if (ap.y - bp.y == -2) { connectPos = ap + new Vec2(0, 1); return true; } } } } connectPos = Vec2.Zero; return false; } void CutMaze() { var region = context.regions[context.regionIDIdx]; List<Vec2> dirs = new List<Vec2>(); foreach (var pos in region.positions) CutMazeArrangement(pos); } void CutMazeArrangement(Vec2 pos) { if (context.map[pos.x, pos.y] == 0) return; List<Vec2> dirs = new List<Vec2>(); foreach (var pair in dirDict) { var dir = pair.Value; var test = pos + dir; if (!InMap(test)) continue; if (context.map[test.x, test.y] == 1) dirs.Add(test); } if (dirs.Count == 1) { context.map[pos.x, pos.y] = 0; CutMazeArrangement(dirs[0]); } } bool CanMazeGrow(Vec2 pos, Vec2 dir) { return CanCarve(pos + dir) && CanCarve(pos + 2 * dir); } bool CanCarve(Vec2 pos) { return CanCarve(pos.x, pos.y); } bool CanCarve(int x, int y) { return InMap(x, y) && context.map[x, y] == 0; } bool InMap(Vec2 pos) { return InMap(pos.x, pos.y); } bool InMap(int x, int y) { var size = context.size; return x >= 0 && x < size.x && y >= 0 && y < size.y; } void Carve(Vec2 pos, int ty = 1) { Carve(pos.x, pos.y, ty); } void Carve(int x, int y, int ty = 1) { context.map[x, y] = ty; context.regions[context.regionIDIdx].positions.Add(new Vec2(x, y)); } } 
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/3.jpg&w=218&h=124&zc=1)
