[游戏开发][Godot][GDScript] 二维洞穴地图随机生成

1. ver1

照搬 Unity 的做法 https://blog.csdn.net/PriceCheap/article/details/125962352

版本：Godot_v4.0-alpha13_win64

该脚本附加在 GridMap 节点上，节点的 Meshibrary 需要至少一个元素

MapGenerator.gd

class_name MapGenerator
extends GridMap

enum TileType {Empty, Wall}

@export var width : int = 64
@export var height : int = 36

@export var mapSeed : String # 随机种子
@export var useRandomSeed : bool = true

@export_range(0.0,1.0) var threshold : float = 0.5 # 随机填充百分比，越大洞越小

@export_range(0,20) var smoothLevel : int = 4 # 平滑程度

@export var wallThresholdSize : int = 50 # 清除小墙体的阈值
@export var roomThresholdSize : int = 50 # 清除小孔的的阈值

@export var passageWidth : int = 4 # 通道（房间与房间直接）宽度

@export var borderSize : int = 1

var map : Array # 地图集，Empty为空洞，Wall为实体墙

var upDownLeftRight : Array = [Vector2i(0,1), Vector2i(0,-1), Vector2i(-1,0), Vector2i(1,0)]

var survivingRooms : Array # 存放最后实际有效的空洞房间

const Room = preload("Room.gd")

func _ready():
	GenerateMap()
	SetGridMap()


func _input(event):
	if event is InputEventMouseButton:
		match event.button_index:
			MOUSE_BUTTON_LEFT:
				survivingRooms.clear()
				GenerateMap()
				clear()
				SetGridMap()

# 生成随机地图
func GenerateMap():
	for x in range(width):
		map.append([])
		for y in range(height):
			map[x].append(TileType.Empty)
	RandomFillMap()

	for i in range(smoothLevel):
		SmoothMap()

	# 清除小洞，小墙
	ProcessMap()

	# 连接各个幸存房间
	ConnectAllRoomsToMainRoom(survivingRooms)

# 设置 3d 瓦片地图
func SetGridMap():
	for x in range(width):
		for y in range(height):
			if map[x][y] == TileType.Empty:
				set_cell_item(Vector3i(x,0,y),0,0)
	
# 随机填充地图
func RandomFillMap():
	if useRandomSeed:
		mapSeed = Time.get_datetime_string_from_system()
	seed(mapSeed.hash())

	for x in range(width):
		for y in range(height):
			if x == 0 || x == width - 1 || y == 0 || y == height - 1:
				map[x][y] = TileType.Wall
			else:
				map[x][y] = TileType.Wall if randf_range(0,1) < threshold else TileType.Empty

# 平滑地图
func SmoothMap():
	for x in range(width):
		for y in range(height):
			var neighbourWallTiles = GetSurroundingWallCount(x, y)
			if neighbourWallTiles > 4: # 周围大于四个墙，那自己也是墙
				map[x][y] = TileType.Wall
			elif neighbourWallTiles < 4: #周围大于四个为空，那自己也为空
				map[x][y] = TileType.Empty
			# 还有如果四四开，那就保持不变。

# 获取该点周围 8 个点为实体墙（map[x][y] == 1）的个数
func GetSurroundingWallCount(x, y):
	var wallCount = 0
	for nx in [x-1, x+1]:
		for ny in [y-1, y+1]:
			if nx >= 0 && nx < width && ny >= 0 && ny < height:
				wallCount += 1 if map[x][y] == TileType.Wall else 0
			else:
				wallCount += 1
	return wallCount

