1
\$\begingroup\$

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?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ A maze can be thought of as a spanning tree over a graph of cells (edges in the tree are open passages, edges not in the tree are walls). So, thinking of it this way, you can use spanning tree algorithms to construct a maze on any arbitrary topology you want. Have you encountered any particular difficulty with a specific shape? \$\endgroup\$
    – DMGregory
    Mar 11, 2017 at 0:51
  • \$\begingroup\$ So I guess I need some structure that knows what it's adjacent nodes are. With a grid it is easy they do not need to be predefined as it is one to the left one to to the right one above one below. With a triangle for example I guess I am going to need to manually create a set of nodes each that understand what other nodes they can go to. It is the code structure for this I am unsure of. \$\endgroup\$
    – John
    Mar 11, 2017 at 8:15
  • \$\begingroup\$ Hint: a triangular grid is isomorphic to a square one, all it takes is a little skew. The same goes for hex grids. \$\endgroup\$
    – DMGregory
    Mar 11, 2017 at 15:22

1 Answer 1

3
\$\begingroup\$

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:

enter image description here

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .