Graphs

A graph, as Godot's AStar2D, holds points in the plane and the connections between them. A path moves along connections, and costs what its moves cost: by default, each move's length times the weight scale of the point it moves to.

Points

(defvar *roads* (astar:make-graph))

(list (astar:add-point *roads* (astar:next-point-id *roads*) 0 0)
      (astar:add-point *roads* (astar:next-point-id *roads*) 4 0)
      (astar:add-point *roads* (astar:next-point-id *roads*) 4 3)
      (astar:add-point *roads* (astar:next-point-id *roads*) 0 3 :weight-scale 2))
;; => (0 1 2 3)

make-graph makes an empty graph.
add-point adds a point with an id, an integer from 0 of your choosing, at X and Y, any reals, and returns the id. :weight-scale, a real of 0 or more, 1 by default, multiplies the cost of every move to the point: here, entering point 3 costs twice its distance. Adding a point the graph has moves it and sets its weight scale, and keeps its connections.
next-point-id returns an id no point has, as Godot's get_available_point_id: the one it returned before, or that of the point removed since, if it is still free, or else the first free id above it.
remove-point removes a point and every connection to and from it.

point-position returns a point'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; setf takes any sequence of two reals. point-weight-scale reads and sets the weight scale; has-point-p, point-count and point-ids tell what the graph holds, the ids in Godot's order: as added, each removed point's place taken by the last. reserve-points makes room for many points at once, so that adding them grows no array, and point-capacity tells how many fit; clear-graph removes everything.

Connections

(astar:connect-points *roads* 0 1)
(astar:connect-points *roads* 1 2)
(astar:connect-points *roads* 0 3)
(astar:connect-points *roads* 3 2 :bidirectional nil)    ; from 3 to 2 only

(list (astar:points-connected-p *roads* 2 3)
      (astar:points-connected-p *roads* 2 3 :bidirectional nil)
      (astar:point-connections *roads* 0))
;; => (T NIL #(1 3))

connect-points connects both ways unless :bidirectional nil; connecting points that are connected adds the direction asked for. disconnect-points removes both directions, or with :bidirectional nil, only the one from the first point to the second. points-connected-p asks whether the points are connected in either direction, or with :bidirectional nil, whether a path may move from the first to the second. point-connections returns the ids a point connects to, in Godot's order: as connected, each disconnected point's place taken by the last.

Paths

(list (astar:id-path *roads* 0 2)
      (astar:point-path *roads* 0 2)
      (astar:id-path *roads* 2 3))
;; => (#(0 1 2) #2A((0.0 0.0) (4.0 0.0) (4.0 3.0)) #(2 1 0 3))

id-path returns the ids of the points on the cheapest path, the first point's first, and point-path their positions, a row of X and Y for each point. From 0 to 2, the way by 1 costs 7, and the way by 3 costs 3 times 2 and then 4. From 2 to 3, the one-way connection leaves only the long way round. A path from a point to itself is that point alone.

The search follows Godot's: it estimates the cost from each point to the end as the distance, and of equally cheap paths it finds the one Godot finds. Costs of Your Own measures both another way.

Disabled points and partial paths

(setf (astar:point-disabled *roads* 1) t)

(list (astar:id-path *roads* 0 2)
      (astar:id-path *roads* 2 0)
      (astar:id-path *roads* 2 0 :allow-partial-path t))
;; => (#(0 3 2) #() #(2))

A disabled point is a temporary obstacle: no path passes through it, starts at it or ends at it, not even a path from it to itself. Where there is no path, id-path and point-path return an empty array, unless :allow-partial-path asks for the path to the reachable point whose estimated cost to the end is lowest, the one nearer the start of those as low; it may be the first point alone, as here. A partial path to a disabled point searches every point it can reach first.

Nearest points

(list (astar:closest-point *roads* 3.5 0.5)
      (astar:closest-point *roads* 3.5 0.5 :include-disabled t)
      (astar:closest-position-in-segment *roads* 1 2))
;; => (2 1 #(0.0 2.0))

closest-point returns the id of the enabled point nearest a position, or with :include-disabled, of any point; of points as near, the lowest id. closest-position-in-segment returns the position nearest it on a connection between two enabled points, or NIL if there is none. Of connections as near, it takes the first in Godot's order of them: as they were made, each one connected or disconnected again moved last, and each removed one's place taken by the last.

cl-astar

Reference

API Reference