# 加工地图，清除小洞，小墙，连接房间。
func ProcessMap():
	# 获取最大房间的索引
	var currentIndex : int = 0
	var maxIndex : int = 0
	var maxSize : int = 0
	
	# 获取墙区域
	var wallRegions = GetRegions(TileType.Wall)
	for wallRegion in wallRegions:
		if wallRegion.size() < wallThresholdSize:
			for tile in wallRegion:
				map[tile.x][tile.y] = TileType.Empty # 把小于阈值的都铲掉
				
	# 获取空洞区域
	var roomRegions = GetRegions(TileType.Empty)
	for roomRegion in roomRegions:
		if roomRegion.size() < roomThresholdSize:
			for tile in roomRegion:
				map[tile.x][tile.y] = TileType.Wall # 把小于阈值的都填充
		else:
			var sRoom = Room.new(roomRegion, map)
			survivingRooms.append(sRoom) # 添加到幸存房间列表里
			if maxSize < roomRegion.size():
				maxSize = roomRegion.size()
				maxIndex = currentIndex # 找出最大房间的索引
			currentIndex += 1

	if survivingRooms.size() == 0:
		print_debug("No Survived Rooms Here!!")
	else:
		survivingRooms[maxIndex].isMainRoom = true # 最大房间就是主房间
		survivingRooms[maxIndex].isAccessibleFromMainRoom = true

# 获取区域
func GetRegions(tileType):
	var regions : Array
	var mapFlags = BitMap.new()
	mapFlags.create(Vector2(width, height))
	
	for x in range(width):
		for y in range(height):
			if mapFlags.get_bit(Vector2(x, y)) == false && map[x][y] == tileType:
				regions.append(GetRegionTiles(x, y, tileType, mapFlags))
	
	return regions

# 从这个点开始获取区域，广度优先算法
func GetRegionTiles(startX, startY, tileType, mapFlags):
	var tiles : Array
	var quene1 : Array
	var quene2 : Array
	quene1.append(Vector2i(startX, startY))
	mapFlags.set_bit(Vector2(startX, startY), true)

	while quene1.size() > 0:
		var tile = quene1.pop_back()
		tiles.append(tile)

		# 遍历上下左右四格
		for i in range(4):
			var x = tile.x + upDownLeftRight[i].x;
			var y = tile.y + upDownLeftRight[i].y;
			if IsInMapRange(x, y) && mapFlags.get_bit(Vector2(x, y)) == false && map[x][y] == tileType:
				mapFlags.set_bit(Vector2(x, y), true)
				quene2.append(Vector2i(x, y))

		if quene1.size() == 0:
			quene1 = quene2
			quene2 = Array()

	return tiles

# 把所有房间都连接到主房间
func ConnectAllRoomsToMainRoom(allRooms):
	for room in allRooms:
		ConnectToClosestRoom(room, allRooms)

	var count = 0
	for room in allRooms:
		if room.isAccessibleFromMainRoom:
			count += 1
	if count != allRooms.size():
		ConnectAllRoomsToMainRoom(allRooms)
	
# 连接本房间与距离自己最近的一个与自己尚未连接的房间
# 可能找不到满足条件的待连接房间
func ConnectToClosestRoom(roomA, roomListB):
	var bestDistance : int = 9223372036854775807
	var bestTileA : Vector2i
	var bestTileB : Vector2i
	var bestRoomB
	
	var hasChecked = false
	
	for roomB in roomListB:
		if roomA == roomB || roomA.IsConnected(roomB):
			continue
		
		for tileA in roomA.edgeTiles:
			for tileB in roomB.edgeTiles:
				var distanceBetweenRooms = (tileA - tileB).length_squared()
				# 如果找到更近的（相对roomA）房间，更新最短路径。
				if distanceBetweenRooms < bestDistance:
					bestDistance = distanceBetweenRooms
					bestTileA = tileA
					bestTileB = tileB
					bestRoomB = roomB

	if bestRoomB != null:
		CreatePassage(roomA, bestRoomB, bestTileA, bestTileB)

# 创建两个房间的通道
func CreatePassage(roomA, roomB, tileA, tileB):
	roomA.ConnectRooms(roomB)
	var line = GetLine(tileA, tileB)
	for coord in line:
		DrawCircle(coord, passageWidth)

