Puzzle Platformer Stage Creator for Unity

I returned to work on Fail to Win and decided to build myself some better tools. So I started build a stage creator. It is front-facing, so it makes it possible for players to design and save their own puzzles, something I plan to include in the release of Fail to Win. I figured, though, that there isn’t anything quite like this on the Asset Store currently, so once I’m done, I’ll make it available for purchase as a framework for creating 3D puzzle platformers.

All of the above were built using the stage creator. Each stage is a single mesh with no hidden geometry. The stage can be saved as a JSON file and then loaded into the game later. The developer can configure the stage creator to pick what is exposed to the in-game stage creator (list of props, stage size, etc.).

There is still a lot more to come. Currently, I’m working on finishing prop placement and play-testing. If you are a Unity developer, please let me know what you think and what you might like to see in this framework. If you are a gamer, I’m interested in your thoughts on player-generated content and stage creators.

Maze Generation

Mazes are designed to be complex; otherwise, they would not be used to make people lost. However, the techniques for creating mazes can actually be quite straightforward. You can create a complex maze by following a simple algorithm. This makes mazes ideal for diving into procedural content generation, a field of study devoted to building complex structures and art from code with little or no input from humans during the process. This tutorial will not provide any actual code, but rather is designed to be an introduction to maze generation algorithms. Let’s first look at an example algorithm:

  1. Begin with an empty space with no walls.
  2. Divide the space in half with a vertical wall.
  3. Randomly place a single opening in the wall.
  4. Divide each half in half with a horizontal wall.
  5. Place an opening in each wall.
  6. Repeat 2-5 for each new section until the desired level of detail is achieved.

This is an example of a recursive division algorithm. Following this algorithm, we end up with this:

simple subdivision algorithm

There are obvious weaknesses. One is that there are more horizontal walls than vertical walls. This is inevitably the case for any square maze created with this algorithm. The other problem is that it is somewhat predictable. Given a view of the whole maze, you can see an obvious middle point you must reach to get to the other side of the maze. You could find similar points that connect each quadrant of the maze to another quadrant. You can easily find the red, then green, then blue dots that you must pass through to access other parts of the maze. Connecting those and finding any other point in the maze from those is trivial. We could modify the algorithm, but related algorithms will have similar issues. Instead, we need a different model for our mazes, one that will give us flexibility to create all sorts of algorithms.

Graph Theory and Mazes

We need to better define our goal. Let’s say that our ideal maze is a maze where every point in the maze is accessible to every other point in the maze in exactly one way. This means no loops and no inaccessible areas. We can see the recursive division algorithm achieved this, which makes sense. Since we only left one opening between halves at each level of detail, there could only be one path between them. Looking at mazes in this way though, of points connecting to other points, lets us use graph theory. For those not familiar with graph theory, it is a mathematical field of studying graphs, which are structures that have objects, or nodes, connected to each other through edges. If our nodes, for example, are cities, then we might consider the presence of a road between them to be an edge. In our maze example, we can set up various points that we assume will be empty, like a room, and connect them together in various ways.

Our definition of an ideal maze lets us do something interesting with our graph. If there is only one path to any node from any other node, we could use any node as the root node of a tree. Trees are a special type of graph, and a lot of algorithms have been invented for building and traversing tree structures.

Because mazes are random though, we do not know what the tree will look like until we generate it. This is okay. If we imagine our maze as a tree, we can traverse it to “discover” what that tree looks like, even if that is not determined until the traversal. There are two popular types of tree traversal/generation algorithms worth describing, and they each produce a very different kind of maze. After their description, I included another algorithm that is a sort of combination of the two.

Depth-First Search

Depth-first search (DFS) is a simple tree traversal algorithm that works the way it sounds. First, keep going deeper in the tree until you can’t go any further. Then back up and try another branch. More specifically, the process is as follows:

  1. Start at the root node, which can be arbitrarily chosen. Mark it as visited, and set it as the active node.
  2. Do the following:
    • If there are no unvisited children of the active node:
      • If the active node is the root, you are done.
      • Else, the parent of the active node becomes the new active node.
    • Else:
      • Pick a child, mark it as visited, and set it as active.
  3. Repeat Step 2.

Since we are using this for maze generation, this requires a few tweaks. To implement this, I used a 2D array, where a 0 represents empty space and a 1 represents a wall. For example:

