pathfinder

README

Modified go-astar library

original repo https://github.com/beefsack/go-astar

Documentation

Index

• Constants
• Variables
• func ConstructMap2dArray(width int, height int, obstacleDensity float64) [][]string
• func DeepCopy2DArr(input [][]string) [][]string
• func SamePos(pos1 Pos, pos2 Pos) bool
• type Pather
  • func AstarPathfinder(start, end Pos, worldMap World) (path []Pather, distance float64, found bool)
  • func Path(from, to Pather) (path []Pather, distance float64, found bool)
• type Pos
• type Tile
  • func (t *Tile) PathEstimatedCost(to Pather) float64
  • func (t *Tile) PathNeighborCost(to Pather) float64
  • func (t *Tile) PathNeighbors(cacheLayer World) []Pather
• type World
  • func ConstructWorldNew(input [][]string, ignoreObstacles bool) World
  • func DeepCopyWorld(input World) World
  • func ParseWorld(input string) World
  • func (w World) FirstOfKind(kind int) *Tile
  • func (w World) From() *Tile
  • func (w World) RenderPath(path []Pather) string
  • func (w World) SetFrom(x, y int)
  • func (w World) SetTile(t *Tile, x, y int)
  • func (w World) SetTileWorldRef(x, y int, worldRef World)
  • func (w World) SetTo(x, y int)
  • func (w World) Tile(x, y int) *Tile
  • func (w World) To() *Tile

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 (
	// mark that the grid space is traversable
	EmptySlotSymbol = "."

	// mark that the grid space is not traversable
	ObstacleSymbol = "X"
)

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.

var TerrainMap = map[string]int{
	".": KindPlain,
	"~": KindRiver,
	"M": KindMountain,
	"X": KindBlocker,
	"F": KindFrom,
	"T": KindTo,
}

Functions

func ConstructMap2dArray

func ConstructMap2dArray(width int, height int, obstacleDensity float64) [][]string

TODO: make this more efficient

func DeepCopy2DArr

func DeepCopy2DArr(input [][]string) [][]string

func SamePos

func SamePos(pos1 Pos, pos2 Pos) bool

function to check if two positions are the same

Types

type Pather

type Pather interface {
	// PathNeighbors returns the direct neighboring nodes of this node which
	// can be pathed to.
	PathNeighbors(cacheLayer World) []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.

func AstarPathfinder

func AstarPathfinder(start, end Pos, worldMap World) (path []Pather, distance float64, found bool)

func Path

func Path(from, to Pather) (path []Pather, distance float64, found bool)

original astar implementation Path calculates a short path and the distance between the two Pather nodes. If no path is found, found will be false.

type Pos

type Pos struct {
	X int `json:"X"`
	Y int `json:"Y"`
}

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
}

func (*Tile) PathEstimatedCost

func (t *Tile) PathEstimatedCost(to Pather) float64

PathEstimatedCost uses Manhattan distance to estimate orthogonal distance between non-adjacent nodes.

func (*Tile) PathNeighborCost

func (t *Tile) PathNeighborCost(to Pather) float64

PathNeighborCost returns the movement cost of the directly neighboring tile.

func (*Tile) PathNeighbors

func (t *Tile) PathNeighbors(cacheLayer World) []Pather

PathNeighbors returns the neighbors of the tile, excluding blockers and tiles off the edge of the board.

type World

type World map[int]map[int]*Tile

func ConstructWorldNew

func ConstructWorldNew(input [][]string, ignoreObstacles bool) World

Constructs new World for pathfinding. Note: ignoreObstacles is false by default, and true only for planes and other obstacle-ignoring units

func DeepCopyWorld

func DeepCopyWorld(input World) World

func ParseWorld

func ParseWorld(input string) World

ParseWorld parses a textual representation of a world into a world map.

func (World) FirstOfKind

func (w World) FirstOfKind(kind int) *Tile

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) From

func (w World) From() *Tile

From gets the from tile from the world.

func (World) RenderPath

func (w World) RenderPath(path []Pather) string

RenderPath renders a path on top of a world.

func (World) SetFrom

func (w World) SetFrom(x, y int)

set "from" point

func (World) SetTile

func (w World) SetTile(t *Tile, x, y int)

SetTile sets a tile at the given coordinates in the world.

func (World) SetTileWorldRef

func (w World) SetTileWorldRef(x, y int, worldRef World)

func (World) SetTo

func (w World) SetTo(x, y int)

set "to" point

func (World) Tile

func (w World) Tile(x, y int) *Tile

Tile gets the tile at the given coordinates in the world.

func (World) To

func (w World) To() *Tile

To gets the to tile from the world.