;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                           Game Library                           ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; Interface

;;; Returns the next exit along the shortes path from one place
;;; to another place satisfying a predicate
(defgeneric (find-path from target))

;;; Use this to show a message to all players except for one.  Note that
;;; if the player argument is not a player, all will be messaged.
;; (define (message-to-all msg player) ...)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; Implementation

;;; Use this to show a message to all players except for one.
(define (message-to-all msg player)
  (for-each (lambda (p) (unless (eq? p player) (tell p (echos msg))))
            *players*))

;;; Returns the next step along the shortest path to the target place
(defmethod (find-path (start <place>) (target <place>))
  (find-path start (lambda (x) (eq? x target))))

;;; Returns the next step along the shortest path to a place that
;;; satisfies target?.
(defmethod (find-path (start <place>) (target? <function>))
  (let ((history (make-set start))
        (queue   (make <queue>)))
    ;; expand adds the additional search paths to the queue, excluding
    ;; any places that have already been seen. It also adds any place
    ;; to the history see it won't be searched again.
    (define (expand first-step current-place)
      (for-each (lambda (x)
                  (unless (element? x history)
                    (enqueue (cons first-step x) queue)
                    (insert! x history)))
                (map destination (exits current-place)))
      (bfs))
    ;; bfs checks whether the current pair coming out of the queue
    ;; contains the place we are looking for. If the queue is empty
    ;; it means that the search was exhausted and no path exists,
    ;; so we return #f. If the pair contains a satisfactory target
    ;; we return the next step, otherwise we expand the search
    ;; and check the next place.
    (define (bfs)
      (if (empty-queue? queue)
        #f
        (let ((pair (dequeue queue)))
          (if (target? (tail pair))
            (head pair)
            (expand (head pair) (tail pair))))))
    ;; Put the exits of the start in the queue to prime it.
    (for-each (lambda (x)
                (enqueue (cons (destination x) (destination x))
                          queue))
              (exits start))
    ;; If the current location satisfies as the target, return it.
    (if (target? start)
      start
      (bfs))))