1  1  1  1  1  1  1
1  0  0  0  1  0  1
1  1  1  0  1  0  1
1  0  1  0  0  0  1
1  0  1  1  1  0  1
1  0  0  0  0  0  1
1  1  1  1  1  1  1

The bold zeroes are our nodes. A zero between two nodes means the nodes are connected. A 1 means they are not connected, and there is instead a wall. We can begin with a map entirely filled with ones. Whenever we change a node to a zero, it means we have visited it. If we go back to thinking about this maze as a tree, then each node can have up to four children, one in each cardinal direction. This is not always the case, though, since sometimes, moving in a direction means leaving the edge of the maze or connecting to an already-visited node, creating a loop. If there is no direction to possibly connect to, then we back up to the previous node. Here is how we carved out the above maze. Red is the active node. Blue shows the possible next move. Orange is the path created so far.

Normally, DFS would have a consistent yet arbitrary way of selecting the next node in the path. For a maze, though, it is better to choose randomly. Whenever there are multiple blue paths, one is chosen completely at random. Note that at steps 5 and 10, there were no options for possible moves. In these situations, we back up until there are possible moves. We can keep track of the path using a stack. With each move, add something about the move, such as coordinates, on the top of the stack. When backtracking, take the top coordinates off the stack and set that as the active node. When we arrive back at the root node (which we know we did if the stack of moves is empty), and there are no possible moves, we know we are done. Following this, I created a maze that looks like this:

This does not have the same problem as recursive subdivision. There are no obvious ways to divide this maze in half. However, if you try following a path, you will notice that you are not actually faced with many choices when navigating this maze. There are a few dead ends, but most of the maze is just a couple long, winding paths. This might be preferred in many situations, but not always, so it is worth exploring other algorithms.

Simplified Prim’s Algorithm

Prim’s algorithm is in many ways opposite of DFS. It is breadth-first, so we will be looking very shallowly at a lot of paths before moving deeper. It is usually used for finding minimum spanning trees, or a tree with the fewest/shortest edges. The result is an optimal path that connects everything together. The algorithm looks something like this:

  1. Start at the root node, which can be arbitrarily chosen. Add it to the tree.
  2. Of all the edges that connect the tree to an unvisited node, choose the one with the smallest edge weight.
  3. Repeat until all nodes are visited.

For our purposes in making a maze, we can simplify this by removing all concept of edge weight. We don’t want to find an optimal solution; that would be a very boring maze. Instead, we will choose the edge randomly. Imagine maintaining a list of possible next moves. Every time you visit a new node, you can add another move to its adjacent unvisited nodes to the list. However, unlike DFS, the next move is selected from the entire list, not just the ones from the last visited node.

 

While this maze is also random, it is significantly different in appearance to a DFS maze. The modified Prim’s algorithm creates a maze with lots of dead ends, but very short paths. While this fixes the problem mentioned about DFS, it takes it to another extreme. There are so many dead ends that none of them go very far. You aren’t likely to be fooled by a dozen nearby dead ends that don’t even turn a corner.

Combination of the two

Both maze algorithms have weaknesses, so I figured a combination of the two ideas would create a better balance. For this algorithm, like our simplified Prim’s algorithm, we maintain a list of edges, but we tend to stick to the same path a little longer like in DFS. Do this by defining some maximum number of moves before a jump, such as 5. Now, when we pick an edge, we then do DFS for only 5 moves before quitting and picking another edge like in Prim’s. For simplicity, it may not be necessary to maintain a stack of move history like in DFS. Instead, you could simply say that if you get stuck, switch back to the Prim’s algorithm instead of DFS, and start working elsewhere.

  1. Start at an arbitrary root node. Add it to the tree.
  2. Add this nodes edges to a list of possible edges to choose from.
  3. Choose one of the edges to connect to. Add its edges to the list of edges. Also replace lastEdges with its edges.
  4. Do the following MaxMovesBeforeJump times or until lastEdges is empty:
    • Choose one edge from lastEdges and connect to it.
    • Replace lastEdges with just the edges available from the last move.
  5. Repeat 3 and 4 until there are no edges left.

After experimenting with different values for the maximum number of moves before a jump, I was able to get different mazes on the range of qualities we see from the DFS and Prim’s algorithm extremes.

