Costs of Your Own

A search adds up what its moves cost and steers by an estimate of what is left. By default a graph measures both as distances between points, and a grid with its heuristics. A subclass measures them its own way with methods, as a script overrides Godot's _compute_cost and _estimate_cost. Make an instance of the subclass with make-instance, which takes the arguments of make-graph or make-grid as initargs.

Graphs

Generic function	Returns	By default
(compute-cost graph from to)	the cost of the move from the point from to to, ids of connected points	the distance between them
(estimate-cost graph from end)	an estimate of the cost from the point from to end, the end of the search	the distance between them
(filter-neighbor graph from neighbor)	true to refuse the move from from to its neighbour, as if they were not connected	false

(defclass toll-graph (astar:graph)
  ((tolls :initform (make-hash-table) :reader graph-tolls))
  (:documentation "A graph some of whose points cost a toll to enter."))

(defmethod astar:compute-cost ((graph toll-graph) from to)
  (+ (call-next-method) (gethash to (graph-tolls graph) 0)))

In a square of points 1 to 4, 10 apart, the path from 1 to 3 goes by 2, #(1 2 3), until point 2 costs a toll of 5, when it goes by 4, #(1 4 3). call-next-method gives the distance. A search multiplies each cost by the weight scale of the point it moves to.

A search asks filter-neighbor only while the graph's graph-neighbor-filter-enabled is true, as Godot's neighbor_filter_enabled:

(defclass closed-roads (astar:graph)
  ((closed :initform '() :accessor closed-moves))
  (:documentation "A graph whose closed moves, conses of the ids from and to, are refused."))

(defmethod astar:filter-neighbor ((graph closed-roads) from neighbor)
  (member (cons from neighbor) (closed-moves graph) :test #'equal))

(make-instance 'closed-roads :neighbor-filter-enabled t)

In the same square, closing the move from 1 to 2 sends the path from 1 to 3 by 4, while the path from 3 to 1 still goes by 2.

Grids

Generic function	Returns	By default
(compute-cell-cost grid from-x from-y to-x to-y)	the cost of the move from one cell to the other, a neighbour, or when the grid jumps, a cell further along a line	grid-default-compute-heuristic's
(estimate-cell-cost grid from-x from-y end-x end-y)	an estimate of the cost from a cell to the end of the search	grid-default-estimate-heuristic's

;; A grid whose row 1 is a road, along which moves cost a tenth.
(defclass road-grid (astar:grid) ())

(defmethod astar:compute-cell-cost ((grid road-grid) from-x from-y to-x to-y)
  (let ((cost (call-next-method)))
    (if (= from-y to-y 1) (/ cost 10) cost)))

;; Never estimate more than a path can cost, or the path found may not be
;; the cheapest.
(defmethod astar:estimate-cell-cost ((grid road-grid) from-x from-y end-x end-y)
  (/ (call-next-method) 10))

(astar:cell-path (make-instance 'road-grid :region '(0 0 7 3) :diagonal-mode :never)
                 0 0 6 0)
;; => #2A((0 0) (0 1) (1 1) (2 1) (3 1) (4 1) (5 1) (6 1) (6 0))

A search multiplies each cost by the weight scale of the cell it moves to, unless the grid jumps.

What a method returns

• A cost is a real of 0 or more: a negative one would make a search miss the cheapest path, so a search signals an astar-error for one, or for anything else that is not a real. An estimate is any real.
• A search takes costs and estimates as single floats, as Godot's, and adds them up in Godot's order. A method that returns a single float or an integer allocates nothing; a double float is boxed as it returns.
• The cheapest path is found while no estimate exceeds what the rest of a path really costs; a higher estimate finds a path sooner, though not always the cheapest. An estimate of 0 searches as Dijkstra's algorithm does.
• A search calls the methods many times, from the thread that searches, and never while another search of the same graph or grid runs.