Class AStar

Implements an optimized AStar pathfinding algorithm. Optionally supports custom heuristics, and custom weights for each tile.

Inheritance

object

AStar

FastAStar

Inherited Members

object.GetType()

object.MemberwiseClone()

object.ToString()

object.Equals(object)

object.Equals(object, object)

object.ReferenceEquals(object, object)

object.GetHashCode()

Namespace: GoRogue.Pathing

Assembly: GoRogue.dll

Syntax

public class AStar

Remarks

Like most GoRogue algorithms, AStar takes as a construction parameter an IGridView representing the map. Specifically, it takes an IGridView<T>, where true indicates that a tile should be considered walkable, and false indicates that a tile should be considered impassable. For details on the map view system in general, see IGridView<T>. As well, there is an article explaining the map view system at the GoRogue documentation page here If truly shortest paths are not strictly necessary, you may want to consider FastAStar instead.

Constructors

View Source

AStar(IGridView<bool>, Distance)

Constructor. Uses a default heuristic corresponding to the distance calculation given, along with a safe/efficient tie-breaking/smoothing element which will produce guaranteed shortest paths.

Declaration

public AStar(IGridView<bool> walkabilityView, Distance distanceMeasurement)

Parameters

Type	Name	Description
IGridView<bool>	walkabilityView	Map view used to determine whether or not each location can be traversed -- true indicates a tile can be traversed, and false indicates it cannot.
Distance	distanceMeasurement	Distance calculation used to determine whether 4-way or 8-way connectivity is used, and to determine how to calculate the distance between points.

View Source

AStar(IGridView<bool>, Distance, IGridView<double>, double)

Constructor. Uses a default heuristic corresponding to the distance calculation given, along with a safe/efficient tie-breaking/smoothing element which will produce guaranteed shortest paths, provided minimumWeight is correct.

Declaration

public AStar(IGridView<bool> walkabilityView, Distance distanceMeasurement, IGridView<double> weights, double minimumWeight)

Parameters

Type	Name	Description
IGridView<bool>	walkabilityView	Map view used to determine whether or not each location can be traversed -- true indicates a tile can be traversed, and false indicates it cannot.
Distance	distanceMeasurement	Distance calculation used to determine whether 4-way or 8-way connectivity is used, and to determine how to calculate the distance between points.
IGridView<double>	weights	A map view indicating the weights of each location (see Weights.
double	minimumWeight	The minimum value that will be present in `weights`. It must be greater than 0.0 and must be less than or equal to the minimum value present in the weights view -- the algorithm may not produce truly shortest paths if this condition is not met. If this minimum changes after construction, it may be updated via the MinimumWeight property.

View Source

AStar(IGridView<bool>, Distance, Func<Point, Point, double>)

Constructor.

Declaration

public AStar(IGridView<bool> walkabilityView, Distance distanceMeasurement, Func<Point, Point, double> heuristic)

Parameters

Type	Name	Description
IGridView<bool>	walkabilityView	Map view used to determine whether or not each location can be traversed -- true indicates a tile can be traversed, and false indicates it cannot.
Distance	distanceMeasurement	Distance calculation used to determine whether 4-way or 8-way connectivity is used, and to determine how to calculate the distance between points.
Func<Point, Point, double>	heuristic	Function used to estimate the distance between two given points.

View Source

AStar(IGridView<bool>, Distance, Func<Point, Point, double>, IGridView<double>)

Constructor.

Declaration

public AStar(IGridView<bool> walkabilityView, Distance distanceMeasurement, Func<Point, Point, double> heuristic, IGridView<double> weights)

Parameters

Type	Name	Description
IGridView<bool>	walkabilityView	Map view used to determine whether or not each location can be traversed -- true indicates a tile can be traversed, and false indicates it cannot.
Distance	distanceMeasurement	Distance calculation used to determine whether 4-way or 8-way connectivity is used, and to determine how to calculate the distance between points.
Func<Point, Point, double>	heuristic	Function used to estimate the distance between two given points.
IGridView<double>	weights	A map view indicating the weights of each location (see Weights.

Fields

View Source

MinimumWeight

The minimum value that is allowed to occur in the Weights map view. This value is only used with the default heuristic for AStar and FastAStar, so if a custom heuristic is used, the value is also ignored. Must be greater than 0.0 and less than or equal to the minimum value in the Weights map view. Defaults to 1.0 in cases where the default heuristic is used.

Declaration

public double MinimumWeight

Field Value

Type	Description
double

Properties

View Source

DistanceMeasurement

The distance calculation being used to determine distance between points. Manhattan implies 4-way connectivity, while Chebyshev or Euclidean imply 8-way connectivity for the purpose of determining adjacent coordinates.

Declaration

public Distance DistanceMeasurement { get; set; }

Property Value

Type	Description
Distance

View Source

Heuristic

The heuristic used to estimate distance from nodes to the end point. If unspecified or specified as null, it defaults to using the distance calculation specified by DistanceMeasurement, with a safe/efficient tie-breaking multiplier added on.

Declaration

public Func<Point, Point, double> Heuristic { get; set; }

Property Value

Type	Description
Func<Point, Point, double>

View Source

MaxEuclideanMultiplier

Multiplier that is used in the tie-breaking/smoothing element of the default heuristic. This value is based on the maximum possible EuclideanDistanceMagnitude(Point, Point) between two points on the map. Typically you don't need this value unless you're creating a custom heuristic an introducing the same tie-breaking/smoothing element as the default heuristic.

Declaration

public double MaxEuclideanMultiplier { get; }

Property Value

Type	Description
double

View Source

WalkabilityView

The map view being used to determine whether or not each tile is walkable.

Declaration

public IGridView<bool> WalkabilityView { get; }

Property Value

Type	Description
IGridView<bool>

View Source

Weights

Weights given to each tile. The weight is multiplied by the cost of a tile, so a tile with weight 2 is twice as hard to enter as a tile with weight 1. If unspecified or specified as null, all tiles have weight 1.

Declaration

public IGridView<double>? Weights { get; }

Property Value

Type	Description
IGridView<double>

Methods

View Source

ShortestPath(Point, Point, bool)

Finds the shortest path between the two specified points.

Declaration

public Path? ShortestPath(Point start, Point end, bool assumeEndpointsWalkable = true)

Parameters

Type	Name	Description
Point	start	The starting point of the path.
Point	end	The ending point of the path.
bool	assumeEndpointsWalkable	Whether or not to assume the start and end points are walkable, regardless of what the WalkabilityView reports. Defaults to true.

Returns

Type	Description
Path	The shortest path between the two points, or null if no valid path exists.

Remarks

Returns null if there is no path between the specified points. Will still return an appropriate path object if the start point is equal to the end point.

View Source

ShortestPath(int, int, int, int, bool)

Finds the shortest path between the two specified points.

Declaration

public Path? ShortestPath(int startX, int startY, int endX, int endY, bool assumeEndpointsWalkable = true)

Parameters

Type	Name	Description
int	startX	The x-coordinate of the starting point of the path.
int	startY	The y-coordinate of the starting point of the path.
int	endX	The x-coordinate of the ending point of the path.
int	endY	The y-coordinate of the ending point of the path.
bool	assumeEndpointsWalkable	Whether or not to assume the start and end points are walkable, regardless of what the WalkabilityView reports. Defaults to true.

Returns

Type	Description
Path	The shortest path between the two points, or null if no valid path exists.

Remarks

Returns null if there is no path between the specified points. Will still return an appropriate path object if the start point is equal to the end point.

Extension Methods

Utility.Yield<T>(T)