AStar3D
An implementation of A* for finding the shortest path between two vertices on a connected graph in 3D space.
AStar3D.swift:20class AStar3DA* (A star) is a computer algorithm used in pathfinding and graph traversal, the process of plotting short paths among vertices (points), passing through a given set of edges (segments). It enjoys widespread use due to its performance and accuracy. Godot’s A* implementation uses points in 3D space and Euclidean distances by default.
You must add points manually with addPoint(id:position:weightScale:) and create segments manually with connectPoints(id:toId:bidirectional:). Once done, you can test if there is a path between two points with the arePointsConnected(id:toId:bidirectional:) function, get a path containing indices by getIdPath(fromId:toId:), or one containing actual coordinates with getPointPath(fromId:toId:).
It is also possible to use non-Euclidean distances. To do so, create a class that extends AStar3D and override methods _computeCost(fromId:toId:) and _estimateCost(fromId:toId:). Both take two indices and return a length, as is shown in the following example.
_estimateCost(fromId:toId:) should return a lower bound of the distance, i.e. _estimate_cost(u, v) <= _compute_cost(u, v). This serves as a hint to the algorithm because the custom _computeCost(fromId:toId:) might be computation-heavy. If this is not the case, make _estimateCost(fromId:toId:) return the same value as _computeCost(fromId:toId:) to provide the algorithm with the most accurate information.
If the default _estimateCost(fromId:toId:) and _computeCost(fromId:toId:) methods are used, or if the supplied _estimateCost(fromId:toId:) method returns a lower bound of the cost, then the paths returned by A* will be the lowest-cost paths. Here, the cost of a path equals the sum of the _computeCost(fromId:toId:) results of all segments in the path multiplied by the weight_scales of the endpoints of the respective segments. If the default methods are used and the weight_scales of all points are set to 1.0, then this equals the sum of Euclidean distances of all segments in the path.
Superclasses
class RefCountedBase class for reference-counted objects.
Citizens in SwiftGodot
Conformances
protocol CustomStringConvertibleA type with a customized textual representation.
protocol EquatableA type that can be compared for value equality.
protocol HashableA type that can be hashed into a
Hasherto produce an integer hash value.protocol Identifiable<ID>A class of types whose instances hold the value of an entity with stable identity.
protocol VariantRepresentableTypes that conform to VariantRepresentable can be stored directly in
Variantwith no conversion. These include all of the Variant types from Godot (for exampleGString,Rect,Plane), Godot objects (those that subclass SwiftGodot.Object) as well as the built-in Swift types UInt8, Int64 and Double.protocol VariantStorableTypes that conform to VariantStorable can be stored in a Variant and can be extracted back out of a Variant.
Type members
Instance members
func addPoint(id: Int, position: Vector3, weightScale: Double) Adds a new point at the given position with the given identifier. The
idmust be 0 or larger, and theweightScalemust be 0.0 or greater.func arePointsConnected(id: Int, toId: Int, bidirectional: Bool) -> Bool Returns whether the two given points are directly connected by a segment. If
bidirectionalisfalse, returns whether movement fromidtotoIdis possible through this segment.func clear() Clears all the points and segments.
func connectPoints(id: Int, toId: Int, bidirectional: Bool) Creates a segment between the given points. If
bidirectionalisfalse, only movement fromidtotoIdis allowed, not the reverse direction.func disconnectPoints(id: Int, toId: Int, bidirectional: Bool) Deletes the segment between the given points. If
bidirectionalisfalse, only movement fromidtotoIdis prevented, and a unidirectional segment possibly remains.func getAvailablePointId() -> Int Returns the next available point ID with no point associated to it.
func getClosestPoint(toPosition: Vector3, includeDisabled: Bool) -> Int Returns the ID of the closest point to
toPosition, optionally taking disabled points into account. Returns-1if there are no points in the points pool.func getClosestPositionInSegment(toPosition: Vector3) -> Vector3 Returns the closest position to
toPositionthat resides inside a segment between two connected points.func getIdPath(fromId: Int, toId: Int) -> PackedInt64Array Returns an array with the IDs of the points that form the path found by AStar3D between the given points. The array is ordered from the starting point to the ending point of the path.
func getPointCapacity() -> Int Returns the capacity of the structure backing the points, useful in conjunction with
reserveSpace(numNodes:).func getPointConnections(id: Int) -> PackedInt64Array Returns an array with the IDs of the points that form the connection with the given point.
func getPointCount() -> Int Returns the number of points currently in the points pool.
func getPointIds() -> PackedInt64Array Returns an array of all point IDs.
func getPointPath(fromId: Int, toId: Int) -> PackedVector3Array Returns an array with the points that are in the path found by AStar3D between the given points. The array is ordered from the starting point to the ending point of the path.
func getPointPosition(id: Int) -> Vector3 Returns the position of the point associated with the given
id.func getPointWeightScale(id: Int) -> Double Returns the weight scale of the point associated with the given
id.func hasPoint(id: Int) -> Bool Returns whether a point associated with the given
idexists.func isPointDisabled(id: Int) -> Bool Returns whether a point is disabled or not for pathfinding. By default, all points are enabled.
func removePoint(id: Int) Removes the point associated with the given
idfrom the points pool.func reserveSpace(numNodes: Int) Reserves space internally for
numNodespoints. Useful if you’re adding a known large number of points at once, such as points on a grid. New capacity must be greater or equals to old capacity.func setPointDisabled(id: Int, disabled: Bool) Disables or enables the specified point for pathfinding. Useful for making a temporary obstacle.
func setPointPosition(id: Int, position: Vector3) Sets the
positionfor the point with the givenid.func setPointWeightScale(id: Int, weightScale: Double) Sets the
weightScalefor the point with the givenid. TheweightScaleis multiplied by the result of_computeCost(fromId:toId:)when determining the overall cost of traveling across a segment from a neighboring point to this point.
Show implementation details (2)
Hide implementation details
func _computeCost(fromId: Int, toId: Int) -> Double Called when computing the cost between two connected points.
func _estimateCost(fromId: Int, toId: Int) -> Double Called when estimating the cost between a point and the path’s ending point.