Introduction

Since this assignment includes code for a UI application, let’s first take a moment to go over the distinct components of the code to frame the parts you will be implementing.

Application GUI

The mazes package contains the main application code for this assignment; find and run Main.java inside the package. This will launch a program that will (eventually) generate and solve mazes. If IntelliJ fails to run (e.g. cannot find symbol ExtrinsicMinPQ), remember to refresh Gradle manually through the Gradle tool window (in the upper right by default).

The GUI consists of two main regions: the large region at the top that displays the current maze, and a few options and buttons at the bottom.

  • The “Maze base shape” drop-down controls what underlying “shape” your maze will have. The default is “Grid”, which creates a maze where each room is a rectangle. Switching to “Voronoi” and generating a new maze with the “Generate new maze” button to the left creates a more irregular pattern.

  • The “Maze generator” drop-down controls the actual maze generation process—it takes the initial set of room and removes walls to generate a plausible maze. By default, mazes are generated with the option of “Do not delete any walls”. Selecting one of the “delete random walls” options and regenerating the maze creates something more close to an actual maze.

In this project you will implement:

  • “Run (randomized) Kruskal” which generates a much more complex but always solvable maze compared to “randomly remove walls”—either generates a too easy (30% removal) or unsolvable maze (50% removal).
  • “Find shortest path” which solves the maze between two endpoints.