# Path finding

Indigo includes a generic pathfinding algorithm (A* generic variant) as of release `0.15.3`.

### Quick start

All of the pathfinding primitives are available with the following import:

``import indigoextras.pathfinding.*``

The computation of the path can be done with the following function call:

``````// def findPath[T](start: T, end: T, pathBuilder: PathBuilder[T])(using CanEqual[T,T]): Option[Batch[T]]
PathFinder.findPath(start, end, pathBuilder)``````

`start` and `end` have the same type and are the start and end points of the path. `pathBuilder` is the type allowing to customize the pathfinding algorithm (see below).

If `start` and `end` are of type `Point`:

• when a path is found, the function returns a `Some[Batch[Point]]` containing the path from `start` to `end`.
• when no path is found, the function returns `None`
• when `start` and `end` are the same point, the function returns `Some(Batch(start))` (that is also `Some(Batch(end))`).

You may also find samples in the tests `indigoextras.pathfinding.PathFinderTests` or in the sandbox `com.example.sandbox.scenes.PathFindingScene`.

### PathBuilder

The path builder is a trait that allows to customize the pathfinding algorithm. It requires the implementations of the 3 main characteristics of the A* algorithm:

• `neighbours`: the function that returns the neighbours of a point
• `distance`: the function that returns the distance (cost) to reach a neighbour from a point
• `heuristic`: the heuristic function used to estimate the distance (cost) from a point to reach the end point

The path builder also requires a given of type `CanEqual[T,T]` to compare the points.

## Default path builders

This object contains default path builders for the most common use cases. It also contains a few helper functions and constants to compute the neighbours and to define the allowed movements. If you need to customize the pathfinding algorithm this file is a good starting point.

Indigo provides default path builders, for `Point`, located in `indigoextras.pathfinding.PathBuilder` companion object.

• `PathBuilder.fromAllowedPoints`
• `PathBuilder.fromImpassablePoints`
• `PathBuilder.fromWeightedGrid`
• `PathBuilder.fromWeighted2DGrid`