Individual Onboarding Project: Maze Search Algorithms

This project is intended to be an introduction to the course's procedures and to help you practice improving your coding process and design. It will not be explicitly graded but, instead, serve as a starting point for us to see your coding strengths and weaknesses (and how well you follow directions). Thus, you will get the most out of this assignment by putting in a good faith effort.

You will be given code that implements several maze search algorithms:

• Random Walk: randomly chooses a place to step and “hopes” to one day find the goal.
  An “exploration bias” is included so the algorithm will prefer a step that it has not already taken, making it more likely to find a solution.
• DFS (Depth-First search): goes as far as possible in one direction until it reaches a dead end; then it backtracks to a point at which it can choose a new path.
• BFS (Breadth-First search): looks one step in every viable direction at once, maintaining a list of the open path possibilities and cycles through them sequentially (it will always find the shortest path to the goal).
• Greedy: similar to Breadth-First, but always chooses to move forward with the path that is closest to the goal (it cannot guarantee to find the shortest path, but it often does so, and more quickly).
• Magic: similar to the Greedy algorithm, but ignores walls on its way to the goal (this is not an actual search algorithm, just something added for fun :)

Your goal is to improve the design of the code in the model package, not its functionality, and practice using GIT effectively in two iterations:

1. Planning: Update your development environment, evaluate the code to understand how it works (and find a bug), then make refactoring and test plans
2. Refactoring: Take time to use GIT more intentionally to manage your project and implement your plans

You will be provided a GIT repository, maze_NETID, hosted in the course's Gitlab group to work on this project.

Submission

You will not "submit" projects as in many other CompSci classes. Instead, what is in the main branch of your Gitlab repository at the deadline is what will be graded.

The final version of the code must:

• follow Google's Java code format standards
• pass all automated tests
• contain comments for all public packages/modules, classes, methods/functions, and constants (inline comments should be kept to a minimum because the code should be readable on its own)
• use logging (rather than print statements)

You are responsible for ensuring that all files are correctly pushed to the repository on time.

Specifications

Phase 1

Install and connect the latest version of the necessary development tools for this project. Later projects will provide you with more freedom :)

Clone the project repository created for you on the course Gitlab server.

Evaluate only the code in the model package to determine how best to factor out as much of the duplicated code as possible (you can add any new non-public classes or methods as you want: protected (for subclasses to override) and private (to factor out common functionality)). You are strongly encouraged to write many small methods that clearly identify the general steps of a search algorithm and that can be overridden or shared as needed.

Make a refactoring plan, in the file REFACTOR_PLAN.md, for the changes you intend to make that identify issues you find in the code and justify how your proposed changes will improve its design. Include the following points:

• describe the general steps the maze-solving algorithms share (even if some of them implement them by doing nothing)
• convert each step into a Java method signature (i.e., name, parameters, and return type)
• describe how the SearchAlgorithm's general step() method could utilize your new methods
• determine if these new methods should be implemented in the SearchAlgorithm superclass or its subclasses (and whether they can be made protected or private)?
• describe any other classes could be created to help improve the code in the model package

Note, an algorithm's data structure is essential to why it works (i.e., a Stack organizes its data completely differently than a Queue or PriorityQueue), so you will not be able to use a single concrete data structure for all the algorithms. However, Java does have a Collection abstraction (of which they are all concrete instances) that may help in storing the data structures in a common variable but, at some point, you will need to call the Stack's push() or pop() method.

Create a test plan, in the file TEST_PLAN.md, using the ZOMBIES acronym to think of both positive and “negative” tests, for each non-random, non-trivial public method in the model package code. Include the following for each:

• describe at least four positive tests, their purpose, example values, and what JUnit assertion you expect to use
• describe at least one negative test, its purpose, example values, and what JUnit assertion you expect to use

Describe the existing bug in the program, in the file TEST_PLAN.md, that you can find by running the program or perhaps when coming up with your tests, by answering the following questions:

• when does the bug occur?
• what is the cause of the bug?
• what test could you write that would show the bug (i.e., it would fail in the current version of the code)?
• how would you fix the bug?

