astar

README

astar

Package astar implements the A* shortest path finding algorithm.

Examples

In order to use the astar.FindPath function to find the shortest path between two nodes of a graph you need a graph data structure that implements the Neighbours method to satisfy the astar.Graph[Node] interface and a cost function. It is up to you how the graph is internally implemented.

A maze

In this example the graph is represented by a slice of strings, each character representing a cell of a floor plan. Graph nodes are cell positions as image.Point values, with (0, 0) in the upper left corner. Spaces represent free cells available for walking, other characters like # represent walls. The Neighbours method returns the positions of the adjacent free cells to the north, east, south, and west of a given position (diagonal movement is not allowed in this example).

The cost function nodeDist simply calculates the Euclidean distance between two cell positions.

package main

import (
	"fmt"
	"image"
	"math"

	"github.com/fzipp/astar"
)

func main() {
	maze := graph{
		"###############",
		"#   # #     # #",
		"# ### ### ### #",
		"#   # # #   # #",
		"### # # # ### #",
		"# # #         #",
		"# # ### ### ###",
		"#   # # # #   #",
		"### # # # # ###",
		"# #       # # #",
		"# # ######### #",
		"#         #   #",
		"# ### # # ### #",
		"#   # # #     #",
		"###############",
	}
	start := image.Pt(1, 13) // Bottom left corner
	dest := image.Pt(13, 1)  // Top right corner

	// Find the shortest path
	path := astar.FindPath[image.Point](maze, start, dest, nodeDist, nodeDist)

	// Mark the path with dots before printing
	for _, p := range path {
		maze.put(p, '.')
	}
	maze.print()
}

// nodeDist is our cost function. We use points as nodes, so we
// calculate their Euclidean distance.
func nodeDist(p, q image.Point) float64 {
	d := q.Sub(p)
	return math.Sqrt(float64(d.X*d.X + d.Y*d.Y))
}

type graph []string

// Neighbours implements the astar.Graph[Node] interface (with Node = image.Point).
func (g graph) Neighbours(p image.Point) []image.Point {
	offsets := []image.Point{
		image.Pt(0, -1), // North
		image.Pt(1, 0),  // East
		image.Pt(0, 1),  // South
		image.Pt(-1, 0), // West
	}
	res := make([]image.Point, 0, 4)
	for _, off := range offsets {
		q := p.Add(off)
		if g.isFreeAt(q) {
			res = append(res, q)
		}
	}
	return res
}

func (g graph) isFreeAt(p image.Point) bool {
	return g.isInBounds(p) && g[p.Y][p.X] == ' '
}

func (g graph) isInBounds(p image.Point) bool {
	return p.Y >= 0 && p.X >= 0 && p.Y < len(g) && p.X < len(g[p.Y])
}

func (g graph) put(p image.Point, c rune) {
	g[p.Y] = g[p.Y][:p.X] + string(c) + g[p.Y][p.X+1:]
}

func (g graph) print() {
	for _, row := range g {
		fmt.Println(row)
	}
}

Output:

###############
#   # #     #.#
# ### ### ###.#
#   # # #   #.#
### # # # ###.#
# # #  .......#
# # ###.### ###
#   # #.# #   #
### # #.# # ###
# #.....  # # #
# #.######### #
#...      #   #
#.### # # ### #
#.  # # #     #
###############

2D points as nodes

In this example the graph is represented by an adjacency list. Nodes are 2D points in Euclidean space as image.Point values. The link function creates a bi-directed edge between a pair of nodes.

The cost function nodeDist calculates the Euclidean distance between two points (nodes).

package main

import (
	"fmt"
	"image"
	"math"

	"github.com/fzipp/astar"
)

func main() {
	// Create a graph with 2D points as nodes
	a := image.Pt(2, 3)
	b := image.Pt(1, 7)
	c := image.Pt(1, 6)
	d := image.Pt(5, 6)
	g := newGraph().link(a, b).link(a, c).link(b, c).link(b, d).link(c, d)

	// Find the shortest path from a to d
	p := astar.FindPath[image.Point](g, a, d, nodeDist, nodeDist)

	// Output the result
	if p == nil {
		fmt.Println("No path found.")
		return
	}
	for i, n := range p {
		fmt.Printf("%d: %s\n", i, n)
	}
}

// graph is represented by an adjacency list.
type graph map[image.Point][]image.Point

func newGraph() graph {
	return make(map[image.Point][]image.Point)
}

// link creates a bi-directed edge between nodes a and b.
func (g graph) link(a, b image.Point) graph {
	g[a] = append(g[a], b)
	g[b] = append(g[b], a)
	return g
}

// Neighbours returns the neighbour nodes of node n in the graph.
func (g graph) Neighbours(n image.Point) []image.Point {
	return g[n]
}

// nodeDist is our cost function. We use points as nodes, so we
// calculate their Euclidean distance.
func nodeDist(p, q image.Point) float64 {
	d := q.Sub(p)
	return math.Sqrt(float64(d.X*d.X + d.Y*d.Y))
}

Output:

0: (2,3)
1: (1,6)
2: (5,6)

License

This project is free and open source software licensed under the BSD 3-Clause License.

Documentation

Overview

Package astar implements the A* shortest path finding algorithm.

Index

