README
¶
paths
What is paths?
paths is a pathfinding library written in Golang created mainly for video games. Its main feature is simple best-first and shortest-cost path finding.
Why is it called that?
Because I finally learned how to spell.
Why did you create paths?
Because I needed to do pathfinding for a game and couldn't really find any pre-made Golang libraries that seemed to do this, so... Yet again, here we are.
How do I install it?
Just go get it:
go get github.com/SolarLune/paths
How do I use it?
paths is based around defining a Grid, which consists of a rectangular series of Cells. Each Cell occupies a single X and Y position in space, and has a couple of properties that influence pathfinding, which are Cost and Walkability. If a Cell isn't walkable, then it is considered an obstacle that paths generated must circumvent. All Cells default to a Cost of 1; pathfinding will prioritize lower-cost Cells.
import "github.com/SolarLune/paths"
func Init() {
// This line creates a new Grid, comprised (internally) of Cells. The size is 10x10. Each Cell's
// "world" size is 16x16. By default, all Cells are walkable, have a cost of 1, and a blank rune
// of ' ' associated with them.
firstMap = paths.NewGrid(10, 10, 16, 16)
// You can also create the Grid from an array of strings (which are interpreted as arrays of runes),
// if you already have it:
layout := []string{
"xxxxxxxxxx",
"x x",
"x xxxxxx x",
"x xg x x",
"x xgxx x x",
"x gggx x x",
"x xxxx x",
"x xgg x x",
"xg ggx x x",
"xxxxxxxxxx",
}
secondMap := paths.NewGridFromStringArrays(layout, 16, 16)
// After creating the Grid, you can edit it using the Grid's functions. Note that here, we're using 'x'
// to get Cells that have the rune for the lowercase x character 'x', not the string "x".
firstMap.SetWalkable('x', false)
// You can also loop through them by using the `GetCells` functions thusly...
for _, goop := range secondMap.GetCellsByRune('g') {
goop.Cost = 5
}
// This gets a new Path from the Cell occupied by a starting position [24, 21], to another [99, 78]. The last boolean argument,
// false, indicates whether moving diagonally is fine when creating the Path.
firstPath := GameMap.GetPath(24, 21, 99, 78, false)
// You can also get a path using references to the Cells directly.
secondPath := GameMap.GetPathFromCell(GameMap.Get(1, 1), GameMap.Get(6, 3), false)
// After that, you can use Path.Current() and Path.Next() to get the current and next Cells on the Path. When you determine that
// the pathfinding agent has reached that Cell, you can kick the Path forward with path.Advance().
// And that's it!
}
And that's about it! If you want to see more info or examples, feel free to examine the main.go and world.go tests to see how the test is set up.
You can check out the GoDoc link here, as well.
You can also run the example by installing SDL with the instructions here and then:
$ cd ./example
$ go run ./
Dependencies?
For the actual package, there are no external dependencies.
For the tests, paths requires veandco's sdl2 port to create the window, handle input, and draw the shapes and text.
Shout-out Time!
Props to whoever made arcadepi.ttf! It's a nice font.
Thanks a lot to the SDL2 team for development.
Thanks to veandco for maintaining the Golang SDL2 port, as well!
Documentation
¶
Overview ¶
Package paths is a simple library written in Go made to handle 2D pathfinding for games. All you need to do is generate a Grid, specify which cells aren't walkable, optionally change the cost on specific cells, and finally get a path from one cell to another.
Index ¶
- func DiaganalDistance(start, dest *Cell) float64
- func ManhattenDistance(start, dest *Cell) float64
- type Cell
- type Grid
- func (m *Grid) AllCells() []*Cell
- func (m *Grid) CellsByCost(cost float64) []*Cell
- func (m *Grid) CellsByRune(char rune) []*Cell
- func (m *Grid) CellsByWalkable(walkable bool) []*Cell
- func (m *Grid) DataAsRuneArrays() [][]rune
- func (m *Grid) DataAsStringArray() []string
- func (m *Grid) DataToString() string
- func (m *Grid) Get(x, y int) *Cell
- func (m *Grid) GetPath(startX, startY, endX, endY float64, diagonals bool, wallsBlockDiagonals bool) *Path
- func (m *Grid) GetPathFromCells(start, dest *Cell, diagonals, wallsBlockDiagonals bool) *Path
- func (m *Grid) GetPathFromCellsAStar(start, dest *Cell, diagonals, wallsBlockDiagonals bool) *Path
- func (m *Grid) GridToWorld(x, y int) (float64, float64)
- func (m *Grid) Height() int
- func (m *Grid) SetCost(char rune, cost float64)
- func (m *Grid) SetWalkable(char rune, walkable bool)
- func (m *Grid) Width() int
- func (m *Grid) WorldToGrid(x, y float64) (int, int)
- type Node
- type Path
- func (p *Path) Advance()
- func (p *Path) AtEnd() bool
- func (p *Path) AtStart() bool
- func (p *Path) Current() *Cell
- func (p *Path) Get(index int) *Cell
- func (p *Path) Index(cell *Cell) int
- func (p *Path) Length() int
- func (p *Path) Next() *Cell
- func (p *Path) Prev() *Cell
- func (p *Path) Restart()
- func (p *Path) Reverse()
- func (p *Path) Same(otherPath *Path) bool
- func (p *Path) SetIndex(index int)
- func (p *Path) String() string
- func (p *Path) TotalCost() float64
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DiaganalDistance ¶
DiaganalDistance heuristic for when diaganol movement is allowed.
func ManhattenDistance ¶
ManhattenDistance heuristic for a simple four directional movement.
Types ¶
type Cell ¶
A Cell represents a point on a Grid map. It has an X and Y value for the position, a Cost, which influences which Cells are ideal for paths, Walkable, which indicates if the tile can be walked on or should be avoided, and a Rune, which indicates which rune character the Cell is represented by.
type Grid ¶
Grid represents a "map" composed of individual Cells at each point in the map. Data is a 2D array of Cells. CellWidth and CellHeight indicate the size of Cells for Cell Position <-> World Position translation.
func NewGrid ¶
NewGrid returns a new Grid of (gridWidth x gridHeight) size. cellWidth and cellHeight changes the size of each Cell in the Grid. This is used to translate world position to Cell positions (i.e. the Cell position [2, 5] with a CellWidth and CellHeight of [16, 16] would be the world positon [32, 80]).
func NewGridFromRuneArrays ¶
NewGridFromRuneArrays creates a Grid map from a 2D array of runes. Each individual Rune becomes a Cell in the resulting Grid. cellWidth and cellHeight changes the size of each Cell in the Grid. This is used to translate world position to Cell positions (i.e. the Cell position [2, 5] with a CellWidth and CellHeight of [16, 16] would be the world positon [32, 80]).
func NewGridFromStringArrays ¶
NewGridFromStringArrays creates a Grid map from a 1D array of strings. Each string becomes a row of Cells, each with one rune as its character. cellWidth and cellHeight changes the size of each Cell in the Grid. This is used to translate world position to Cell positions (i.e. the Cell position [2, 5] with a CellWidth and CellHeight of [16, 16] would be the world positon [32, 80]).
func (*Grid) AllCells ¶
AllCells returns a single slice of pointers to all Cells contained in the Grid's 2D Data array.
func (*Grid) CellsByCost ¶
CellsByCost returns a slice of pointers to Cells that all have the Cost value provided.
func (*Grid) CellsByRune ¶
CellsByRune returns a slice of pointers to Cells that all have the character provided.
func (*Grid) CellsByWalkable ¶
CellsByWalkable returns a slice of pointers to Cells that all have the Cost value provided.
func (*Grid) DataAsRuneArrays ¶
DataAsRuneArrays returns a 2D array of runes for each Cell in the Grid. The first axis is the Y axis.
func (*Grid) DataAsStringArray ¶
DataAsStringArray returns a 2D array of runes for each Cell in the Grid. The first axis is the Y axis.
func (*Grid) DataToString ¶
DataToString returns a string, used to easily identify the Grid map.
func (*Grid) GetPath ¶
func (m *Grid) GetPath(startX, startY, endX, endY float64, diagonals bool, wallsBlockDiagonals bool) *Path
GetPath returns a Path, from the starting world X and Y position to the ending X and Y position. diagonals controls whether moving diagonally is acceptable when creating the Path. wallsBlockDiagonals indicates whether to allow diagonal movement "through" walls that are positioned diagonally. This is essentially just a smoother way to get a Path from GetPathFromCells().
func (*Grid) GetPathFromCells ¶
GetPathFromCells returns a Path, from the starting Cell to the destination Cell. diagonals controls whether moving diagonally is acceptable when creating the Path. wallsBlockDiagonals indicates whether to allow diagonal movement "through" walls that are positioned diagonally.
func (*Grid) GetPathFromCellsAStar ¶
GetPathFromCellsAStar returns a Path, from the starting Cell to the destination Cell. diagonals controls whether moving diagonally is acceptable when creating the Path. wallsBlockDiagonals indicates whether to allow diagonal movement "through" walls that are positioned diagonally.
func (*Grid) GridToWorld ¶
GridToWorld converts from a grid position to world position, multiplying the value by the CellWidth and CellHeight of the Grid.
func (*Grid) SetCost ¶
SetCost sets the movement cost across all cells in the Grid with the specified rune.
func (*Grid) SetWalkable ¶
SetWalkable sets walkability across all cells in the Grid with the specified rune.
type Node ¶
Node represents the node a path, it contains the cell it represents. Also contains other information such as the parent and the cost.
type Path ¶
A Path is a struct that represents a path, or sequence of Cells from point A to point B. The Cells list is the list of Cells contained in the Path, and the CurrentIndex value represents the current step on the Path. Using Path.Next() and Path.Prev() advances and walks back the Path by one step.
func (*Path) AtStart ¶
AtStart returns if the Path's current index is 0, the first Cell in the Path.
func (*Path) Get ¶
Get returns the Cell of the specified index in the Path. If the index is outside of the length of the Path, it returns -1.
func (*Path) Index ¶
Index returns the index of the specified Cell in the Path. If the Cell isn't contained in the Path, it returns -1.
func (*Path) Next ¶
Next returns the next cell in the path. If the Path is at the end, Next() returns nil.
func (*Path) Prev ¶
Prev returns the previous cell in the path. If the Path is at the start, Prev() returns nil.
func (*Path) Restart ¶
func (p *Path) Restart()
Restart restarts the Path, so that calling path.Current() will now return the first Cell in the Path.
func (*Path) Same ¶
Same returns if the Path shares the exact same cells as the other specified Path.
func (*Path) SetIndex ¶
SetIndex sets the index of the Path, allowing you to safely manually manipulate the Path as necessary. If the index exceeds the bounds of the Path, it will be clamped.
Source Files