Coming from Godot

cl-astar is Godot 4.7's AStar2D and AStarGrid2D, in Lisp. This page maps Godot's names to cl-astar's, and lists where the two differ.

Names

Godot	cl-astar
AStar2D.new()	make-graph
get_available_point_id	next-point-id
add_point, remove_point, has_point	add-point, remove-point, has-point-p
get_point_position, set_point_position	point-position, (setf point-position)
get_point_weight_scale, set_point_weight_scale	point-weight-scale, (setf point-weight-scale)
is_point_disabled, set_point_disabled	point-disabled, (setf point-disabled)
connect_points, disconnect_points, are_points_connected	connect-points, disconnect-points, points-connected-p
get_point_connections, get_point_ids, get_point_count	point-connections, point-ids, point-count
reserve_space, get_point_capacity, clear	reserve-points, point-capacity, clear-graph
get_closest_point, get_closest_position_in_segment	closest-point, closest-position-in-segment
get_id_path, get_point_path	id-path, point-path
neighbor_filter_enabled, _filter_neighbor	graph-neighbor-filter-enabled, filter-neighbor
_compute_cost, _estimate_cost	compute-cost, estimate-cost
AStarGrid2D.new(), then update()	make-grid
region, offset, cell_size, cell_shape	grid-region, grid-offset, grid-cell-size, grid-cell-shape
diagonal_mode, jumping_enabled	grid-diagonal-mode, grid-jumping-enabled
default_compute_heuristic, default_estimate_heuristic	grid-default-compute-heuristic, grid-default-estimate-heuristic
update, is_dirty, clear	update-grid, grid-dirty-p, clear-grid
is_in_bounds, is_in_boundsv	cell-in-bounds-p
is_point_solid, set_point_solid, fill_solid_region	cell-solid, (setf cell-solid), fill-solid-region
get_point_weight_scale, set_point_weight_scale, fill_weight_scale_region	cell-weight-scale, (setf cell-weight-scale), fill-weight-scale-region
get_point_position, get_point_data_in_region	cell-position, cell-data-in-region
get_id_path, get_point_path	cell-path, cell-point-path
_compute_cost, _estimate_cost	compute-cell-cost, estimate-cell-cost

Godot's enum values are keywords: DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE is :at-least-one-walkable, HEURISTIC_OCTILE is :octile, CELL_SHAPE_ISOMETRIC_DOWN is :isometric-down. A grid's cell is two arguments, X and Y, where Godot takes a Vector2i; a Rect2i is a list (X Y WIDTH HEIGHT); a Vector2 given is any sequence of two reals, such as (16 16), and one returned a specialised array of two single floats. A path is a specialised array: a vector of ids, or a row of X and Y for each cell or position.

The same paths

Of several equally cheap paths, cl-astar finds the one Godot finds. It keeps positions, costs and scores in single floats, as Godot does unless built for double precision, adds costs up in Godot's order, keeps Godot's order of points, neighbours and connections, and its open list breaks ties as Godot's binary heap does.

tests/godot-answers.txt in the repository holds Godot 4.7.2's answers to 2772 queries about random graphs and grids, which tests/godot-test.lisp makes from a fixed seed: point ids and connections, paths and partial paths with disabled points, nearest points and positions, and grid paths with every diagonal mode, heuristic and jumping. The suite checks that cl-astar gives every one of them. To ask another Godot:

(asdf:load-system "cl-astar/test")
(cl-astar/test:write-godot-cases "cases.txt")

godot --headless --script tools/godot-answers.gd -- cases.txt tests/godot-answers.txt

Where cl-astar differs

• Errors. Where Godot logs an error and returns an empty or default value, as for a point a graph lacks or a cell outside a grid, cl-astar signals an astar-error, and a type-error for an argument of the wrong type. See Errors.
• No segment. On a graph that connects no two enabled points, closest-position-in-segment returns NIL, where Godot returns the origin.
• Far away. Godot's get_closest_point and get_closest_position_in_segment leave out what is more than 10^10 from the position they are given; cl-astar leaves nothing out.
• A new grid. make-grid makes the grid's cells, so it needs no update-grid before its first path. Changing its region, offset, cell size or cell shape later leaves it dirty, as in Godot.
• Tiny changes. Godot ignores an offset or cell size that is approximately the one it has; cl-astar takes any other value, and leaves the grid dirty.
• Costs of your own. A method may return any real; a negative cost, which Godot takes, signals an astar-error.
• Not here. AStar3D, and AStarGrid2D's size, which Godot deprecates for region.

As in Godot 4.7, no path starts at a disabled point or a solid cell, not even a path from it to itself.