# Procedural Caves - Binary Space Partitioning¶

procedural_caves_bsp.py
```  1"""
2This example procedurally develops a random cave based on
3Binary Space Partitioning (BSP)
4
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:
11"""
12
13import random
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
135        """ See if two rooms are next to each other. """
138        for r in range(room1.row, room1.row + room1.height):
139            if room2.row <= r < room2.row + room2.height:
141
142        for c in range(room1.col, room1.col + room1.width):
143            if room2.col <= c < room2.col + room2.width:
145
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
246                    room_dict[key].append((other, adj[0], 'rows', self.distance_between_rooms(room, other)))
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
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
289
290    def setup(self):
291        """ Set up the game """
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 == '#':
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
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
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?
351            if len(walls_hit) == 0:
352                # Not in a wall! Success!
353                placed = True
354
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.
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}"
377                         self.view_left + 20,
378                         WINDOW_HEIGHT - 20 + self.view_bottom,
380
381        output = f"Drawing time: {self.draw_time:.3f}"
383                         self.view_left + 20,
384                         WINDOW_HEIGHT - 40 + self.view_bottom,
386
387        output = f"Processing time: {self.processing_time:.3f}"
389                         self.view_left + 20,
390                         WINDOW_HEIGHT - 60 + self.view_bottom,
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
399            self.player_sprite.change_y = MOVEMENT_SPEED
401            self.player_sprite.change_y = -MOVEMENT_SPEED
403            self.player_sprite.change_x = -MOVEMENT_SPEED
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
411            self.player_sprite.change_y = 0
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:
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()