1
地下城地图图块生成算法 - 张宏港
source link: https://www.cnblogs.com/hggzhang/p/16971561.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
生成地下城，包含房间和迷宫通路。类似：
- 示例效果一
- 示例效果二
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));
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK