Assignment 4, CSC102, Spring 2012

1 Guidelines

1.1 Contracts & Test Cases

For this and all remaining assignments, every method you develop must come with the following things:

• A commented header line that expresses the result of the function in terms of its inputs, written in English. Be as precise as you can within the space of a line or two. When implementing a method on mixed data, this comment only need appear in the interface.

• Data Definition. When a problem asks you to develop data (classes and interfaces), provide examples of the data. Every class needs to come with constructors and an equals method.

• Test cases. When a problem asks you to develop a method, provide assertEquals tests. If the method is on a piece of mixed data, be sure to provide test cases for all of the union’s variants. In this assignment, put all of the test cases in a single class named Tests.

2 Assignment

In this assignment, you’ll develop functions that generate and solve mazes.

Put all of your classes in a package called assignment4 .

Please make all of your methods and constructors public, to allow testing.

You may choose to develop a plugin for Minecraft that creates your maze as pathways in the sky, but it’s not required.

The following few sections provide a high-level description of the functionality you must implement. Following this is a more low-level look at the classes you’ll need to implement.

3 Representing Mazes

As we discussed in class, we can represent mazes as "places", indexed by an x and y coordinate, and a set of "connections", or wall openings, connecting one place to another, along with a "start" place and a "goal" place. A "path" can be represented as a list of places.

4 Implementing Maze Generation

In a MazeUtils class, implement the generateMaze method. It should accept a width and height in cells, a start place and a goal place, and return a Maze.

I’m going to describe what I see as the most straightforward way to generate mazes. You’re welcome to choose a different algorithm, as long as it has the same signature. Also, I’ve attached my Racket code to the bottom of this assignment; although Racket is not a language you’re familiar with, it may nevertheless be useful to you to read a working implementation of the program.

Generating the maze involves generative recursion. Specifically, maze generation involves extending a set of paths, branching sometimes, until the grid is full, and no paths can be extended any more.

For more detail, see the code below for the extend function.

When all of the paths have dead-ended, we’re done.

5 Implementing Maze Solving

In the Maze class, implement the object-oriented solve method, that returns a solution path for a maze, or signals an exception if there is no solution.

Maze solving is quite similar to maze generation. In this case, the generative recursion halts when we find a path that reaches the goal location.

In this case, we’re going to keep track of a set of paths. At each step, we’ll remove one path from the queue, figure out all the ways to extend it, taking care not to go through walls or re-visit places, and add the extended paths to the bottom of the queue. Again, see the code below for the extend-solution-path function.

6 Displaying Mazes

It’s all fine and well to generate and solve mazes, but if you have no way of displaying the mazes, it all feels a bit abstract. Develop the display method on the Maze class that prints a maze in a simple textual form, where spaces indicate places and openings, and the letter O indicates walls or wall intersections. There should be a solid frame of wall around the maze. The a period (.) should indicate the start, and the letter ’X’ should indicate the goal. When the two are the same, you can show either one. That’s not a very interesting maze, though.

Use the function System.out.println to display a line of text.

Here’s a simple example of a 4x4 maze. Note that the ’O’s representing the walls fall in between the cells:

OOOOOOOOO

O O.    O

OOOOO OOO

O       O

OOOOO O O

O     O O

O O OOO O

O O   OXO

OOOOOOOOO

In order to make this function testable, also implement the toDisplayLines method that returns a List<String> containing the lines of the output above (not including the newlines) so that calling System.out.println on each one in turn produces the diagram above. In fact, the easy way to develop this is to develop this one first, and then have display call it.

Also, develop the method displayWithSolution that draws a solution path using periods. Here’s the same example as before, drawn with solution path:

OOOOOOOOO

O O...  O

OOOOO.OOO

O    ...O

OOOOO O.O

O     O.O

O O OOO.O

O O   OXO

OOOOOOOOO

As for display, you must implement a testable toDisplayLinesWithSolution method (sorry about the name) that returns the lines of text as a list of strings.

7 Implementation

This assignment requires us to represent places, sets of places, openings, sets of openings, paths, and queues of paths.

We’ll start with the small ones, and work our way up.

You must develop the Place class that contains an x and a y field, and represents a place in the maze. It will need an equals method, just like all of the other classes you develop other than MazeUtils and Tests.

You must develop the Opening class that contains two places, and represents a pathway between two cells. The interesting thing about this class is that since the connections are bidirectional, we would like an opening from place A to place B to be "equals" to an opening from place B to place A. In order to implement this, you’ll need to extend the eclipse-provided "equals" method so that it considers two Openings equal if they contain the same two places, regardless of their order.

