;;; -*- Mode: Lisp; Syntax: Common-Lisp; -*- File: search/domains/route-finding

;;;; Find a Route Between Cities on a Map

(defstructure (route-finding-problem (:include problem
					       (initial-state 'A)
					       (goal 'B)))
  "The problem of finding a route from one city to another on a map.
  By default it is a random map.  A state in a route-finding problem is just 
  the name of the current city. Note that a more complicated version of this
  problem would augment the state with considerations of time, gas
  used, wear on car, tolls to pay, etc."
  (map (random-route-map)))

(defmethod successors ((problem route-finding-problem) city-name)
  "Return a list of (action . new-state) pairs.
  In this case, the action and the new state are both the name of the city."
  (let ((result nil))
   (for each pair in (city-neighbors (find-city city-name problem)) do
	(push (cons (first pair) (first pair)) result))
   result))

(defmethod edge-cost ((problem route-finding-problem) node action city)
  "The edge-cost is the road distance to the next city."
  (declare-ignore action)
  (road-distance (find-city (node-state node) problem) city))

(defmethod h-cost ((problem route-finding-problem) city-name)
  "The heuristic cost is the straight-line distance to the goal."
  (straight-distance (find-city city-name problem)
		     (find-city (problem-goal problem) problem)))

;;;; The City and Map data structures

(defstruct (city (:type list))
  "A city's loc (location) is an (x y) pair.  The neighbors slot holds
  a list of (city-name . distance-along-road) pairs.  Be careful to 
  distinguish between a city name and a city structure."
  name loc neighbors)

(defun road-distance (city1 city-name2)
  "The distance along the road between two cities.  The first is a city 
  structure, the second just the name of the intended destination."
  (if (eq (city-name city1) city-name2)
      0
    (cdr (assoc city-name2 (city-neighbors city1)))))

(defun straight-distance (city1 city2)
  "Distance between two cities on a straight line (as the crow flies)."
  ;; We round this to the nearest integer, just to make things easier to read
  (round (xy-distance (city-loc city1) (city-loc city2))))

(defun find-city (name map)
  "Look up the city on the map, and return its information."
  (if (problem-p map) (setf map (route-finding-problem-map map)))
  (assoc name map))

(defun random-route-map (&key (n-cities 10) (width 100) (height 100)
			      (min-roads 2)
			      (max-roads (min n-cities (+ min-roads 3))))
  "Return a random map with n-cities in it, and some roads between them.
  Each city is connected to between MIN-ROADS and MAX-ROADS other cities.
  The default is from 2 to 5.  The road between any two cities has a length 
  of 1 to 1.5 times the straight-line distance between them."
  ;; First build the cities
  (let ((map nil))
    (for i = 1 to n-cities do
	 (push (make-city :name (number->name i) :neighbors nil
			  :loc (@ (random width) (random height)))
	       map))
    ;; Now lay down the roads
    (for each city in map do
	 (let* ((n-roads (max 0 (- (random-integer min-roads max-roads)
				   (length (city-neighbors city)))))
		(candidates
		 (sort (copy-list map) #'<
		       :key #'(lambda (city2)
				(straight-distance city city2)))))
	   (while (and candidates (> n-roads 0)) do
		(let ((city2 (pop candidates)))
		  (when (and city2 (not (eq city city2))
			     (not (assoc (city-name city2)
					 (city-neighbors city))))
			(decf n-roads)
			(build-road city city2))))))
    map))

(defun build-road (city1 city2)
  "Construct a road between two cities."
  (let* ((distance (straight-distance city1 city2))
	 (road-distance (round (* (+ 1.0 (random 0.5)) distance))))
    (push (cons (city-name city1) road-distance) (city-neighbors city2))
    (push (cons (city-name city2) road-distance) (city-neighbors city1))))

(defun number->name (i)
  "Turn an integer into a symbol.  1-26 go to A-Z; beyond that use Ci"
  (if (<= 1 i 26)
      (aref '#(0 a b c d e f g h i j k l m n o p q r s t u v w x y z) i)
    (intern (format nil "C~D" i))))

;;;; The Romanian Map

(defparameter *romania-map*
  '(
    (Arad       ( 91 492) ((Zerind . 75) (Sibiu . 140) (Timisoara . 118)))
    (Bucharest	(400 327) ((Fagaras . 211) (Pitesti . 101) (Giurgiu . 90)
			   (Urziceni . 85)))
    (Craiova	(253 288) ((Dobreta . 120) (Rimnicu . 146) (Pitesti . 138)))
    (Dobreta	(165 299) ((Mehadia . 75) (Craiova . 120)))
    (Eforie	(562 293) ((Hirsova . 86)))
    (Fagaras	(305 449) ((Sibiu . 99) (Bucharest . 211)))
    (Giurgiu	(375 270) ((Bucharest . 90)))
    (Hirsova	(534 350) ((Urziceni . 98) (Eforie . 86)))
    (Iasi	(473 506) ((Neamt . 87) (Vaslui . 92)))
    (Lugoj	(165 379) ((Timisoara . 111) (Mehadia . 70)))
    (Mehadia	(168 339) ((Lugoj . 70) (Dobreta . 75)))
    (Neamt	(406 537) ((Iasi . 87)))
    (Oradea	(131 571) ((Zerind . 71) (Sibiu . 151)))
    (Pitesti	(320 368) ((Rimnicu . 97) (Craiova . 138) (Bucharest . 101)))
    (Rimnicu	(233 410) ((Sibiu . 80) (Pitesti . 97) (Craiova . 146)))
    (Sibiu	(207 457) ((Arad . 140) (Oradea . 151) (Fagaras . 99)
			   (Rimnicu . 80)))
    (Timisoara	( 94 410) ((Arad . 118) (Lugoj . 111)))
    (Urziceni	(456 350) ((Bucharest . 85) (Hirsova . 98) (Vaslui . 142)))
    (Vaslui	(509 444) ((Iasi . 92) (Urziceni . 142)))
    (Zerind	(108 531) ((Arad . 75) (Oradea . 71)))
    )
  "A representation of the map in Figure 4.2 [p 95].
  But note that the straight-line distances to Bucharest are NOT the same.")

(defstructure (romanian-problem (:include route-finding-problem
					  (initial-state 'Arad)
					  (goal 'Bucharest)
					  (map *romania-map*)))
  "A route-finding problem on the Romania map, with random start and goal.")