README
¶
A* 寻路算法
A*算法，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。
Documentation
¶
Index ¶
Constants ¶
const ( // KindPlain (.) is a plain tile with a movement cost of 1. KindPlain = iota // KindRiver (~) is a river tile with a movement cost of 2. KindRiver // KindMountain (M) is a mountain tile with a movement cost of 3. KindMountain // KindBlocker (X) is a tile which blocks movement. KindBlocker // KindFrom (F) is a tile which marks where the path should be calculated // from. KindFrom // KindTo (T) is a tile which marks the goal of the path. KindTo // KindPath (●) is a tile to represent where the path is in the output. KindPath )
Kind* constants refer to tile kinds for input and output.
Variables ¶
var KindCosts = map[int]float64{ KindPlain: 1.0, KindFrom: 1.0, KindTo: 1.0, KindRiver: 2.0, KindMountain: 3.0, }
KindCosts map tile kinds to movement costs.
var KindRunes = map[int]rune{ KindPlain: '.', KindRiver: '~', KindMountain: 'M', KindBlocker: 'X', KindFrom: 'F', KindTo: 'T', KindPath: '●', }
KindRunes map tile kinds to output runes.
var RuneKinds = map[rune]int{ '.': KindPlain, '~': KindRiver, 'M': KindMountain, 'X': KindBlocker, 'F': KindFrom, 'T': KindTo, }
RuneKinds map input runes to tile kinds.
Functions ¶
This section is empty.
Types ¶
type Goreland ¶
type Goreland struct {
}
func (Goreland) RenderPath ¶
RenderPath renders a path on top of a Goreland world.
type Pather ¶
type Pather interface {
// PathNeighbors returns the direct neighboring nodes of this node which
// can be pathed to.
PathNeighbors() []Pather
// PathNeighborCost calculates the exact movement cost to neighbor nodes.
PathNeighborCost(to Pather) float64
// PathEstimatedCost is a heuristic method for estimating movement costs
// between non-adjacent nodes.
PathEstimatedCost(to Pather) float64
}
Pather is an interface which allows A* searching on arbitrary objects which can represent a weighted graph.
type Tile ¶
type Tile struct {
// Kind is the kind of tile, potentially affecting movement.
Kind int
// X and Y are the coordinates of the tile.
X, Y int
// W is a reference to the World that the tile is a part of.
W World
}
A Tile is a tile in a grid which implements Pather.
func (*Tile) PathEstimatedCost ¶
PathEstimatedCost uses Manhattan distance to estimate orthogonal distance between non-adjacent nodes.
func (*Tile) PathNeighborCost ¶
PathNeighborCost returns the movement cost of the directly neighboring tile.
func (*Tile) PathNeighbors ¶
PathNeighbors returns the neighbors of the tile, excluding blockers and tiles off the edge of the board.
type Truck ¶
type Truck struct {
// X and Y are the coordinates of the truck.
X, Y int
// contains filtered or unexported fields
}
A Truck is a Truck in a grid which implements Grapher.
func (*Truck) PathEstimatedCost ¶
PathEstimatedCost uses Manhattan distance to estimate orthogonal distance between non-adjacent nodes.
func (*Truck) PathNeighborCost ¶
PathNeighborCost returns the cost of the tube leading to Truck.
func (*Truck) PathNeighbors ¶
PathNeighbors returns the neighbors of the Truck
type World ¶
World is a two dimensional map of Tiles.
func ParseWorld ¶
ParseWorld parses a textual representation of a world into a world map.
func (World) FirstOfKind ¶
FirstOfKind gets the first tile on the board of a kind, used to get the from and to tiles as there should only be one of each.
func (World) RenderPath ¶
RenderPath renders a path on top of a world.
Source Files