diff --git a/distances.lisp b/distances.lisp index 3842db3..9df73ee 100644 --- a/distances.lisp +++ b/distances.lisp @@ -3,16 +3,18 @@ (defclass distances () ((root :initarg :root :accessor root-cell) (cells :initarg :cells :initform (make-hash-table) :accessor distance-cells) - (grid :initarg :grid :accessor distance-grid)) + (grid :initarg :grid :accessor distance-grid) + (matrix :initform () :accessor distance-matrix)) (:documentation "Keeps track of the distance of each cell from the given root cell.")) (defmethod initialize-instance :after ((d distances) &key) + (setf (distance-matrix d) (grid-matrix (distance-grid d))) (setf (gethash (root-cell d) (distance-cells d)) 0)) (defgeneric set-distance (distances &key) (:documentation "Set the distance of the given cell from the root cell")) -(defgeneric calc-distance (distances) +(defgeneric calculate-distance (distances) (:documentation "Set the distance of the given cell from the root cell")) @@ -30,12 +32,20 @@ |# -(defmethod calc-distance ((d distances)) - (let* ((matrix (grid-matrix (distance-grid d))) - (num-rows (grid-rows (distance-grid d))) - (num-cols (grid-cols (distance-grid d))))) - (format t "calculate-distances...")) - +(defmethod calculate-distance ((d distances)) + (declare (optimize (debug 3))) + (let* ((frontier (list (root-cell d))) + (new-frontier ())) + (loop while frontier + do (dolist (cell frontier) + (setf new-frontier ()) + (dolist (linked (links cell)) + (when (gethash linked (distance-cells d)) + (set-distance d :cell linked :distance (+ 1 (gethash cell (distance-cells d)))) + (setf new-frontier (append `(,linked) new-frontier)))) + + (setf frontier (copy-tree new-frontier))))) + (distance-cells d)) (defun make-distance (root grid) (make-instance 'distances :root root :grid grid))