Lab 3

Lab 3: Maze Generation, Deadline: Dec 13, AoE

Overview

For lab 3, you will implement a maze generation algorithm in Processing 4.

Framework

You can download a framework to get you started with the lab here. It contains some classes that you will need:

  • Map.pde contains a class for the map and the walls
  • settings.pde contains some setting you might want to play with, including the GRID_SIZE
  • lab3.pde contains the main code: It will call the generate method of the map when you press g.

You are free to add and modify any of the code, as long as you fulfill the requirements of the assignment: When the user presses g a new maze should be generated, which uses the GRID_SIZE variable to control its grid size.

Maze Generation

The requirements for this lab are that you generate grid-aligned mazes that do not contain loops, where the size of the grid cells is controlled by the GRID_SIZE variable. You start by dividing the map into cells with this width and height:

This grid defines a graph: Each cell is one node, and edges connect two cells if they are adjacent:

To generate a maze without loops you have to calculate a (randomized!) spanning tree on this graph. You can choose which algorithm to use for this, but I recommend either randomized Kruskal or randomized Prim’s:

Randomized Kruskal

To generate a maze with Kruskal, you have to store which components of your graph are already connected. You start with each node in its own component, i.e. the graph is completely disconnected. Then you add a random connection between two adjacent components, merging them into one, an repeating that until you are done. Note: If you store the components in a list, you can not just take two random entries from the list and connect them, as they may not be adjacent. A better strategy might be to select one component at random, find all of its neighbors, and merge it with a random neighbor. Also note that two components may have multiple ways to be connected: Consider the case where you connected all cells in the right-most column, and all cells in the column to its left. When you want to merge these two components, you can merge them in any row (choose one at random).

Randomized Prim’s

While Kruskal is perhaps conceptually simpler, Prim’s is slightly easier to implement, since you do not need to determine how to merge arbitrarily shaped components. Instead of starting with the entire graph, you pick a random starting node, and expand the tree outwards. You will need to keep track of which nodes you have already visited (starting with the randomly chosen one), and what the “frontier” of new nodes to explore is. However, instead of storing a frontier of nodes, it may be easier to store a frontier of “walls” that can be removed next: The start node has up to four walls adjacent to it (you can not remove the outer walls of the map), so these are the initial “frontier”, then you choose a random wall from the frontier, and check if the node on the other side has not been visited yet. Then you add a connection, if the other node has not been visited yet. In either case, you remove that wall from your frontier. You keep repeating this until all nodes have been visited.

Maze result

Regardless of which algorithm you use, you should end up with a representation of your maze. The final step is to draw the maze: Perhaps the simplest way is to draw it node by node, where each node draws a wall for each neighbor that it does not have an edge to. You can optimize this slightly by observing that this would draw each wall twice, and have e.g. each node only draw the walls to its right and below it (make sure to draw the outline around the entire map, though). You may, but are not required to, also draw the graph, i.e. the required output is the maze itself, but the graph may be helpful for debugging. You may then end up with something like this:

Maze Navigation (optional)

As you may have noticed, the framework for this assignment bears some similarity to the framework for lab 1. You could therefore use the code from this lab with lab 1 and try to have your boid navigate the maze. However, you will run into one major challenge: The way we generated mazes is (probably) not how you expect the map to be represented for your NavMeshes. However, instead of generating a NavMesh for the maze you could use the fact that you generated the maze as a graph to begin with: Each node is a square (which is certainly convex), and you have the neighbor-information. If you take your maze and put it into the graph representation you used for A* you could use the existing code to navigate the maze. You’ll still have to tweak some things to avoid that a NavMesh is being generated, and your constructed graph is used instead, but you could integrate the two labs into one. If you get your boid to navigate the maze (same controls: left-click sends the boid to a location, it will find a path through the maze using A*) you can get up to 5 bonus points.

Report

Your report should consist of two sections:

  1. Briefly describe the maze generation algorithm you implemented
  2. Show some example mazes generated by your algorithm using a few different grid sizes.

Submission

Submit the finished code (the entire processing-sketch as a folder!), and your report pdf in a single zip file on Canvas. Do not forget to put the names and BroncoIDs of both team members in the report as well! Only one of you has to submit, but if both do, please make sure you submit the same file, or I will pick one at random.