astar

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

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 beefsack@gmail.com Robin Ranjit Chauhan robin@pathwayi.com

Documentation

Index

• type Goreland
  • func (w Goreland) RenderPath(path []Pather) string
• type Pather
• type Pathfinder
  • func NewPathfinder() (pf *Pathfinder)
  • func (pf *Pathfinder) Get(p Pather) *node
  • func (pf *Pathfinder) Search(from, to Pather) (path []Pather, distance float64, found bool)
• type Truck
  • func (t *Truck) PathEstimatedCost(world interface{}, to Pather) float64
  • func (t *Truck) PathNeighborCost(world interface{}, to Pather) float64
  • func (t *Truck) PathNeighbors(world interface{}) []Pather
• type Tube

Types

type Goreland

type Goreland struct {
}

func (Goreland) RenderPath

func (w Goreland) RenderPath(path []Pather) string

RenderPath renders a path on top of a Goreland world.

type Pather

type Pather interface {
	// PathNeighbors returns the direct neighboring nodes of this node which
	// can be pathed to.
	PathNeighbors(world interface{}) []Pather
	// PathNeighbourCost calculates the exact movement Cost to neighbor nodes.
	PathNeighborCost(world interface{}, to Pather) float64
	// PathEstimatedCost is a heuristic method for estimating movement costs
	// between non-adjacent nodes.
	PathEstimatedCost(world interface{}, to Pather) float64
}

Pather is an interface which allows A* searching on arbitrary objects which can represent a weighted graph.

type Pathfinder

type Pathfinder struct {
	World interface{}
	// contains filtered or unexported fields
}

func NewPathfinder

func NewPathfinder() (pf *Pathfinder)

Public constructor for the Pathfinder struct, initializes the nodes

func (*Pathfinder) Get

func (pf *Pathfinder) Get(p Pather) *node

Get returns the Pather object wrapped in a node, instantiating if required.

func (*Pathfinder) Search

func (pf *Pathfinder) Search(from, to Pather) (path []Pather, distance float64, found bool)

Path calculates a short path and the distance between the two Pather nodes.

If no path is found, found will be false.

type Truck

type Truck struct {

	// X and Y are the coordinates of the truck.
	X, Y int
	// contains filtered or unexported fields
}

A Truck is a Truck in a grid which implements Grapher.

func (*Truck) PathEstimatedCost

func (t *Truck) PathEstimatedCost(world interface{}, to Pather) float64

PathEstimatedCost uses Manhattan distance to estimate orthogonal distance between non-adjacent nodes.

func (*Truck) PathNeighborCost

func (t *Truck) PathNeighborCost(world interface{}, to Pather) float64

PathNeighborCost returns the Cost of the tube leading to Truck.

func (*Truck) PathNeighbors

func (t *Truck) PathNeighbors(world interface{}) []Pather

PathNeighbors returns the neighbors of the Truck

type Tube

type Tube struct {
	Cost float64
	// contains filtered or unexported fields
}