Instructions
Please read and understand these expectations thoroughly. Failure to follow these instructions could negatively impact your grade. Rules detailed in the course syllabus also apply but will not necessarily be repeated here.
- Identification: Place you and your partner’s x500 in a comment near the top of all files you submit. Failure to do so may result in a penalty.
- Partners: You may work alone or with one partner. Failure to tell us who is your partner is indistinguishable from cheating and you will both receive a zero. Ensure all code shared with your partner is private.
- Code: You must use the EXACT class and method signatures we ask for. This is because we may use a program to evaluate your code. Code that doesn’t compile will receive a significant penalty. Code should be compatible with Java 11, which is installed on the CSE Labs computers. Credit ALL outside references used in completing this project both in the README and within the code that utilizes the referenced material.
- Questions: Questions related to the project can be discussed on Piazza or Discord in abstract. This relates to programming in Java, understanding the writeup, and topics covered in lecture and labs. Do not post any code or solutions on the forum. Do not e-mail the TAs your questions when they can be asked on Piazza or Discord.
- Grading: Grading will be done by the TAs, so please address grading problems to them privately through the ticket system on Discord or a private Piazza post.
- README: Make sure to include a README.txt in your submission that contains the following information:
- Group member’s names and x500s
- Contributions of each partner (if applicable)
- Any assumptions
- Additional features that your project had (if applicable)
- Any known bugs or defects in the program
- Credit ALL outside references used in completing this project both in the README and within the code that utilizes the referenced material.
IMPORTANT: You are NOT permitted to use ANY built-in libraries, classes, etc… besides java.awt.Color, java.util.Random, and java.util.Scanner. Double check that you have NO import statements in your code, except for those explicitly permitted.
Code Style
Part of your grade will be decided based on the “code style” demonstrated by your programming. In general, all projects will involve a style component. This should not be intimidating, but it is fundamentally important. The following items represent “good” coding style:
- Use effective comments to document what important variables, functions, and sections of the code are for. In general, the TA should be able to understand your logic through the comments left in the code. Try to leave comments as you program, rather than adding them all in at the end. Comments should not feel like arbitrary busy work - they should be written assuming the reader is fluent in Java, yet has no idea how your program works or why you chose certain solutions.
- Use effective and standard indentation.
- Use descriptive names for variables. Use standard Java style for your names: ClassName, functionName, variableName for structures in your code, and ClassName.java for the file names.
Try to avoid the following stylistic problems:
- Missing or highly redundant, useless comments. int a = 5; //Set a to be 5 is not helpful.
- Disorganized and messy files. Poor indentation of braces ({ and }).
- Incoherent variable names. Names such as m and numberOfIndicesToCount are not useful. The former is too short to be descriptive, while the latter is much too descriptive and redundant.
- Slow functions. While some algorithms are more efficient than others, functions that are aggressively inefficient could be penalized even if they are otherwise correct. In general, functions ought to terminate in under 5 seconds for any reasonable input.
The programming exercises detailed in the following pages will both be evaluated for code style. This will not be strict - for example, one bad indent or one subjective variable name are hardly a problem. However, if your code seems careless or confusing, or if no significant effort was made to document the code, then points will be deducted.
If you are confused about the style guide, please talk with a TA.
Project Structure
Your project submission must adhere to the following rules. Failure to do so will impact your grade.
- Your submission should be one ZIP file named [partner1 x500]_[partner2 x500]_Project4.zip
- The ZIP file should contain a single directory (folder) named [partner1 x500]_[partner2 x500]_Project4
- This directory should contain only these 2 files:
- MyGrid.java
- README.txt
For example, the following would be a valid project structure:
- shino012_hoang159_Project4.zip
- shino012_hoang159_Project4
- MyGrid.java
- README.txt
If you are working alone, just include your single x500 in the naming of the ZIP file and directory.
If you have any questions about this structure, ask a TA.
Credits
It also implements a search algorithm to create mazes inspired by the following Wikipedia article: https://en.wikipedia.org/wiki/Maze_generation_algorithm#Depth-first_search
While we are pulling ideas from this, do not follow any instructions found on the web links.
Introduction
In this project, you will use Stacks and Queues to solve special grids. A grid in this instance is a network of paths designed so there is at least one path from the entrance of the grid to the exit of the grid. You will be using a queue structure to find this correct path through the grid, and a stack structure to randomly generate new grids.
Files Given
Along with the project write-up, you will be given the following files:
- MyGrid.java The main java class for this project
- Cell.java A helper class for MyGrid
- NGen.java - Both the queue and stack structure will utilize this generic node class
- Q1.java - An interface for a generic queue
- Q1Gen.java - An implementation of a generic queue
- StackGen.java - An interface for a generic stack
- Stack1Gen.java - An implementation of a basic stack
- Canvas.java - A class to draw shape objects to the screen
- Square.java - A shape class
You will not change any of the files given except for the class called MyGrid. All other files are provided with everything you should need.
Stack and Queue data structures
Both the stack and queue data structures provided have basic functionality. Take a look at both classes to ensure you know how to instantiate and use them properly. They should be similar to the examples you have seen in lecture.
Cell
You do not need to change the Cell class, but this section describes how a cell works. The Cell class has the following attributes:
- boolean visited - true if this cell has been visited, false otherwise
- boolean right - true if a right boundary, false if an open right side
- boolean down - true if a lower boundary, false if an open bottom
Each of these attributes have setter and getter functions respectively. The Cell constructor initializes the cell to have walls on the right and bottom. When we say a cell has been visited, assume we are referring to the visited attribute unless otherwise noted. The purpose for each attribute will become evident in the MyGrid section below.
Canvas and Square
You do not need to change either class. The Canvas class is very similar to the one seen on Project 1. It has been updated to incorporate the new shape class Square. The Square class works identical to the shapes that you implemented in Project 1 as well. Make sure to familiarize yourself again with the shape class as it will be very important for the drawGrid() method.
MyGrid
The MyGrid class is where the majority of the work will take place. There will be three main functions for the grid class:1
2
3public static MyGrid makeGrid(int level);
public void drawGrid();
public void solveGrid();
More detail about each function will be found in their respective sections. The MyGrid class will have three main attributes: Cell[][] grid, int startRow, and int endRow. The grid attribute will be how the grid is represented. This attribute will have the following properties:
- The Grid dimensions will depend on user input in main. The inputs for each level: Level 1: 5x5, Level 2: 5x10, Level 3: 12x12
- The start of the grid will always be on the left: grid[startRow][0] (open on the left)
- The end of the grid will always be on the right: grid[endRow][cols-1] (open on the right)
- All Cells on the “top” (row 0) have an implicit top boundary
- All Cells of the “left” (column 0) have an implicit left boundary
- Once initialized, the grid should have a path from the beginning to the end of the grid.
For example, a grid of size 5x5 that could be generated is shown in Figure 1 on the left.
Constructor
The MyGrid constructor should have the following signature: public MyGrid(int rows, int cols, int startRow, int endRow); It should instantiate the grid attribute: grid = new Cell[rows][cols] and create a new cell object for each index: grid[i][j] = new Cell(). It should also set the attributes startRow and endRow.
makeGrid
This function should instantiate a new MyGrid object, generate the grid, and then return the new MyGrid object. This will build a grid from scratch by utilizing a stack. By choosing randomly which direction to go from a particular cell, and visiting every cell, there should be a path from the entrance to every cell, including the exit. You can do this by implementing the following search algorithm:
- Initialize a stack with the start index {startRow, 0}. Mark this cell (grid[startRow][0]) as visited.
- Loop until the stack is empty:
- Get the top element off the stack but do not remove it.
- Choose a random neighbor to the corresponding cell that has not been visited and do the following:
- Add the neighbor’s index to the stack.
- Mark the neighbor as visited.
- Remove the wall between the current cell and the neighbor cell.
- If the current cell does not have any un-visited neighbors, then it is a dead end. Pop the corresponding index from the top of the stack.
where a neighbor is defined as a cell that is either horizontally or vertically next to reference cell. The last thing the makeGrid function should do before returning is set the visited attribute of each grid cell to false.
drawGrid
This function will print a visual representation of the grid to the terminal. Using the Canvas and Squares class, you will print the representation of the grid to the user. This can be done by utilizing the Canvas object already made for you and calling the drawShape() method. For this method, we will only be drawing squares.
- By changing the color of the square, we will be able to visualize the paths each algorithm takes. You will use the imported Color class to do this.
- Start by choosing three colors to represent your walls, visited cells, not visited but open cells, and the start and end cells.
- You may also leave your start and end cells empty like shown in the figure above.
- Make sure to utilize the right and bottom cell attributes in order to implement this properly.
- You can use different colors for the path and the grid walls as long as it is clear they are different colors.
You are not restricted to how you draw the grid, but it may be easiest to going though each row one-at-a-time. There may be two special cases depending on how you implement the algorithm. You may need to remove the walls for the entrance and exit on the border of the grid separate from the loop.
By the end of this function, you should have the entire representation of the grid. Do not reset the visited attribute of the cells.
solveGrid
To solve a grid, we will use a queue to test all possible paths. The algorithm should work as follows.:
- Initialize a queue with the start index {startRow, 0}
- Loop until the queue is empty:
- Dequeue the front index of the queue and mark the corresponding cell’s visited attribute as true.
- If the current cell is the finish point (i.e. the index {endRow, columns-1}), then break from the loop. The grid has been solved.
- Enqueue all reachable neighbors that are un-visited.
At the end of the function, call the drawGrid function. An example of a solved grid is figure 2.
Testing
You are free to do any testing you see fit. You will know the functions are being generated correctly if there exists a path from the entrance cell to every cell of the grid, including the exit cell.