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