1.18.3 Breadth-first Search
The cat’s move decision is based on a breadth-first search of a graph. The graph’s nodes are the cells on the board plus a special node called 'boundary that is adjacent to every cell on the boundary of the graph. In addition to the boundary edges, there are edges between each pair of adjacent cells, unless one of the cells is blocked, in which case it has no edges at all (even to the boundary).
This section describes the implementation of the breadth-first search, leaving details of how the graph connectivity is computed from the board to the next section.
The breadth-first function constructs a distance-map, which is a list of dist-cell structs:
(define-struct/contract dist-cell ([p (or/c 'boundary posn?)] [n natural-number/c]) #:transparent)
Each p field in the dist-cell is a position on the board and the n field is a natural number, indicating the distance of the shortest path from the node to some fixed point on the board.
The function lookup-in-table returns the distance from the fixed point to the given posn, returning '∞ if the posn is not in the table.
(define/contract (lookup-in-table t p) (-> (listof dist-cell?) posn? (or/c '∞ natural-number/c)) (cond [(empty? t) '∞] [else (cond [(equal? p (dist-cell-p (first t))) (dist-cell-n (first t))] [else (lookup-in-table (rest t) p)])]))
The build-bfs-table accepts a world and a cell (indicating the fixed point) and returns a distance map encoding the distance to that cell. For example, here is the distance map for the distance to the boundary.
(test/set (build-bfs-table (empty-world 3) 'boundary) (list (make-dist-cell 'boundary 0) (make-dist-cell (make-posn 1 0) 1) (make-dist-cell (make-posn 2 0) 1) (make-dist-cell (make-posn 0 1) 1) (make-dist-cell (make-posn 1 1) 2) (make-dist-cell (make-posn 2 1) 1) (make-dist-cell (make-posn 1 2) 1) (make-dist-cell (make-posn 2 2) 1)))
The boundary is zero steps away; each of the cells that are on the boundary are one step away and the center is two steps away.
The core of the breadth-first search is this function, bst. It accepts a queue of the pending nodes to visit and a dist-table that records the same information as a distance-map, but in an immutable hash-table. The dist-map is an accumulator, recording the distances to all of the nodes that have already been visited in the graph, and is used here to speed up the computation. The queue is represented as a list of vectors of length two. Each element in the queue contains a posn, or the symbol 'boundary and that posn’s distance.
(define/contract (bfs queue dist-table) (-> (listof (vector/c (or/c 'boundary posn?) natural-number/c)) hash? hash?) #:freevar neighbors/w (-> (or/c 'boundary posn?) (listof (or/c 'boundary posn?))) (cond [(empty? queue) dist-table] [else (let* ([p (vector-ref (first queue) 0)] [dist (vector-ref (first queue) 1)]) (cond [(hash-ref dist-table p #f) (bfs (rest queue) dist-table)] [else (bfs (append (rest queue) (map (λ (p) (vector p (+ dist 1))) (neighbors/w p))) (hash-set dist-table p dist))]))]))
If the queue is empty, then the accumulator contains bindings for all of the (reachable) nodes in the graph, so we just return it. If it isn’t empty, then we extract the first element from the queue and name its consituents p and dist. Next we check to see if the node at the head of the queue is in dist-table. If it is, we just move on to the next element in the queue. If that node is not in the dist-table, then we add all of the neighbors to the queue, in the append expression, and update the dist-table with the distance to this node. Because we always add the new children to the end of the queue and always look at the front of the queue, we are guaranteed that the first time we see a node, it will be with the shortest distance.
The build-bfs-table function packages up bfs function. It accepts a world and an initial position and returns a distance-table.
(define/contract (build-bfs-table world init-point) (-> world? (or/c 'boundary posn?) (listof dist-cell?)) (define neighbors/w (neighbors world)) <bfs> (hash-map (bfs (list (vector init-point 0)) (make-immutable-hash '())) make-dist-cell))
As you can see, the first thing it does is bind the free variable in bfs to the result of calling the neighbors function (defined in the chunk <neighbors>) and then it has the <bfs> chunk. In the body it calls the bfs function and then transforms the result, using hash-map, into a list of cells.