After an awesome Christmas with White Elephant, I’m feeling a lot more confident. If you haven’t played White Elephant, it is a first-person 3D puzzle platformer where you must open an absurdly-wrapped Christmas present in an escape-room-like way. The game was well-received with nearly five-hundred downloads, five-star ratings, and lots of recorded walkthroughs. It was one of the most popular games on Itch this past week. This was an exciting response to a game I threw together in four days. Now that Christmas is over and I expect the excitement of White Elephant to die down, I’ve been turning my attention over to my other project: Fail to Win.
What is it?
Fail to Win is a 3D puzzle platformer where in order to progress, sometimes you have to die. With a respawn point that acts as a teleporter and explosives that can launch your corpse at hard-to-reach locations, you solve a series of puzzles while being led by mysterious fourth-wall-breaking guide.
I actually started making this about a year ago when I was playing with ragdoll physics. It was just a proof of concept, and I had no idea what direction to go with aesthetic or plot. I left it for some smaller projects hoping that when I came back to it, I’d have a bit more popularity and could actually get this game in front of people. It is one of my more ambitious projects, so I want people to actually play this one.
Then, a couple months ago, I got impatient and indirectly returned to it anyway by working on making some Asset Store tools. I’m an Asset Store publisher, currently with five code packages for sale. I hadn’t published any new packages recently, so I figured I could work on programming a stage creator designed around 3D puzzle platformers. I’ve been making a lot of progress, so I started using this stage creator to build stages for Fail to Win.
It isn’t quite ready for releasing on Itch, but it is getting close. Expect the demo to make an official appearance some time in January. Recently, another game jammer, Yru2kind, offered to help out with audio. The full demo might just be this single stage with a little extra polish, or I might add a couple other shorts stages that are close to ready, depending on how much time I have.
What’s coming later?
I’d like to make Fail to Win into a full game, but that is up to the response the demo gets. If people like the demo, and I get enough people following the project (Itch follows, YouTube subscriptions, etc.) then I’ll start looking into crowd funding. The full game will likely last a couple hours for the average player, but maybe more depending on how much funding we can get. Development will take about a year to incorporate all the things I currently have planned for it.
Even the demo is currently a work in progress (more of a demo of a demo), but please try it out and send any feedback my way. Thanks!
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.
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:
Begin with an empty space with no walls.
Divide the space in half with a vertical wall.
Randomly place a single opening in the wall.
Divide each half in half with a horizontal wall.
Place an opening in each wall.
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:
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 (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:
Start at the root node, which can be arbitrarily chosen. Mark it as visited, and set it as the active node.
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.
Pick a child, mark it as visited, and set it as active.
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:
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:
Start at the root node, which can be arbitrarily chosen. Add it to the tree.
Of all the edges that connect the tree to an unvisited node, choose the one with the smallest edge weight.
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.
Start at an arbitrary root node. Add it to the tree.
Add this nodes edges to a list of possible edges to choose from.
Choose one of the edges to connect to. Add its edges to the list of edges. Also replace lastEdges with its edges.
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.
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.
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!
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!