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# How fast the camera pans to the player. 1.0 is instant.
47CAMERA_SPEED = 0.1
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 = []
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 = []
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(
248 (other, adj[0], 'rows', self.distance_between_rooms(room, other))
249 )
250 elif len(adj[1]) > 0:
251 room_dict[key].append(
252 (other, adj[1], 'cols', self.distance_between_rooms(room, other))
253 )
254
255 groups.append([room])
256
257 while len(groups) > 1:
258 self.find_closest_unconnect_groups(groups, room_dict)
259
260 def generate_map(self):
261 """ Make the map """
262 self.random_split(1, 1, self.height - 1, self.width - 1)
263 self.carve_rooms()
264 self.connect_rooms()
265
266
267class GameView(arcade.View):
268 """
269 Main application class.
270 """
271
272 def __init__(self):
273 super().__init__()
274
275 self.grid = None
276 self.wall_list = None
277 self.player_list = None
278 self.player_sprite = None
279 self.physics_engine = None
280
281 self.processing_time = 0
282 self.draw_time = 0
283
284 self.sprite_count_text = None
285 self.draw_time_text = None
286 self.processing_time_text = None
287
288 # Create the cameras. One for the GUI, one for the sprites.
289 # We scroll the 'sprite world' but not the GUI.
290 self.camera_sprites = arcade.camera.Camera2D()
291 self.camera_gui = arcade.camera.Camera2D()
292
293 self.background_color = arcade.color.BLACK
294
295 def setup(self):
296 """ Set up the game """
297 self.wall_list = arcade.SpriteList(use_spatial_hash=True)
298 self.player_list = arcade.SpriteList()
299
300 # Create cave system using a 2D grid
301 dg = RLDungeonGenerator(GRID_WIDTH, GRID_HEIGHT)
302 dg.generate_map()
303
304 # Create sprites based on 2D grid
305 texture = arcade.load_texture(":resources:images/tiles/grassCenter.png")
306
307 # Each grid location is a sprite.
308 for row in range(dg.height):
309 for column in range(dg.width):
310 value = dg.dungeon[row][column]
311 if value == '#':
312 wall = arcade.BasicSprite(texture, scale=WALL_SPRITE_SCALING)
313 wall.center_x = column * WALL_SPRITE_SIZE + WALL_SPRITE_SIZE / 2
314 wall.center_y = row * WALL_SPRITE_SIZE + WALL_SPRITE_SIZE / 2
315 self.wall_list.append(wall)
316
317 # Set up the player
318 self.player_sprite = arcade.Sprite(
319 ":resources:images/animated_characters/female_person/femalePerson_idle.png",
320 scale=PLAYER_SPRITE_SCALING)
321 self.player_list.append(self.player_sprite)
322
323 # Randomly place the player. If we are in a wall, repeat until we aren't.
324 placed = False
325 while not placed:
326
327 # Randomly position
328 self.player_sprite.center_x = random.randrange(AREA_WIDTH)
329 self.player_sprite.center_y = random.randrange(AREA_HEIGHT)
330
331 # Are we in a wall?
332 walls_hit = arcade.check_for_collision_with_list(self.player_sprite, self.wall_list)
333 if len(walls_hit) == 0:
334 # Not in a wall! Success!
335 placed = True
336
337 # Draw info on the screen
338 sprite_count = len(self.wall_list)
339 output = f"Sprite Count: {sprite_count:,}"
340 self.sprite_count_text = arcade.Text(output,
341 20,
342 self.height - 20,
343 arcade.color.WHITE, 16)
344
345 output = "Drawing time:"
346 self.draw_time_text = arcade.Text(output,
347 20,
348 self.height - 40,
349 arcade.color.WHITE, 16)
350
351 output = "Processing time:"
352 self.processing_time_text = arcade.Text(output,
353 20,
354 self.height - 60,
355 arcade.color.WHITE, 16)
356
357 self.physics_engine = arcade.PhysicsEngineSimple(self.player_sprite,
358 self.wall_list)
359
360 self.scroll_to_player(camera_speed=1.0)
361
362 def on_draw(self):
363 """ Render the screen. """
364
365 # Start timing how long this takes
366 draw_start_time = timeit.default_timer()
367
368 # This command should happen before we start drawing. It will clear
369 # the screen to the background color, and erase what we drew last frame.
370 self.clear()
371
372 # Select the scrolling camera
373 with self.camera_sprites.activate():
374 # Draw the sprites
375 self.wall_list.draw()
376 self.player_list.draw()
377
378 # Use the non-scrolling camera
379 with self.camera_gui.activate():
380 # Draw info on the screen
381 self.sprite_count_text.draw()
382 output = f"Drawing time: {self.draw_time:.3f}"
383 self.draw_time_text.text = output
384 self.draw_time_text.draw()
385
386 output = f"Processing time: {self.processing_time:.3f}"
387 self.processing_time_text.text = output
388 self.processing_time_text.draw()
389 self.draw_time = timeit.default_timer() - draw_start_time
390
391 def on_key_press(self, key, modifiers):
392 """Called whenever a key is pressed. """
393
394 if key == arcade.key.UP:
395 self.player_sprite.change_y = MOVEMENT_SPEED
396 elif key == arcade.key.DOWN:
397 self.player_sprite.change_y = -MOVEMENT_SPEED
398 elif key == arcade.key.LEFT:
399 self.player_sprite.change_x = -MOVEMENT_SPEED
400 elif key == arcade.key.RIGHT:
401 self.player_sprite.change_x = MOVEMENT_SPEED
402
403 def on_key_release(self, key, modifiers):
404 """Called when the user releases a key. """
405
406 if key == arcade.key.UP or key == arcade.key.DOWN:
407 self.player_sprite.change_y = 0
408 elif key == arcade.key.LEFT or key == arcade.key.RIGHT:
409 self.player_sprite.change_x = 0
410
411 def scroll_to_player(self, camera_speed):
412 """
413 Scroll the window to the player.
414
415 if CAMERA_SPEED is 1, the camera will immediately move to the desired position.
416 Anything between 0 and 1 will have the camera move to the location with a smoother
417 pan.
418 """
419
420 position = (self.player_sprite.center_x, self.player_sprite.center_y)
421 self.camera_sprites.position = arcade.math.lerp_2d(
422 self.camera_sprites.position,
423 position,
424 camera_speed,
425 )
426
427 def on_update(self, delta_time):
428 """ Movement and game logic """
429
430 start_time = timeit.default_timer()
431
432 # Move the player
433 self.physics_engine.update()
434
435 # Scroll the screen to the player
436 self.scroll_to_player(camera_speed=CAMERA_SPEED)
437
438 # Save the time it took to do this.
439 self.processing_time = timeit.default_timer() - start_time
440
441
442def main():
443 """ Main function """
444 # Create a window class. This is what actually shows up on screen
445 window = arcade.Window(WINDOW_WIDTH, WINDOW_HEIGHT, WINDOW_TITLE)
446
447 # Create and setup the GameView
448 game = GameView()
449 game.setup()
450
451 # Show GameView on screen
452 window.show_view(game)
453
454 # Start the arcade game loop
455 arcade.run()
456
457
458if __name__ == "__main__":
459 main()