2D Pac-Man style Maze Generation

procedural maze generation

A simple method for procedurally generating 2D mazes as used in Chompston. The generated maps are “Pac-Man style” in that they are a series of interconnected corridors with no dead ends.

The maze is produced by placing a number of “builders” in an empty map and then carving out paths by moving them simultaneously until none remain. Essentially it’s a simulation of a multiplayer Light Cycles type of game performed by unskilled participants.

maze generation 01

First we place a number of spawners in random locations in our world – a typical 2D array of cells which is initially the map is filled with solid cells.

maze generation 02

At the spawner locations we place between two and four builders, each of which is assigned one of the four available directions. There needs to be at least two builders per spawner to avoid dead-ends in our maze. Each builder is also assigned a random distance it will travel before changing direction.

maze generation 03

All the builders are moved simultaneously in their current direction, clearing cells in the map as they go. With every iteration each builder’s remaining travel distance is decreased.

maze generation 04

When a builder’s remaining travel distance reaches zero it turns 90 degress left or right and we assign a new random distance to it. If they reach the edge of the world they also turn left or right.

maze generation 05

A builder is removed when it encounters an empty cell, so we just need to continue iterating until none remain.

maze generation 06

The finished maze, but we’ve produced a few little rooms so it’s not strictly Pac-Man-like.

maze generation 07

Ensuring our maze comprises single-block wide corridors is simple – constrain the placement of spawners to every other column and row of the 2D grid and always move the builders for an even number of steps before changing direction.

maze_generation_08

In this instance the maze was generated by placing five spawners and moving each builder between two and ten blocks before changing direction. By encapsulating the generation algorithm in a function that accepts a few parameters we gain some control of the flavour of the maps it produces. So with a maze generation function defined as:

BuildMap(Spawners,MinimumDistance,MaximumDistance)

the random mazes produced have characteristics similar to the following:

BuildMap(3,8,12)
BuildMap(3,8,12)
BuildMap(6,2,4)
BuildMap(6,2,4)
BuildMap(12,8,20)
BuildMap(12,8,20)

Implementing this technique for procedural maze generation in Chompston allowed me to progressively increase the complexity of the random maps through successive levels.

12 thoughts on “2D Pac-Man style Maze Generation

    1. Chris B Post author

      Sure – but the code is a bit of a mess at the moment. I’d like to untangle it into something more portable first.

      1. Peter Eismann

        You know were I am?
        Icesoft from the PureBasic forum. I ask you for a port to mobiles.
        When I have the PB source it is easier to adapt it to C++ for me.
        Please send me a mail (you know me eMail) ;-)

        Thanks
        icesoft

  1. Will Morrison

    This is pretty basic strategy for procedural maze generation. The interesting part was your trick for ensuring corridors span only 1 row/column. Clever.

    A download with well designed code would be nice.

    1. Chris B Post author

      Well designed code isn’t my strong point – but I’ve been meaning to make a little JavaScript thing of it sometime.

  2. ZXDunny

    Just a thought – and I realise this is quite an old post now (!) but how do you manage to avoid disconnected sections of the maze on larger maps? If two spawns are sufficiently far enough from the maze that their builders collide with eachother’s paths, then they would die without actually connecting with the other builders?

    1. Chris B Post author

      ah.. Iā€™d neglected to mention that step!

      The method I used was to perform a flood-fill starting from a cell in the maze ā€“ any unfilled cells are discarded. I keep a count of iterations of the flood-fill algo and return that value from the maze generation function, so I can just call the function again if the generated maze is too small.

      Also, I write the current iteration into the array where I store the maze data ā€“ in Chompston I use this value to color the dots you have to collect, so the color-cycling effect sort of flows from the player start location. It can also be used for path-finding to the spawn point: just move to whichever adjacent cell has the lowest number.

        1. Dolphin Wood

          I solved this problem by calculating the weights of four directions when the builder turns (two directions are enough, actually).

          When the builder turns, we compare its position with **all other spawners**:

          1. If the spawner is above the builder, increase up_weight by 1;
          2. If the spawner is below the builder, increase down_weight by 1;
          3. If the spawner is on the left the builder, increase left_weight by 1;
          4. If the spawner is on the right the builder, increase right_weight by 1;

          Then turn the builder to the one direction that has the highest weight so that it will get close to the other spawners :)

          I wrote a demo that implements this thought (the code is a bit messy now): https://stackblitz.com/edit/fog-man?file=src%2Fmaze-gen.ts

          See

          “`
          class Builder {
          _calcWeight(spawners) {}
          _turn(weight) {}
          }
          “`

Comments are closed.