; ★★★ CSC 104 2015 Fall Project I : Maze Generator ★★★
; This program creates a maze as a list of Cells containing x-y coordinates,
; starting from (0, 0) and staying within a grid of size 'maze-size'.
(define maze-size 15) ; The algorithm is:
; ; ;
Keep picking a random Cell adjacent to a random Cell from the maze so far, and if it's not already in the maze, and is within the bounds of the grid, and touches only one Cell in the maze, then add it to the maze.
; In Part I below you complete the maze generator by following steps 1-10. ; That is worth 85% of the project grade.
; In Part II below you add the ability for a player to move around the maze. ; That is worth the remaining 15% of the project grade.
; Where new 'check-expect's are required, feel free to make more than the ones ; requested, especially new partial design ones to help you build up to the ; full design ones.
; Try to use 'map' and 'apply' where appropriate. ; Notice that a function 'list-4' is defined for you: it might be useful in ; situations where you could 'map' and/or 'apply'.
; ★★★ Part I: Maze Generation ★★★
; 1. Fix 'random-element' to do what its contract and purpose statement say. ; 2. Make a full design 'check-expect' for 'adjust'. ; 3. Fix 'adjust' to do what its tests, contract, and purpose statement say. ; 4. Make a full design 'check-expect' for 'adjacents', that uses 'adjust'. ; 5. Fix 'adjacents' to do what its tests, contract, and purpose statement say.
-
; You might enjoy using a 'map' with three lists to implement it, but
-
; that is not a requirement. ; 6. Fix 'random-adjacent' to do what its contract and purpose statement say. ; 7. Fix 'count-in' to do what its tests, contract, and purpose statement say. ; 8. Make a full design 'check-expect' for 'touches' ; 9. Fix 'touches' to do what its tests, contract, and purpose statement say. ; 10. Fix the first clause in 'try' to do what the contract and purpose statement say.
; A 'Cell' contains two numbers: 'x' and 'y' coordinates. ; The intended usage is:
; ; ; (define-struct Cell (x y))
make-Cell : number number -> Cell Cell-x : Cell -> number Cell-y : Cell -> number
(check-expect (list-4 104) (list 104 104 104 104))
; list-4 : any -> list ; Produce a list containing 'element' four times. (define (list-4 element) (list element element element element))
; random-element : list -> any ; Produce a random element from the non-empty list 'a-list'. (define (random-element a-list)
(list-ref a-list (random 1)))
(check-expect (adjust (make-Cell 104 123) 2 -3)
(make-Cell 106 120))
; A partial design for 'adjust':
(check-expect (adjust (make-Cell 104 123) 2 -3)
(make-Cell (+ 104 2)
(+ 123 -3)))
; adjust : Cell number number -> Cell ; Produce a Cell like 'cell' but with 'x' and 'y' added to the 'x' and 'y' of 'cell'. (define (adjust cell x y)
“hi”)
(check-expect (adjacents (make-Cell 123 104))
(list (make-Cell 123 105)
(make-Cell 123 103)
(make-Cell 122 104)
(make-Cell 124 104)))
; adjacents : Cell -> list-of-Cells ; Produce a list of the four Cells above, below, left, and right of 'cell'. (define (adjacents cell)
“hi”)
; random-adjacent : list-of-Cells -> Cell ; Produce a random Cell adjacent to a random Cell from the non-empty list 'cells'. (define (random-adjacent cells)
“hi”)
(check-expect (count-in (make-Cell 104 123)
(list (make-Cell 104 123)
(make-Cell 45 67)))
1) (check-expect (count-in (make-Cell 100 123)
(list (make-Cell 104 123)
(make-Cell 45 67)))
0) ; A full design for 'count-in':
(check-expect (count-in (make-Cell 100 123)
(list (make-Cell 104 123)
(make-Cell 45 67)))
(cond [(member? (make-Cell 100 123)
(list (make-Cell 104 123)
(make-Cell 45 67)))
1]
[else 0]))
; count-in : Cell list-of-Cells -> number ; Produce 1 if 'cell' is in 'cells', otherwise produce 0. (define (count-in cell cells)
“hi”)
(check-expect (touches (make-Cell 2 30)
(list (make-Cell 2 31)
(make-Cell 1 29)
(make-Cell 1 30)
(make-Cell 2 30)))
2) ; A partial design for 'touches':
(check-expect (touches (make-Cell 2 30)
(list (make-Cell 2 31)
(make-Cell 1 29)
(make-Cell 1 30)
(make-Cell 2 30)))
(+ (count-in
(make-Cell 2 31)
(list (make-Cell 2 31) (make-Cell 1 29) (make-Cell 1 30) (make-Cell 2 30)))
(count-in
(make-Cell 2 29)
(list (make-Cell 2 31) (make-Cell 1 29) (make-Cell 1 30) (make-Cell 2 30)))
(count-in
(make-Cell 1 30)
(list (make-Cell 2 31) (make-Cell 1 29) (make-Cell 1 30) (make-Cell 2 30)))
(count-in
(make-Cell 3 30)
(list (make-Cell 2 31) (make-Cell 1 29) (make-Cell 1 30) (make-Cell 2 30)))))
; touches : Cell list-of-Cells -> number ; Produce the number of Cells adjacent to 'cell' that are in 'cells'. (define (touches cell cells)
“hi”)
; extend : list-of-Cells -> list-of-Cells ; Produce the version of 'cells' produced from trying to include a random Cell adjacent to one of ; the Cells in 'cells'. (define (extend cells)
(try (random-adjacent cells) cells))
; try : Cell list-of-Cells -> list-of-Cells ; If 'cell' is not in 'cells', and the coordinates of 'cell' are between 0 and 'maze-size'-1 ; inclusive, and 'cell' touches exactly one Cell in 'cells', then produce 'cells' with the ; new 'cell' included. ; Otherwise, with a small probability give up and produce just 'cells'. ; Otherwise, try to extend 'cells' again. (define (try cell cells)
(cond [#false (list* cell cells)]
[(zero? (random (sqr maze-size))) cells]
[else (extend cells)]))
; ★★★ Part II: Visualizing the Maze Generation and Moving the Player ★★★
; Once you’ve done steps 1-10 of Part I and the following appears to be working reasonably, then
; you can uncomment the 'big-bang' expression at the very end of the program to see a visualization.
; To complete this part do the following steps to allow the player to move around the maze. ; 1. Add contracts to 'try-adjust-place' and 'try-move'. ; 2. Add some 'check-expects' for 'try-adjust-place' and 'try-move' to clarify what they ; should do, with a good variety of arguments.
; 3. Fix 'try-move' to allow the player to move right. ; 4. Fix 'try-move' to prevent the player from moving off the grid or to a cell not in the maze. ; 5. Fix 'key' to allow the player to move in the three other directions.
; repeat : any unary-function number -> list
(define (repeat start transformer times) (cond [(zero? times) (list)]
[else (list* start (repeat (transformer start) transformer (sub1 times)))])) ; A list of the intermediate mazes created by extending a single cell maze ten times.
(repeat (list (make-Cell 0 0)) extend 10) (require picturing-programs)
; The state of the animation is the current list of Cells in the maze, ; along with the Cell in the maze where the player currently is. ; The intended usage is:
; ; ; (define-struct World (cells place))
make-World : list-of-Cells Cell -> World World-cells : World -> list-of-Cells World-place : World -> Cell
; tick : World -> World ; Produce a new state of the world by extending the maze, but leaving ; the player in the same place. (define (tick world)
(make-World (extend (World-cells world)) (World-place world)))
(define cat )
(define cell-width (image-width cat))
(define cell-height (image-height cat))
(define grass (rectangle cell-width cell-height “solid” “darkgreen”)) (define shrub (overlay/align “middle” “bottom”
; shrub/rock : any -> image
(define (shrub/rock ignore)
(ellipse (floor (* 3/4 cell-width))
(floor (* 1/2 cell-height))
"solid" "brown")))
(overlay (random-element (list shrub shrub shrub )) grass))
; row : any -> image
(define (row ignore) (apply beside (map shrub/rock (range 0 maze-size 1)))) (define background (freeze (apply above (map row (range 0 maze-size 1)))))
(define void (rectangle (* cell-width maze-size) (* cell-height maze-size) "outline" "transparent")) ; grass-at : Cell -> image (define (grass-at cell)
(place-image/align grass
(* cell-width (Cell-x cell))
(* cell-height (Cell-y cell))
"left" "top"
void))
; draw : World -> image ; Produce an image of the maze and the player. (define (draw world)
(scale 1/2
(underlay/align/offset "left" "top"
(apply underlay background
(map grass-at (World-cells world)))
(* cell-width (Cell-x (World-place world)))
(* cell-height (Cell-y (World-place world)))
cat)))
(define (try-adjust-place world x y) (make-World (World-cells world)
(try-move (World-place world)
(adjust (World-place world) x y)
(World-cells world)))) (define (try-move cell-from cell-to cells)
cell-from)
; key : World KeyEvent -> World ; Produce a new state of the world with the player moved according to the user ; pressing the left, right, up, or down arrow keys. (define (key world a-key)
(cond [(key=? a-key "right") (try-adjust-place world 1 0)]
[else world]))
;(big-bang (make-World (list (make-Cell 0 0)) (make-Cell 0 0))
-
; [on-tick tick]
-
; [to-draw draw]
-
; [on-key key])