Practice using Gitlab to manage Phase 2 of your project by creating Issues for your Refactoring and Test plans:

• Read this series of short blog posts describe how to think about building software differently that we will emphasize in this course:
  GIT, in general, and Gitlab, specifically, provide a lot of support built in to help you manage your project
  
  • Always start with an issue
  • The Gitlab Issue Board
  • It's all connected in Gitlab
  • Use Tags to organize your history
  • Use Protected Branches Keep Your Code Safe
  • Code Review via Gitlab Merge Requests
  And here is a longer video that gives some of the technical details of how GIT works so you can use it more effectively in this philosophy.
• Practice working with this flow in GIT on your own before working in a team, including using multiple branches, protecting main, and using Merge Requests
  For the phases of this project, we suggest:
• using branches to show the intent of your work
• creating issues before you do the work
• moving and tagging those issues on Gitlab's Issue Board
• closing or updating issues with your commits or Merge Requests using Gitlab's action words
• write good commit messages annotated with their purpose

Phase 2

Implement your Refactoring and Test plans, using GIT effectively and intentionally rather than a few large "kitchen sink" or "submit-only" commits:

• make many small purposeful commits rather than just one or two large "kitchen sink" or "submit-only" commits
• use Issues to help manage your project
• use Tags to clearly identify important commits
• use Feature branches to identify short work that needs to be done
• follow these Commit message formatting guidelines and always reference an Issue

All programming languages have at least one logging library to make it as easy as possible. In Java, use Log4j2 to output different levels of information rather than println() statements, including any time an Exception is thrown:

• control what’s emitted, easily turning it on or off to get more or less information
• define what types of information you want to include in your logs
• configure how it looks when it’s emitted
• save WARN, ERROR, and FATAL level messages to a file in the folder named log (it is fine for INFO and DEBUG messages to continue to go to the console (standard out))

All programming languages have at least one testing library to make it as easy as possible. In Java, use JUnit to write separate Test classes and methods:

• annotated with @Test
• written in separate methods, that follow these naming standards to show what you are intending to test
• commented as needed to show how the chosen input values relate to the test's goal
• simple enough that you know the expected output values for each test before you run the code

While you are not required to practice TDD strictly (always writing a test before writing any code), you are expected to create tests frequently during the coding process rather than waiting until the end. In addition to helping regularize your programming session, it provides a host of other benefits and even more! No matter what you decide, to demonstrate you are regularly attempting to test your code, all GIT commits must include at least one new or updated test.

Optional Extra Credit

Add a new search algorithm (such as A*).

Add public methods to the SearchAlgorithm abstraction for any of the following behaviors and implement them for all search algorithms without duplicating the code:

• report whether or not the algorithm has successfully found the goal (note, this is different behavior than the current private method isSearchOver())
• report the current number of steps taken by the algorithm exploring the maze
• report the current maximum size the data structure has been while exploring the maze
• report the current number of times the algorithm has had to backtrack (i.e., reached a deadend and had to go back to a different path)

Add any of the following interactive elements to the view package:

• create a Pause button, whose title switches between "Pause" and "Resume" depending on the state of the animation
• add a slider to the bottom action panel that controls how fast the animation updates (i.e., a higher slider value results in a smaller delay between frame updates)
• turn the color of the algorithm title panel green (or some positive color) only when the maze is successfully completed
• add each of the numeric values, with appropriate labels, to the algorithm title panel and update them dynamically as the algorithm runs
• add a new panel between the maze display and the action buttons that
  • displays the name of the algorithm with the smallest number for each numeric value (i.e., smallest size, smallest data structure size, and fewest backtracks)
  • compare only those algorithms that have been run on the current maze (i.e., do not show any stats for algorithms not yet run on that maze)
  • reset the values to 0 when a new maze is created

Keep the display code as clean as possible, rather than assuming that it has to have long methods because "OpenJFX has to be that way" or the code can be repetitious because "it is only called once". The example code in MazeDisplay provides one such way to keep your methods small (but, unless you are careful, it may also encourage you to write duplicated code as you add features).