paths

package module
v0.0.0-...-5c2bf4e Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 8, 2023 License: MIT Imports: 6 Imported by: 0

README

paths3D

What is paths3D?

paths3D is a pathfinding library written in Golang. Its main feature is simple best-first and shortest-cost path finding.

Fork goals

This is a fork form SolarLune's paths path finding library. The fork aims at adding a third dimension to the pathfinding system: height. Each cell will have a specific height level. By default, the pathfinding only can go 1 height unit up per cell. And can drop down infinite Blocks. Configuration is planned ;)

Fork Status

Feature State
Height Pathfinding
Add pathfinding with heiht levels		 Finished
Step Heights
Make the height that can be stepped up configurable		 Finished
Drop Heights
Make the height that can be dropped down at once configurable		 Finished

Why did you create paths3D?

I was doing day 12 of the AoC and was wondering if there is a simple and straight-forward pathfinding library for this. I couldn't find a lib for this use-case, so I decided to create one. Because I didn't want to start from scratch, so I decided to fork the existing paths lib and extend it with a height level.

How do I install it?

Just go get it:

go get github.com/Simzahn001/paths3D

How do I use it?

Basically paths3D is based on a grid with cells. Each cell does have a position, walkability and height. Further you can specify a cost; lower price cells will be preferred during the path finding process.

To find a detailed and explained example to start, please take a look at the how-to.md.

Here is a whole example of the lib:


import "github.com/Simzahn001/paths3D"

func Init() {
	
    //create a grid with a string array
    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",
    }
    grid := paths.NewGridFromStringArrays(layout)

    // After creating the Grid, you can edit it using the Grid's functions. In this case, we make the
	// cells to "walls". Note that here, we're using 'x' to get Cells that have the rune for the lowercase
	//x character 'x', not the string "x".
    grid.SetWalkable('x', false)

    // You can also loop through them by using the `GetCells` functions thusly...
    for _, goop := range grid.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 next two Parameters
	// specify the maximum height that can be stepped up at once and the maximum height that can be dropped down at once.
	// The last two parameters are settings for diagonal movement between two cells.
    grid := GameMap.GetPathFromCell(GameMap.Get(1, 1), GameMap.Get(6, 3), 1, 5 false, 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().
	
}

Dependencies?

For the actual package, there are no external dependencies.

SolarLune's path docs:

GoDocs

Documentation

Overview

Package paths3D is a simple library written in Go made to handle 3D pathfinding. All you need to do is generate a Grid, specify which cells aren't walkable and what height the cells are, optionally change the cost on specific cells, and finally get a path from one cell to another. For a simple guide, take a look at how-to.md in the github repo: https://github.com/Simzahn001/paths3D

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Cell 

type Cell struct {
	X, Y, HeightLevel int
	Cost              float64
	Walkable          bool
	Rune              rune
}

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, a Rune, which indicates which rune character the Cell is represented by, and a HeightLevel (default: 0), which represents the height of this cell.

func (Cell) String 

func (cell Cell) String() string

type Grid 

type Grid struct {
	Data [][]*Cell
}

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 

func NewGrid(gridWidth, gridHeight int) *Grid

NewGrid returns a new Grid of (gridWidth x gridHeight) size.

func NewGridFromRuneArrays 

func NewGridFromRuneArrays(arrays [][]rune) *Grid

NewGridFromRuneArrays creates a Grid map from a 2D array of runes. Each individual Rune becomes a Cell in the resulting Grid.

func NewGridFromStringArrays 

func NewGridFromStringArrays(arrays []string) *Grid

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.

func (*Grid) AddHeightMap 

func (m *Grid) AddHeightMap(profile map[rune]int)

AddHeightMap adds a height to the grid via a key-value map. All runes, the map contains, do have an assigned height. This height is applied to ALL cells with this rune. After the execution of this method, letters aren't bound to the height; they are no pointers. If you change a letter, the height will stay the same. Keep in mind, that cell runes are case-sensitive.

func (*Grid) AllCells 

func (m *Grid) AllCells() []*Cell

AllCells returns a single slice of pointers to all Cells contained in the Grid's 2D Data array.

func (*Grid) CellsByCost 

func (m *Grid) CellsByCost(cost float64) []*Cell

CellsByCost returns a slice of pointers to Cells that all have the Cost value provided.

func (*Grid) CellsByHeightLevel 

func (m *Grid) CellsByHeightLevel(heightLevel int) []*Cell

CellsByHeightLevel returns a slice of pointers to Cells that all have the height level provided.

func (*Grid) CellsByRune 

func (m *Grid) CellsByRune(char rune) []*Cell

CellsByRune returns a slice of pointers to Cells that all have the character provided.

func (*Grid) CellsByWalkable 

func (m *Grid) CellsByWalkable(walkable bool) []*Cell

CellsByWalkable returns a slice of pointers to Cells that all have the Cost value provided.

func (*Grid) DataAsRuneArrays 

func (m *Grid) DataAsRuneArrays() [][]rune

DataAsRuneArrays returns a 2D array of runes for each Cell in the Grid. The first axis is the Y axis.

func (*Grid) DataAsStringArray 

func (m *Grid) DataAsStringArray() []string

