Time to start putting code to screen, and build my game. I had decided before the Ludum Dare had begun, that I'd use Unity3d to create my game, as I had dabbled in it before. In Part 1, I talked about what the Ludum Dare was, and my process for coming up with a game concept for the theme "Sacrifices Must Be Made". My concept seemed doable enough, in Minotaur Maître D’ you're responsible for running around a maze, picking up sacrifices and bringing them to the Minotaur's altar in the center of the maze while avoiding running into the Minotaur itself. I had decided to craft the game as a top down maze in 2D, sort of like an old Atari game. I'd start with mechanics of the game and add in better graphics later.
Maze Generation
The first step I took was generating the maze. I did not want to spend time making levels by hand, so I started with looking online for some maze generation strategies. I came across two excellent web sites talking about maze generation. This excellent write up of the maze generation used in the 1980's Berzerk video game, and Joseph Hocking's post about procedural maze generation in Unity.
I based my maze generator on Joseph's post, creating a MazeController which was a MonoBehavior class that the rest
of the game would interact with, and a MazeDataGenerator which did the initial maze generation. Breaking up the code like
this creates an opportunity to have more than one type of MazeDataGenerator. For example, rather than the random maze
a data generator could load a hand made maze or use a different algorithm to generate a maze. This would allow for some variation
in the game as the player progressed in levels.
MazeDataGenerator
The MazeDataGenerator has one real purpose, generate a new maze. This is broken into 3 steps:
- Generate a random maze for the specified size
- Cut out the 'altar room' in the center
- Fill in the unreachable areas of the maze with walls
That third step is important because without it the minotaur or the sacrifices could be placed in unreachable parts of the maze.
Generate Maze
The first stage of maze generation is creating a two dimensional array representing the blocks of the maze. This part I
borrowed heavily from Joseph's post as well, since he implemented the Berzerk algorithm pretty cleanly. 0 will represent
open space, while 1 will represent a wall. Generating the maze is then is simply looping through all the (x,y) coordinates
and making a choice to fill them or not. If the cell in the maze is on the edge set the cell to 1 creating an outside wall,
for there is no escape from the maze. For the rest of the cells, only look at every other cell (or when both x and y are even),
and choose if it and a neighbor should be filled in.
maze = new int[sizeRows, sizeCols];
yMax = maze.GetUpperBound(0);
xMax = maze.GetUpperBound(1);
centerX = (xMax) / 2;
centerY = (yMax) / 2;
for (int i = 0; i <= xMax; i++) {
for (int j = 0; j <= yMax; j++) {
// Make the outer wall
if (i == 0 || j == 0 || i == yMax || j == xMax) {
maze[i, j] = 1;
}
// Make inner walls
else if( i % 2 == 0 && j % 2 == 0) {
if (Random.value > placementThreshold) {
maze[i, j] = 1;
// pick a neighbor to make a wall too
int a = Random.value < .5 ? 0 : (Random.value < .5 ? -1 : 1);
int b = a != 0 ? 0 : (Random.value < .5 ? -1 : 1);
maze[i + a, j + b] = 1;
}
}
}
} In the above code he placementThreshold is a tunable float that is the likelihood that a wall gets placed at all. Higher
values of placementThreshold will result in mazes with more open space. The a and b variables pick a single
neighboring cell (North, South, East or West) to also make a wall, meaning walls are always placed in adjacent pairs.
This ends up generating a nice initial maze.
The above maze shows one of the problems that can occur with the base algorithm. There is a room in the lower center that you can't get to, not to mention there isn't space for the altar. At this point I started to deviate from Joesph's code, altering it to suit my needs. Making space for the altar is easy, just set center 3x3 section to zeros. Then to deal with closed off rooms, walk the maze starting at the center and fill in all the spaces we can't get to.
Walking the maze
The way I chose to walk the room to identify spaces that are reachable (or not) from the altar room is a breadth first search (BFS).
Think of the maze as a graph, each cell is a node in the graph connected to the north/south/east/west nodes you can reach from that cell.
A simple way to implement a BFS is a with a Queue of spaces to visit and a List of 'safe' nodes (cells) we've visited. The List represents nodes
which we can reach from the altar at the center. To kick things off, place the node at the center of the maze in the Queue of nodes to visit, and begin our search.
We have a single node in our queue to start, so we pull that out, add it to the safe node list, look
at the 4 neighbors of that node, and if they are not a wall, not the edge, not already marked safe, and not already in our queue to visit,
add them to the queue to visit. Then take out the next node in our queue, and do the same with that node. Repeat until we have
no more nodes to visit. What we're left with is a list of nodes that we can reach from our altar in the center of the maze.
simply loop through all the nodes in the maze, and if they are 0 but not in our safeNodes list, make them a 1
private void fillClosedSpaces() {
// Our maze has a room that is clear in the center. Only valid
// spaces are connected to that room. Fill other rooms with 1.
nodesToVisit.Clear(); // predefined queue, so we don't have to create a new one each time
safeNodes.Clear(); // predefined list which gets used in other methods by the class
nodesToVisit.Enqueue(new Vector2(centerX, centerY));
while (nodesToVisit.Count > 0) {
Vector2 currentNode = nodesToVisit.Dequeue();
// add to safe nodes
safeNodes.Add(currentNode);
Vector2[] otherNodes = new Vector2[4]; // we're only looking at N, S, E, W no diags
otherNodes[0] = new Vector2(currentNode.x -1, currentNode.y);
otherNodes[1] = new Vector2(currentNode.x +1, currentNode.y);
otherNodes[2] = new Vector2(currentNode.x, currentNode.y -1);
otherNodes[3] = new Vector2(currentNode.x, currentNode.y +1);
foreach(Vector2 additionalNode in otherNodes) {
if (additionalNode.x >= 0 && additionalNode.x <= xMax &&
additionalNode.y >= 0 && additionalNode.y <= yMax) {
int mazeVal = maze[(int) additionalNode.x, (int) additionalNode.y];
if (mazeVal == 0) {
if (!safeNodes.Contains(additionalNode)) {
// we haven't already seen this node and marked it safe
if (!nodesToVisit.Contains(additionalNode)) {
// we're not going to visit this node already
nodesToVisit.Enqueue(additionalNode);
}
}
}
}
}
}
// NOW fill in nodes we're not supposed to be able to get to
for (int i = 0; i <= xMax; i++) {
for (int j = 0; j <= yMax; j++) {
if (maze[i, j] == 0 &&
!safeNodes.Contains(new Vector2(i, j))) {
maze[i, j] = 1;
}
}
}
}Now we have a usable maze. In the image below, you can see a block in the upper center that has been filled in, as well as the square carved out in the direct center.
Well, our maze actually isn't a maze just yet. It's still just a two dimensional array of 1s and 0s. This is where our
MazeController comes into play.
MazeController
The MazeController is a Unity3d MonoBehavior we place on an object in the Unity IDE. This post is getting a little long,
so I'm not going to go in depth into the general Unity3D game development, and assume if you've made it this far, you have some idea what I'm
talking about. If you're lost, here is a great Unity tutorial on making 2D games.
Normally, you'll have an invisible object in the game, that holds the logic of your game (your GameController),
and that same object is what I used to hold the MazeController. When the game starts (after splash screens and the player pushing a
key to start), the GameController tells the MazeController to clear the current maze, generate a new maze, then to build the maze.
Generating the maze is just the MazeController using its MazeDataGenerator to create an array of 1s and 0s to represent the maze,
with whatever parameters are necessary like width, height, and wall placement threshold.
Building walls
Once the MazeController has the maze data, we can buildMaze(). Again, I deviated from Joesph's code here, as he was
building up a 3D mesh, and all I needed was a 2D sprite based maze. Unity has the ability to create an object as a prefab. This is
an object that does not exist in the game yet, but is a template for an object. We create a very simple prefab for
a block of the maze that is a wall. This prefab is simply a 1x1 square sprite that is dark gray, along with a BoxCollider2D attached to it,
so the physics system can bump into it. There is a wallData MonoBehavior attached to it, that includes its x and y position
in the maze which was only used so I could tell which wall block was which when debugging things, but could be useful for holding other data later.
We tell our MazeController about the prefab, we also give it a reference to another empty GameObject called wallHolder.
The wallHolder serves two purposes. First, it just keeps things neat by acting as a parent for all the wall objects. Secondly,
the wallHolder has a CompositeCollider2D on it, which will merge all the 2D colliders of its children into a single collider object.
This basically makes sure you can't sneak between wall objects.
We use some code to center the maze on (0,0), loop through our maze data generating a wall object for each 1 we find, and
place that object at the correct world (x,y) location, and set the parent to the wallHolder. The data variable in the code
below is the array generated by the MazeDataGenerator.
public void BuildMaze() {
buildingMaze = true;
// get the upper left corner of where the maze should be (centering the maze on 0,0)
int rMax = data.GetUpperBound(0);
int cMax = data.GetUpperBound(1);
// since we are dealing with odd numbers in x and y...
upperLeft = new Vector2(-1 *((rMax) / 2), (cMax) / 2);
// left is -x, top is +y
// rows are y
for (int i = 0; i <= rMax; i++) {
// cols are x
for (int j = 0; j <= cMax; j++) {
if (data[j, i] == 1) {
Vector3 wallPosition = new Vector3();
wallPosition.x = upperLeft.x + j;
wallPosition.y = upperLeft.y - i;
wallPosition.z = 0; // just to be safe
GameObject wallSegment = Instantiate(wallPrefab, wallPosition, Quaternion.identity);
wallSegment.transform.parent = wallHolder.transform;
wallSegment.GetComponent<wallData>().grid = new Vector2(j,i);
}
}
}
buildingMaze = false;
}You'll notice the buildingMaze = true; and the buildingMaze = false; at the start and end of this function. Since this
function takes time to complete, we want to hold off on things like running the pathfinding system until the maze is completely constructed.
In Part 3 we'll start placing things into the maze, making things move, and look at giving the Minotaur a brain.
The full series:
- Ludum Dare 43 - Part 1 talks about what Ludum Dare is, and my design "process" where I turned the theme into an idea for a game
- Ludum Dare 43 - Part 2 explains how I generated the mazes
- Ludum Dare 43 - Part 3 adds in the player, altar, offerings, and the Minotaur with A* Pathfinding
- Ludum Dare 43 - Part 4 builds a state machine into the Minotaur's brain
- Ludum Dare 43 - Part 5 finishes up the game with points and levels