Procedural Map Generation: From ASCII to Prefabs

(Completed Dec 2024) This project was a vertical slice from the Indie Game Startup Landing Company.

Constraints for Map Generation

Before diving into the workflow and the steps taken to build the procedural map generation system, it’s important to understand the key constraints that guided the design process. These constraints ensured that the generated maps were functional, playable, and aligned with the overall game design goals.

Initial Constraints

• No Hallways: Rooms are placed adjacent to one another without gaps.
• Filling of Rooms: Rooms are required to fill a rectangle of size n x n
• Random Door Placement: Doors initially spawned randomly along room edges.

Evolved Constraints

• Fixed Door Placement: Doors now adhere to specific rules for alignment and connectivity.
• Designer Control: Procedural rules were adjusted to balance randomness with designer input.

Challenges Addressed

• Room Placement: Ensuring rooms of varying sizes fit seamlessly within the grid.
• Door Placement: Avoiding edge cases where doors spawn in inaccessible or illogical locations.
• Design Flexibility: Balancing procedural generation with the need for designer control.

Process of my workflow.

Building the Foundation: Initial Steps

I started with the basics, creating an ASCII map system to visually represent the map grid. This approach allowed me to quickly prototype and debug the layout. While researching existing solutions, I found that none met my current constraints, prompting me to develop my own. By using a monospaced typewriter font, I crafted a simple yet effective debug view, offering clarity and precision for initial development. Next I implemented random room placement. A key challenge here was ensuring no two rooms overlapped. By addressing this early on, I maintained the integrity of the map layout, laying a solid foundation for future system expansion.

Expanding the System: Adding Doors

Initially, I added doors at random positions along room edges. However, I quickly realized this approach was impractical for functional layouts. I introduced constraints to prevent doors from spawning at corners and implemented logic to place doors on opposite edges for better connectivity. These refinements significantly improved room-to-room traversal and laid the groundwork for structured room relationships.

Transitioning to Prefabs

Moving from ASCII representation to actual prefabs was a pivotal step. Translating grid positions into world positions introduced complexity, requiring precise calculations to ensure rooms aligned perfectly in the game world. This transition marked the beginning of blending the generated maps with the game environment.

Changing Door Logic and Room Properties

To improve functionality, I refactored door logic and introduced a container system for room properties, such as size, type, and door positions. This allowed me to shift from random door placement to fixed door logic, offering greater control over room connectivity. I also created room prefab templates, ensuring consistent design and usability for level designers.

Designer-Focused Usability Features

Understanding the importance of designer-friendly tools, I added gizmos and visual indicators to enhance the workflow. For instance, doors in the ASCII map translated to actual door openings in the world. These visuals provided clarity and made adjustments easier for designers, ensuring a smooth collaborative process.

Adding Thematic and Gameplay Elements

To enrich gameplay, I incorporated specialized rooms, such as entrances, exits, and puzzles. Logic was added for defining start and exit rooms, creating a structured flow within the system. Expanding the room library with unique templates ensured a cohesive and engaging map generation pipeline.

Improvements on the system in the future:

• Optimization of spawning rooms due to O(n²).
• More precise gizmos for better visuals.
• More unique rooms if the designers wanted more types of rooms like puzzles.
• Add more unity features like nav mesh for AI to be used.
• Have rooms be possibly rotatable.

Key Details About the ASCII Map System

Definition and Representation

The ASCII map serves as a grid where each character represents specific elements of the map, such as:

• + for corners
• # for walls
• ~ for traversable (filled) space

A monospaced font is used for consistent and clear debug visualization of the ASCII map.

Monospaced Font

Unity Default Font

+########+
#~~~~~~~~#
#~~~~~~~~#
#~~~~~~~~#
#~~~~~~~~#
#~~~~~~~~#
#~~~~~~~~#
#~~~~~~~~#
#~~~~~~~~#
+########+

The coordinate system differs from reading a book (a list of strings):

• x-positive moves to the right.
• y-positive moves downward.

To align with the math-based system (where y-positive moves upward), the string representation is reversed during rendering.

Room Dimensions and Wall Logic

Room Size Breakdown:

• Rooms are defined as n×n, including edges and walls.
• Traversable space inside the room is (n−2)×(n−2).
• Grid space occupied by the room, including walls, is (n−1)×(n−1).

Wall Thickness:

• Represented as 1 unit in ASCII.
• During prefab generation, walls are scaled to 0.5 units in world space.
• The bottom-left corner of a room (including its wall) starts at (0.5, 0.5) for proper alignment.