# 获取两点直接线段经过的点
func GetLine(from, to):
	var line : Array

	var x = from.x
	var y = from.y

	var dx = to.x - from.x
	var dy = to.y - from.y

	var inverted = false
	var step = sign(dx)
	var gradientStep = sign(dy)

	var longest = abs(dx)
	var shortest = abs(dy)

	if longest < shortest:
		inverted = true
		longest = abs(dy)
		shortest = abs(dx)

		step = sign(dy)
		gradientStep = sign(dx)

	var gradientAccumulation = longest / 2 # 梯度积累，最长边的一半。
	for i in range(longest):
		line.append(Vector2i(x, y))

		if inverted:
			y += step
		else:
			x += step

		gradientAccumulation += shortest # 梯度每次增长为短边的长度。
		if gradientAccumulation >= longest:
			if inverted:
				x += gradientStep
			else:
				y += gradientStep
			gradientAccumulation -= longest

	return line

# 以点c为原点，r为半径，画圈（拆墙）
func DrawCircle(c, r):
	for x in range(-r, r):
		for y in range(-r, r):
			if x * x + y * y <= r * r:
				var drawX = c.x + x
				var drawY = c.y + y
				if IsInMapRange(drawX, drawY):
					map[drawX][drawY] = TileType.Empty

# 判断坐标是否在地图里，不管墙还是洞
func IsInMapRange(x, y):
	return x >= 0 && x < width && y >= 0 && y < height

该脚本不用附加到节点上

Room.gd

class_name Room
extends Object

enum TileType {Empty, Wall}

var tiles : Array = [] # 所有坐标
var edgeTiles : Array = [] # 靠边的坐标
var connectedRooms : Array = [] # 与其直接相连的房间。
var isAccessibleFromMainRoom : bool = false # 是否能连接到主房间
var isMainRoom : bool = false # 是否主房间（最大的房间）
var upDownLeftRight : Array = [Vector2i(0,1), Vector2i(0,-1), Vector2i(-1,0), Vector2i(1,0)]

func _init(roomTiles, map):
	tiles = roomTiles
	UpdateEdgeTiles(map)

# 更新房间边缘瓦片集
func UpdateEdgeTiles(map):
	edgeTiles.clear()
	# 遍历上下左右四格，判断是否有墙
	for tile in tiles:
		for i in range(4):
			var x = tile.x + upDownLeftRight[i].x
			var y = tile.y + upDownLeftRight[i].y
			if map[x][y] == TileType.Wall && !edgeTiles.has(tile):
				edgeTiles.append(tile)
				
# 标记相对于主房间的连接性
func MarkAccessibleFromMainRoom():
	# 标记自己能够连接到主房间
	if !isAccessibleFromMainRoom:
		isAccessibleFromMainRoom = true
		# 和自己连接的房间都能连到主房间
		for connectedRoom in connectedRooms:
			connectedRoom.MarkAccessibleFromMainRoom()

# 连接房间
func ConnectRooms(roomB):
	# 传递连接标记
	if isAccessibleFromMainRoom:
		roomB.MarkAccessibleFromMainRoom()
	elif roomB.isAccessibleFromMainRoom:
		MarkAccessibleFromMainRoom()
	# 传递连接行为
	connectedRooms.append(roomB)
	roomB.connectedRooms.append(self)

# 是否连接另一个房间
func IsConnected(otherRoom):
	if connectedRooms.find(otherRoom) == -1:
		return false
	else:
		return true

本来 TileType 和 upDownLeftRight 应该做成全局变量的
但是 4.0-alpha 的 autoload 设置有点问题，我就没有用

2. ver2

具体来说，问题在于，perload 一个引用了 autoload 中的脚本会报错
https://github.com/godotengine/godot/issues/58551
因此我的地图生成器在 preload 房间脚本的时候，房间脚本里面如果用到了自动加载的 GEnum，就不行
这是一个已知的 bug