DataAsStringArray returns a 2D array of runes for each Cell in the Grid. The first axis is the Y axis.

func (*Grid) DataToString 

func (m *Grid) DataToString() string

DataToString returns a string, used to easily identify the Grid map.

func (*Grid) Get 

func (m *Grid) Get(x, y int) *Cell

Get returns a pointer to the Cell in the x and y position provided.

func (*Grid) GetAverageHeight 

func (m *Grid) GetAverageHeight() float64

GetAverageHeight returns the average height over all the Grid. Use math.Round to get an int

func (*Grid) GetHeightLevels 

func (m *Grid) GetHeightLevels() []int

GetHeightLevels returns a list of all different height levels. use len() on the returned slice to get the amount of different height levels

func (*Grid) GetMaxHeight 

func (m *Grid) GetMaxHeight() int

GetMaxHeight returns the maximum height of the whole Grid

func (*Grid) GetMinHeight 

func (m *Grid) GetMinHeight() int

GetMinHeight returns the minimum height of the whole Grid

func (*Grid) GetPath 

func (m *Grid) GetPath(startX, startY, endX, endY float64, stepHeight, dropHeight int, diagonals, wallsBlockDiagonals bool) *Path

GetPath returns a Path, from the starting cell's X and Y to the ending cell's X and Y. 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 

func (m *Grid) GetPathFromCells(start, dest *Cell, stepHeight, dropHeight int, diagonals, wallsBlockDiagonals bool) *Path

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. If stepHeight and/or dropHeight are negative, they will not be used in the calculation -> infinite drop and/or step height

func (*Grid) GetPathFromSettings 

func (m *Grid) GetPathFromSettings(settings PathSettings) *Path

GetPathFromSettings returns a Path, from the starting Cell to the ending Cell. The starting and ending Cells as well as the other parameters (stepHeight, dropHeight, diagonals, wallsBlockDiagonals) are read from the passed PathSettings object.

func (*Grid) Height 

func (m *Grid) Height() int

Height returns the height of the Grid map.

func (*Grid) SetCost 

func (m *Grid) SetCost(char rune, cost float64)

SetCost sets the movement cost across all cells in the Grid with the specified rune.

func (*Grid) SetHeightLevel 

func (m *Grid) SetHeightLevel(char rune, heightLevel int)

SetHeightLevel sets the height level for all cells in the Grid with the specified rune.

func (*Grid) SetWalkable 

func (m *Grid) SetWalkable(char rune, walkable bool)

SetWalkable sets walkability across all cells in the Grid with the specified rune.

func (*Grid) Visualise 

func (m *Grid) Visualise() (visualisation []string, error error)

Visualise return a string visualisation of the grid's cell heights. Not walkable blocks are represented by a blank space. An error is returned if there are more than 26 height levels. The heightmap is filled though, but every layer after the 26th is still visualised with the letter 'z'

func (*Grid) VisualisePath 

func (m *Grid) VisualisePath(path *Path) []string

func (*Grid) Width 

func (m *Grid) Width() int

Width returns the width of the Grid map.

type Node 

type Node struct {
	Cell   *Cell
	Parent *Node
	Cost   float64
}

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 

type Path struct {
	Cells                    []*Cell
	CurrentIndex, StepHeight int
}

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

func (p *Path) Advance()

Advance advances the path by one cell.

func (*Path) Current 

func (p *Path) Current() *Cell

Current returns the current Cell in the Path.

func (*Path) Get 

func (p *Path) Get(index int) *Cell

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 

func (p *Path) Index(cell *Cell) int

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

func (p *Path) IsAtEnd() bool

IsAtEnd returns if the Path's current index is the last Cell in the Path.

func (*Path) IsAtStart 

func (p *Path) IsAtStart() bool

IsAtStart returns if the Path's current index is 0, the first Cell in the Path.

func (*Path) Length 

func (p *Path) Length() int

Length returns the length of the Path (how many Cells are in the Path).

func (*Path) Next 

func (p *Path) Next() *Cell

Next returns the next cell in the path. If the Path is at the end, Next() returns nil.

func (*Path) Prev 

func (p *Path) Prev() *Cell

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

func (p *Path) Reverse()

Reverse reverses the Cells in the Path.

func (*Path) Same 

func (p *Path) Same(otherPath *Path) bool

Same returns if the Path shares the exact same cells as the other specified Path.

func (*Path) SetIndex 

func (p *Path) SetIndex(index int)

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.

func (*Path) TotalCost 

func (p *Path) TotalCost() float64

TotalCost returns the total cost of the Path (i.e. is the sum of all the Cells in the Path).

type PathSettings 

type PathSettings struct {
	// contains filtered or unexported fields
}

PathSettings represents the settings used when finding a path. See Grid.GetPath for more information on each setting. Create a path with Grid.GetPathFromSettings.

func NewDefaultPathSettings 

func NewDefaultPathSettings(startCell, endCell *Cell) *PathSettings

NewDefaultPathSettings returns a new PathSettings struct with default values.

Default values:

  • StepHeight: 1
  • DropHeight: 1
  • Diagonals: true
  • WallBlocksDiagonals: true

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.