Avoiding Wide Hallways:

Doors placed on ASCII map walls ensure hallways are not unintentionally two tiles wide when connecting rooms.

Debugging and Visualization

The ASCII map uses a bottom-left origin (pivot) at (0, 0) for rooms, ensuring:

• Consistency in ASCII generation.
• Smooth transition to prefab placement.

Room Alignment:

• Walls have a consistent offset of 0.5 units.
• The ASCII map structure aligns perfectly with traversable spaces.

Example ASCII Map Representation

For a 5×5 room at position (1, 1):

• +: Room corners.
• #: Walls.
• ~: Traversable space (player walkable area).

--------
--------
-+###+--
-#~~~#--
-#~~~#--
-#~~~#--
-+###+--
--------

Room Placement and Validation

Room Placement Algorithm

Grid Setup:

1. Initialize a grid large enough to fit the room at its specified position.

Room Boundaries:

1. Place corners (+) at the four corners of the room with the initial given position:

   (0, 0), (0, 4), (4, 0), (4, 4) for a 5×5 room.

   (1, 1), (1, 5), (5, 1), (5, 5) for a 5×5 room with initial position (1,1).

2. Place walls (#) along the edges, excluding corners:

   Along x = 1, y = 1, x = 5, y = 5.

3. Fill the inner traversable space (~):

   This is a 3×3 starting at position (2,2).

Room Placement Check:

1. Ensure the grid has enough space to fit the room.
2. Verify that none of the room’s traversable spaces (~) overlap with previously occupied spaces.
   • If placement is invalid:
     • Return a message indicating the issue.
     • Skip the room placement.

Code Adjustments for Placement Validation

CanPlaceRoom Method:

• Checks if the room fits within grid bounds and if the traversable spaces are unoccupied.

GenerateRoom Method:

• Places walls, corners, and traversable spaces if CanPlaceRoom returns true.
• Otherwise, skips placement and prints a message.

DisplayGrid Method:

• Visualizes the grid in the console for debugging purposes.

Door Placement and Room Connectivity

Door Logic for Random Room Generation

• Doors (D) are placed on walls (#), excluding corners (+).
• The door’s placement must:
  1. Be aligned with a wall.
  2. Avoid overlap with corners or traversable spaces.
• After placing a door, the corresponding wall changes from # to D.

Fixed Door Placement Logic

Predefined Door Positions:

• Each room has a list of fixed door locations along its edges.
• Example for a 4×4 room:
  • Doors (D) connect to other rooms via corresponding door positions.

New Room Placement Logic:

1. Choose a door from the current room (e.g., (1, 0) in Room A).
2. Choose a corresponding door in the new room (e.g., (0, 1) in Room B).
3. Align the new room’s position by subtracting the door coordinates:
   (1, 0) - (0, 1) = (1, -1).
4. Validate the placement:
   • Ensure the new room does not overlap with filled (~) spaces.
   • If valid, place the room.

Optimization and Complexity

Current Complexity:

• Checking every door for every possible new room results in O(n²), where n is the number of doors.

Potential Optimizations:

• Limit door checks to nearby grid areas.
• Assign doors to be NSWE in the room.

Example Workflow

Lets assuming we have:

• Room A: Size (4,4) with door positions at (0,1) and (3,2).

+##+
#~~D
D~~+
+##+

• Room B: Size (3,3) with door positions at (0,1) and (2,1).

+#+
D~D
+#+

• Total Level size is (8,5)

Place the First Room:

• Start with Room A at (0, 0).

Door Pair 1: Room A (0,1)

• Check if any room can connect to this door position.
• Result: No room can be placed due to insufficient space.

Door Pair 2: Room A (3,2)

• Select Room B’s door at (0,1).
• Calculate the pivot position as (3,1) to place Room B.
• Result: Room B successfully placed at (3,1).

Door Pair 3: Room B (2,1)

• Map this to global coordinates, (5,2).
• Check if another Room B can connect using its door at (0,1).
• Calculate the new pivot position as (5,1) to place Room B.
• Result: Another Room B successfully placed at (5,1).

Result in Debug

--------
+##+#+#+
#~~D~X~D
X~~+#+#+
+##+----

Benefits of Fixed Door Placement

• Deterministic Layouts:
  Predictable connections between rooms.
• Complex Room Shapes:
  Supports non-rectangular designs like L-shaped rooms.
• Customizable Connections:
  Designers can adjust door positions to control connectivity.