2 step combo algorithm
2 steps max before jump
5 step combo algorithm
5 steps max before jump
10 step combo algorithm
10 steps max before jump

Conclusion

These algorithms form the basis for most maze generation, and they can be adapted in many ways. While these examples acted on a 2D array to produce a square maze as is most common, the graph theory behind the algorithms does not require these kinds of limitations. It can easily be adapted to 3 or more dimensions (I actually created a 4D maze one time). You could even build a maze from other types of graphs, such as a maze with hexagon nodes. I would have posted my implementation code, but it is too long for this post, and it is for sale on the Unity Asset Store in a package called Maze Creator. The package also allows the creation of maze templates, a tool for greater design flexibility outside the scope of this article. If anyone is doing anything cool with mazes or have any questions/suggestions, I’d love to hear about it!

3-Handed Laser Shuffle

I recently competed in a game jam on Itch.io. The requirements were a 128×128 resolution, four colors, one weekend, and a theme of “break out.” So I made this. The controls take some getting used to. It’s intentionally a bit awkward, and requires some practice switching among three controls with only two hands. WASD controls the red laser. TFGH controls the green laser. The arrow keys control blue. Try to destroy the matching blocks before they get too close. Every 100 blocks cleared gives you a power-up that you can use with SPACE. This pauses block movement for a few seconds.

3-Handed Laser Shuffle won first place in the Mini Jam, among 20 entries. Try it out!

Creating a Circuit in Unity

During a recent game jam, my team made a game called Elevator Circuit. The game is now available on for free on Itch: https://tykenn.itch.io/elevator-circuit. The objective is to complete a circuit by moving elevators holding circuit segments, aligning them into a complete path. It currently has five short puzzles with more to come. My biggest role in the project was to program the circuit system.

The idea was that any segment without a path to a generator would be red. A segment with a path from one side, but not a path from the other is yellow. When there is a path to a battery from both sides, current can actually pass through the segment, it turns green. I used Procedural Lightning to indicate that the connectors of two segments are close enough to be connected (It happens even when the two segments are not connected to a battery, but we needed some kind of feedback).

My first (failed) attempt

I made a script for each connector that checked for other connectors to enter and exit its trigger area. It then registered the segment of the other connector to current segment. The connector then told the segment to update its material by recursively checking its neighboring segments, and then its neighbor’s neighbors, until it either dead-ends, loops , or reaches a battery. All the segments along that path would update their materials accordingly. I soon ran into all sorts of race conditions and edge cases. The lightning would correctly connect segments, but the colors of the segments would be wrong half the time. So, I scrapped that and tried something new.

Working from the battery to the segment.

Since there would only ever be a handful of segments in any stage, it would not be too expensive to check for changes every frame. I kept what I had before with each connector registering other segments to its own segments, but instead of updating the materials only during a connection change, the battery would “pulse” every frame. Going recursively to each connected segment from the battery, it would mark the visited segments as “connected” either from the left or right, depending on where the pulse came from. The segments would then all update their materials accordingly, the frame would render, and then the connections would reset for the next pulse.

visual explanation of circuits

 

Here is the script that goes on the individual connectors:

using UnityEngine;

public class CircuitConnector : MonoBehaviour {

    public bool isLeft;
    CircuitSegment segment;

    private void Awake()
    {
        //Expect CircuitSegment script to be on parent.
        segment = transform.parent.GetComponent();
    }

    //Make a connection
    private void OnTriggerEnter(Collider other)
    {
        CircuitConnector otherCon = other.GetComponent();
        if (otherCon != null && otherCon != this)
        {
            //Register connection to segment
            if (isLeft)
            {
                segment.leftSegment = otherCon.segment;
            }
            else
            {
                segment.rightSegment = otherCon.segment;
            }
            //Code for anything else to do during a
            //connection, like instantiate lightning
        }
    }

    //Lose connection
    private void OnTriggerExit(Collider other)
    {
     
        CircuitConnector otherCon = other.GetComponent();
        if (otherCon != null && otherCon != this)
        {
            //Unregister segment
            if (isLeft && segment.leftSegment == otherCon.segment)
            {
                segment.leftSegment = null;
            }
            if (!isLeft && segment.rightSegment == otherCon.segment)
            {
                segment.rightSegment = null;
            }
        }
    }
}

