Project 05 Grid Search with Stacks and Queues
A maze is a grid of FREE cells and OBSTACLE cells. Starting at one FREE cell, can you find a path to a target using only up, down, left, and right moves? You will implement depth-first search (DFS) with your Stack and breadth-first search (BFS) with your Queue. The search process is shared; the frontier's removal rule changes the behavior.
printStackOrder and printQueueOrder. The project's search is that same loop plus two additions: it stops when it removes the target, and it uses prev links to rebuild the path it found. The lines you listed as "changed" between the two methods are exactly what the subclasses in Task 4 supply. Everything else, you will write once in Task 3.Setup and deliverables
Continue in Projects/Project05 using the lab's LinkedList, Stack, Queue, Cell, CellType, and Maze. No additional data structures are required this week.
Download now:
You create: MazeDepthFirstSearch.java, MazeBreadthFirstSearch.java, and MazeSearchSimulation.java. Submit these, your completed AbstractMazeSearch.java, your own tests, and your report.
javac *.java fails until MazeDepthFirstSearch and MazeBreadthFirstSearch exist. Until then, compile with javac AbstractMazeSearch.java; Java compiles the files it depends on automatically.Task 1 — A shared abstract search class
Open the provided AbstractMazeSearch.java and read it before writing anything. It is a scaffold: the parts that every search needs in the same form are given, and the parts you write are marked TODO.
| Provided | You write |
|---|---|
private fields maze, start, target, cur; the constructor; getMaze(), getStart(), getTarget(), getCur(), setCur(Cell) | reset() — this task |
| the four abstract frontier methods below | traceback(Cell) — Task 2 |
the two-argument search(start, target) | search(start, target, display, delay) — Task 3; draw(Graphics, int) — Task 6 |
The scaffold declares these public abstract methods, leaving their bodies to the subclasses:
public abstract Cell findNextCell(); public abstract void addCell(Cell next); public abstract int numRemainingCells(); public abstract void clearFrontier();
The first removes and returns the next cell; the second adds one; the third reports frontier size. clearFrontier replaces or drains the frontier so that repeated searches do not retain old work. Implement public void reset() to clear the frontier, call maze.reset(), and set start, target, and cur to null. Do not call overridable methods from the superclass constructor; initialize subclass frontiers in subclass constructors.
Task 2 — Traceback
prev only answered "has this cell been discovered?" It also records who discovered it: when cur discovers neighbor n, the search sets n.prev = cur. Every discovered cell therefore points one step closer to the start, and the start points to itself. Following prev from the target walks the found path backward. Drawn together, all the prev links form a tree rooted at the start; the display draws this tree in Task 6.Implement public LinkedList<Cell> traceback(Cell cell). Return null if cell is null or undiscovered. Otherwise follow prev references back to start, placing each cell at the head of a result list with push. Stop at start, whose prev is itself. Return the cells in start-to-target order, including both endpoints. A successful path from a cell to itself contains one Cell and zero moves. A path with k cells has k−1 moves. For an invalid chain that reaches null or self-links somewhere other than start, return null.
Task 3 — Write the shared search once
Implement the four-argument version. The two-argument version is provided; it delegates with false and 0:
public LinkedList<Cell> search(Cell start, Cell target) public LinkedList<Cell> search(Cell start, Cell target, boolean display, int delay)
Require non-null endpoints that are actual Cell objects from this maze and are FREE. Reject invalid arguments with IllegalArgumentException; reject a negative delay too. Check coordinates and object identity, not just Cell.equals, which can match a cell from another maze.
- Reset this searcher's frontier and the maze's discovery marks. Save the supplied start and target in the fields.
- Mark start with
start.setPrev(start)and add it to the frontier. - While the frontier is nonempty, remove its next cell and save it in cur.
- If cur is target, return traceback(target). Checking here handles start == target naturally.
- For each FREE neighbor in Maze's order, if its prev is null, set prev to cur and add it to the frontier. Mark it before adding it. Do not change a previously discovered cell's prev.
- If the frontier empties without finding target, return null.
Do not add a path-improvement branch or priority updates. Each reachable cell enters the frontier at most once. A prev reference records how a cell was first discovered, not the cell processed immediately before it in time.
Task 4 — Two small subclasses
| Class | Private frontier field | Add | Remove | Size |
|---|---|---|---|---|
| MazeDepthFirstSearch | Stack<Cell> stack | push | pop | size |
| MazeBreadthFirstSearch | Queue<Cell> queue | offer | poll | size |
Each extends AbstractMazeSearch. Each constructor takes Maze, calls super(maze), and initializes its frontier with new LinkedList<Cell>(). Implement the abstract methods by delegating to the appropriate interface methods. clearFrontier may assign a new empty LinkedList to the interface-typed field. Do not duplicate the search loop.
BFS explores in increasing distance from the start, so it finds a shortest path measured in moves on this grid, where each move has equal cost. DFS finds a path if one exists, but does not guarantee a shortest path. Both must agree on reachability. Neighbor order can affect which particular path is found.
Task 5 — Test before animating
javac *.java java Project05Tester
Project05Tester runs every check, keeps going after a failure, and ends with a summary. Its sections are labeled by task, so you can run it as you go: the Task 4 frontier checks can pass before your search is written.
| Section | What it checks (for DFS and for BFS) |
|---|---|
| Task 4: frontier methods | add, remove, and size in Stack or Queue order; clearFrontier |
| Task 1: reset | frontier, prev marks, and start, target, and cur all cleared; obstacles kept |
| Task 2: traceback | null and undiscovered cells, start-to-target order, and broken prev chains |
| Task 3: bad arguments | null, obstacle, out-of-bounds, and other-maze endpoints; negative delay |
| Task 3: fixed grids | the cases listed below, plus exact BFS path lengths and repeated searches |
| Random mazes | 300 mazes: both searches agree on reachability, every path is valid, and every BFS path is a shortest path |
The random checks test rules that hold for every maze, so they never pass or fail by luck. If a section runs for more than 10 seconds, the tester reports a likely infinite loop and stops. That usually means the search adds a cell without marking it first.
Write tests of your own as well. Check a rectangular grid, adjacent endpoints, start equal to target, a forced detour, unreachable targets, and repeated searches using the same searcher. Check that returned paths begin and end correctly, contain only FREE cells, and move one row or column at a time. Passing the basic checks does not guarantee full credit.
Task 6 — Visualize the search
The provided MazeSearchDisplay calls public void draw(java.awt.Graphics g, int scale) on your searcher. Write that method to draw the maze first, the discovered prev links, the current cell, and the found path. Use Cell's drawing methods. Guard null start, target, and cur so the display can be repainted before or after a search.
Suggested colors: gray undiscovered FREE cells, black obstacles, yellow discovered cells, blue start, red target, magenta current cell, green path interior. Draw endpoint colors last so the path cannot hide them. A discovered cell is one added to the frontier; an expanded cell is one removed and processed. These are different measures.
If display is true, create new MazeSearchDisplay(this, 20) after setting the endpoints. Within each iteration repaint and pause for delay milliseconds. Repaint again before returning on success or failure. Handle InterruptedException by restoring the interrupt flag and returning null; do not silently swallow it. If display is false, create no window and do not sleep. Reuse or close old windows when running repeated demonstrations. The provided display's close button exits the program, so run experiments without display.
Task 7 — Controlled experiments
Create MazeSearchSimulation with a main method that can demonstrate DFS and BFS and run a batch of experiments with display disabled. Use the same obstacle arrangement and endpoints for both algorithms in each trial. Run DFS, save its metrics, reset discovery marks, then run BFS. Calling reinitialize between the two searches would generate a different maze and invalidate the comparison.
Use a fixed grid size, such as 20×30, fixed distinct endpoints such as opposite corners, and at least 10 obstacle-density settings spaced between 0 and 1. At each setting run at least 50 independently generated mazes. Explicitly set both endpoint types to FREE before searching. Your results therefore describe mazes with those endpoints forced FREE; at density 1 all other cells are obstacles.
- Success rate: successful searches divided by all trials. Keep unreachable trials in this denominator. Both algorithms should have identical success counts.
- Path length: number of moves (returned list size minus one). Compare means over the same successful trials; do not count an unreachable result as length zero. Show N/A if none succeed.
- Discovered cells: use maze.countVisitedCells immediately after each search, before reset. It includes start and cells left in the frontier. Average over all trials and state this denominator.
Record the density, trial count, successes, success rate, each mean path length, and each mean discovered-cell count in CSV or a clearly labeled table. Keep full precision while accumulating; round only for presentation. Do not use a loop that keeps generating mazes until it has enough successes: that would hide the failure probability.
Report
Include a short abstract, an explanation of interfaces and code reuse, your singly linked list and tail invariants, how the Stack and Queue change search order, your experimental method, labeled tables or graphs with captions, and a discussion of results. Include one small visual example of each algorithm and explain the prev links and final path.
- How does obstacle density affect success for your chosen grid and endpoints? Describe the observed transition; do not claim a universal exact cutoff from a finite experiment.
- How do DFS and BFS path lengths compare? Was BFS ever longer on the same maze? If so, debug before interpreting the result.
- How do discovered-cell counts compare? Does a shorter path necessarily require discovering fewer cells?
- What changed in the shared search code when you changed the frontier implementation? What does this show about programming to an interface?
Optional extensions
Keep all extension files in Extension1, Extension2, etc., each containing everything needed to run it. Possible extensions: compare different fixed neighbor orders, or visualize the frontier separately from expanded cells. Explain the question, method, and findings in your report.
Submission
Submit source files, your own tests, experiment output, and report in your personal Google Drive Projects/Project05 folder. The project is due Wednesday at 11:59 pm. A 10% deduction applies per day late. For work more than seven days late, consult the course's posted late-work policy.