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.

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.

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.

ProvidedYou write
private fields maze, start, target, cur; the constructor; getMaze(), getStart(), getTarget(), getCur(), setCur(Cell)reset() — this task
the four abstract frontier methods belowtraceback(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

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.

  1. Reset this searcher's frontier and the maze's discovery marks. Save the supplied start and target in the fields.
  2. Mark start with start.setPrev(start) and add it to the frontier.
  3. While the frontier is nonempty, remove its next cell and save it in cur.
  4. If cur is target, return traceback(target). Checking here handles start == target naturally.
  5. 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.
  6. 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

ClassPrivate frontier fieldAddRemoveSize
MazeDepthFirstSearchStack<Cell> stackpushpopsize
MazeBreadthFirstSearchQueue<Cell> queueofferpollsize

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.

SectionWhat it checks (for DFS and for BFS)
Task 4: frontier methodsadd, remove, and size in Stack or Queue order; clearFrontier
Task 1: resetfrontier, prev marks, and start, target, and cur all cleared; obstacles kept
Task 2: tracebacknull and undiscovered cells, start-to-target order, and broken prev chains
Task 3: bad argumentsnull, obstacle, out-of-bounds, and other-maze endpoints; negative delay
Task 3: fixed gridsthe cases listed below, plus exact BFS path lengths and repeated searches
Random mazes300 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.

  1. 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.
  2. How do DFS and BFS path lengths compare? Was BFS ever longer on the same maze? If so, debug before interpreting the result.
  3. How do discovered-cell counts compare? Does a shorter path necessarily require discovering fewer cells?
  4. 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.

← Back to Lab 05