# Procedural Caves - Binary Space Partitioning¶

procedural_caves_bsp.py
```  1"""
2This example procedurally develops a random cave based on
3Binary Space Partitioning (BSP)
4
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:
11"""
12
13import random
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:
140
141        for c in range(room1.col, room1.col + room1.width):
142            if room2.col <= c < room2.col + room2.width:
144
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
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
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
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        left, bottom = self.cam.bottom_left
372                         left + 20,
373                         WINDOW_HEIGHT - 20 + bottom,
375
376        output = f"Drawing time: {self.draw_time:.3f}"
378                         left + 20,
379                         WINDOW_HEIGHT - 40 + bottom,
381
382        output = f"Processing time: {self.processing_time:.3f}"
384                         left + 20,
385                         WINDOW_HEIGHT - 60 + bottom,
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        # Keep track of if we changed the boundary. We don't want to
421        # update the camera if we don't need to.
422        changed = False
423
424        pos = self.cam.position
425
426        top_left = self.cam.top_left
427        bottom_right = self.cam.bottom_right
428
429        # Scroll left
430        left_boundary = top_left[0] + VIEWPORT_MARGIN
431        if self.player_sprite.left < left_boundary:
432            changed = True
433            pos = pos[0] + (self.player_sprite.left - left_boundary), pos[1]
434
435        # Scroll up
436        top_boundary = top_left[1] - VIEWPORT_MARGIN
437        if self.player_sprite.top > top_boundary:
438            changed = True
439            pos = pos[0], pos[1] + (self.player_sprite.top - top_boundary)
440
441        # Scroll right
442        right_boundary = bottom_right[0] - VIEWPORT_MARGIN
443        if self.player_sprite.right > right_boundary:
444            changed = True
445            pos = pos[0] + (self.player_sprite.right - right_boundary), pos[1]
446
447        # Scroll down
448        bottom_boundary = bottom_right[1] + VIEWPORT_MARGIN
449        if self.player_sprite.bottom < bottom_boundary:
450            changed = True
451            pos = pos[0], pos[1] + (self.player_sprite.bottom - bottom_boundary)
452
453        # If we changed the boundary values, update the view port to match
454        if changed:
455            print(pos)
456            self.cam.position = pos
457            self.cam.use()
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 function, start up window and run """
465    game = MyGame(WINDOW_WIDTH, WINDOW_HEIGHT, WINDOW_TITLE)
466    game.setup()