如果没有这个 bug 的话，可以写得更好看一点

genum.gd

extends Object

enum TileType {Empty, Wall}

var Vector2_Dir : Array = [Vector2i(0,1), Vector2i(0,-1), Vector2i(-1,0), Vector2i(1,0)]

room_1.gd

extends Object

var tiles : Array = [] # 所有坐标
var edgeTiles : Array = [] # 靠边的坐标
var connectedRooms : Array = [] # 与其直接相连的房间。
var isAccessibleFromMainRoom : bool = false # 是否能连接到主房间
var isMainRoom : bool = false # 是否主房间（最大的房间）

func _init(roomTiles, map):
	tiles = roomTiles
	UpdateEdgeTiles(map)

# 更新房间边缘瓦片集
func UpdateEdgeTiles(map):
	edgeTiles.clear()
	# 遍历上下左右四格，判断是否有墙
	for tile in tiles:
		for i in range(4):
			var x = tile.x + GEnum.Vector2_Dir[i].x
			var y = tile.y + GEnum.Vector2_Dir[i].y
			if map[x][y] == GEnum.TileType.Wall && !edgeTiles.has(tile):
				edgeTiles.append(tile)
				
# 标记相对于主房间的连接性
func MarkAccessibleFromMainRoom():
	# 标记自己能够连接到主房间
	if !isAccessibleFromMainRoom:
		isAccessibleFromMainRoom = true
		# 和自己连接的房间都能连到主房间
		for connectedRoom in connectedRooms:
			connectedRoom.MarkAccessibleFromMainRoom()

# 连接房间
func ConnectRooms(roomB):
	# 传递连接标记
	if isAccessibleFromMainRoom:
		roomB.MarkAccessibleFromMainRoom()
	elif roomB.isAccessibleFromMainRoom:
		MarkAccessibleFromMainRoom()
	# 传递连接行为
	connectedRooms.append(roomB)
	roomB.connectedRooms.append(self)

# 是否连接另一个房间
func IsConnected(otherRoom):
	if connectedRooms.find(otherRoom) == -1:
		return false
	else:
		return true

map_generator_base

class_name MapGeneratorBase
extends GridMap

# 地图的宽度
@export var width : int = 64
# 地图的高度
@export var height : int = 64

# 地图种子
@export var mapSeed : String
# 是否使用随机种子
@export var useRandomSeed : bool = true

# 房间列表
var roomList : Array

# Bresenham 直线生成算法
# 对于直线 y = k*x (0<k<1) 
# 每在 x 方向上走一步，直线在 y 方向上都增加一个 k 的距离
# 要确定 y 方向上取直线上方的格还是直线下方的格，即
# d += k > 0.5 d 为累加器，初值为 0，取得直线上方一格后需减 1
# 两边同乘 2*dx 其中 dx 为起点到终点的在 x 方向上的距离，得
# 2*dx*d += 2*dy > dx 其中 dy 为起点到终点的在 x 方向上的距离
func get_line(from, to):
	var line : Array

	var x = from.x
	var y = from.y

	var dx = to.x - from.x
	var dy = to.y - from.y

	var inverted = false
	var step = sign(dx)
	var gradientStep = sign(dy)

	var longest = abs(dx)
	var shortest = abs(dy)

	if longest < shortest:
		inverted = true
		longest = abs(dy)
		shortest = abs(dx)

		step = sign(dy)
		gradientStep = sign(dx)

	var acc = 0
	for i in range(longest):
		line.append(Vector2i(x, y))

		if inverted:
			y += step
		else:
			x += step

		acc += 2*shortest # 梯度每次增长为短边的长度。
		if acc >= longest:
			if inverted:
				x += gradientStep
			else:
				y += gradientStep
			acc -= 2*longest

	return line

