# massung/pathfind

A generic A* pathfinding algorithm for Go
Go
Switch branches/tags
Nothing to show
 Failed to load latest commit information. README.md Nov 30, 2012 pathfind.go Nov 30, 2012

# A* Pathfinding in Go

This is a simple A* pathfinding solution for Go.

# Installation

``````go get github.com/massung/pathfind
``````

# Usage

``````import "github.com/massung/pathfind"
``````

# Quickstart

The `pathfind` package works by having your data structure implement the `Graph` interface, which is comprised of two functions:

``````type Graph interface {
Neighbors(chan Edge, Node)
H(Node, Node) float32
}
``````

The first of these is a function that - given a channel and a `Node` (an `interface{}`) - will send a list of `Edge` values that represent neighboring nodes that can be traversed to the channel and then close it.

The second is a heuristic function. Given a from `Node` and a goal `Node`, the `H` function should return an approximate cost to traverse that are.

Once you have implemented these two functions, then you should be able to call the `Search` function and get back a list of `Node` values that comprise the optimal path to take.

# Example (a 2D Map)

Since many times A* pathfinding is used for 2D games, this will be an example of using the `pathfind` module for walking a 2D map.

``````// the world will be our node graph
type World struct {
Tiles [10][10]Tile
}

// a simple definition for a node in the graph
type Tile struct {
X, Y int
Cost float32
}

// create a simple heuristic to estimate the cost from A to B
func (w *World) H(from, goal pathfind.Node) float32 {
dx := goal.(*Tile).X - from.(*Tile).X
dy := goal.(*Tile).Y - from.(*Tile).Y

// distance squared...
return float32(dx * dx + dy * dy)
}

// write all the edges to a channel
func (w *World) Neighbors(ns chan pathfind.Edge, node pathfind.Node) {
edges := make([]pathfind.Edge, 0, 8)
tile := node.(*Tile)

// look in the 4 cardinal directions...
if tile.X > 0 {
ns <- pathfind.Edge{
Node: &w.Tiles[tile.X - 1][tile.Y],
Cost: w.Tiles[tile.X - 1][tile.Y].Cost,
}
}

/* TODO: look at the other 3 directions as well... */

close ns
}
``````

Now that we have our basic node graph, node definition, a heuristic function, and a function that can return a list of neighbors for any given "node" on the graph, we can now perform simple searches.

``````// get a starting and ending node for the path
start := &world.Tile[0][0]
goal := &world.Tile[9][9]

// perform the search...
path, found := pathfind.Search(world, start, goal)

// make sure there was a path found
if found {
for _, node := range path {
tile := node.(*Tile)

/* TODO: traverse each tile in the world... */
}
}
``````