diff --git a/distances.lisp b/distances.lisp index 7809e00..1347ccc 100644 --- a/distances.lisp +++ b/distances.lisp @@ -1,51 +1,34 @@ -(in-package #:mazes) +;;;; distance.lisp -(defclass distances () - ((root :initarg :root :accessor root-cell) - (cells :initarg :cells :initform (make-hash-table) :accessor distance-cells) - (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.")) +(in-package :mazes) -(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)) +(defclass distance () + ((root :initarg :root :accessor root) + (cells :initform (make-hash-table) :accessor cells)) + (:documentation "Keeps track of the distance of each cell from the root")) -(defgeneric set-distance (distances &key) - (:documentation "Set the distance of the given cell from the root cell")) +(defmethod initialize-instance :after ((d distance) &key) + (setf (gethash (root d) (cells d)) 0)) -(defgeneric calculate-distance (distances) - (:documentation "Set the distance of the given cell from the root cell")) +(defgeneric distance-to (distance &key) + (:documentation "return the distance from root to :CELL")) +(defgeneric set-distance (distance &key) + (:documentation "set the :DISTANCE from root to :CELL")) -(defmethod set-distance ((d distances) &key cell distance) - (let ((cells (distance-cells d))) - (setf (gethash cell cells) distance))) +(defgeneric cells-map (distance) + (:documentation "return the hash map cells")) +(defmethod distance-to ((d distance) &key cell) + (when (gethash cell (cells d)) + (gethash cell (cells d)) + nil)) -(defgeneric distance-all-cells (distances) - (:documentation "Return a list of cells with their respective distance from root")) +(defmethod set-distance ((d distance) &key cell distance) + (setf (gethash cell (cells d)) distance)) -#| -(defmethod distance-all-cells ((d distances)) - (get-hash-keys (distance-cells d))) -|# +(defmethod cells-map ((d distance)) + (cells d)) - -(defmethod calculate-distance ((d distances)) - ; (declare (optimize (debug 3))) - (let* ((frontier (list (root-cell d))) - (new-frontier ())) - (loop while (not (null frontier)) - do - (setf new-frontier ()) - (dolist (cell frontier) - (dolist (linked (links cell)) - (when (not (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)) +(defun make-distance (root) + (make-instance 'distance :root root)) diff --git a/mazes.asd b/mazes.asd index 1c398f1..efd9403 100644 --- a/mazes.asd +++ b/mazes.asd @@ -2,8 +2,8 @@ (asdf:defsystem #:mazes :description "Describe mazes here" - :author "Your Name " - :license "Specify license here" + :author "Curt Lewis " + :license "TBD" :version "0.0.1" :serial t :components ((:file "package") diff --git a/mazes.lisp b/mazes.lisp index 9e71b6c..a464c74 100644 --- a/mazes.lisp +++ b/mazes.lisp @@ -34,7 +34,8 @@ (defgeneric neighbors (cell) (:documentation "List of cells that adjoin this cell.")) -(defgeneric distance-to (cell) + +(defgeneric distances (cell) (:documentation "Caluclate distance of each cell from root cell")) (defmethod link ((current-cell cell) &key neighbor-cell (bidi t)) @@ -68,44 +69,23 @@ (cell-neighbors current-cell)) -#| -(defmethod distances ((root cell)) - ((let ((distances (make-distance root)) - (frontier '(root)) - (new-frontier ())) - ; DO..UNTIL frontier is empty - (do () ((null frontier) ()) - (mapcar #'(lambda (x) - (setf x (* x x)) - (+ x 2)) '(1 2 3)))))) -|# -#| -(defmethod distance-to ((ROOT CELL)) - (LET ((DIST (MAKE-DISTANCE ROOT)) - (FRONTIER `(,ROOT)) - (NEW-FRONTIER ())) - (DO () ((NULL FRONTIER) ()) - (MAPCAR #'(LAMBDA (CELL) - (MAPCAR #'(LAMBDA (LINKED) - (FORMAT T "MAPCAR2: ~A~%" LINKED) - (SET-DISTANCE DIST :DISTANCE ())) - (LINKS CELL)) - (FORMAT T "~A" CELL) - (SETF FRONTIER ())) - FRONTIER)) - DIST)) -|# -(defmethod distance-to ((root cell)) - (let* ((dist (make-distance root)) - (frontier '(root))) - (do () ((null frontier) ()) - (mapcar #'(lambda (cell) - (mapcar #'(lambda (linked) - (format t "2nd mapcar: ~a~%" linked)) - (links cell)) - (format t "~a~%" cell)) - frontier)) - dist)) +(defmethod distances ((root-cell cell)) + (let ((dist (make-distance root-cell)) + (frontier (list root-cell)) + (new-frontier ())) + (loop while (not (null frontier)) + do + (progn + (setf new-frontier ()) + (dolist (c frontier) + (dolist (linked (links c)) + (when (not (gethash linked (cells dist))) + (set-distance dist :cell linked :distance (1+ (gethash c (cells dist)))) + (setf new-frontier (append (list linked) new-frontier))))) + (setf frontier (copy-tree new-frontier)))) + (cells dist))) + + ;; ;; cell constructor ;; diff --git a/statements.lisp b/statements.lisp index 6d1ee4b..3021e6e 100644 --- a/statements.lisp +++ b/statements.lisp @@ -7,11 +7,12 @@ (defvar c00 (get-cell g 0 0)) -(defvar d (make-distance c00 g)) +(defvar dists (distances c00)) +;(defvar d (make-distance c00 g)) -(defvar dcells (distance-cells d)) +;(defvar dcells (distance-cells d)) -(defvar dc (calculate-distance d)) +;(defvar dc (calculate-distance d)) (defun hash-keys (hash-table) (loop for key being the hash-keys of hash-table collect key))