Go implementation of the A* search algorithm

Overview

go-astar

A* pathfinding implementation for Go

Build Status

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]

Comments
  • Patch for beefsack/go-astar Issue 1, moving goal condition check in asta...

    Patch for beefsack/go-astar Issue 1, moving goal condition check in asta...

    ... astar.go to preserve optimality

    Moved the check for goal state out of the neighbour expansion loop.

    This patch was designed to fix https://github.com/beefsack/go-astar/issues/1

    opened by pathway 9
  • bidirectional a-star

    bidirectional a-star

    Basic idea is to implement bidirectional a-star, which can (or not) depending on the problem, be more efficient. So there are two priority queues. I thought it would be a nice addition to this package.

    However:

    • unlike one-directional, it is not guaranteed to find the exact optimal path. this makes it harder to test
    • it is solving some tests nicely, but I am still getting some unexpected results, still debugging
    opened by pathway 6
  • astar.go will not always choose the optimal path

    astar.go will not always choose the optimal path

    The "Found a path to the goal" condition is checked when expanding neighbours. But to be optimal, this condition should be checked for a node freshly popped from the priority queue instead.

    Its taking me longer than Id like to produce a failing testcase, but I can show a simple thought experiment that illustrates the problem. It's not as easy to illustrate in the grid world (and Im not even certain I could illustrate it in that world, because it does not use Edge weights), but your algorithm appears to be designed to be more general that just solving the grids.

    Consider a world with Nodes and Edges, Edges each having a cost

          E
        /  |
      /    |
    S---- M
    

    S=Start E=End M=Middle

    Edges: S-E is a giant chasm, cost: 10000 S-M and M-E are paved roads. cost: 1

    Currently, astar.go would do this. -Push S onto the Queue -Pop S -Expand neighbors of S using Edges -Neighbor E found. END.

    Resulting solution would be S-E cost 10000. But optimal solution is S-M-E, cost 2.

    opened by pathway 5
  • Typo in the README

    Typo in the README

    In the example in the README, the methods on Tile use the English spelling of "Neighbour", whereas the interface Pather requires the methods to spell it "Neighbor".

    opened by zac-garby 1
  • Remove the 'close' and 'opened' fields.

    Remove the 'close' and 'opened' fields.

    Hi, beefsack. I think the closed and open fields are a bit of a contradiction, so I try to keep it simple. And I removed the head.Remove method, which gave a slight performance improvement.

    Benchmark

    Original

    $ go test -benchmem -benchtime 3s  -bench . astar
    goos: windows
    goarch: amd64
    pkg: astar
    cpu: Intel(R) Core(TM) i5-9600KF CPU @ 3.70GHz
    BenchmarkLarge-6            2955           1188135 ns/op          542940 B/op       6652 allocs/op
    PASS
    ok      astar   3.669s
    

    After

    $ go test -benchmem -benchtime 3s  -bench . astar
    oos: windows
    goarch: amd64
    pkg: astar
    cpu: Intel(R) Core(TM) i5-9600KF CPU @ 3.70GHz
    BenchmarkLarge-6            3030           1157325 ns/op          516254 B/op       6652 allocs/op
    PASS
    ok      astar   3.665s
    
    opened by aitsuki 0
  • Returns path in wrong direction

    Returns path in wrong direction

    While defined as func Path(from, to Pather) ..., the resulting path actually starts at to node and ends at from.

    This can be seen using this patch to pather_test.go:

    diff --git pather_test.go pather_test.go
    index b9d78bd..331ee0d 100644
    --- pather_test.go
    +++ pather_test.go
    @@ -159,18 +159,19 @@ func (w World) RenderPath(path []Pather) string {
                    return ""
            }
            height := len(w[0])
    -       pathLocs := map[string]bool{}
    -       for _, p := range path {
    +       pathLocs := map[string]rune{}
    +       for i, p := range path {
                    pT := p.(*Tile)
    -               pathLocs[fmt.Sprintf("%d,%d", pT.X, pT.Y)] = true
    +               nr := []rune("0123456789abc")[i%12] // "clever" rendering of node index in path.
    +               pathLocs[fmt.Sprintf("%d,%d", pT.X, pT.Y)] = nr
            }
            rows := make([]string, height)
            for x := 0; x < width; x++ {
                    for y := 0; y < height; y++ {
                            t := w.Tile(x, y)
                            r := ' '
    -                       if pathLocs[fmt.Sprintf("%d,%d", x, y)] {
    -                               r = KindRunes[KindPath]
    +                       if nr := pathLocs[fmt.Sprintf("%d,%d", x, y)]; nr != 0 {
    +                               r = nr
                            } else if t != nil {
                                    r = KindRunes[t.Kind]
                            }
    

    which renders 0 on T and 9 on F:

    === RUN   TestStraightLine
        path_test.go:14: Input world
            .....~......
            .....MM.....
            .F........T.
            ....MMM.....
            ............
        path_test.go:19: Resulting path
            .....~......
            .....MM.....
            .9876543210.
            ....MMM.....
            ............
    --- PASS: TestStraightLine (0.01s)
    
    opened by avivey 1
Owner
Michael Alexander
Programmer from Canberra, Australia, currently working for Technology 360 Group. Passionate about Rust, Linux, and FOSS.
Michael Alexander
An open source re-implementation of Diablo 2

OpenDiablo2 Join us on Discord! Development Live stream Support us on Patreon We are also working on a toolset: https://github.com/OpenDiablo2/HellSpa

OpenDiablo2 10.4k Dec 2, 2022
⛏ 🐹 Minecraft Protocol implementation in Go

illustration by @talentlessguy Install Go 1.16.x is required to use this library go get github.com/BRA1L0R/go-mcproto Opening a connection client := m

Pietro Tamilia 31 Sep 20, 2022
An open-source re-implementation of Pokémon Red

This project is open source re-implementation of Pokémon Red.

Akatsuki 214 Aug 13, 2022
This project is designed to be an open source implementation for streaming desktop games using WebRTC

The aim of this project is develop a WebRTC screenshare designed for streaming video games and accepting remote inputs. There will be ansible instruct

Akilan Selvacoumar 20 Oct 6, 2022
A go implementation of Conway's game of life

go-life A go implementation of Conway's game of life. The program takes input from stdin. It's recommended to use it as cat input.txt | go-life with i

Maxim 0 Oct 20, 2021
Go implementation of 2048 game

Go implementation of 2048 game

Kaushal Shah 0 Oct 21, 2021
snake game implementation using 2d array in Go

Snake Game Implementation Snake game implementation in Go using a 2-dimensional array. Demo Install download the package git clone https://github.com/

Iss Meftah 10 May 14, 2022
a Go implementation of the game of Briscola

BrisGolang BrisGolang is a Go implementation of the game of briscola using the WebSocket protocol for client/server communication. Usage You can play

Calogero Miraglia 0 Sep 15, 2022
Minecraft server implementation using Golang

Deepslate Deepslate is a Minecraft server implementation in Go. Deepslate if WIP and currently not available for installation Goals First implementati

virusbear 1 Nov 19, 2021
Implementation of a popular graphics benchmark written on Ebiten.

Ebiten Bunny Mark This is an implementation of the popular graphics benchmark written on Ebiten. The initial benchmark was created by Ian Lobb (code)

Artem Sedykh 16 Nov 5, 2022
An implementation of Conway's Game of Life.

Conway's Game of Life From Wikipedia, the free encyclopedia: The Game of Life, also known simply as Life, is a cellular automaton devised by the Briti

Erik Hovsepyan 1 Mar 16, 2022
Go implementation of the A* search algorithm

go-astar A* pathfinding implementation for Go The A* pathfinding algorithm is a pathfinding algorithm noted for its performance and accuracy and is co

Michael Alexander 531 Nov 25, 2022
Implementation of Boyer-Moore fast string search algorithm in Go

boyermoore Implementation of Boyer-Moore fast string search algorithm in Go

sarp dağ demirel 52 Oct 7, 2022
Go-enum-algorithm - Implement an enumeration algorithm in GO

go-enum-algorithm implement an enumeration algorithm in GO run the code go run m

Leon 1 Feb 15, 2022
A native Go clean room implementation of the Porter Stemming algorithm.

Go Porter Stemmer A native Go clean room implementation of the Porter Stemming Algorithm. This algorithm is of interest to people doing Machine Learni

Charles Iliya Krempeaux 181 Dec 2, 2022
Golang implementation of the Paice/Husk Stemming Algorithm

##Golang Implementation of the Paice/Husk stemming algorithm This project was created for the QUT course INB344. Details on the algorithm can be found

Aaron Groves 29 Sep 27, 2022
Golang implementation of the Paice/Husk Stemming Algorithm

##Golang Implementation of the Paice/Husk stemming algorithm This project was created for the QUT course INB344. Details on the algorithm can be found

Aaron Groves 29 Sep 27, 2022
Go implementation of the bspatch algorithm

binarydist Package binarydist implements binary diff and patch as described on http://www.daemonology.net/bsdiff/. It reads and writes files compatibl

Keith Rarick 285 Nov 20, 2022
Fast (linear time) implementation of the Gaussian Blur algorithm in Go.

Song2 Fast (linear time) implementation of the Gaussian Blur algorithm in Go.

Masaya Watanabe 52 Oct 25, 2022
A Go implementation of the 64-bit xxHash algorithm (XXH64)

xxhash xxhash is a Go implementation of the 64-bit xxHash algorithm, XXH64. This is a high-quality hashing algorithm that is much faster than anything

Caleb Spare 1.3k Nov 30, 2022