How to structure a non rectangular maze

Question

I have built a few mazes and are familiar with maze algorithms however all examples I have learnt from are square or rectangular.

In these mazes the code structure usally has a 2d array of maze cells and it is easy to navigate or test to adjacent cells.

How do you structure the code for a say a Y or circular shaped maze to know what the avaliable joints between cells/nodes in the maze are?

Answer 1

If your maze doesn't easily map to a 2d array, make it a graph.

Make each cell a structure which includes where that cell is, how it looks and most importantly an array of references to the the cells which are adjacent to it. Unless you plan to change the connections between cells at runtime, you might only want to keep those connections which are actually walkable.

This graph:

Might represent this dungeon:

        +-----+
        |     |
        |     |
+-------+     +--------+
|       |  3  |        |
|   2                  +----+
|       |     |          6  |
+- -+- -+-----+   4    |    |
|   |         |        +----+
| 1                    |
|   |         |        |
+---     5    +--------+
    |         |
    |         |
    +---------+

The JSON representation of node 1 would look something like this:

{
    // information about the node itself:
    x: 0,
    y: 7,
    width: 5,
    height; 5,
    // information about connections to other nodes:
    connections: [
        { x: 2, y: 0, destination: 2 },
        { x: 4, y: 2, destination: 5 }
    ]
}

The nice thing about representing your mazes with graphs is that they don't even need to have an euclidean geometry. That gives you a lot of interesting possibilities:

• You can connect two cells which are far away from each other. This might, for example, represent a teleporter. Or a maze which loops with itself.
• You can represent connections which only work in one direction (like pitfalls) by connecting cell A to B but not B to A.
• You can easily make the maze three-dimensional (or, heck, four-dimensional if you want to really screw with your player's minds).
• You can have a maze which isn't even spatially possible, like one where two rooms overlap each other. When you only show one room at a time, the player might not even notice.

Most route finding algorithms are designed to work on graphs anyway, so they will easily deal with such "weird" maze topographies.