Path-finding

[info]Many algorithms in Grids, including the path finding methods, take delegates as parameters, and we usually pass in lambda expressions. If you are not familiar with these concepts in C#, check out http://msdn.microsoft.com/en-us/library/ms173171.aspx.

[/info]

The path finding methods all take a grid, a starting point, a goal, a few tuning parameters, and returns a list of points that represents the path.

This is the method with all the arguments, and the one you should generally use.

public static IEnumerable 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)

Here is a simple call using the above method.

var path = Algorithms.AStar(
   grid, 
   start, 
   goal, 
   (p,q) => p.DistanceFrom(q), 
   c => true, 
   (p, q) => 1);

The rest of the tutorial will explain what you need to do to make this call and how the various parameters work.

[dropcap style=”dark”]1[/dropcap] Implement a cell that supports the necessary functionality for the type of path-finding you want to do. For more information on implementing your own cells, see Making your own cells. Here is an example of a cell that has a property that determines whether this cell is accessible, and another property for getting the movement cost of the cell.

public class MyCell : SpriteCell
{
   public bool IsAccessible {get; set;}
   public float Cost {get; set;}
}

You can leave out either property if you do not need them; if you can do without both you don’t need to implement your own cell.

[dropcap style=”dark”]2[/dropcap]
Work out what types all your parameters should be. (If you are fluent in generics and C# interfaces, this step is probably just making a mental note or two.)

All the parameter types will depend on the grid that pass as the first parameter. To work out the other types, follow these steps:

1. Determine which IGrid interface the grid you want to use implements. All grids implement the IGrid<TCell, TPoint> interface. TCell is the type of elements in your grid. TPoint is the point type of your grid. For example, PointyHexGrid contains elements of type TCell, and uses point type PointyHexPoint. Therefore, it implements the interface IGrid<PointyHexPoint, SpriteCell>.
2. The start and goal are points of the same type as your grid. For example, if you use a PointyHexGrid, the start and goal nodes must be PointyHexPoints.
3. The two cost functions should take two points, and return an integer value. The type of the two points is the same as the grid point type.
4. The accessibility function takes a cell, and returns true or false. The cell type must be of the same type as that which the grid contains. If your grid is a PointyHexGrid, then this function will take cells of type SpriteCell.

[dropcap style=”dark”]3[/dropcap]

Write a method or lambda expression to decide whether a cell is accessible or not.

If all cells are accessible, you can pass in the lambda expression c => true (it always returns true, regardless of the cell).

Otherwise, if you implemented your own cell as above, you can access the IsAccessible property in the lambda expression. This will make the function skip points that cannot be reached.

var path = Algorithms.AStar(
   grid,
   start,
   goal,
   (p,q) => p.DistanceFrom(q),
   c => c.IsAccessible,
   (p, q) => 1);

Note that you can also write a method instead of the lamda expression:

public bool IsCellAccessible(MyCell cell)
{
   return cell.IsAccessible;
}

And then call the path-finding method like this:

var path = Algorithms.AStar(
   grid,
   start,
   goal,
   (p,q) => p.DistanceFrom(q),
   IsCellAccessible,
   1);

[dropcap style=”dark”]4[/dropcap]

Write a lambda expression or method for determining the true cost of reaching two points if they are neighbors.

If you want the cost between all neighbors to be the same, then you can simply use the expression (p, q) => 1.

The path depends on how you set up neighbors. Here is the path for the three different configurations:

Main and Diagonals	Main	Diagonals

But you may use a different scheme too. Here are two common scenarios:

Euclidean distance

In this case, you can use the expression:

(p, q) => (map[p] – map[q]).magnitude

Main and Diagonals	Main	Diagonals

Weighted paths

It’s common to assign a cost to each cell in your grid. You can incorporate theses costs easily as follows:

(p, q) => (grid[p].Cost + grid[q].Cost)/2

Main and Diagonals	Main	Diagonals

[dropcap style=”dark”]5[/dropcap]

Write a lambda expression or method for a cost heuristic between two points. The cost heuristic should always be smaller or equal than the real distance.

If neighbor-to-neighbor costs are 1, then the heuristic cost should be the distance returned by the DistanceFrom method defined for (most) points.

DistanceFrom is not defined for all spliced grids – in this case you can use DistanceFrom of the base points.

Cost	Heuristic to use
(p,q) => 1	(p,q) => p.DistanceFrom(q) (p,q) => p.BasePoint.DistanceFrom(q.BasePoint)
(p,q) => (map[p] – map[q]).magnitude	(p,q) => (map[p] – map[q]).magnitude
(p,q) => (grid[p].Cost + grid[q].Cost)/2	(p,q) => p.DistanceFrom(q) * MinCost (p,q) => p.BasePoint.DistanceFrom(q.BasePoint) * MinCost

If you use the Euclidean distance for the neighbor-to-neighbor cost, then you can use the Euclidean distance for the heuristic too.

If you use weighted paths, then you can use the grid-distance times the minimum cell cost. If the grid distance is not defined for your grid type, then use the grid distance for the base grid.

Here is an example that shows how to set it up:

(Import Grids, import the package, and open the PathFinding scene.)

PathFinding.unitypackage