<h1>Technical Dive into Procedural Room Generation and Connection in Maps</h1>
<p>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.</p>
<h1>Procedural Generation: An Overview</h1>
<p>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.</p>
<p>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.</p>
<h1>Initializing the Map</h1>
<p>The first step in our procedural generation process is initializing the map with a base tile, typically representing the
ground:</p>
<pre><code class="language-python">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
</code></pre>
<p>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.</p>
<h1>Room Generation</h1>
<p>Rooms are generated using the <code>create_rooms</code> function, which randomly determines their number, size, and position:</p>
<pre><code class="language-python">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
</code></pre>
<p>Each room is created and placed on the map ensuring it fits within the map boundaries. The <code>create_room</code> function is
responsible for the specifics of each room's dimensions and location.</p>
<h1>Handling Room Overlaps</h1>
<div>
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:
</div>
<div style="margin-bottom: 20px; text-align: center" class="img-bordered">
  <img style="width: 250px; height: 250px; margin: auto;" src="/assets/blog/procedural_maps/overlaps.png" class="img-bordered" alt="overlaps"/>
</div>
<pre><code class="language-python">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)

</code></pre>
<p>by removing the overlapping internal walls, we end up with something that makes sense</p>
<div style="margin-bottom: 20px; text-align: center;">
<img style="width: 250px; height: 250px; margin: auto;" src="/assets/blog/procedural_maps/overlap_solved.png" class="img-bordered" alt="overlaps_solved"/>
</div>
<h1>Connecting Rooms</h1>
<p>The connect_rooms function weaves the rooms together by creating corridors or paths, making the map navigable:</p>
<pre><code class="language-python">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
</code></pre>
<div style="margin-top: 20px; text-align: center; display: flex; justify-content: center;">
    <img style="width: 250px; height: 250px; margin: auto;" src="/assets/blog/procedural_maps/connected_overlap_solved.png" class="img-bordered" alt="overlaps"/>
    <img style="width: 250px; height: 250px; margin: auto;" src="/assets/blog/procedural_maps/connected.png" class="img-bordered" alt="overlaps"/>
</div>
<p>This function ensures each room is connected to at least one other room, using the create_hallway function to lay down
the paths.</p>
<h1>Conclusion</h1>
<p>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.</p>
<p>This example barely scratches the surface of what we can do with simple techniques.</p>
<blockquote style="margin-left: 15px; margin-right: 15px;">
  <i>Give me a lever long enough and a fulcrum on which to place it, and I shall move the world.</i>
<p>— <i>Archimedes</i></p>
</blockquote>
<h1>Helper Functions</h1>
<pre><code class="language-python">def place_tile(game_map, tile, p, lvl=0):
  """
  place the given tile at the given location
  """
  if p[0] &#x3C; 0 or p[1] &#x3C; 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] &#x3C;= br2[0] and br1[0] >= tl2[0] and  # Check vertical overlap
      tl1[1] &#x3C;= 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 &#x3C; x2 + w2 and x1 + w1 > x2 and
            y1 &#x3C; 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 &#x3C; i &#x3C; width - 1 and 0 &#x3C; j &#x3C; 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 &#x3C; 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
    ]
</code></pre>

Procedural Maps