Class AStar

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

Inheritance

System.Object

AStar

FastAStar

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: GoRogue.Pathing

Assembly: GoRogue.dll

Syntax

public class AStar

Remarks

Like most GoRogue algorithms, AStar takes as a construction parameter an IMapView representing the map. Specifically, it takes an IMapView<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 IMapView<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

| Improve this Doc View Source

AStar(IMapView<Boolean>, Distance)

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

Declaration

public AStar(IMapView<bool> walkabilityMap, Distance distanceMeasurement)

Parameters

Type	Name	Description
IMapView<System.Boolean>	walkabilityMap	Map view used to deterine 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.

| Improve this Doc View Source

AStar(IMapView<Boolean>, Distance, IMapView<Double>, Double)

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

Declaration

public AStar(IMapView<bool> walkabilityMap, Distance distanceMeasurement, IMapView<double> weights, double minimumWeight)

Parameters

Type	Name	Description
IMapView<System.Boolean>	walkabilityMap	Map view used to deterine 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.
IMapView<System.Double>	weights	A map view indicating the weights of each location (see Weights.
System.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.

| Improve this Doc View Source

AStar(IMapView<Boolean>, Distance, Func<Coord, Coord, Double>)

Constructor.

Declaration

public AStar(IMapView<bool> walkabilityMap, Distance distanceMeasurement, Func<Coord, Coord, double> heuristic)

Parameters

Type	Name	Description
IMapView<System.Boolean>	walkabilityMap	Map view used to deterine 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.
System.Func<Coord, Coord, System.Double>	heuristic	Function used to estimate the distance between two given points.

| Improve this Doc View Source

AStar(IMapView<Boolean>, Distance, Func<Coord, Coord, Double>, IMapView<Double>)

Constructor.

Declaration

public AStar(IMapView<bool> walkabilityMap, Distance distanceMeasurement, Func<Coord, Coord, double> heuristic, IMapView<double> weights)

Parameters

Type	Name	Description
IMapView<System.Boolean>	walkabilityMap	Map view used to deterine 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.
System.Func<Coord, Coord, System.Double>	heuristic	Function used to estimate the distance between two given points.
IMapView<System.Double>	weights	A map view indicating the weights of each location (see Weights.

Fields

| Improve this Doc 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
System.Double

Properties

| Improve this Doc 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

| Improve this Doc 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<Coord, Coord, double> Heuristic { get; set; }

Property Value

Type	Description
System.Func<Coord, Coord, System.Double>

| Improve this Doc View Source

MaxEuclideanMultiplier

Multiplier that is used in the tiebreaking/smoothing element of the default heuristic. This value is based on the maximum possible EuclideanDistanceMagnitude(Coord, Coord) between two points on the map.

Typically you dont' need this value unless you're creating a custom heuristic an introducing the same tiebreaking/smoothing element as the default heuristic.

Declaration

public double MaxEuclideanMultiplier { get; }

Property Value

Type	Description
System.Double

| Improve this Doc View Source

WalkabilityMap

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

Declaration

public IMapView<bool> WalkabilityMap { get; }

Property Value

Type	Description
IMapView<System.Boolean>

| Improve this Doc 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 IMapView<double> Weights { get; }

Property Value

Type	Description
IMapView<System.Double>

Methods

| Improve this Doc View Source

ShortestPath(Coord, Coord, Boolean)

Finds the shortest path between the two specified points.

Declaration

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

Parameters

Type	Name	Description
Coord	start	The starting point of the path.
Coord	end	The ending point of the path.
System.Boolean	assumeEndpointsWalkable	Whether or not to assume the start and end points are walkable, regardless of what the WalkabilityMap 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.

| Improve this Doc View Source

ShortestPath(Int32, Int32, Int32, Int32, Boolean)

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
System.Int32	startX	The x-coordinate of the starting point of the path.
System.Int32	startY	The y-coordinate of the starting point of the path.
System.Int32	endX	The x-coordinate of the ending point of the path.
System.Int32	endY	The y-coordinate of the ending point of the path.
System.Boolean	assumeEndpointsWalkable	Whether or not to assume the start and end points are walkable, regardless of what the WalkabilityMap 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)