To represent sets of places and sets of openings we can use a HashSet. Specifically, we’ll be using HashSet<Place> and HashSet<Opening>. You’ll learn more about what exactly the "Hash" part means later, but for now, you can simply regard these as a high-level way to represent sets.

To represent a path, just use LinkedList<Place>, where the first element in the list represents the end of the path, and the last element represents the beginning of the list (this makes it easier to extend the list.)

To represent a Queue of paths, it turns out that the LinkedList implements the Queue interface. This means that a Queue of Paths will be represented as a LinkedList<LinkedList<Place>>.

Develop the Maze class; it should contain a width in cells, a height in cells, set of openings, and a start and goal Place. Make sure that your constructor accepts these arguments in this order, to make testing possible.

8 Getting Started

If you’re like me, you probably want the satisfaction of seeing something printed before you go on. I would work on the display functions before working on Maze Generation or Maze Solving. Maybe that’s just me, though.

9 Bugs or Corrections

Let me know right away about any bugs or problems in the assignment specification.

10 The Racket Version

#lang racket

(require 2htdp/image

rackunit)

; a maze is a set of openings between cells.

; an opening is a set of two cells.

; a cell is a list of two integers.

; given the width of the maze in cells, the height in

; cells, and the width and height of a cell, generate

; a maze and a solution and draw them both:

(define (generate-and-draw-maze w h start-location goal-location

cell-w cell-h)

; generate the maze:

(define small-maze (fill-up-maze (list start-location)

(set)

(make-empty-board w h)))

; find the solution:

(define solution-path

(with-handlers ([exn:fail?

; oops, no solution found:

(lambda (exn) (eprintf "~a" (exn-message exn))

empty)])

(extend-solution-loop goal-location

small-maze

(list (list start-location)))))

; draw the maze and the solution

(draw-solution

w h cell-w cell-h

solution-path

(draw-maze w h cell-w cell-h (maze-segments w h small-maze))))

; MAZE GENERATION

; a partial maze is a set of openings, and a list of "heads"

; of the maze exploration tree, and a map of unused cells

; call the "extend" function until there are no

; more heads

(define (fill-up-maze heads openings unused)

(cond [(empty? heads) openings]

[else (apply fill-up-maze

(extend heads openings unused))]))

; choose a head, extend it by one, possibly branching.

; takes the list of path heads, the table of openings,

; and the table of unused cells, and returns a list containing

; the new values for all three.

(define (extend heads openings unused)

; pick a head:

(define shuffled-heads (shuffle heads))

; find what's adjacent:

(define adjacent-empty (adjacent-empties (first shuffled-heads) unused))

; how many branches? :

(define new-heads

(take (shuffle adjacent-empty)

(add1 (weighted-random (length adjacent-empty)))))

; mark the new head places as used:

(define new-unused

(for/fold ([unused unused]) ([head new-heads])

(set-remove unused head)))

; remove the dead ends from the new heads:

(define non-dead-end-heads

(filter (lambda (x) (not (empty? (adjacent-empties x new-unused))))

(append new-heads (rest shuffled-heads))))

(define new-openings

(for/fold ([openings openings]) ([head new-heads])

(set-add openings (set (first shuffled-heads) head))))

; return the results

(list non-dead-end-heads

new-openings

new-unused))

; return a list of the adjacent cells

(define (adjacent-cells cell)

(match-define (list x y) cell)

(list (list (sub1 x) y)

(list (add1 x) y)

(list x (sub1 y))

(list x (add1 y))))

; return a list of the adjacent empty cells

(define (adjacent-empties cell unused)

(filter (lambda (cell) (set-member? unused cell))

(adjacent-cells cell)))

; generate a random number from 0 to n-1 (how many paths

; to follow in extending this path). If the result is greater

; than 0, the path branches.

(define (weighted-random n)

(cond [(or (= n 1) (< (random) 0.8)) 0]

[else (add1 (random (sub1 n)))]))

; make an "unused" map of the given dimensions,

; with 0,0 taken.

(define (make-empty-board w h)

(set-remove

(for*/set ([x w] [y h]) (list x y))

(list 0 0)))

; MAZE SOLVING

; a path is a list of cells.

; a solve-list is a list of paths.

; keep extending paths until we get to the end or run out of paths

