This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Grids

A grid, as Godot's AStarGrid2D, is a rectangle of cells, each connected to its neighbours: no points to add and no connections to make. A cell is known by its column and row, X and Y.

Making a grid

(defvar *map* (astar:make-grid :region '(-2 -2 6 5) :cell-size '(32 32) :offset '(16 16)))

(list (astar:cell-in-bounds-p *map* -2 -2)
      (astar:cell-in-bounds-p *map* 4 0)
      (astar:cell-position *map* -2 -2)
      (astar:cell-position *map* 0 0))
;; => (T NIL #(-48.0 -48.0) #(16.0 16.0))

make-grid takes:

• :region, a list (X Y WIDTH HEIGHT): the first column and row, which may be below 0, and the number of columns and rows. (0 0 0 0) by default.
• :cell-size and :offset, sequences of two reals, (1 1) and (0 0) by default, and :cell-shape, which place the cells for cell-position and cell-point-path: a square cell at its corner, the offset plus its column and row times the cell size; a diamond at its middle (see Diamonds).
• :diagonal-mode, :default-compute-heuristic, :default-estimate-heuristic and :jumping-enabled, which shape paths (below).

The grid's cells are made at once, none solid, each of weight scale 1. Each setting has a reader of the grid's name for it, such as grid-region, and a setf writer; grid-offset and grid-cell-size return single floats in a specialised array. cell-in-bounds-p tells whether a cell is in the region. cell-position returns a cell's position as two single floats in a specialised array, as cl-gmath's vec2, and writes into an array you give it, allocating nothing.

Solid cells and weight scales

(setf (astar:cell-solid *map* 0 0) t)
(astar:fill-weight-scale-region *map* '(-2 1 6 2) 3)

(list (astar:cell-path *map* -1 0 1 0)
      (astar:cell-weight-scale *map* 0 2))
;; => (#2A((-1 0) (0 -1) (1 0)) 3.0)

A solid cell is an obstacle: no path passes through it, starts at it or ends at it. (setf cell-solid) makes one cell solid or free, and fill-solid-region every cell of a region, true by default or free with nil. A cell's weight scale, a real of 0 or more, multiplies the cost of every move to it; (setf cell-weight-scale) sets one, fill-weight-scale-region a region's. A region given to either may reach beyond the grid's: the cells they share are filled.

Paths

cell-path returns the cells of the cheapest path between two cells, as a specialised array of a row of X and Y for each, the first cell's first; cell-point-path returns their positions. A path from a cell to itself is that cell alone. Where there is no path, both return an array of no rows, unless :allow-partial-path asks for the path to the reachable cell whose estimated cost to the end is lowest, the one nearer the start of those as low. A partial path to a solid cell searches every cell it can reach first.

Diagonal moves

(defvar *corner* (astar:make-grid :region '(0 0 3 3)))
(astar:fill-solid-region *corner* '(1 0 1 2))     ; a wall from the top

(loop for mode in '(:always :at-least-one-walkable :only-if-no-obstacles :never)
      collect (progn (setf (astar:grid-diagonal-mode *corner*) mode)
                     (list mode (astar:cell-path *corner* 0 0 2 0))))
;; => ((:ALWAYS #2A((0 0) (0 1) (1 2) (2 1) (2 0)))
;;     (:AT-LEAST-ONE-WALKABLE #2A((0 0) (0 1) (1 2) (2 1) (2 0)))
;;     (:ONLY-IF-NO-OBSTACLES #2A((0 0) (0 1) (0 2) (1 2) (2 2) (2 1) (2 0)))
;;     (:NEVER #2A((0 0) (0 1) (0 2) (1 2) (2 2) (2 1) (2 0))))

A diagonal move passes two cells, the ones beside it. The diagonal mode says when a path may make one:

Mode	A diagonal move
:always (the default)	always, between two solid cells too
:at-least-one-walkable	unless both cells beside it are solid
:only-if-no-obstacles	only if neither is solid
:never	never: paths keep to rows and columns

Heuristics

(loop for heuristic in '(:euclidean :manhattan :octile :chebyshev)
      collect (progn (setf (astar:grid-default-compute-heuristic *corner*) heuristic)
                     (list heuristic (astar:compute-cell-cost *corner* 0 0 2 1))))
;; => ((:EUCLIDEAN 2.236068) (:MANHATTAN 3.0) (:OCTILE 2.4142137) (:CHEBYSHEV 2.0))

A heuristic measures the cost between two cells DX columns and DY rows apart, as Godot's do:

Heuristic	Cost
:euclidean (the default)	the length of the line between them
:manhattan	DX + DY, for paths that never move diagonally
:octile	(√2 − 1) times the smaller of DX and DY, plus the larger
:chebyshev	the larger of DX and DY

:default-compute-heuristic measures each move, and :default-estimate-heuristic estimates the cost from a cell to the end. Give both the same heuristic, so that no estimate exceeds the real cost and the path found is the cheapest; a larger estimate finds a path sooner, though not always the cheapest. Costs of Your Own measures them another way.

Jumping

(defvar *field* (astar:make-grid :region '(0 0 20 10)))
(astar:fill-solid-region *field* '(10 0 1 8))

(list (array-dimension (astar:cell-path *field* 0 0 19 0) 0)
      (progn (setf (astar:grid-jumping-enabled *field*) t)
             (astar:cell-path *field* 0 0 19 0)))
;; => (20 #2A((0 0) (8 8) (10 8) (18 0) (19 0)))

With :jumping-enabled, a search jumps along lines of free cells, as jump point search does, instead of opening every cell: much faster across open ground. The path lists only the cells where it turns; the cells between two of them lie on a straight line, along a row, a column or a diagonal. Weight scales count for nothing while the grid jumps, as in Godot.

Diamonds

(defvar *diamonds* (astar:make-grid :region '(0 0 4 4) :cell-size '(64 32)
                                    :cell-shape :isometric-down))

(list (astar:cell-position *diamonds* 0 0)
      (astar:cell-position *diamonds* 1 0)
      (astar:cell-position *diamonds* 0 1))
;; => (#(32.0 16.0) #(64.0 32.0) #(0.0 32.0))

:cell-shape places the cells, as Godot's CellShape:

Shape	A cell X, Y is at
:square (the default)	the offset, plus X times the cell's width and Y times its height
:isometric-right	the offset and half a cell, plus X + Y half widths and Y − X half heights: the X axis goes up and to the right, the Y axis down and to the right
:isometric-down	the offset and half a cell, plus X − Y half widths and X + Y half heights: the X axis goes down and to the right, the Y axis down and to the left

The shape moves positions only: a cell's neighbours are the same.

Updating

(setf (astar:grid-region *corner*) '(0 0 4 3))

(list (astar:grid-dirty-p *corner*)
      (astar:cell-in-bounds-p *corner* 3 0)
      (handler-case (astar:cell-solid *corner* 1 0)
        (astar:astar-error (condition) (astar:astar-error-message condition))))
;; => (T T "Can't read whether a cell is solid: the grid's region, offset, cell size
;;         or cell shape changed since its cells were made.  Call UPDATE-GRID first,
;;         which makes them anew, none solid.")

(astar:update-grid *corner*)
(list (astar:grid-dirty-p *corner*) (astar:cell-solid *corner* 1 0))
;; => (NIL NIL)

A new region, offset, cell size or cell shape leaves the grid dirty, as grid-dirty-p tells, as Godot's does: its cells are as they were made until update-grid makes them anew, none solid and each of weight scale

1. Until then, only its settings and cell-in-bounds-p, which takes the new region, can be read; reading or changing a cell or finding a path signals an astar-error. Setting a value the grid has changes nothing, and the diagonal mode, the heuristics and jumping take effect at once. clear-grid gives the grid the empty region (0 0 0 0).

Reading many cells

(astar:cell-data-in-region *map* '(-1 -1 2 1))
;; => ((:X -1 :Y -1 :POSITION #(-16.0 -16.0) :SOLID NIL :WEIGHT-SCALE 1.0)
;;     (:X 0 :Y -1 :POSITION #(16.0 -16.0) :SOLID NIL :WEIGHT-SCALE 1.0))

cell-data-in-region returns a property list for each cell of a region the grid shares, row by row, as Godot's get_point_data_in_region returns dictionaries.