1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
extends Node3D
@export_category("Level Generator")
@export var width: int = 40
@export var height: int = 40
@export var min_dim: int = 5
@export_category("Geometry Generator")
## Geometry generation config
@export var wall_thickness: float = 1
var wall_inst = preload("res://models/wall.blend")
var level_geo: Node3D
enum Direction {LEFT, RIGHT}
signal grid_generated(grid: Array[Tile], p_grid_width: int, p_grid_height: int)
var min_room_size: int = min_dim * min_dim
var grid_width = width + 1
var grid_height = height + 1
class BSPNode:
var axis: int
var min_dims: Vector2i
var max_dims: Vector2i
var left: BSPNode
var right: BSPNode
func _init(p_axis: int, p_min_dims: Vector2i, p_max_dims: Vector2i, p_left: BSPNode, p_right: BSPNode):
axis = p_axis
min_dims = p_min_dims
max_dims = p_max_dims
left = p_left
right = p_right
func generate_level(axis: int, min_space: Vector2i, max_space: Vector2i, depth: int = 0) -> BSPNode:
var dims = max_space - min_space
var new_axis = (axis + 1) % 2
# 10% we stop here and just create a big room
if (depth > 2 and randi_range(0, 9) == 0) \
or dims.x * dims.y <= min_dim * min_dim \
or dims[new_axis] / 2 < min_dim:
return BSPNode.new(new_axis, min_space, max_space, null, null)
# Calculate min and max ranges so that a split
# doesn't create a room that violates min dimensions
var min_value = min_space[axis] + min_dim
var max_value = max_space[axis] - min_dim
var split = randi_range(min_value, max_value)
#print("Spliting axis ", axis, " at ", split)
var left_min_space = min_space
var left_max_space = max_space
left_max_space[axis] = split
var left = generate_level(new_axis, left_min_space, left_max_space, depth + 1)
var right_min_space = min_space
right_min_space[axis] = split
var right_max_space = max_space
var right = generate_level(new_axis, right_min_space, right_max_space, depth + 1)
return BSPNode.new(axis, min_space, max_space, left, right)
func is_leaf(node: BSPNode) -> bool:
return node.left == null and node.right == null
func check_door(grid: Array[Tile.Tile], axis: int, door_pos: Vector2i) -> bool:
var room_left = door_pos
room_left[axis] -= 1
var room_right = door_pos
room_right[axis] += 1
if door_pos.x >= grid_width or door_pos.y >= grid_height:
return false
if room_left.x >= grid_width or room_left.y >= grid_height:
return false
if room_right.x >= grid_width or room_right.y >= grid_height:
return false
# Check if there are two spaces to connect
# And ensure no door already exists in the space
return grid[room_left.y * grid_width + room_left.x] == Tile.Tile.FLOOR \
and grid[room_right.y * grid_width + room_right.x] == Tile.Tile.FLOOR \
and grid[door_pos.y * grid_width + door_pos.x] == Tile.Tile.WALL
func generate_grid(map: BSPNode, grid: Array[Tile.Tile]) -> void:
if is_leaf(map):
for y in range(map.min_dims.y, map.max_dims.y - 1):
for x in range(map.min_dims.x, map.max_dims.x - 1):
grid[(y+1) * grid_width + (x+1)] = Tile.Tile.FLOOR
else:
generate_grid(map.left, grid)
generate_grid(map.right, grid)
# Look for space on dividing wall to place door
var other_axis = (map.axis + 1) % 2
var split_axis = map.left.max_dims[map.axis]
var have_door = false
var tries = 0
while not have_door:
var test_door = randi_range(map.min_dims[other_axis], map.max_dims[other_axis] - 1)
var door_pos = Vector2i.ZERO
door_pos[map.axis] = split_axis
door_pos[other_axis] = test_door + 1
var door_pos2 = door_pos
door_pos2[other_axis] += 1
if check_door(grid, map.axis, door_pos) and check_door(grid, map.axis, door_pos2):
have_door = true
# Place grid for mesh
grid[door_pos.y * grid_width + door_pos.x] = Tile.Tile.DOOR
grid[door_pos2.y * grid_width + door_pos2.x] = Tile.Tile.DOOR
#door_pos[map.axis] -= 1
#grid[door_pos.y * grid_width + door_pos.x] = Tile.Tile.FLOOR
tries += 1
if tries > 1000:
print("Took too many attempts to generate a door")
get_tree().quit()
return
func generate_plane(array: Array, pos: Vector3, dim: Array[Vector3], normal: Vector3) -> void:
var index = len(array[Mesh.ARRAY_VERTEX])
array[Mesh.ARRAY_VERTEX].append(wall_thickness*pos)
array[Mesh.ARRAY_VERTEX].append(wall_thickness*(pos+dim[0]))
array[Mesh.ARRAY_VERTEX].append(wall_thickness*(pos+dim[0]+dim[1]))
array[Mesh.ARRAY_VERTEX].append(wall_thickness*(pos+dim[1]))
array[Mesh.ARRAY_NORMAL].append(normal)
array[Mesh.ARRAY_NORMAL].append(normal)
array[Mesh.ARRAY_NORMAL].append(normal)
array[Mesh.ARRAY_NORMAL].append(normal)
array[Mesh.ARRAY_INDEX].append(index + 0)
array[Mesh.ARRAY_INDEX].append(index + 1)
array[Mesh.ARRAY_INDEX].append(index + 2)
array[Mesh.ARRAY_INDEX].append(index + 0)
array[Mesh.ARRAY_INDEX].append(index + 2)
array[Mesh.ARRAY_INDEX].append(index + 3)
func generate_geo(grid: Array[Tile.Tile], array: Array) -> void:
for y in range(grid_height):
for x in range(grid_width):
var tile = grid[y * grid_width + x]
if tile == Tile.Tile.FLOOR or tile == Tile.Tile.DOOR:
generate_plane(array, Vector3(x, 0, y), [Vector3(1, 0, 0), Vector3(0, 0, 1)], Vector3.UP)
var floor_tile: Node3D = level_geo.get_node("./Floor").duplicate()
floor_tile.position = Vector3(x, 0, y)
add_child(floor_tile)
var ciel_tile: Node3D = level_geo.get_node("./Floor").duplicate()
ciel_tile.rotate_z(deg_to_rad(180))
ciel_tile.position = Vector3(x+1, 2, y)
add_child(ciel_tile)
elif tile == Tile.Tile.WALL:
generate_plane(array, Vector3(x, 2, y), [Vector3(0, 0, 1), Vector3(0, -2, 0)], Vector3.LEFT)
generate_plane(array, Vector3(x, 2, y+1), [Vector3(1, 0, 0), Vector3(0, -2, 0)], Vector3.BACK)
generate_plane(array, Vector3(x+1, 2, y+1), [Vector3(0, 0, -1), Vector3(0, -2, 0)], Vector3.RIGHT)
generate_plane(array, Vector3(x+1, 2, y), [Vector3(-1, 0, 0), Vector3(0, -2, 0)], Vector3.FORWARD)
var wall: Node3D = level_geo.get_node("./Wall").duplicate()
wall.position = Vector3(x, 0, y)
add_child(wall)
func _ready() -> void:
var starting_axis = randi_range(0, 1)
var min_space = Vector2i(0, 0)
var max_space = Vector2i(width, height)
var map = generate_level(starting_axis, min_space, max_space)
var grid: Array[Tile.Tile] = []
grid.resize(grid_width * grid_height)
grid.fill(Tile.Tile.WALL)
var surface_array = []
surface_array.resize(Mesh.ARRAY_MAX)
surface_array[Mesh.ARRAY_VERTEX] = PackedVector3Array()
surface_array[Mesh.ARRAY_INDEX] = PackedInt32Array()
surface_array[Mesh.ARRAY_NORMAL] = PackedVector3Array()
generate_grid(map, grid)
grid_generated.emit(grid, grid_width, grid_height)
level_geo = wall_inst.instantiate()
generate_geo(grid, surface_array)
var mesh = ArrayMesh.new()
mesh.add_surface_from_arrays(Mesh.PRIMITIVE_TRIANGLES, surface_array)
var tri_mesh = mesh.create_trimesh_shape()
$NavigationRegion3D/StaticBody3D/CollisionShape3D.shape = tri_mesh
#$NavigationRegion3D.navigation_mesh = NavigationMesh.new()
#$NavigationRegion3D.navigation_mesh.radius
$NavigationRegion3D.bake_navigation_mesh(false)
|