(define (extend-solution-loop goal-cell openings paths)

(define (ends-at-goal? path) (equal? (first path) goal-cell))

; did we run out of paths to explore?

(cond [(empty? paths) (error 'extend-solution-loop "no solutions")]

[else

(define maybe-found (filter ends-at-goal? paths))

; have we not yet found the goal?

(cond [(empty? maybe-found)

(define new-paths

(extend-solution-path openings (first paths)))

(extend-solution-loop goal-cell

openings (append

(rest paths)

new-paths))]

; we found the goal!

[else (first maybe-found)])]))

; given a map of openings and a path, extend

; in any ways possible to produce a list of paths

(define (extend-solution-path openings path)

; what's adjacent to the head of this path?

(define possible-nexts (adjacent-cells (first path)))

; which ones have wall openings to allow passage?

(define nexts-with-paths

(filter (lambda (cell) (set-member? openings

(set (first path) cell)))

possible-nexts))

; which ones haven't yet been visited?

(define non-loop-nexts

(filter (lambda (cell) (not (member cell path))) nexts-with-paths))

; fork the path for each:

(for/list ([next non-loop-nexts])

(cons next path)))

; GRAPHICS:

; given a width and height and openings,

; return a list of all of the segments

; to be drawn in the list.

(define (maze-segments w h openings)

(apply

append

(for*/list ([x (in-range w)]

[y (in-range h)])

(append

(cond [(and

(< x (sub1 w))

(not

(set-member? openings (set (list x y) (list (add1 x) y)))))

(list (list (add1 x) y (add1 x) (add1 y)))]

[else empty])

(cond [(and

(< y (sub1 h))

(not

(set-member? openings (set (list x y) (list x (add1 y))))))

(list (list x (add1 y) (add1 x) (add1 y)))]

[else empty])))))

; given a width, a height, a cell-width and cell-height,

; and a list of segments (in cell coordinates), return

; a scene containing the maze.

(define (draw-maze w h cell-w cell-h segments)

(foldr

(lambda (segment scene)

(add-line scene

(* cell-w (first segment))

(* cell-h (second segment))

(* cell-w (third segment))

(* cell-h (fourth segment))

"black"))

(empty-scene (* w cell-w) (* h cell-h))

segments))

; make the blue square image used to indicate a path

(define (make-path-square-image cell-w cell-h)

(rectangle (ceiling (/ cell-w 2))

(ceiling  (/ cell-h 2))

"solid"

"blue"))

; given the maze parameters and the path and the image, draw

; blue dots along the path

(define (draw-solution w h cell-w cell-h path maze-image)

(define path-square-image (make-path-square-image cell-w cell-h))

(for/fold ([image maze-image]) ([cell path])

(underlay/xy image

(* (+ 1/4 (first cell)) cell-w)

(* (+ 1/4 (second cell)) cell-h)

path-square-image)))

(generate-and-draw-maze 60 60 (list 0 0) (list 59 59) 8 8)

(generate-and-draw-maze 4 4 (list 1 0) (list 3 3) 20 20)

; TEST CASES

(check-equal? (maze-segments 1 1 (set)) empty)

(check-equal? (list->set (maze-segments 3 2 (set)))

(set (list 1 0 1 1)

(list 1 1 1 2)

(list 2 0 2 1)

(list 2 1 2 2)

(list 0 1 1 1)

(list 1 1 2 1)

(list 2 1 3 1)))

(check-equal? (list->set (maze-segments 3 2

(set (set (list 1 1)

(list 1 0))

(set (list 1 1)

(list 2 1)))))

(set (list 1 0 1 1)

(list 1 1 1 2)

(list 2 0 2 1)

(list 0 1 1 1)

(list 2 1 3 1)))

(define three-cells-taken (set (list 0 0) (list 0 1) (list 1 1)))

(check-equal? (length (adjacent-empties (list 2 0) three-cells-taken)) 0)

(check-equal? (length (adjacent-empties (list 1 1) three-cells-taken)) 1)

(check-equal? (length (adjacent-empties (list 0 1) three-cells-taken)) 2)

(check-equal? (extend-solution-path (set (set (list 3 3) (list 3 2))

(set (list 3 3) (list 4 3)))

(list (list 3 3) (list 3 2) (list 3 1)))

(list (list (list 4 3) (list 3 3) (list 3 2) (list 3 1))))

(define 3x3-empty (make-empty-board 3 3))

(define 5x5-empty (make-empty-board 5 5))

(check-equal? (adjacent-empties (list 0 0) 5x5-empty)

(list (list 1 0) (list 0 1)))