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 PathNeighbors
method should return a slice of the direct neighbors.
The PathNeighborCost
method should calculate an exact movement cost for direct neighbors.
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) PathNeighbors() []astar.Pather {
return []astar.Pather{
t.Up(),
t.Right(),
t.Down(),
t.Left(),
}
}
func (t *Tile) PathNeighborCost(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 [email protected] Robin Ranjit Chauhan [email protected]