Class FastAStar

A version of AStar that may perform significantly faster, in exchange for not being guaranteed to always produce a shortest path. A valid path will still be produced, but it is not guaranteed to be the shortest possible.

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 FastAStar : AStar
Remarks

This class is exactly like a regular AStar instance, but sets the heuristic by default to the MANHATTAN calculate function (with the same tiebreaking/smoothing element as regular AStar. In the case that euclidean or chebyshev distance is used, this heuristic is over-estimating -- that is, it may in some cases produce a value that is greater than the actual shortest path between two points. As such, this means that, while the algorithm will still produce valid paths, the algorithm is no longer guaranteed to produce fully shortest paths. In exchange, however, the algorithm may perform significantly faster than an AStar instance with its default heuristic.

In practice, however, it is worth noting that the paths are often (though not always) the shortest path regardless, and when they are not, the deviation in length between the path that the algorithm returns and the actual shortest path is often very small (less than 5%). As such, it may be viable for use in most cases.

Constructors

| Improve this Doc View Source

FastAStar(IMapView<Boolean>, Distance)

Constructor.

Declaration
public FastAStar(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

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

Declaration
public FastAStar(IMapView<bool> walkabilityMap, Distance distanceMeasurement, IMapView<double> weights, double minimumWeight)
Parameters
Type Name Description
IMapView<System.Boolean> walkabilityMap
Distance distanceMeasurement
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.

Extension Methods