Technical Dive into Procedural Room Generation and Connection in Maps

In this post, we explore the technical aspects of generating and connecting rooms procedurally within a map, a key technique in game development and simulations to create dynamic and varied environments.

Procedural Generation: An Overview

Procedural generation refers to the algorithmic creation of data with randomness, widely used for generating maps in games. This method allows for a high degree of variability, ensuring that each map is unique. The core principle involves using algorithms and randomness to layout elements like rooms, corridors, and obstacles.

Note: The matrix has three dimensions to it so we can denote depth in the map. Full definitions of helper functions can be found at the end of the page.

Initializing the Map

The first step in our procedural generation process is initializing the map with a base tile, typically representing the ground:

def init_map(initial_tile=TILE_TYPES['Ground']):
  # initialize the map with 0 values
  matrix = np.full((MAP_SIZE, MAP_SIZE, MAP_DEPTH), 0)
  for x in range(MAP_SIZE):
    for y in range(MAP_SIZE):
      # place ground tile type on the entirety of the lowest "depth"
      place_tile(matrix, initial_tile, [y, x])
  return matrix

This function creates a 3D NumPy array representing our map, filling it with an initial tile type, ensuring we have a starting point for adding more complex structures.

Room Generation

Rooms are generated using the create_rooms function, which randomly determines their number, size, and position:

def create_rooms(game_map, num_rooms, obstruction_tile, ground_tile, local_rand):
  # keep track of created rooms
  rooms = []
  for _ in range(num_rooms):
    rooms.append(create_room(game_map, local_rand, obstruction_tile))
  # remove walls that overlap w/ each other
  solve_room_overlap(game_map, rooms, ground_tile)
  
  # connect the rooms
  rooms = connect_rooms(game_map, rooms, obstruction_tile, ground_tile)
  return rooms

Each room is created and placed on the map ensuring it fits within the map boundaries. The create_room function is responsible for the specifics of each room's dimensions and location.

Handling Room Overlaps

The `solve_room_overlap` function addresses any overlaps between rooms, adjusting their positions or modifying walls to ensure each room is distinct. without these overlaps we would end up with many occurrences of rooms that look like so:
overlaps
def solve_room_overlap(game_map, rooms, tile_type):
  """for each room in rooms, check if overlap is present. if so, remove the overlapping sections of walls"""
  for i, room1 in enumerate(rooms):
    for room2 in rooms[i + 1:]:
      if rooms_overlap(room1, room2):
        remove_internal_walls(game_map, room1, room2, tile_type)

by removing the overlapping internal walls, we end up with something that makes sense

overlaps_solved

Connecting Rooms

The connect_rooms function weaves the rooms together by creating corridors or paths, making the map navigable:

def connect_rooms(game_map, rooms, wall_tile, ground_tile):
  """for each room, find the closest room in rooms, then draw a line connecting each room's midpoint"""
  while len(rooms) > 1:
    room = rooms.pop(0)
    closest_room = find_closest_room(room, rooms)
    if closest_room:
      create_hallway(game_map, room, closest_room, wall_tile, ground_tile)
  return rooms
overlaps overlaps

This function ensures each room is connected to at least one other room, using the create_hallway function to lay down the paths.

Conclusion

Through this technical exploration, we've seen how procedural generation can be harnessed to create complex and varied map layouts with interconnected rooms. This process, from initialization to visualization, showcases the power of algorithmic content creation in crafting immersive game environments.

This example barely scratches the surface of what we can do with simple techniques.

Give me a lever long enough and a fulcrum on which to place it, and I shall move the world.

Archimedes

Helper Functions

def place_tile(game_map, tile, p, lvl=0):
  """ 
  place the given tile at the given location
  """
  if p[0] < 0 or p[1] < 0:
    # return if out of bounds of map
    return
  try:
    game_map[*p, lvl] = tile
  except IndexError:
    pass