# 判断坐标是否在地图里，不管墙还是洞
func is_in_map_range(x, y):
	return x >= 0 && x < width && y >= 0 && y < height

map_generator_1.gd

extends MapGeneratorBase

const Room = preload("room_1.gd")

# 随机填充百分比，越大洞越小
@export_range(0.0,1.0) var fillThreshold : float = 0.55

# 平滑程度（次数）
@export_range(0,20) var smoothLevel : int = 4

# 清除小墙体的阈值
@export var wallThresholdSize : int = 50
# 清除小孔的的阈值
@export var roomThresholdSize : int = 50

# 通道（房间与房间直接）宽度
@export var passageWidth : int = 4

@export var borderSize : int = 1

# 地图集，Empty为空洞，Wall为实体墙
var map : Array

func _ready():
	generate_map()
	set_gridmap_by_empty()

func _input(event):
	if event is InputEventMouseButton:
		match event.button_index:
			MOUSE_BUTTON_LEFT:
				roomList.clear()
				generate_map()
				clear()
				set_gridmap_by_empty()

# 生成随机地图
func generate_map():
	for x in range(width):
		map.append([])
		for y in range(height):
			map[x].append(GEnum.TileType.Empty)
	random_fill_map()

	for i in range(smoothLevel):
		smooth_map()

	# 清除小洞，小墙
	eliminate_small_hole_and_wall()

	# 连接各个幸存房间
	connect_all_rooms_to_mainroom(roomList)

# 设置 3d 瓦片地图
func set_gridmap_by_empty():
	for x in range(width):
		for y in range(height):
			if map[x][y] == GEnum.TileType.Empty:
				set_cell_item(Vector3i(x,0,y),0,0)
	
# 随机填充地图
func random_fill_map():
	if useRandomSeed:
		mapSeed = Time.get_datetime_string_from_system()
	seed(mapSeed.hash())

	for x in range(width):
		for y in range(height):
			if x == 0 || x == width - 1 || y == 0 || y == height - 1:
				map[x][y] = GEnum.TileType.Wall
			else:
				map[x][y] = GEnum.TileType.Wall if randf_range(0,1) < fillThreshold else GEnum.TileType.Empty

# 平滑地图
func smooth_map():
	for x in range(width):
		for y in range(height):
			var neighbourWallTiles = get_surround_wall_count(x, y)
			if neighbourWallTiles > 4: # 周围大于四个墙，那自己也是墙
				map[x][y] = GEnum.TileType.Wall
			elif neighbourWallTiles < 4: #周围大于四个为空，那自己也为空
				map[x][y] = GEnum.TileType.Empty
			# 还有如果四四开，那就保持不变。

# 获取该点周围 8 个点为实体墙（map[x][y] == 1）的个数
func get_surround_wall_count(x, y):
	var wallCount = 0
	for nx in [x-1, x+1]:
		for ny in [y-1, y+1]:
			if nx >= 0 && nx < width && ny >= 0 && ny < height:
				wallCount += 1 if map[x][y] == GEnum.TileType.Wall else 0
			else:
				wallCount += 1
	return wallCount

# 加工地图，清除小洞，小墙，连接房间。
func eliminate_small_hole_and_wall():
	# 获取最大房间的索引
	var currentIndex : int = 0
	var maxIndex : int = 0
	var maxSize : int = 0
	
	# 获取墙区域
	var wallRegions = get_regions(GEnum.TileType.Wall)
	for wallRegion in wallRegions:
		if wallRegion.size() < wallThresholdSize:
			for tile in wallRegion:
				map[tile.x][tile.y] = GEnum.TileType.Empty # 把小于阈值的都铲掉
				
	# 获取空洞区域
	var roomRegions = get_regions(GEnum.TileType.Empty)
	for roomRegion in roomRegions:
		if roomRegion.size() < roomThresholdSize:
			for tile in roomRegion:
				map[tile.x][tile.y] = GEnum.TileType.Wall # 把小于阈值的都填充
		else:
			var sRoom = Room.new(roomRegion, map)
			roomList.append(sRoom) # 添加到幸存房间列表里
			if maxSize < roomRegion.size():
				maxSize = roomRegion.size()
				maxIndex = currentIndex # 找出最大房间的索引
			currentIndex += 1

	if roomList.size() == 0:
		print_debug("No Survived Rooms Here!!")
	else:
		roomList[maxIndex].isMainRoom = true # 最大房间就是主房间
		roomList[maxIndex].isAccessibleFromMainRoom = true

