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