README
¶
astar
A small package that implements the A* (A star) pathfinding algorithm.
Example
import (
"fmt"
"github.com/sperre/astar"
)
func main() {
// If your map is something more than 2D matrix then you might want to modify adjacentNodes
map_data := astar.GetMapFromImage(test.png)
// Returns a list of nodes from start to stop avoiding all, obstacles if possible
startx, starty := 0, 0
stopx, stopy := 99, 99
dir8 := false // Use 4 directions, not 8
shortest_path := astar.Astar(map_data, startx, starty, stopx, stopy, dir8)
}
Origin
This library was developed for Eurobot-NTNU 2012, based on code from: https://github.com/humanfromearth/gopathfinding
Compared to the original library, our version was benchmarked to run approximately 27x faster.
Documentation
¶
Index ¶
- Constants
- func Heuristic(tile, stop *Node) (h int)
- type Graph
- type MapData
- type Node
- type PriorityQueue
- func (pq PriorityQueue) Len() int
- func (pq PriorityQueue) Less(i, j int) bool
- func (pq *PriorityQueue) Pop() interface{}
- func (pq *PriorityQueue) PopNode() *Node
- func (pq *PriorityQueue) Push(x interface{})
- func (pq *PriorityQueue) PushNode(n *Node)
- func (pq *PriorityQueue) RemoveNode(n *Node)
- func (pq PriorityQueue) Swap(i, j int)
Constants ¶
const ( LAND = 1 << iota WALL )
Tile information
const ( COST_STRAIGHT = 1000 COST_DIAGONAL = 1414 )
Tile movement cotsts
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
Start, stop nodes and a slice of nodes
type MapData ¶
type MapData [][]int
func GetMapFromImage ¶
func NewMapData ¶
Return a new MapData by value given some dimensions
type Node ¶
type Node struct {
X, Y int
// contains filtered or unexported fields
}
X and Y are coordinates, parent is a link to where we came from. cost are the estimated cost from start along the best known path. h is the heuristic value (air line distance to goal).
func Astar ¶
A* search algorithm. See http://en.wikipedia.org/wiki/A*_search_algorithm
type PriorityQueue ¶
type PriorityQueue []*Node
A PriorityQueue implements heap.Interface and holds Items.
func (PriorityQueue) Less ¶
func (pq PriorityQueue) Less(i, j int) bool
func (*PriorityQueue) Pop ¶
func (pq *PriorityQueue) Pop() interface{}
func (*PriorityQueue) PopNode ¶
func (pq *PriorityQueue) PopNode() *Node
func (*PriorityQueue) PushNode ¶
func (pq *PriorityQueue) PushNode(n *Node)
func (*PriorityQueue) RemoveNode ¶
func (pq *PriorityQueue) RemoveNode(n *Node)
func (PriorityQueue) Swap ¶
func (pq PriorityQueue) Swap(i, j int)
Source Files