• type CostFunc
• type Graph
• type Path
  • func FindPath[Node comparable](g Graph[Node], start, dest Node, d, h CostFunc[Node]) Path[Node]
  • func (p Path[Node]) Cost(d CostFunc[Node]) (c float64)

Examples

• FindPath
• FindPath (Maze)

Types

type CostFunc

type CostFunc[Node any] func(a, b Node) float64

A CostFunc is a function that returns a cost for the transition from node a to node b.

type Graph

type Graph[Node any] interface {
	// Neighbours returns the neighbour nodes of node n in the graph.
	Neighbours(n Node) []Node
}

The Graph interface is the minimal interface a graph data structure must satisfy to be suitable for the A* algorithm.

type Path

type Path[Node any] []Node

A Path is a sequence of nodes in a graph.

func FindPath

func FindPath[Node comparable](g Graph[Node], start, dest Node, d, h CostFunc[Node]) Path[Node]

FindPath finds the shortest path between start and dest in graph g using the cost function d and the cost heuristic function h.

Example

package main

import (
	"fmt"
	"image"
	"math"

	"github.com/fzipp/astar"
)

func main() {
	// Create a graph with 2D points as nodes
	a := image.Pt(2, 3)
	b := image.Pt(1, 7)
	c := image.Pt(1, 6)
	d := image.Pt(5, 6)
	g := newGraph[image.Point]().link(a, b).link(a, c).link(b, c).link(b, d).link(c, d)

	// Find the shortest path from a to d
	p := astar.FindPath[image.Point](g, a, d, nodeDist, nodeDist)

	// Output the result
	if p == nil {
		fmt.Println("No path found.")
		return
	}
	for i, n := range p {
		fmt.Printf("%d: %s\n", i, n)
	}
}

// nodeDist is our cost function. We use points as nodes, so we
// calculate their Euclidean distance.
func nodeDist(p, q image.Point) float64 {
	d := q.Sub(p)
	return math.Sqrt(float64(d.X*d.X + d.Y*d.Y))
}

// graph is represented by an adjacency list.
type graph[Node comparable] map[Node][]Node

func newGraph[Node comparable]() graph[Node] {
	return make(map[Node][]Node)
}

// link creates a bi-directed edge between nodes a and b.
func (g graph[Node]) link(a, b Node) graph[Node] {
	g[a] = append(g[a], b)
	g[b] = append(g[b], a)
	return g
}

// Neighbours returns the neighbour nodes of node n in the graph.
func (g graph[Node]) Neighbours(n Node) []Node {
	return g[n]
}

Output:

0: (2,3)
1: (1,6)
2: (5,6)

Example (Maze)

package main

import (
	"fmt"
	"image"
	"math"

	"github.com/fzipp/astar"
)

func main() {
	maze := floorPlan{
		"###############",
		"#   # #     # #",
		"# ### ### ### #",
		"#   # # #   # #",
		"### # # # ### #",
		"# # #         #",
		"# # ### ### ###",
		"#   # # # #   #",
		"### # # # # ###",
		"# #       # # #",
		"# # ######### #",
		"#         #   #",
		"# ### # # ### #",
		"#   # # #     #",
		"###############",
	}
	start := image.Pt(1, 13) // Bottom left corner
	dest := image.Pt(13, 1)  // Top right corner

	// Find the shortest path
	path := astar.FindPath[image.Point](maze, start, dest, distance, distance)

	// Mark the path with dots before printing
	for _, p := range path {
		maze.put(p, '.')
	}
	maze.print()
}

// distance is our cost function. We use points as nodes, so we
// calculate their Euclidean distance.
func distance(p, q image.Point) float64 {
	d := q.Sub(p)
	return math.Sqrt(float64(d.X*d.X + d.Y*d.Y))
}

type floorPlan []string

// Neighbours implements the astar.Graph interface
func (f floorPlan) Neighbours(p image.Point) []image.Point {
	offsets := []image.Point{
		image.Pt(0, -1), // North
		image.Pt(1, 0),  // East
		image.Pt(0, 1),  // South
		image.Pt(-1, 0), // West
	}
	res := make([]image.Point, 0, 4)
	for _, off := range offsets {
		q := p.Add(off)
		if f.isFreeAt(q) {
			res = append(res, q)
		}
	}
	return res
}

func (f floorPlan) isFreeAt(p image.Point) bool {
	return f.isInBounds(p) && f[p.Y][p.X] == ' '
}

func (f floorPlan) isInBounds(p image.Point) bool {
	return p.Y >= 0 && p.X >= 0 && p.Y < len(f) && p.X < len(f[p.Y])
}

func (f floorPlan) put(p image.Point, c rune) {
	f[p.Y] = f[p.Y][:p.X] + string(c) + f[p.Y][p.X+1:]
}

func (f floorPlan) print() {
	for _, row := range f {
		fmt.Println(row)
	}
}

Output:

###############
#   # #     #.#
# ### ### ###.#
#   # # #   #.#
### # # # ###.#
# # #  .......#
# # ###.### ###
#   # #.# #   #
### # #.# # ###
# #.....  # # #
# #.######### #
#...      #   #
#.### # # ### #
#.  # # #     #
###############

func (Path[Node]) Cost

func (p Path[Node]) Cost(d CostFunc[Node]) (c float64)

Cost calculates the total cost of path p by applying the cost function d to all path segments and returning the sum.