Class Algorithms
This class provide generic functions for common grid operations, such as finding a shortest path or connected shapes.
[Version(1, 0, 0)]
public static class Algorithms
- Inheritance
-
Algorithms
- Inherited Members
Methods
AStar2<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, TPoint, Func<TPoint, TPoint, float>, Func<TPoint, bool>, Func<TPoint, TPoint, float>)
public static IEnumerable<TPoint> AStar2<TCell, TPoint>(IGrid<TCell, TPoint> grid, TPoint start, TPoint goal, Func<TPoint, TPoint, float> heuristicCostEstimate, Func<TPoint, bool> isAccessible, Func<TPoint, TPoint, float> neighborToNeighborCost) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>startTPointgoalTPointheuristicCostEstimateFunc<TPoint, TPoint, float>isAccessibleFunc<TPoint, bool>neighborToNeighborCostFunc<TPoint, TPoint, float>
Returns
- IEnumerable<TPoint>
Type Parameters
TCellTPoint
AStar<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, TPoint)
Find the shortest path between a start and goal node.
The distance between nodes(as defined by TPoint.DistanceFrom) are used as the heuristic and actual cost between nodes.In some cases the result may be unintuitive, and an overload specifying a different cost should be used.
See AStar<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, TPoint, Func<TPoint, TPoint, float>, Func<TCell, bool>, Func<TPoint, TPoint, float>)
public static IEnumerable<TPoint> AStar<TCell, TPoint>(IGrid<TCell, TPoint> grid, TPoint start, TPoint goal) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>startTPointgoalTPoint
Returns
- IEnumerable<TPoint>
The list of nodes on the path in order.If no path is possible, null is returned.
Type Parameters
TCellTPoint
AStar<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, TPoint, Func<TPoint, TPoint, float>, Func<TCell, bool>)
Find the shortest path between a start and goal node.
The distance between nodes(as defined by TPoint.DistanceFrom) are used as the actual cost between nodes.In some cases the result may be unintuitive, and an overload specifying a different cost should be used.
Using an overload with an appropriate distance function can solve the issue.
See AStar<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, TPoint, Func<TPoint, TPoint, float>, Func<TCell, bool>, Func<TPoint, TPoint, float>)
[Obsolete("Use the overload instead that allows you to specify the cost in addition to the cost heuristic")]
public static IEnumerable<TPoint> AStar<TCell, TPoint>(IGrid<TCell, TPoint> grid, TPoint start, TPoint goal, Func<TPoint, TPoint, float> heuristicCostEstimate, Func<TCell, bool> isAccessible) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>startTPointgoalTPointheuristicCostEstimateFunc<TPoint, TPoint, float>isAccessibleFunc<TCell, bool>
Returns
- IEnumerable<TPoint>
Type Parameters
TCellTPoint
AStar<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, TPoint, Func<TPoint, TPoint, float>, Func<TCell, bool>, Func<TPoint, TPoint, float>)
public static IEnumerable<TPoint> AStar<TCell, TPoint>(IGrid<TCell, TPoint> grid, TPoint start, TPoint goal, Func<TPoint, TPoint, float> heuristicCostEstimate, Func<TCell, bool> isAccessible, Func<TPoint, TPoint, float> neighborToNeighborCost) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>startTPointgoalTPointheuristicCostEstimateFunc<TPoint, TPoint, float>isAccessibleFunc<TCell, bool>neighborToNeighborCostFunc<TPoint, TPoint, float>
Returns
- IEnumerable<TPoint>
Type Parameters
TCellTPoint
AggregateNeighborhood<TCell, TPoint>(IGrid<TCell, TPoint>, Func<TPoint, IEnumerable<TPoint>, TCell>)
public static void AggregateNeighborhood<TCell, TPoint>(IGrid<TCell, TPoint> grid, Func<TPoint, IEnumerable<TPoint>, TCell> aggregator) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>aggregatorFunc<TPoint, IEnumerable<TPoint>, TCell>
Type Parameters
TCellTPoint
AggregateNeighborhood<TCell, TPoint, TResultGrid, TResultCell>(IGrid<TCell, TPoint>, Func<TPoint, IEnumerable<TPoint>, TResultCell>)
public static TResultGrid AggregateNeighborhood<TCell, TPoint, TResultGrid, TResultCell>(IGrid<TCell, TPoint> grid, Func<TPoint, IEnumerable<TPoint>, TResultCell> aggregator) where TPoint : IGridPoint<TPoint> where TResultGrid : IGrid<TResultCell, TPoint>
Parameters
gridIGrid<TCell, TPoint>aggregatorFunc<TPoint, IEnumerable<TPoint>, TResultCell>
Returns
- TResultGrid
Type Parameters
TCellTPointTResultGridTResultCell
Contains<TPoint>(IEnumerable<TPoint>, IEnumerable<TPoint>)
public static bool Contains<TPoint>(IEnumerable<TPoint> bigShape, IEnumerable<TPoint> smallShape) where TPoint : IGridPoint<TPoint>
Parameters
bigShapeIEnumerable<TPoint>smallShapeIEnumerable<TPoint>
Returns
Type Parameters
TPoint
GetBiggestShape<TPoint>(IEnumerable<IEnumerable<TPoint>>)
Gets the biggest shape (by number of points) in the given list.
public static IEnumerable<TPoint> GetBiggestShape<TPoint>(IEnumerable<IEnumerable<TPoint>> shapes) where TPoint : IGridPoint<TPoint>
Parameters
shapesIEnumerable<IEnumerable<TPoint>>Each shape is represented as a list of points.
Returns
- IEnumerable<TPoint>
Type Parameters
TPointThe type of point of the shapes.
GetConnectedLines<TCell, TPoint, TBasePoint>(IEvenGrid<TCell, TPoint, TBasePoint>, TPoint, Func<TPoint, TPoint, bool>)
Gets the longest line of connected points that contains this point. GetConnectedRays<TCell, TPoint>(AbstractUniformGrid<TCell, TPoint>, TPoint, Func<TPoint, TPoint, bool>)
public static IEnumerable<IEnumerable<TPoint>> GetConnectedLines<TCell, TPoint, TBasePoint>(IEvenGrid<TCell, TPoint, TBasePoint> grid, TPoint point, Func<TPoint, TPoint, bool> isNeighborsConnected) where TPoint : ISplicedVectorPoint<TPoint, TBasePoint>, IGridPoint<TPoint> where TBasePoint : IVectorPoint<TBasePoint>, IGridPoint<TBasePoint>
Parameters
gridIEvenGrid<TCell, TPoint, TBasePoint>pointTPointisNeighborsConnectedFunc<TPoint, TPoint, bool>
Returns
- IEnumerable<IEnumerable<TPoint>>
Type Parameters
TCellThe type of cell of the grid that this algorithm takes.
TPointThe type of point of the grid that this algorithm takes.
TBasePointThe base type of the point.
GetConnectedRays<TCell, TPoint>(AbstractUniformGrid<TCell, TPoint>, TPoint, Func<TPoint, TPoint, bool>)
Returns a list containing lines connected to the given points. A line is a list of points. Only returns correct results for square or hex grids.
public static IEnumerable<IEnumerable<TPoint>> GetConnectedRays<TCell, TPoint>(AbstractUniformGrid<TCell, TPoint> grid, TPoint point, Func<TPoint, TPoint, bool> isNeighborsConnected) where TPoint : IVectorPoint<TPoint>, IGridPoint<TPoint>
Parameters
gridAbstractUniformGrid<TCell, TPoint>pointTPointisNeighborsConnectedFunc<TPoint, TPoint, bool>A functions that returns true or false, depending on whether two points can be considered connected when they are neighbors.For example, if you want rays of points that refer to cells of the same color, you can pass in a functions that compares the DefaultColors of cells.
Returns
- IEnumerable<IEnumerable<TPoint>>
Type Parameters
TCellThe type of cell of the grid that this algorithm takes.
TPointThe type of point of the grid that this algorithm takes.
Examples
private bool IsSameColour(point1, point2)
{
return grid[point1].Color == grid[point2].Color;
}
private SomeMethod()
{
...
var rays = GetConnectedRays<ColourCell, PointyHexPoint, PointyHexNeighborIndex>(
grid, point, IsSameColour);
...
}
You can of course also use a lambda expression, like this:
//The following code returns all lines that radiate from the given point
GetConnectedRays<ColourCell, PointyHexPoint, PointyHexNeighborIndex>(
grid, point, (x, y) => grid[x].Color == grid[y].Color);
GetConnectedSet<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, Func<TPoint, TPoint, bool>)
public static HashSet<TPoint> GetConnectedSet<TCell, TPoint>(IGrid<TCell, TPoint> grid, TPoint point, Func<TPoint, TPoint, bool> isNeighborsConnected) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>pointTPointisNeighborsConnectedFunc<TPoint, TPoint, bool>The function to use to check whether two neighbors are connected
Returns
- HashSet<TPoint>
Returns a list of points connected to the given point.
Type Parameters
TCellThe type of cell of the grid that this algorithm takes.
TPointThe type of point of the grid that this algorithm takes.
GetLongestConnectedLine<TCell, TPoint, TBasePoint>(IEvenGrid<TCell, TPoint, TBasePoint>, TPoint, Func<TPoint, TPoint, bool>)
Get the longest line of points connected to the given point
public static IEnumerable<TPoint> GetLongestConnectedLine<TCell, TPoint, TBasePoint>(IEvenGrid<TCell, TPoint, TBasePoint> grid, TPoint point, Func<TPoint, TPoint, bool> isNeighborsConnected) where TPoint : ISplicedVectorPoint<TPoint, TBasePoint>, IGridPoint<TPoint> where TBasePoint : IVectorPoint<TBasePoint>, IGridPoint<TBasePoint>
Parameters
gridIEvenGrid<TCell, TPoint, TBasePoint>pointTPointisNeighborsConnectedFunc<TPoint, TPoint, bool>
Returns
- IEnumerable<TPoint>
Type Parameters
TCellThe type of cell of the grid that this algorithm takes.
TPointThe type of point of the grid that this algorithm takes.
TBasePointThe base type of the point.
GetLongestConnectedRay<TCell, TPoint>(AbstractUniformGrid<TCell, TPoint>, TPoint, Func<TPoint, TPoint, bool>)
Gets the longest of the rays connected to this cell. GetConnectedRays<TCell, TPoint>(AbstractUniformGrid<TCell, TPoint>, TPoint, Func<TPoint, TPoint, bool>)
public static IEnumerable<TPoint> GetLongestConnectedRay<TCell, TPoint>(AbstractUniformGrid<TCell, TPoint> grid, TPoint point, Func<TPoint, TPoint, bool> isNeighborsConnected) where TPoint : IVectorPoint<TPoint>, IGridPoint<TPoint>
Parameters
gridAbstractUniformGrid<TCell, TPoint>pointTPointisNeighborsConnectedFunc<TPoint, TPoint, bool>
Returns
- IEnumerable<TPoint>
Type Parameters
TCellThe type of cell of the grid that this algorithm takes.
TPointThe type of point of the grid that this algorithm takes.
GetLongestConnected<TCell, TPoint, TBasePoint>(IEvenGrid<TCell, TPoint, TBasePoint>, TPoint, Func<TPoint, TPoint, bool>)
[Obsolete("Use GetLongestConnectedLine instead. Will be removed in a future version.")]
public static IEnumerable<TPoint> GetLongestConnected<TCell, TPoint, TBasePoint>(IEvenGrid<TCell, TPoint, TBasePoint> grid, TPoint point, Func<TPoint, TPoint, bool> isNeighborsConnected) where TPoint : ISplicedVectorPoint<TPoint, TBasePoint>, IGridPoint<TPoint> where TBasePoint : IVectorPoint<TBasePoint>, IGridPoint<TBasePoint>
Parameters
gridIEvenGrid<TCell, TPoint, TBasePoint>pointTPointisNeighborsConnectedFunc<TPoint, TPoint, bool>
Returns
- IEnumerable<TPoint>
Type Parameters
TCellTPointTBasePoint
GetPointsInRangeCost<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, Func<TCell, bool>, Func<TPoint, TPoint, int>, int)
public static Dictionary<TPoint, int> GetPointsInRangeCost<TCell, TPoint>(IGrid<TCell, TPoint> grid, TPoint start, Func<TCell, bool> isAcessible, Func<TPoint, TPoint, int> getCellMoveCost, int moveRange) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>startTPointisAcessibleFunc<TCell, bool>getCellMoveCostFunc<TPoint, TPoint, int>moveRangeint
Returns
- Dictionary<TPoint, int>
Type Parameters
TCellTPoint
GetPointsInRangeCost<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, Func<TCell, bool>, Func<TPoint, TPoint, float>, float)
A generic function that returns the points in range based on a given start point, moveRange, and a function that returns the cost of moving between neighboring cells.
author Justin Kivak
[Version(1, 10, 0)]
public static Dictionary<TPoint, float> GetPointsInRangeCost<TCell, TPoint>(IGrid<TCell, TPoint> grid, TPoint start, Func<TCell, bool> isAcessible, Func<TPoint, TPoint, float> getCellMoveCost, float moveRange) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>The grid to use for the calculations
startTPointThe starting point for the range calculation
isAcessibleFunc<TCell, bool>getCellMoveCostFunc<TPoint, TPoint, float>A function that returns the move cost given a cell
moveRangefloatThe range from which to return cells
Returns
- Dictionary<TPoint, float>
Type Parameters
TCellTPoint
Examples
Example usage:
var costs = Algorithms.GetPointsInRangeCost(
grid,
start,
tile1, tile2 => DistanceBetween(tile1, tile2),
5f);
GetPointsInRange<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, Func<TCell, bool>, Func<TPoint, TPoint, int>, int)
public static IEnumerable<TPoint> GetPointsInRange<TCell, TPoint>(IGrid<TCell, TPoint> grid, TPoint start, Func<TCell, bool> isAcessible, Func<TPoint, TPoint, int> getCellMoveCost, int moveRange) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>startTPointisAcessibleFunc<TCell, bool>getCellMoveCostFunc<TPoint, TPoint, int>moveRangeint
Returns
- IEnumerable<TPoint>
Type Parameters
TCellTPoint
GetPointsInRange<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, Func<TCell, bool>, Func<TPoint, TPoint, float>, float)
A generic function that returns the points in range based on a given start point, moveRange, and a function that returns the cost of moving between neighboring cells.
author Justin Kivak
[Version(1, 10, 0)]
public static IEnumerable<TPoint> GetPointsInRange<TCell, TPoint>(IGrid<TCell, TPoint> grid, TPoint start, Func<TCell, bool> isAcessible, Func<TPoint, TPoint, float> getCellMoveCost, float moveRange) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>The grid to use for the calculations
startTPointThe starting point for the range calculation
isAcessibleFunc<TCell, bool>Whether the given cell can be reached
getCellMoveCostFunc<TPoint, TPoint, float>A function that returns the move cost given a cell
moveRangefloatThe range from which to return cells
Returns
- IEnumerable<TPoint>
Type Parameters
TCellTPoint
Examples
Example usage:
var tilesInRange = Algorithms.GetPointsInRange(
grid,
start,
tile1, tile2 => DistanceBetween(tile1, tile2),
5f);
IsConnected<TCell, TPoint>(IGrid<TCell, TPoint>, IEnumerable<TPoint>, Func<TPoint, TPoint, bool>)
The set is connected if the set of points are neighbor-connected, and isNeighborsConnected return true for each two neighbors in the set.Two points are connected if they are neighbors, or one point has a neighbor that is neighbor-connected with the other point.
public static bool IsConnected<TCell, TPoint>(IGrid<TCell, TPoint> grid, IEnumerable<TPoint> points, Func<TPoint, TPoint, bool> isNeighborsConnected) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>The grid on which to do the check
pointsIEnumerable<TPoint>The set of points to check. It is assumed all points are in the grid.
isNeighborsConnectedFunc<TPoint, TPoint, bool>The function to use to check whether two neighbors are connected
Returns
- bool
Returns true if the collection of points are connected.
Type Parameters
TCellThe type of cell of the grid that this algorithm takes.
TPointThe type of point of the grid that this algorithm takes.
Examples
checks whether the list of points are connected by color.
IsConnected(grid, points, (p, q) => grid[p].Color == grid[q].Color)
IsConnected<TCell, TPoint>(IGrid<TCell, TPoint>, TPoint, TPoint, Func<TPoint, TPoint, bool>)
The set is connected if the set of points are neighbor-connected, and isNeighborsConnected return true for each two neighbors in the set.Two points are connected if they are neighbors, or one point has
a neighbor that is neighbor-connected with the other point.
Another way to put this is, this function returns true if there is a set that connects point1 to point2.
public static bool IsConnected<TCell, TPoint>(IGrid<TCell, TPoint> grid, TPoint point1, TPoint point2, Func<TPoint, TPoint, bool> isNeighborsConnected) where TPoint : IGridPoint<TPoint>
Parameters
gridIGrid<TCell, TPoint>The grid on which to do the check
point1TPointThe first point to check.
point2TPointThe second point to check.
isNeighborsConnectedFunc<TPoint, TPoint, bool>The function to use to check whether two neighbors are connected.
Returns
- bool
Returns true if the two points are in a connected set.
Type Parameters
TCellThe type of cell of the grid that this algorithm takes.
TPointThe type of point of the grid that this algorithm takes.
Examples
checks whether the two points are connected by color.
IsConnected(grid, p1, p2, (p, q) => grid[p].Color == grid[q].Color)
IsEquivalentUnderTransformsAndTranslation<TPoint>(IEnumerable<TPoint>, IEnumerable<TPoint>, IEnumerable<Func<TPoint, TPoint>>, Func<IEnumerable<TPoint>, IEnumerable<TPoint>>)
public static bool IsEquivalentUnderTransformsAndTranslation<TPoint>(IEnumerable<TPoint> shape1, IEnumerable<TPoint> shape2, IEnumerable<Func<TPoint, TPoint>> pointTransformations, Func<IEnumerable<TPoint>, IEnumerable<TPoint>> toCanonicalPosition) where TPoint : IGridPoint<TPoint>
Parameters
shape1IEnumerable<TPoint>shape2IEnumerable<TPoint>pointTransformationsIEnumerable<Func<TPoint, TPoint>>toCanonicalPositionFunc<IEnumerable<TPoint>, IEnumerable<TPoint>>
Returns
Type Parameters
TPoint
IsEquivalentUnderTranslation<TPoint>(IEnumerable<TPoint>, IEnumerable<TPoint>, Func<IEnumerable<TPoint>, IEnumerable<TPoint>>)
public static bool IsEquivalentUnderTranslation<TPoint>(IEnumerable<TPoint> shape1, IEnumerable<TPoint> shape2, Func<IEnumerable<TPoint>, IEnumerable<TPoint>> toCanonicalPosition) where TPoint : IGridPoint<TPoint>
Parameters
shape1IEnumerable<TPoint>shape2IEnumerable<TPoint>toCanonicalPositionFunc<IEnumerable<TPoint>, IEnumerable<TPoint>>
Returns
Type Parameters
TPoint
IsEquivalent<TPoint>(IEnumerable<TPoint>, IEnumerable<TPoint>)
public static bool IsEquivalent<TPoint>(IEnumerable<TPoint> shape1, IEnumerable<TPoint> shape2) where TPoint : IGridPoint<TPoint>
Parameters
shape1IEnumerable<TPoint>shape2IEnumerable<TPoint>
Returns
Type Parameters
TPoint
Rotate120About(IEnumerable<FlatHexPoint>, FlatHexPoint, FlatHexPoint, FlatHexPoint)
Rotates a shape 120 degrees around the vertice shared by the three given points.
The three points must form a close triangle (they must share a vertex).
public static IEnumerable<FlatHexPoint> Rotate120About(IEnumerable<FlatHexPoint> shape, FlatHexPoint p1, FlatHexPoint p2, FlatHexPoint p3)
Parameters
shapeIEnumerable<FlatHexPoint>p1FlatHexPointp2FlatHexPointp3FlatHexPoint
Returns
Rotate120About(IEnumerable<PointyHexPoint>, PointyHexPoint, PointyHexPoint, PointyHexPoint)
Rotates a shape 120 degrees around the vertice shared by the three given points.
The three points must form a close triangle (they must share a vertex).
public static IEnumerable<PointyHexPoint> Rotate120About(IEnumerable<PointyHexPoint> shape, PointyHexPoint p1, PointyHexPoint p2, PointyHexPoint p3)
Parameters
shapeIEnumerable<PointyHexPoint>p1PointyHexPointp2PointyHexPointp3PointyHexPoint
Returns
Rotate180About(IEnumerable<FlatHexPoint>, FlatHexPoint, FlatHexPoint)
Rotates a shape 180 degrees around the edge shared by the two given points.
The two points must be neighbors.
public static IEnumerable<FlatHexPoint> Rotate180About(IEnumerable<FlatHexPoint> shape, FlatHexPoint p1, FlatHexPoint p2)
Parameters
shapeIEnumerable<FlatHexPoint>p1FlatHexPointp2FlatHexPoint
Returns
Rotate180About(IEnumerable<PointyHexPoint>, PointyHexPoint, PointyHexPoint)
Rotates a shape 180 degrees around the edge shared by the two given points.
The two points must be neighbors.
public static IEnumerable<PointyHexPoint> Rotate180About(IEnumerable<PointyHexPoint> shape, PointyHexPoint p1, PointyHexPoint p2)
Parameters
shapeIEnumerable<PointyHexPoint>p1PointyHexPointp2PointyHexPoint
Returns
Rotate240About(IEnumerable<FlatHexPoint>, FlatHexPoint, FlatHexPoint, FlatHexPoint)
Rotates a shape 240 degrees around the vertice shared by the three given points.
The three points must form a close triangle (they must share a vertex).
public static IEnumerable<FlatHexPoint> Rotate240About(IEnumerable<FlatHexPoint> shape, FlatHexPoint p1, FlatHexPoint p2, FlatHexPoint p3)
Parameters
shapeIEnumerable<FlatHexPoint>p1FlatHexPointp2FlatHexPointp3FlatHexPoint
Returns
Rotate240About(IEnumerable<PointyHexPoint>, PointyHexPoint, PointyHexPoint, PointyHexPoint)
Rotates a shape 240 degrees around the vertice shared by the three given points.
The three points must form a close triangle (they must share a vertex).
public static IEnumerable<PointyHexPoint> Rotate240About(IEnumerable<PointyHexPoint> shape, PointyHexPoint p1, PointyHexPoint p2, PointyHexPoint p3)
Parameters
shapeIEnumerable<PointyHexPoint>p1PointyHexPointp2PointyHexPointp3PointyHexPoint
Returns
TransformShape<TPoint>(IEnumerable<TPoint>, Func<TPoint, TPoint>)
Transform each point in the list with the give point transformation.
public static IEnumerable<TPoint> TransformShape<TPoint>(IEnumerable<TPoint> shape, Func<TPoint, TPoint> pointTransformation) where TPoint : IGridPoint<TPoint>
Parameters
shapeIEnumerable<TPoint>pointTransformationFunc<TPoint, TPoint>
Returns
- IEnumerable<TPoint>
Type Parameters
TPoint