# 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:
``````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

# 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
``````

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!