This is a completely new recipe oriented toward having fun while creating maps and levels procedurally. The main recipe works by creating a maze completely procedurally. Furthermore, we will explore a gray area, where both level design and procedurally generated content meet.
In this recipe, it is important to understand the concepts of Binary Space Partitioning and the Breadth-first Search algorithm learned in Chapter 2, Navigation.
We will implement two classes, one for the nodes to be partitioned and one for holding all the nodes and the maze representation, as follows:
- Create the
BSPNodeclass and its members:using UnityEngine; [System.Serializable] public class BSPNode { public Rect rect; public BSPNode nodeA; public BSPNode nodeB; } - Implement the class constructor:
public BSPNode(Rect rect) { this.rect = rect; nodeA = null; nodeB = null; } - Define the function for splitting the node into two subregions:
public void Split(float stopArea) { // next steps } - Validate its base case:
if (rect.width * rect.height >= stopArea) return; - Initialize all the necessary function variables:
bool vertSplit = Random.Range(0, 1) == 1; float x, y, w, h; Rect rectA, rectB;
- Compute the horizontal split:
if (!vertSplit) { x = rect.x; y = rect.y; w = rect.width; h = rect.height / 2f; rectA = new Rect(x, y, w, h); y += h; rectB = new Rect(x, y, w, h); } - Compute the vertical split:
else { x = rect.x; y = rect.y; w = rect.width / 2f; h = rect.height; rectA = new Rect(x, y, w, h); x += w; rectB = new Rect(x, y, w, h); } - Create the class for handling the dungeon and declare all its member variables:
using UnityEngine; using System.Collections.Generic; public class Dungeon : MonoBehaviour { public Vector2 dungeonSize; public float roomAreaToStop; public float middleThreshold; public GameObject floorPrefab; private BSPNode root; private List<BSPNode> nodeList; } - Implement the function for splitting:
public void Split() { float x, y, w, h; x = dungeonSize.x / 2f * -1f; y = dungeonSize.y / 2f * -1f; w = dungeonSize.x; h = dungeonSize.y; Rect rootRect = new Rect(x, y, w, h); root = new BSPNode(rootRect); } - Implement the function for drawing the maze using the nodes:
public void DrawNode(BSPNode n) { GameObject go = Instantiate(floorPrefab) as GameObject; Vector3 position = new Vector3(n.rect.x, 0f, n.rect.y); Vector3 scale = new Vector3(n.rect.width, 1f, n.rect.height); go.transform.position = position; go.transform.localScale = scale; }
We divided the maze into two big data structures. The logical side that is handled via the BSP nodes and the visual and construction representation handled by the main Maze class. The idea behind this representation is to divide the space twice as many times as necessary until a condition is met. This is the Binary Space Partitioning.
We then created rooms for the leave nodes, and finally, we connected the regions on the tree from the bottom to the top (leaves to root).
- There's another technique that is a little bit simpler, but it requires more input from the art or level-design team. It creates a level with BFS using random pieces in a list and connects them.
- The pieces can be rotated.
- It can be improved by using the random function learned previously and tuning the pieces' placement on the list.
- The Finding the shortest path in a grid with BFS recipe in Chapter 2, Navigation