A* pathfinding implementation for Go
The A* pathfinding algorithm is a pathfinding algorithm noted for its performance and accuracy and is commonly used in game development. It can be used to find short paths for any weighted graph.
A fantastic overview of A* can be found at Amit Patel's Stanford website.
The following crude examples were taken directly from the automated tests. Please see path_test.go
for more examples.
.
- Plain (movement cost 1)~
- River (movement cost 2)M
- Mountain (movement cost 3)X
- Blocker, unable to move throughF
- From / start positionT
- To / goal position●
- Calculated path
.....~...... .....~......
.....MM..... .....MM.....
.F........T. -> .●●●●●●●●●●.
....MMM..... ....MMM.....
............ ............
.....~...... .....~......
.....MM..... .....MM.....
.F..MMMM..T. -> .●●●MMMM●●●.
....MMM..... ...●MMM●●...
............ ...●●●●●....
............
.........XXX
.F.......XTX -> No path
.........XXX
............
FX.X........ ●X.X●●●●●●..
.X...XXXX.X. ●X●●●XXXX●X.
.X.X.X....X. -> ●X●X.X●●●●X.
...X.X.XXXXX ●●●X.X●XXXXX
.XX..X.....T .XX..X●●●●●●
..F..M...... ..●●●●●●●●●.
.....MM..... .....MM...●.
....MMMM..T. -> ....MMMM..●.
....MMM..... ....MMM.....
............ ............
.....~...... .....~......
.....~...... ....●●●.....
.F...X...T.. -> .●●●●X●●●●..
.....M...... .....M......
.....M...... .....M......
import "github.com/beefsack/go-astar"
An example implementation is done for the tests in path_test.go
for the Tile type.
The PathNeighbours
method should return a slice of the direct neighbours.
The PathNeighbourCost
method should calculate an exact movement cost for direct neighbours.
The PathEstimatedCost
is a heuristic method for estimating the distance between arbitrary tiles. The examples in the test files use Manhattan distance to estimate orthogonal distance between tiles.
type Tile struct{}
func (t *Tile) PathNeighbours() []astar.Pather {
return []astar.Pather{
t.Up(),
t.Right(),
t.Down(),
t.Left(),
}
}
func (t *Tile) PathNeighbourCost(to astar.Pather) float64 {
return to.MovementCost
}
func (t *Tile) PathEstimatedCost(to astar.Pather) float64 {
return t.ManhattanDistance(to)
}
// t1 and t2 are *Tile objects from inside the world.
path, distance, found := astar.Path(t1, t2)
if !found {
log.Println("Could not find path")
}
// path is a slice of Pather objects which you can cast back to *Tile.
Michael Alexander beefsack@gmail.com Robin Ranjit Chauhan robin@pathwayi.com