def create_room(game_map, local_rand, tile_type):
  # randomly place a room outlined by the provided tiletype
  width = local_rand.randint(4, 10)
  height = local_rand.randint(4, 10)

  start_x = local_rand.randint(0, MAP_SIZE - width)
  start_y = local_rand.randint(0, MAP_SIZE - height)

  for i in range(width):
    for j in range(height):
      x = start_x + i
      y = start_y + j
      if i == 0 or j == 0 or i == width - 1 or j == height - 1:
        place_tile(game_map, tile_type, [y, x])
  return start_x, start_y, width, height


def rooms_overlap(room1, room2):
  if isinstance(room1, list) and isinstance(room2, list) and isinstance(room1[0], list):
    # Both rooms are defined as lists of 4 points where each point is [y, x]
    # Extract the points
    tl1, tr1, br1, bl1 = room1
    tl2, tr2, br2, bl2 = room2

    # Check for overlap
    return (
      tl1[0] <= br2[0] and br1[0] >= tl2[0] and  # Check vertical overlap
      tl1[1] <= br2[1] and br1[1] >= tl2[1]  # Check horizontal overlap
    )
  else:
    # Unpack room parameters
    x1, y1, w1, h1 = room1
    x2, y2, w2, h2 = room2

    # Check for overlap
    return (x1 < x2 + w2 and x1 + w1 > x2 and
            y1 < y2 + h2 and y1 + h1 > y2)


def remove_internal_walls(game_map, room1, room2, tile_type):
  # Modify the walls of room1 and room2 that are internal after the overlap
  def modify_walls(start_x, start_y, width, height):
    for i in range(width):
      for j in range(height):
        if 0 < i < width - 1 and 0 < j < height - 1:
          x = start_x + i
          y = start_y + j
          place_tile(game_map, tile_type, [y, x])

  # Unpack room parameters
  modify_walls(*room1)
  modify_walls(*room2)


def find_closest_room(room, rooms):
  # Find the closest room to the given room
  closest_room = None
  room_vertices = get_room_vertices(room)
  for other_room in rooms:
    if rooms_overlap(room, other_room):
      continue
    other_room_vertices = get_room_vertices(other_room)

    # find min distance between vertices
    distances = []
    for point_1 in room_vertices:
      for point_2 in other_room_vertices:
        distances.append(abs(math.dist(point_1, point_2)))
    min_distance = min(*distances)

    # closer room has been found
    if not closest_room or min_distance < closest_room[0]:
      closest_room = [min_distance, other_room]
  if closest_room:
    return closest_room[1]
  return None


def create_hallway(room1, room2, wall_tile, ground_tile, game_map):
  # Assuming room format is (start_x, start_y, width, height)
  x1, y1, w1, h1 = room1
  x2, y2, w2, h2 = room2

  # Midpoints of the rooms
  mid_x1, mid_y1 = x1 + w1 // 2, y1 + h1 // 2
  mid_x2, mid_y2 = x2 + w2 // 2, y2 + h2 // 2

  # Decide the direction of the hallway (horizontal or vertical first)
  horizontal_first = abs(mid_x1 - mid_x2) > abs(mid_y1 - mid_y2)

  # Create the hallway
  if horizontal_first:
    # Create horizontal part
    for x in range(min(mid_x1, mid_x2), max(mid_x1, mid_x2) + 1):
      place_tile(game_map, ground_tile, [mid_y1, x])

    # Create vertical part
    for y in range(min(mid_y1, mid_y2), max(mid_y1, mid_y2) + 1):
      place_tile(game_map, ground_tile, [y, mid_x2])
  else:
    # Create vertical part
    for y in range(min(mid_y1, mid_y2), max(mid_y1, mid_y2) + 1):
      place_tile(game_map, ground_tile, [y, mid_x1])

    # Create horizontal part
    for x in range(min(mid_x1, mid_x2), max(mid_x1, mid_x2) + 1):
      place_tile(game_map, ground_tile, [mid_y2, x])

def get_room_vertices(room):
    # Unpack room parameters
    x1, y1, w1, h1 = room
    return [
        (x1, y1),            # top left
        (x1 + w1, y1),       # top right
        (x1 + w1, y1 + h1),  # bot right
        (x1, y1 + h1),       # bot left
    ]

Have any questions?
We'd love to hear from you!