CSE 373, Summer 2019: Project 4 - Generating and Solving Mazes

Overview

In this homework, you will implement Kruskal's algorithm to generate mazes and Dijkstra's algorithm to solve them.

You will use these files from prior assignments:

  • src/main/java/datastructures/lists/DoubleLinkedList.java
  • src/main/java/datastructures/dictionaries/ArrayDictionary.java
  • src/main/java/datastructures/dictionaries/ChainedHashDictionary.java
  • src/main/java/datastructures/sets/ChainedHashSet.java
  • src/main/java/datastructures/priorityqueues/ArrayHeapPriorityQueue.java
  • src/main/java/misc/Sorter.java

If you have chosen a new partner for this assignment, choose either of your submissions from and verify that these are functioning properly.

You will be modifying the following files:

  • src/main/java/datastructures/disjointsets/ArrayDisjointSets.java
  • src/main/java/datastructures/graphs/Graph.java
  • src/main/java/mazes/generators/carvers/KruskalMazeCarver.java

Additionally, here are a few more files that you might want to review while completing the assignment (note that this is just a starting point, not necessarily an exhaustive list):

  • src/main/java/datastructures/disjointsets/IDisjointSets.java
  • src/test/java/datastructures/disjointsets/TestArrayDisjointSets.java
  • src/test/java/datastructures/graphs/TestGraph.java
  • src/main/java/datastructures/graphs/Edge.java
  • src/main/java/mazes/entities/Wall.java
  • src/main/java/mazes/entities/Room.java
  • src/main/java/mazes/entities/Maze.java
  • src/main/java/mazes/Main.java
  • src/main/java/mazes/gui/MainWindow.java

This is a team assignment. This entire homework is due on Monday, August 19 at 11:59pm.

Expectations

Here are some baseline expectations you should meet in all projects:

  • Follow the course collaboration policies

  • DO NOT use any classes from java.util.*. There are only two exceptions to this rule:

    1. You may import and use the following classes:

      • java.util.Iterator
      • java.util.NoSuchElementException
      • java.util.Objects
      • java.util.Arrays

    2. You may import and use anything from java.util.* within your testing code.

  • DO NOT make modifications to instructor-provided code (unless told otherwise). If you need to temporarily change our code for debugging, make sure to change it back afterwards.

Part 0: Initial Setup

  1. Clone the starter code from GitLab and open the project in your IDE. See the instructions from Project 0 if you need a reminder on how to do this.

  2. Copy all of your data structures, algorithms, and tests from the previous homework to this new one.

  3. Finally, make sure everything works.

    Try running TestGraph.java and make sure the tests run.

    Try running SanityCheck.java, and try running Checkstyle. Checkstyle should still report the same 5 errors with SanityCheck.java as it did in the previous projects.

Part 1: Try running the maze generator

Task: make sure you can run Main.java

Navigate to the mazes package and run Main.java. This will launch a program that will (eventually) generate and solve mazes.

The GUI consists of two main regions. The large region at the top, which will initially contain your maze, and a few options and buttons at the bottom.

Here is a brief explanation of the user interface:

  • The "Base maze 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.

    Try switching the option to "Voronoi" and click the "Generate new maze" button to the left. This will generate a maze where the rooms are more irregular.

  • The "Maze generator" drop-down controls the actual maze generation process—it takes the initial set of room and removes edges to generate a plausible maze.

    The default option is "Do not delete any edges", which, as you may have guessed, does not delete any edges.

    Now, try picking one of the "Delete random edges" options and generate a new maze. You should now see some of the edges removed and see something that more closely resembles a maze.

    Unfortunately, the "randomly remove edges" strategy is not that great. If we remove 30% of the edges, the maze is too easy. If we remove 50% of the edges, we often end up with an unsolvable maze. (The red dots in the upper-left and lower-right corners are our starting and ending points.)

    The final option labeled "Run (randomized) Kruskal" is what you will be implementing later. It turns out we can use the properties of minimum spanning trees to generate a much more interesting (and yet always solvable) maze!

  • The "Find shortest path" button, once implemented, will draw the shortest path between the two red dots.

    Clicking this button should currently throw an exception—we haven't implemented it yet.

  • If you want to customize the different options (e.g. change the number of rows and columns in the grid maze, change the percentage of edges removed), look at the MainWindow.launch method. Feel free to change any of the constants there—we will not be looking at this file when grading, so we don't care what changes you make.

  • For reference, creating the maze with either of the "Delete random edges" options takes less than half a second on our solution.