# 获取区域
func get_regions(tileType):
	var regions : Array
	var mapFlags = BitMap.new()
	mapFlags.create(Vector2(width, height))
	
	for x in range(width):
		for y in range(height):
			if mapFlags.get_bit(Vector2(x, y)) == false && map[x][y] == tileType:
				regions.append(get_region_tiles(x, y, tileType, mapFlags))
	
	return regions

# 从这个点开始获取区域，广度优先算法
func get_region_tiles(startX, startY, tileType, mapFlags):
	var tiles : Array
	var quene1 : Array
	var quene2 : Array
	quene1.append(Vector2i(startX, startY))
	mapFlags.set_bit(Vector2(startX, startY), true)

	while quene1.size() > 0:
		var tile = quene1.pop_back()
		tiles.append(tile)

		# 遍历上下左右四格
		for i in range(4):
			var x = tile.x + GEnum.Vector2_Dir[i].x;
			var y = tile.y + GEnum.Vector2_Dir[i].y;
			if is_in_map_range(x, y) && mapFlags.get_bit(Vector2(x, y)) == false && map[x][y] == tileType:
				mapFlags.set_bit(Vector2(x, y), true)
				quene2.append(Vector2i(x, y))

		if quene1.size() == 0:
			quene1 = quene2
			quene2 = Array()

	return tiles

# 把所有房间都连接到主房间
func connect_all_rooms_to_mainroom(allRooms):
	for room in allRooms:
		connect_to_closest_room(room, allRooms)

	var count = 0
	for room in allRooms:
		if room.isAccessibleFromMainRoom:
			count += 1
	if count != allRooms.size():
		connect_all_rooms_to_mainroom(allRooms)
	
# 连接本房间与距离自己最近的一个与自己尚未连接的房间
# 可能找不到满足条件的待连接房间
func connect_to_closest_room(roomA, roomListB):
	var bestDistance : int = 9223372036854775807
	var bestTileA : Vector2i
	var bestTileB : Vector2i
	var bestRoomB
	
	var hasChecked = false
	
	for roomB in roomListB:
		if roomA == roomB || roomA.IsConnected(roomB):
			continue
		
		for tileA in roomA.edgeTiles:
			for tileB in roomB.edgeTiles:
				var distanceBetweenRooms = (tileA - tileB).length_squared()
				# 如果找到更近的（相对roomA）房间，更新最短路径。
				if distanceBetweenRooms < bestDistance:
					bestDistance = distanceBetweenRooms
					bestTileA = tileA
					bestTileB = tileB
					bestRoomB = roomB

	if bestRoomB != null:
		create_passage(roomA, bestRoomB, bestTileA, bestTileB)

# 创建两个房间的通道
func create_passage(roomA, roomB, tileA, tileB):
	roomA.ConnectRooms(roomB)
	var line = get_line(tileA, tileB)
	for coord in line:
		draw_circle(coord, passageWidth)

# 以点c为原点，r为半径，画圈（拆墙）
func draw_circle(c, r):
	for x in range(-r, r):
		for y in range(-r, r):
			if x * x + y * y <= r * r:
				var drawX = c.x + x
				var drawY = c.y + y
				if is_in_map_range(drawX, drawY):
					map[drawX][drawY] = GEnum.TileType.Empty