go-astar

Go implementation of the A* search algorithm

Programming language: Go

License: MIT License

Tags: Game Development    

README

go-astar

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.

Examples

The following crude examples were taken directly from the automated tests. Please see path_test.go for more examples.

Key

• . - Plain (movement cost 1)
• ~ - River (movement cost 2)
• M - Mountain (movement cost 3)
• X - Blocker, unable to move through
• F - From / start position
• T - To / goal position
• ● - Calculated path

Straight line

.....~......      .....~......
.....MM.....      .....MM.....
.F........T.  ->  .●●●●●●●●●●.
....MMM.....      ....MMM.....
............      ............

Around a mountain

.....~......      .....~......
.....MM.....      .....MM.....
.F..MMMM..T.  ->  .●●●MMMM●●●.
....MMM.....      ...●MMM●●...
............      ...●●●●●....

Blocked path

............      
.........XXX
.F.......XTX  ->  No path
.........XXX
............

Maze

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●●●●●●

Mountain climber

..F..M......      ..●●●●●●●●●.
.....MM.....      .....MM...●.
....MMMM..T.  ->  ....MMMM..●.
....MMM.....      ....MMM.....
............      ............

River swimmer

.....~......      .....~......
.....~......      ....●●●.....
.F...X...T..  ->  .●●●●X●●●●..
.....M......      .....M......
.....M......      .....M......

Usage

Import the package

import "github.com/beefsack/go-astar"

Implement Pather interface

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)
}

Call Path function

// 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.

Authors

Michael Alexander [email protected] Robin Ranjit Chauhan [email protected]