Hypermaze Prototype

A maze does not have to begin with a floor plan. Hypermaze begins with rooms and the links between them, then builds the space around the doorway the player enters. A corridor can lead to an earlier room, or return to another side of the same room. The graph describes the connection; the tile map provides a local view of it.

This 2016 prototype is about keeping those two descriptions working together. The player moves through rooms and corridors, while terrain is added to the map as it is needed. Different graph paths can place spaces over the same tile coordinates, so a coordinate alone is not enough to describe where the player is.

Giving the maze its connections

Generation starts from a root node and expands outward through a queue. A generation parameter limits how far that expansion proceeds. Connections can create new rooms or link back to rooms that already exist, producing loops as well as branches and dead ends.

I used C++11 number distributions to shape those decisions. A complexity value between zero and one changes the probabilities for larger rooms, dead ends, and loops. Piecewise-linear distributions weight doorway counts; Bernoulli distributions make the yes-or-no choices. That gives the generator related controls for the character of a maze, with different weights for the available outcomes.

Putting a doorway into the right place

A graph node becomes a room whose walls have enough space for its doors. A link becomes a corridor between two entrances. On crossing a boundary, the maze finds the destination through the graph, creates its terrain if needed, and calculates an offset that places the matching doorway next to the player.

That last translation is easy to underestimate. There are room and corridor coordinates, tile-map coordinates, and coordinates within a tile chunk. The original map uses 32-by-32 chunks. A room can start near a chunk edge and spill into several others, so placement must calculate both which chunks are touched and which part of the terrain each chunk receives.

The map grows as terrain is added; generation does not first have to flatten the entire graph into one fixed rectangle. The tradeoff is that a valid graph connection still needs careful local placement. Getting an offset wrong can draw a sensible room in the wrong place, even though the connection itself is correct.

The coordinate problem became the useful lesson

The original tile-placement work took weeks of writing, debugging, and rewriting. My conclusion in Undefined Spaces and TileMaps was to start with the coordinate systems and the translations between them. The graph tells me which space comes next; those translations determine whether I can actually put it on screen.

Number Distributions covers the generation controls in more detail. The animation above belongs to this historical prototype, which depends on its older graphics framework. It demonstrates this version’s local room-and-corridor presentation. Artwork uses the linked Dungeon Tileset.