Procedural Caves - Binary Space Partitioning¶
procedural_caves_bsp.py¶
1"""
2This example procedurally develops a random cave based on
3Binary Space Partitioning (BSP)
4
5For more information, see:
6https://roguebasin.roguelikedevelopment.org/index.php?title=Basic_BSP_Dungeon_generation
7https://github.com/DanaL/RLDungeonGenerator
8
9If Python and Arcade are installed, this example can be run from the command line with:
10python -m arcade.examples.procedural_caves_bsp
11"""
12
13import random
14import arcade
15import timeit
16import math
17
18# Sprite scaling. Make this larger, like 0.5 to zoom in and add
19# 'mystery' to what you can see. Make it smaller, like 0.1 to see
20# more of the map.
21WALL_SPRITE_SCALING = 0.5
22PLAYER_SPRITE_SCALING = 0.25
23
24WALL_SPRITE_SIZE = int(128 * WALL_SPRITE_SCALING)
25
26# How big the grid is
27GRID_WIDTH = 100
28GRID_HEIGHT = 100
29
30AREA_WIDTH = GRID_WIDTH * WALL_SPRITE_SIZE
31AREA_HEIGHT = GRID_HEIGHT * WALL_SPRITE_SIZE
32
33# How fast the player moves
34MOVEMENT_SPEED = 5
35
36# How close the player can get to the edge before we scroll.
37VIEWPORT_MARGIN = 300
38
39# How big the window is
40WINDOW_WIDTH = 800
41WINDOW_HEIGHT = 600
42WINDOW_TITLE = "Procedural Caves BSP Example"
43
44MERGE_SPRITES = False
45
46
47class Room:
48 """ A room """
49 def __init__(self, r, c, h, w):
50 self.row = r
51 self.col = c
52 self.height = h
53 self.width = w
54
55
56class RLDungeonGenerator:
57 """ Generate the dungeon """
58 def __init__(self, w, h):
59 """ Create the board """
60 self.MAX = 15 # Cutoff for when we want to stop dividing sections
61 self.width = w
62 self.height = h
63 self.leaves = []
64 self.dungeon = []
65 self.rooms = []
66
67 for h in range(self.height):
68 row = []
69 for w in range(self.width):
70 row.append('#')
71
72 self.dungeon.append(row)
73
74 def random_split(self, min_row, min_col, max_row, max_col):
75 # We want to keep splitting until the sections get down to the threshold
76 seg_height = max_row - min_row
77 seg_width = max_col - min_col
78
79 if seg_height < self.MAX and seg_width < self.MAX:
80 self.leaves.append((min_row, min_col, max_row, max_col))
81 elif seg_height < self.MAX <= seg_width:
82 self.split_on_vertical(min_row, min_col, max_row, max_col)
83 elif seg_height >= self.MAX > seg_width:
84 self.split_on_horizontal(min_row, min_col, max_row, max_col)
85 else:
86 if random.random() < 0.5:
87 self.split_on_horizontal(min_row, min_col, max_row, max_col)
88 else:
89 self.split_on_vertical(min_row, min_col, max_row, max_col)
90
91 def split_on_horizontal(self, min_row, min_col, max_row, max_col):
92 split = (min_row + max_row) // 2 + random.choice((-2, -1, 0, 1, 2))
93 self.random_split(min_row, min_col, split, max_col)
94 self.random_split(split + 1, min_col, max_row, max_col)
95
96 def split_on_vertical(self, min_row, min_col, max_row, max_col):
97 split = (min_col + max_col) // 2 + random.choice((-2, -1, 0, 1, 2))
98 self.random_split(min_row, min_col, max_row, split)
99 self.random_split(min_row, split + 1, max_row, max_col)
100
101 def carve_rooms(self):
102 for leaf in self.leaves:
103 # We don't want to fill in every possible room or the
104 # dungeon looks too uniform
105 if random.random() > 0.80:
106 continue
107 section_width = leaf[3] - leaf[1]
108 section_height = leaf[2] - leaf[0]
109
110 # The actual room's height and width will be 60-100% of the
111 # available section.
112 room_width = round(random.randrange(60, 100) / 100 * section_width)
113 room_height = round(random.randrange(60, 100) / 100 * section_height)
114
115 # If the room doesn't occupy the entire section we are carving it from,
116 # 'jiggle' it a bit in the square
117 if section_height > room_height:
118 room_start_row = leaf[0] + random.randrange(section_height - room_height)
119 else:
120 room_start_row = leaf[0]
121
122 if section_width > room_width:
123 room_start_col = leaf[1] + random.randrange(section_width - room_width)
124 else:
125 room_start_col = leaf[1]
126
127 self.rooms.append(Room(room_start_row, room_start_col, room_height, room_width))
128 for r in range(room_start_row, room_start_row + room_height):
129 for c in range(room_start_col, room_start_col + room_width):
130 self.dungeon[r][c] = '.'
131
132 @staticmethod
133 def are_rooms_adjacent(room1, room2):
134 """ See if two rooms are next to each other. """
135 adj_rows = []
136 adj_cols = []
137 for r in range(room1.row, room1.row + room1.height):
138 if room2.row <= r < room2.row + room2.height:
139 adj_rows.append(r)
140
141 for c in range(room1.col, room1.col + room1.width):
142 if room2.col <= c < room2.col + room2.width:
143 adj_cols.append(c)
144
145 return adj_rows, adj_cols
146
147 @staticmethod
148 def distance_between_rooms(room1, room2):
149 """ Get the distance between two rooms """
150 centre1 = (room1.row + room1.height // 2, room1.col + room1.width // 2)
151 centre2 = (room2.row + room2.height // 2, room2.col + room2.width // 2)
152
153 return math.sqrt((centre1[0] - centre2[0]) ** 2 + (centre1[1] - centre2[1]) ** 2)
154
155 def carve_corridor_between_rooms(self, room1, room2):
156 """ Make a corridor between rooms """
157 if room2[2] == 'rows':
158 row = random.choice(room2[1])
159 # Figure out which room is to the left of the other
160 if room1.col + room1.width < room2[0].col:
161 start_col = room1.col + room1.width
162 end_col = room2[0].col
163 else:
164 start_col = room2[0].col + room2[0].width
165 end_col = room1.col
166 for c in range(start_col, end_col):
167 self.dungeon[row][c] = '.'
168
169 if end_col - start_col >= 4:
170 self.dungeon[row][start_col] = '+'
171 self.dungeon[row][end_col - 1] = '+'
172 elif start_col == end_col - 1:
173 self.dungeon[row][start_col] = '+'
174 else:
175 col = random.choice(room2[1])
176 # Figure out which room is above the other
177 if room1.row + room1.height < room2[0].row:
178 start_row = room1.row + room1.height
179 end_row = room2[0].row
180 else:
181 start_row = room2[0].row + room2[0].height
182 end_row = room1.row
183
184 for r in range(start_row, end_row):
185 self.dungeon[r][col] = '.'
186
187 if end_row - start_row >= 4:
188 self.dungeon[start_row][col] = '+'
189 self.dungeon[end_row - 1][col] = '+'
190 elif start_row == end_row - 1:
191 self.dungeon[start_row][col] = '+'
192
193 def find_closest_unconnect_groups(self, groups, room_dict):
194 """
195 Find two nearby rooms that are in difference groups, draw
196 a corridor between them and merge the groups
197 """
198
199 shortest_distance = 99999
200 start = None
201 start_group = None
202 nearest = None
203
204 for group in groups:
205 for room in group:
206 key = (room.row, room.col)
207 for other in room_dict[key]:
208 if other[0] not in group and other[3] < shortest_distance:
209 shortest_distance = other[3]
210 start = room
211 nearest = other
212 start_group = group
213
214 self.carve_corridor_between_rooms(start, nearest)
215
216 # Merge the groups
217 other_group = None
218 for group in groups:
219 if nearest[0] in group:
220 other_group = group
221 break
222
223 start_group += other_group
224 groups.remove(other_group)
225
226 def connect_rooms(self):
227 """
228 Build a dictionary containing an entry for each room. Each bucket will
229 hold a list of the adjacent rooms, weather they are adjacent along rows or
230 columns and the distance between them.
231
232 Also build the initial groups (which start of as a list of individual rooms)
233 """
234 groups = []
235 room_dict = {}
236 for room in self.rooms:
237 key = (room.row, room.col)
238 room_dict[key] = []
239 for other in self.rooms:
240 other_key = (other.row, other.col)
241 if key == other_key:
242 continue
243 adj = self.are_rooms_adjacent(room, other)
244 if len(adj[0]) > 0:
245 room_dict[key].append((other, adj[0], 'rows', self.distance_between_rooms(room, other)))
246 elif len(adj[1]) > 0:
247 room_dict[key].append((other, adj[1], 'cols', self.distance_between_rooms(room, other)))
248
249 groups.append([room])
250
251 while len(groups) > 1:
252 self.find_closest_unconnect_groups(groups, room_dict)
253
254 def generate_map(self):
255 """ Make the map """
256 self.random_split(1, 1, self.height - 1, self.width - 1)
257 self.carve_rooms()
258 self.connect_rooms()
259
260
261class MyGame(arcade.Window):
262 """
263 Main application class.
264 """
265
266 def __init__(self, width, height, title):
267 super().__init__(width, height, title)
268
269 self.grid = None
270 self.wall_list = None
271 self.player_list = None
272 self.player_sprite = None
273 self.cam = None
274 self.physics_engine = None
275
276 self.processing_time = 0
277 self.draw_time = 0
278
279 self.background_color = arcade.color.BLACK
280
281 def setup(self):
282 """ Set up the game """
283 self.wall_list = arcade.SpriteList(use_spatial_hash=True)
284 self.player_list = arcade.SpriteList()
285
286 # Create cave system using a 2D grid
287 dg = RLDungeonGenerator(GRID_WIDTH, GRID_HEIGHT)
288 dg.generate_map()
289
290 # Create sprites based on 2D grid
291 texture = arcade.load_texture(":resources:images/tiles/grassCenter.png")
292 if not MERGE_SPRITES:
293 # This is the simple-to-understand method. Each grid location
294 # is a sprite.
295 for row in range(dg.height):
296 for column in range(dg.width):
297 value = dg.dungeon[row][column]
298 if value == '#':
299 wall = arcade.BasicSprite(texture, scale=WALL_SPRITE_SCALING)
300 wall.center_x = column * WALL_SPRITE_SIZE + WALL_SPRITE_SIZE / 2
301 wall.center_y = row * WALL_SPRITE_SIZE + WALL_SPRITE_SIZE / 2
302 self.wall_list.append(wall)
303 else:
304 # This uses new Arcade 1.3.1 features, that allow me to create a
305 # larger sprite with a repeating texture. So if there are multiple
306 # cells in a row with a wall, we merge them into one sprite, with a
307 # repeating texture for each cell. This reduces our sprite count.
308 for row in range(dg.height):
309 column = 0
310 while column < dg.width:
311 while column < dg.width and dg.dungeon[row][column] != '#':
312 column += 1
313 start_column = column
314 while column < dg.width and dg.dungeon[row][column] == '#':
315 column += 1
316 end_column = column - 1
317
318 column_count = end_column - start_column + 1
319 column_mid = (start_column + end_column) / 2
320
321 wall = arcade.BasicSprite(texture, scale=WALL_SPRITE_SCALING)
322 wall.center_x = column_mid * WALL_SPRITE_SIZE + WALL_SPRITE_SIZE / 2
323 wall.center_y = row * WALL_SPRITE_SIZE + WALL_SPRITE_SIZE / 2
324 wall.width = WALL_SPRITE_SIZE * column_count
325 self.wall_list.append(wall)
326
327 # Set up the player
328 self.player_sprite = arcade.Sprite(
329 ":resources:images/animated_characters/female_person/femalePerson_idle.png",
330 scale=PLAYER_SPRITE_SCALING)
331 self.player_list.append(self.player_sprite)
332
333 # Randomly place the player. If we are in a wall, repeat until we aren't.
334 placed = False
335 while not placed:
336
337 # Randomly position
338 self.player_sprite.center_x = random.randrange(AREA_WIDTH)
339 self.player_sprite.center_y = random.randrange(AREA_HEIGHT)
340
341 # Are we in a wall?
342 walls_hit = arcade.check_for_collision_with_list(self.player_sprite, self.wall_list)
343 if len(walls_hit) == 0:
344 # Not in a wall! Success!
345 placed = True
346
347 self.physics_engine = arcade.PhysicsEngineSimple(self.player_sprite,
348 self.wall_list)
349
350 self.cam = arcade.camera.Camera2D()
351
352 def on_draw(self):
353 """ Render the screen. """
354
355 # Start timing how long this takes
356 draw_start_time = timeit.default_timer()
357
358 # This command should happen before we start drawing. It will clear
359 # the screen to the background color, and erase what we drew last frame.
360 self.clear()
361
362 # Draw the sprites
363 self.wall_list.draw()
364 self.player_list.draw()
365
366 # Draw info on the screen
367 sprite_count = len(self.wall_list)
368
369 output = f"Sprite Count: {sprite_count}"
370 arcade.draw_text(output,
371 self.cam.left + 20,
372 WINDOW_HEIGHT - 20 + self.cam.bottom,
373 arcade.color.WHITE, 16)
374
375 output = f"Drawing time: {self.draw_time:.3f}"
376 arcade.draw_text(output,
377 self.cam.left + 20,
378 WINDOW_HEIGHT - 40 + self.cam.bottom,
379 arcade.color.WHITE, 16)
380
381 output = f"Processing time: {self.processing_time:.3f}"
382 arcade.draw_text(output,
383 self.cam.left + 20,
384 WINDOW_HEIGHT - 60 + self.cam.bottom,
385 arcade.color.WHITE, 16)
386
387 self.draw_time = timeit.default_timer() - draw_start_time
388
389 def on_key_press(self, key, modifiers):
390 """Called whenever a key is pressed. """
391
392 if key == arcade.key.UP:
393 self.player_sprite.change_y = MOVEMENT_SPEED
394 elif key == arcade.key.DOWN:
395 self.player_sprite.change_y = -MOVEMENT_SPEED
396 elif key == arcade.key.LEFT:
397 self.player_sprite.change_x = -MOVEMENT_SPEED
398 elif key == arcade.key.RIGHT:
399 self.player_sprite.change_x = MOVEMENT_SPEED
400
401 def on_key_release(self, key, modifiers):
402 """Called when the user releases a key. """
403
404 if key == arcade.key.UP or key == arcade.key.DOWN:
405 self.player_sprite.change_y = 0
406 elif key == arcade.key.LEFT or key == arcade.key.RIGHT:
407 self.player_sprite.change_x = 0
408
409 def on_update(self, delta_time):
410 """ Movement and game logic """
411
412 start_time = timeit.default_timer()
413
414 # Move the player
415 self.physics_engine.update()
416
417 # --- Manage Scrolling ---
418
419 # Track if we need to change the viewport
420
421 changed = False
422
423 # Scroll left
424 left_bndry = self.cam.left + VIEWPORT_MARGIN
425 if self.player_sprite.left < left_bndry:
426 self.cam.left -= left_bndry - self.player_sprite.left
427 changed = True
428
429 # Scroll right
430 right_bndry = self.cam.right - VIEWPORT_MARGIN
431 if self.player_sprite.right > right_bndry:
432 self.cam.left += self.player_sprite.right - right_bndry
433 changed = True
434
435 # Scroll up
436 top_bndry = self.cam.top - VIEWPORT_MARGIN
437 if self.player_sprite.top > top_bndry:
438 self.cam.bottom += self.player_sprite.top - top_bndry
439 changed = True
440
441 # Scroll down
442 bottom_bndry = self.cam.bottom + VIEWPORT_MARGIN
443 if self.player_sprite.bottom < bottom_bndry:
444 self.cam.bottom -= bottom_bndry - self.player_sprite.bottom
445 changed = True
446
447 if changed:
448 self.cam.use()
449
450 # Save the time it took to do this.
451 self.processing_time = timeit.default_timer() - start_time
452
453
454def main():
455 """ Main function, start up window and run """
456 game = MyGame(WINDOW_WIDTH, WINDOW_HEIGHT, WINDOW_TITLE)
457 game.setup()
458 arcade.run()
459
460
461if __name__ == "__main__":
462 main()