• Stars
    star
    563
  • Rank 79,150 (Top 2 %)
  • Language
    Go
  • License
    MIT License
  • Created over 10 years ago
  • Updated almost 3 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Go implementation of the A* search algorithm

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]

More Repositories

1

webify

Turn shell commands into web services
Go
935
star
2

go-rate

A timed rate limiter for Go
Go
390
star
3

angular-d3

D3.js directives for AngularJS
HTML
109
star
4

git-mirror

Host Git repository mirrors with ease
Go
107
star
5

GDScript-sublime

Godot Engine GDScript syntax highlighting for Sublime Text
GDScript
65
star
6

bgg-ranking-historicals

34
star
7

zsh-simplicity

Minimal composable configs for zsh
Shell
19
star
8

gobndl

Bundle Go dependencies inside Go projects
Go
12
star
9

bgg-climbers

Go
11
star
10

ruby-continent

A ruby library for continents and their countries
Ruby
7
star
11

gar

Go application archiver inspired by JAR for Java
Go
7
star
12

bgg-ranked-csv

Go
6
star
13

go-jch

Jump Consistent Hash implementation in Go
Go
6
star
14

geekdo-chart

A simple application to display Geekdo rankings (boardgamegeek, videogamegeek and rpggeek) as charts over time
Go
4
star
15

go-geekdo

Go
4
star
16

geekdo-search-scraper

Go
4
star
17

github-language-colors

Scrape the GitHub language colors used in the language bar
Go
4
star
18

jch-rs

Jump Consistent Hash for Rust.
Rust
3
star
19

unrealscript-sublime

Deprecated, see https://github.com/Zinggi/UnrealScriptIDE
3
star
20

bash-powerline-installer

Powerline in your bash terminal
Shell
2
star
21

whois_server

2
star
22

domain.availability.js

JavaScript
1
star
23

go-dot

Dot rendering using braille characters in Go
Go
1
star
24

gar-example

An example application designed to use the gar Go application archiver
Go
1
star
25

baconsacktd

1
star
26

rbasic

BASIC interpreter written in Rust
Rust
1
star
27

transmitter-api

API to fetch transmitter data, including location and frequency
Ruby
1
star
28

annscraper

PHP
1
star
29

tourney

PHP
1
star
30

issue-gantt

Ruby
1
star
31

termui-rich-widget

A rich text widget for termui supporting text formatting and input
Go
1
star
32

go-under-cover

Tunnel network traffic through secure websockets
Go
1
star
33

cardy

Cardy is a flashcard server with a bundled jQuery Mobile client.
JavaScript
1
star
34

moodle_quiz_scraper

Ruby
1
star
35

vim_config

My personal vim configuration
Vim Script
1
star
36

design-wok

Connecting businesses with designers
Ruby
1
star
37

gantt.js

CoffeeScript
1
star
38

percy-android

Percy client for Android.
Java
1
star
39

mysql-glb

Benchmark MySQL by replaying a general log
Go
1
star
40

coo

Static web builder, with a vast range of supported languages
CoffeeScript
1
star
41

ez-commerce

Ruby
1
star
42

symbolic_media_library

PHP
1
star
43

pargo

Parser combinator library for Go
Go
1
star
44

spawtz-indoor-cricket-scraper

Go
1
star