Procedural Caves - Binary Space Partitioning

Screen shot of using Binary Space Partitioning to generate caves
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()