30 lines
935 B
Racket
30 lines
935 B
Racket
#lang racket
|
|
|
|
;; the structure representing a maze of size NxM
|
|
(struct maze (N M tbl))
|
|
|
|
;; managing cell properties
|
|
(define (connections tbl c) (dict-ref tbl c '()))
|
|
|
|
(define (connect! tbl c n)
|
|
(dict-set! tbl c (cons n (connections tbl c)))
|
|
(dict-set! tbl n (cons c (connections tbl n))))
|
|
|
|
(define (connected? tbl a b) (member a (connections tbl b)))
|
|
|
|
;; Returns a maze of a given size
|
|
;; build-maze :: Index Index -> Maze
|
|
(define (build-maze N M)
|
|
(define tbl (make-hash))
|
|
(define (visited? tbl c) (dict-has-key? tbl c))
|
|
(define (neigbours c)
|
|
(filter
|
|
(match-lambda [(list i j) (and (<= 0 i (- N 1)) (<= 0 j (- M 1)))])
|
|
(for/list ([d '((0 1) (0 -1) (-1 0) (1 0))]) (map + c d))))
|
|
; generate the maze
|
|
(let move-to-cell ([c (list (random N) (random M))])
|
|
(for ([n (shuffle (neigbours c))] #:unless (visited? tbl n))
|
|
(connect! tbl c n)
|
|
(move-to-cell n)))
|
|
; return the result
|
|
(maze N M tbl))
|