# 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`