astar

README

astar

a* (a-star) pathfinding algorithm written in go

Wikipedia:

EN: A* search algorithm

DE: A*-Algorithmus

Install

go get github.com/jpierer/astar@main

Example

package main

import (
	"fmt"
	"github.com/jpierer/astar"
)

func main() {

	// Example 5x5 Grid
	//
	// [ ] [ ] [ ] [ ] [ ]   S: StartNode    (The node were you are)
	// [ ] [E] [P] [ ] [ ]   E: EndNode      (The destination point where you want to go)
	// [ ] [O] [P] [O] [O]   O: ObstacleNode (Some obstacles you cannot access)
	// [W] [O] [S] [ ] [ ]   P: Valid Path   (This is just a visualisation of the returned found path)
	// [W] [ ] [ ] [ ] [ ]   W: WeightedNode (Nodes like water, which are harder to enter)
	//
	// IMPORTANT: The grid coordinates starts on the "bottom left" -> X:0 / Y:0

	startNode := astar.Node{X: 2, Y: 1}
	endNode := astar.Node{X: 1, Y: 3}

	obstacleNodes := []astar.Node{
		{X: 3, Y: 2},
		{X: 4, Y: 2},
		{X: 1, Y: 1},
		{X: 1, Y: 2},
	}
	waterNodes := []astar.Node{
		{X: 0, Y: 0, Weighting: 20},
		{X: 0, Y: 1, Weighting: 20},
	}

	// set nodes to the config
	aConfig := astar.Config{
		GridWidth:     5,
		GridHeight:    5,
		InvalidNodes:  obstacleNodes,
		WeightedNodes: waterNodes,
	}

	// create the algo with defined config
	algo, err := astar.New(aConfig)
	if err != nil {
		fmt.Println("invalid astar config", err)
		return
	}

	// run it
	foundPath, err := algo.FindPath(startNode, endNode)
	if err != nil || len(foundPath) == 0 {
		fmt.Println("No path found ...")
		return
	}

	// the foundPath has now the way to the target

	// IMPORTANT:
	// the path is in the opposite way so the endpoint node is on index 0
	// you can avoid it by switching the startNode<>endNode parameter
	for _, node := range foundPath {
		fmt.Println(node)
	}

	// output:
	// Node [X:1 Y:3 F:1 G:1 H:0]
	// Node [X:2 Y:3 F:2 G:1 H:1]
	// Node [X:2 Y:2 F:3 G:1 H:2]

}

Support Me

Give a ⭐ if this project was helpful in any way!

License

The code is released under the MIT LICENSE.

Documentation

Index

• func New(config Config) (*astar, error)
• type Config
• type List
  • func NewList() *List
  • func (l *List) Add(nodes ...Node)
  • func (l *List) All() []Node
  • func (l *List) Clear()
  • func (l *List) Contains(searchNode Node) bool
  • func (l *List) GetIndex(searchNode Node) int
  • func (l *List) GetIndexOfMinF() int
  • func (l *List) GetMinFNode() (Node, error)
  • func (l *List) IsEmpty() bool
  • func (l *List) Remove(removeNode Node)
• type Node
  • func (n Node) String() string

Functions

func New

func New(config Config) (*astar, error)

New creates a new astar instance

Types

type Config

type Config struct {
	GridWidth, GridHeight int
	InvalidNodes          []Node
	WeightedNodes         []Node
}

Config holds important settings to perform the calculation

GridWidth and GridHeight are required and represents the size of the grid

InvalidNodes can be used to add not accessible nodes like obstacles etc. WeightedNodes can be used to add nodes to be avoided like mud or mountains

type List

type List struct {
	// contains filtered or unexported fields
}

List represents a list of nodes

func NewList

func NewList() *List

NewList creates a new list

func (*List) Add

func (l *List) Add(nodes ...Node)

Add one or more nodes to the list

func (*List) All

func (l *List) All() []Node

All returns the full list of nodes

func (*List) Clear

func (l *List) Clear()

Clear removes all nodes from the list

func (*List) Contains

func (l *List) Contains(searchNode Node) bool

Contains check if a node is in the list

func (*List) GetIndex

func (l *List) GetIndex(searchNode Node) int

GetIndex returns the index of the node in the list if the node is not found the return value is -1

func (*List) GetIndexOfMinF

func (l *List) GetIndexOfMinF() int

GetIndexOfMinF returns the index of the nodes list with the smallest node.F value

if no node is found it returns -1

func (*List) GetMinFNode

func (l *List) GetMinFNode() (Node, error)

GetMinFNode returns the node with the smallest node.F value

func (*List) IsEmpty

func (l *List) IsEmpty() bool

IsEmpty returns if the nodes list has nodes or not

func (*List) Remove

func (l *List) Remove(removeNode Node)

Remove a node from the list if the node is not found we do nothing

type Node

type Node struct {
	X, Y      int
	Weighting int
	// contains filtered or unexported fields
}

Node represents a simple node X and Y represents the nodes coordinates on the grid

IMPORTANT: The grid coordinates starts on the "bottom left" -> X:0 / Y:0

With the Weighting value you can set the nodes heavy grade so a node with mud or water are heavier as gras or street

func (Node) String

func (n Node) String() string

String returns formatted values of the node