Part 2: Implement ArrayDisjointSets

Task: complete the ArrayDisjointSets class.

Notes:

  • Be sure to use implement your disjoint sets using the array-based representation we discussed in lecture. This includes making the optimizations we've discussed, specifically path compression and union-by-rank.

  • Note that one difference from lecture is that this implementation is generic and so can store any type. To keep track of the corresponding indices of each value in our array implementation, you should use an IDictionary<T, Integer> just like you did for the ArrayHeapPriorityQueue. (The values won't be moving in the array this time, though, so the dictionary indexing code should be more straightforward than before.)

  • We have provided a few tests for this class in TestArrayDisjointSets, but they're deliberately minimal. We strongly encourage you to add more tests to make sure your ArrayDisjointSets is working correctly.

Part 3: Implement constructor and basic methods of Graph

Task: implement the Graph constructor, addVertex, addEdge, numVertices, and numEdges methods.

Notes:

  • You can find this class inside the datastructures.graphs package.

  • You should look over the Edge class in the same package before you start. You will be using Edge objects inside your Graph class to represent your edges and their data, so you'll want to be familiar with it.

  • You will need to add some fields to store the graph in a useful representation (e.g. an adjacency list or adjacency matrix). These fields should have the types V, E and Edge somewhere.

  • You can find (fairly minimal) tests for this class in TestGraph. Again, you'll want to write more tests to ensure your code matches your intentions.

Example graph initializiation

For reference, the graph above could be constructed like this:

Graph<String, Void> graph = new Graph<>();
graph.addVertex("a");
graph.addVertex("b");
graph.addVertex("c");
graph.addVertex("d");
graph.addVertex("e");

graph.addEdge("a", "b", 2);
graph.addEdge("a", "c", 3);
graph.addEdge("a", "e", 2);

graph.addEdge("b", "b", 1); // self-loop
graph.addEdge("b", "c", 0);
graph.addEdge("b", "d", 4); // parallel edge
graph.addEdge("b", "d", 5); // parallel edge

graph.addEdge("c", "c", 0); // self-loop
graph.addEdge("c", "d", 1);
graph.addEdge("c", "e", 3);

Part 4: Implement Graph.findMinimumSpanningTree(...)

Task: implement the Graph.findMinimumSpanningTree(...)

Notes:

  • You should implement findMinimumSpanningTree(...) using Kruskal's algorithm.

  • You can use top topKSort(...) to sort your edges.

Part 5: Implement KruskalMazeCarver

Task: implement the KruskalMazeCarver.returnWallsToRemove(...) method

If you remember when we were running the maze program from before, the "remove random walls" algorithms ended up generating pretty poor mazes. They either removed too many walls and created trivial mazes, or removed too few and created impossible ones.

What we really want is an algorithm that (a) generates a random-looking maze, (b) makes sure the maze is actually solvable, and (c) removes as few walls as possible.

It turns out that we can use algorithms such as Prim's and Kruskal's to do exactly that!

Here's the trick: we take the maze, treat each room as a vertex and each wall as an edge, assign each wall a random weight, and run any MST-finding algorithm. We then remove any wall that was a part of that MST.

This will end up satisfying all three criteria! By randomizing the wall weights, we remove random walls which satisfies criterion (a). A MST-finding algorithm, by definition, will ensure there exists a path from every vertex (every room) to every other one, satisfying criterion (b). And finally, because the MST will not have cycles, we avoid removing unnecessary edges and end up with a maze where there really is only one solution, satisfying criterion (c).

Your task here is to implement this algorithm within the KruskalMazeCarver class.

Other notes:

  • You can find this class inside the mazes.generators.carvers package.

  • Make sure you understand how to use the Maze and Wall objects. Recall that the Room objects should be your vertices and that the Wall objects should be the data for your edges (see the provided type parameters for your graph).

  • You may import and use java.util.Random while implementing this class.

  • If you're stuck, try taking a look at the RandomMazeCarver in the same package. Your algorithm will be a little more complicated, but it may serve as a good source of inspiration.

  • To test your method, try running the program and generate a few mazes after selecting the "Run (randomized) Kruskal" option. On our solution, running this option takes under 1 second (and is faster when running repeatedly after generating the first maze).

Some more maze generation algorithms

You may have noticed that Kruskal's algorithm tends to generate mazes with many short "cul-de-sacs", which lowers the overall difficulty of the maze; a better algorithm might instead try and generate longer, more "windy" paths. If you're curious about how other maze-generation algorithms achieve this, this website has a good overview of a few different maze generation algorithms. If you have some spare time, you can even implement some yourself—we won't be grading them though.

Part 6: Implement Graph.findShortestPathBetween(...)

Task: implement the Graph.findShortestPathBetween(...) method

Finally, you will implement the code to actually solve the mazes.

Notes:

  • You should implement findShortestPathBetween(...) using Dijkstra's algorithm.

  • To represent infinity, use the Double.POSITIVE_INFINITY constant.

  • While we definitely encourage you to look at the pseudocode provided in lecture, please be sure to take it with a grain of salt.

    We've tried to strike a good balance between the high-level overview and the implementation details, but that means we may have omitted some details. The pseudocode is meant to be a guide, not an instructional manual, so include other details as you see fit.

    In addition, you may find it convenient to arrange your code slightly differently from the way the pseudocode is presented, especially since you're trying to solve a slightly different problem than the one from the lecture slides: the algorithm in lecture finds the shortest paths from the starting vertex to every other vertex, whereas you only need the shortest path to a specific destination vertex.

    This doesn't mean you'll be completely rewriting Dijkstra's, but you should be aware that you might need to change things around to better fit your own needs, much like with the pseudocode provided for PageRank in the previous project.

  • Rather than inserting your vertices directly into your heap, you will need to create and insert objects of a custom inner class instead.

    Recall that IPriorityQueue requires its contents to implement the Comparable interface and therefore have a compareTo method, whereas the Graph's generic type V does not require vertices to be comparable. This means you will need to create a custom vertex class to store the data of a vertex while also implementing compareTo to use in the IPriorityQueue.

    Tips for your custom vertex class:

    • Here is some skeleton code you could base your custom vertex class off of: 
      private static class ExampleComparableVertex<V, E>
        implements Comparable<ExampleComparableVertex<V, E>> {
    // Add any fields you think will be useful

    public ExampleComparableVertex(/* your constructor arguments */) {
        // Initialize the object
    }

    public int compareTo() {
        // Define compareTo to determine how your vertices will
        // be ordered in the `IPriorityQueue`
    }
}
    • Be sure to consider what information would be useful to store as fields. If you find yourself stuck trying to implement Dijkstra's, it might be because you need to store more information in your custom vertex class (or elsewhere).
    • We recommend making your fields final so that they cannot be mutated. Mutating objects while they are contained in other data structures is an easy way to create strange bugs.
    • We recommend using the default implementations of equals and hashCode from java.lang.Object by not defining overriding methods for them in your class. The default implementations are sufficient, and incorrect implementations may cause your objects to misbehave in dictionaries and sets.

  • Dijkstra's algorithm involves updating the costs of vertices in the heap, but our IPriorityQueue interface does not have an updatePriority or decreaseKey method as shown in our lecture slides. Instead, we can use the replace(oldValue, newValue) method. This affects how we will use our custom vertex class:

    • You'll need to somehow keep track of your custom vertex objects in your queue in order to replace them with new objects.
    • You'll need to construct a new object with the updated information to replace the old one, since replace requires that the newValue is not already in the queue.

    If you want to review examples of using the replace method, check out this test code from the previous project.

  • Once you're done and all your tests are passing, try re-running the program and click the "Find shortest path" button. If everything went well, the program should now draw a red line connecting the start and the end! (Or, if there is no valid path, display an alert box stating so.)

    Efficient code should be able to generate and solve mazes (or recognize that they are unsolvable) on the default parameters for each maze shape and generator in under 1 second.

Part 7: Complete individual feedback survey

Task: Submit responses to the Canvas survey.

Each group member should answer and submit these questions independently on the form on Canvas. As a general rule of thumb, a good survey should take around 5 minutes to complete, but feel free to include as much detail as you want.

Deliverables

The following deliverables are due on Monday, August 19 at 11:59pm.

Be sure to double-check and make sure that...

Submit by pushing your code to GitLab. If you intend to submit late, fill out this late submission form when you submit.