Corridor Generation

---

Overview

When generating maps for ITHOM, a common issue which came up was the creation of corridors. For many map archetypes, the focus of the map was a collection of disjoint rooms, connected by a number of corridors. Generally, nothing of interest would be generated in corridors, and they would only serve as connecting passageways between rooms, which was where the action happened. However, sometimes this design process led to the introduction of particularly long corridors, with very little to interest the player traveling between rooms.

In order to alleviate the samey-ness of corridors and introduce a little bit of variety into corridors, I explored a variety of algorithms to facilitate the creation of these structures.

The Problems

I started with a number of relatively uninteresting corridor designs. The first of these was the simple A* pathfinding corridor . This algorithm used the A* method to find the shortest path between two doors, shown as pluses in the diagram below:

╔════════════════════╗
║  │                 ║
║  +######           ║
║──┘     ##          ║
║         ##         ║
║          ##        ║
║           ##    ┌──║
║            ##   │  ║
║             ####+  ║
║                 │  ║
╚════════════════════╝
simple A*

This style of corridor is not ideal for a variety of reasons. First and foremost, it is ugly. It is the lowest-effort solution to connecting rooms and the player will be able to notice. I attempted a number of other similer solutions:
I think that it is obvious that out of all of the proposed solutions so far, the NetHack-style corridor is the least stupid-looking. The axis-wise implementation is possibly the ugliest implementation yet, and the simple pipe is not much better. The NetHack-style is still simple, but the algorithm prefers to change direction as little as possible, unless the slope differential becomes to great. This leads to a nicer looking zigzag curve when approaching the midpoint of the room connections. This solution is acceptable sometimes, and is used in the final build. However, this is not the final solution I wanted to settle on.

The Solution

I like the look of the NetHack-style corridor, but I wanted a little more variety in the bends of the corridor than just straight zigzags. My solution was to take the area between the two proposed doorways and superimpose a mask of "no-go" tiles. After this, the corridor generation algorithm would use a combination of simple A* pathfinding and slope detection to build a corridor between the two doors, while avoiding the no-go tiles as much as possible. Typically, the no-go tiles would be randomly selected to provide as much variety as possible, but sometimes would be randomly selected only in a single quadrant between the two doors and then symetrically mirrored across the other quadrants. The diagram below shows one such example of this method:

╔════════════════════╗ ╔════════════════════╗ ╔════════════════════╗
║  │                 ║ ║  │                 ║ ║  │                 ║
║  +    X    X       ║ ║  +####X    X       ║ ║  +####             ║
║──┘    X    X       ║ ║──┘   #X    X       ║ ║──┘   #             ║
║         XX         ║ ║      ## XX         ║ ║      ##            ║
║        XXXX        ║ ║       #XXXX        ║ ║       #            ║
║         XX      ┌──║ ║       ##XX###   ┌──║ ║       ##  ###   ┌──║
║       X    X    │  ║ ║       X####X#   │  ║ ║        #### #   │  ║
║       X    X    +  ║ ║       X    X####+  ║ ║             ####+  ║
║                 │  ║ ║                 │  ║ ║                 │  ║
╚════════════════════╝ ╚════════════════════╝ ╚════════════════════╝
  define dead zones         dig corridor         remove dead zones  

Step-by-step, the process is as follows:

1. Define dead zones. In this case, the dead zone was defined only in one quadrant at random, and then symetrically mirrored across the other three quadrants. The dead zones are indicated by the Xs.
2. Use A* pathfinding to dig from one door to another. Dead zones prevent the generation of corridors. Additionally, when the slope becomes too great on the point between where the corridor digger currently is with regards to its destination point, the algorithm will change directions.
3. Remove the dead zones. The result is a corridor which generally moves from point A to point B, but without being too generic, too repetitive, or too uninteresting.

Not wanted to discard the previous research I had done into the other methods, the map generator sometimes resorts to the other corridor generations as well, to provide even more variety.

---

home :: blog :: corridor generation