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:
  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()