This gets attached to the individual connectors, labeled A and B in the diagram, although in the code, I refer to “left” and “right”.  They must handle collisions with other connectors to register connections, so each connector object will need this script, a rigidbody for collisions (it can be kinematic), and a trigger collider for its range for connection.

And here is the script that goes on the circuit segment:

using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Events;

public class CircuitSegment : MonoBehaviour {

    [HideInInspector]
    public CircuitSegment leftSegment;
    [HideInInspector]
    public CircuitSegment rightSegment;
    [HideInInspector]
    private List meshesToPaint;

    //Usually only one of these in the scene at a time
    public bool hasBattery;

    //I used a red, yellow, and green material
    public Material deadMaterial;
    public Material oneWayMaterial;
    public Material poweredMaterial;

    //Optional event for receiving/losing power,
    //like opening and closing a door
    public UnityEvent powerEvent;
    public UnityEvent losePowerEvent;

    //Resets every frame, set by pulses
    private bool leftPowered = false;
    private bool rightPowered = false;

    //Does not reset, decided after pulsing finishes
    private bool powered = false;

    //only true during a pulse for checking
    //for loops
    private bool pulsing;

    private void Awake()
    {
        //Register all the meshes I want to paint.
        //I tagged all of them with "Wire"
        meshesToPaint = new List();
        foreach (Transform child in transform)
        {
            if (child.tag == "Wire")
            {
                meshesToPaint.Add(child.GetComponent());
            }
        }
        UpdateMat();
    }

    public void Update()
    {
        //Handle events for gaining and losing power.
        if (!powered && leftPowered && rightPowered)
        {
            powered = true;
            powerEvent.Invoke();
        }
        else if (powered && !(leftPowered && rightPowered))
        {
            powered = false;
            losePowerEvent.Invoke();
        }

        //Reset power
        leftPowered = false;
        rightPowered = false;
    }

    //Don't pulse until everything is reset from Update()
    private void LateUpdate()
    {
        //Only segments with batteries start a pulse
        if (hasBattery)
        {
            if (leftSegment != null)
                leftSegment.Pulse(this);
            if (rightSegment != null)
                rightSegment.Pulse(this);
        }
    }

    //Recursive function for deciding connections to batteries
    public void Pulse(CircuitSegment from)
    {
        //If a segment has already been visited in a pulse, it
        //must have looped.
        if (!pulsing)
        {
            pulsing = true;
            if (from == leftSegment && from == rightSegment)
            {
                //Handle edge case of a circuit with only two segments
                leftPowered = true;
                rightPowered = true;
            }
            else if (from == leftSegment)
            {
                leftPowered = true;
                if (rightSegment != null)
                    rightSegment.Pulse(this);
            }
            else if (from == rightSegment)
            {
                rightPowered = true;
                if (leftSegment != null)
                    leftSegment.Pulse(this);
            }
        }
        UpdateMat();
        pulsing = false;
    }

    
    public void UpdateMat() {
        Material mat;
        if (hasBattery)
        {
            //Batteries work a little different. Never red.
            if (leftSegment != null && leftSegment.leftPowered && 
                rightSegment != null && rightSegment.rightPowered)
            {
                mat = poweredMaterial;
            }
            else
            {
                mat = oneWayMaterial;
            }
        }
        else
        {
            if (leftPowered && rightPowered)
            {
               mat = poweredMaterial;
            }
            else if (leftPowered || rightPowered)
            {
                mat = oneWayMaterial;
            }
            else
            {
                mat = deadMaterial;
            }
        }

        //Apply the material to every assigned mesh
        foreach (var rend in meshesToPaint)
        {
            rend.material = mat;
        }
    }
}

This gets attached to the entire segment object. Normally this would be the parent of the connectors, although it technically does not have to be with how I set up the code. Add the segment to both connectors through the inspector, and then mark one of them as left (it doesn’t matter which one). You will also need to assign to the segments the materials you want to paint onto the wires. Any children of the segment with the tag “Wire” will be painted those materials, so be sure to set up that tag.

Mark any segment as having a battery in the inspector, and that segment will now supply power and initiate the pulses. Now, if you have some object you want a complete circuit to trigger, like opening and closing a door, make a new script with two public methods such as Open() and Close(). On the segment that powers the object, you can assign those methods in the inspector through the Power Event and Lose Power Event.