path_finding

package module
v0.0.0-...-9b40a58 Latest Latest
Warning

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

 Go to latest Published: Feb 19, 2024 License: Apache-2.0 Imports: 9 Imported by: 0

README

go-pathfinding

原生go语言写的寻路算法库

Documentation

Index

Constants

View Source 
const (
	DescAStar               = "AStar"
	DescIdaStar             = "Ida star"
	DescBreadthFirstSearch  = "Breadth First Search"
	DescBestFirstSearch     = "Best First Search"
	DescDijkstra            = "Dijkstra"
	DescJumpPointSearch     = "Jump Point Search"
	DescOrthogonalJumpPoint = "Orthogonal Jump Point"
)
View Source 
const (
	DescHeuristicManhattan = "Manhattan "
	DescHeuristicEuclidean = "Euclidean "
	DescHeuristicOctile    = "Octile"
	DescHeuristicChebyshev = "Chebyshev"
)

Variables

This section is empty.

Functions

func GridFromString 

func GridFromString(str string) (grid *Grid, startNode, endNode *GridNode)

Types

type DebugTrace 

type DebugTrace interface {
	SetPathHandle(fn func(v *TracePoint))
	TracePath(x, y int, isJumpPoint bool) bool
	Wait()
	Exit()
	Start()
	Pause()
}

func NewDebugTrace 

func NewDebugTrace() DebugTrace

type DiagonalMovement 

type DiagonalMovement int
const (
	DiagonalMovementNone                DiagonalMovement = 0
	DiagonalMovementAlways              DiagonalMovement = 1
	DiagonalMovementNever               DiagonalMovement = 2
	DiagonalMovementIfAtMostOneObstacle DiagonalMovement = 3
	DiagonalMovementOnlyWhenNoObstacles DiagonalMovement = 4
)

type Grid 

type Grid struct {
	Width  int
	Height int
	Nodes  map[int64]*GridNode //key :x|y,value:node
	Config *PathFindingConfig
}

地图

func NewGrid 

func NewGrid(Width int, Height int, options ...PathFindingConfigOptions) *Grid

func NewGridWithConfig 

func NewGridWithConfig(Width int, Height int, cfg *PathFindingConfig) *Grid

func (*Grid) Clone 

func (grid *Grid) Clone() *Grid

func (*Grid) JPFAlwaysMoveDiagonallyFind 

func (grid *Grid) JPFAlwaysMoveDiagonallyFind(node *GridNodeInfo) (neighbors []*GridNode)

func (*Grid) JPFAlwaysMoveDiagonallyJump 

func (grid *Grid) JPFAlwaysMoveDiagonallyJump(
	x, y, px, py int, endNode *GridNode,
) (jumpPoint *GridNode)

func (*Grid) JPFMoveDiagonallyIfAtMostOneObstacleFind 

func (grid *Grid) JPFMoveDiagonallyIfAtMostOneObstacleFind(node *GridNodeInfo) (neighbors []*GridNode)

func (*Grid) JPFMoveDiagonallyIfAtMostOneObstacleJump 

func (grid *Grid) JPFMoveDiagonallyIfAtMostOneObstacleJump(x, y, px, py int, endNode *GridNode) (jumpPoint *GridNode)

func (*Grid) JPFMoveDiagonallyIfNoObstaclesFind 

func (grid *Grid) JPFMoveDiagonallyIfNoObstaclesFind(node *GridNodeInfo) (neighbors []*GridNode)

func (*Grid) JPFMoveDiagonallyIfNoObstaclesJump 

func (grid *Grid) JPFMoveDiagonallyIfNoObstaclesJump(x, y, px, py int, endNode *GridNode) (jumpPoint *GridNode)

func (*Grid) PathFindingAStar 

func (grid *Grid) PathFindingAStar(startX, startY, endX, endY int) (res []*PathPoint)

A*算法

func (*Grid) PathFindingBestFirst 

func (grid *Grid) PathFindingBestFirst(startX, startY, endX, endY int) (res []*PathPoint)

func (*Grid) PathFindingBiAStar 

func (grid *Grid) PathFindingBiAStar(startX, startY, endX, endY int) (res []*PathPoint)

func (*Grid) PathFindingBiBestFirst 

func (grid *Grid) PathFindingBiBestFirst(startX, startY, endX, endY int) (res []*PathPoint)

func (*Grid) PathFindingBiBreadthFirst 

func (grid *Grid) PathFindingBiBreadthFirst(startX, startY, endX, endY int) (res []*PathPoint)

func (*Grid) PathFindingBiDijkstra 

func (grid *Grid) PathFindingBiDijkstra(startX, startY, endX, endY int) (res []*PathPoint)

func (*Grid) PathFindingBreadthFirst 

func (grid *Grid) PathFindingBreadthFirst(startX, startY, endX, endY int) (res []*PathPoint)

func (*Grid) PathFindingDijkstra 

func (grid *Grid) PathFindingDijkstra(startX, startY, endX, endY int) (res []*PathPoint)

func (*Grid) PathFindingIdaStar 

func (grid *Grid) PathFindingIdaStar(startX, startY, endX, endY int) (res []*PathPoint)

func (*Grid) PathFindingJumpPoint 

func (grid *Grid) PathFindingJumpPoint(startX, startY, endX, endY int) (res []*PathPoint)

func (*Grid) PathFindingPrint 

func (grid *Grid) PathFindingPrint(cmd PathFindingType, startX, startY, endX, endY int)

func (*Grid) PathFindingRoute 

func (grid *Grid) PathFindingRoute(cmd PathFindingType) (cmdFunc PathFindingCmd)

func (*Grid) PrintMap 

func (grid *Grid) PrintMap()

终端打印地图

func (*Grid) SetWalkableAt 

func (grid *Grid) SetWalkableAt(X int, Y int, Walkable bool)

func (*Grid) TraceJumpPointPath 

func (grid *Grid) TraceJumpPointPath(node *GridNode) bool

func (*Grid) TracePath 

func (grid *Grid) TracePath(node *GridNode) bool

type GridNode 

type GridNode struct {
	X        int
	Y        int
	Walkable bool //是否可以行走
}

一个格子存储的对象

func NewNode 

func NewNode(X int, Y int, Walkable bool) *GridNode

func (*GridNode) ToGridNodeInfo 

func (node *GridNode) ToGridNodeInfo() *GridNodeInfo

type GridNodeInfo 

type GridNodeInfo struct {
	*GridNode
	Parent *GridNodeInfo
	G      float64
	H      float64
	F      float64
	Open   bool //是否第一次访问
	// contains filtered or unexported fields
}

一个格子存储的对象

func (*GridNodeInfo) ExpandPath 

func (info *GridNodeInfo) ExpandPath(paths []*PathPoint) (expanded []*PathPoint)

func (*GridNodeInfo) GetPaths 

func (info *GridNodeInfo) GetPaths() (res []*PathPoint)

type Heuristic 

type Heuristic func(x int, y int) int

func GetHeuristicByDesc 

func GetHeuristicByDesc(desc string) Heuristic

type PathFindingCmd 

type PathFindingCmd func(startX, startY, endX, endY int) (res []*PathPoint)

type PathFindingConfig 

type PathFindingConfig struct {
	BiDirectional    bool             //是否是双向
	Weight           float64          //权重
	AllowDiagonal    bool             //允许对角线行走
	DiagonalMovement DiagonalMovement //对角线行走规则
	Heuristic        Heuristic        //估算函数
	DontCrossCorners bool             //是否跨越障碍物
	IdAStarTimeLimit int64            //最大搜索秒数，超过这个值也视为没有找到
	Trace            DebugTrace
}

func GetDefaultConfig 

func GetDefaultConfig() *PathFindingConfig

type PathFindingConfigOptions 

type PathFindingConfigOptions func(cfg *PathFindingConfig)

func WithAllowDiagonal 

func WithAllowDiagonal(allowDiagonal bool) PathFindingConfigOptions

func WithDebugTrace 

func WithDebugTrace(trace DebugTrace) PathFindingConfigOptions

func WithDiagonalMovement 

func WithDiagonalMovement(DiagonalMovement DiagonalMovement) PathFindingConfigOptions

func WithDontCrossCorners 

func WithDontCrossCorners(DontCrossCorners bool) PathFindingConfigOptions

func WithHeuristic 

func WithHeuristic(Heuristic Heuristic) PathFindingConfigOptions

func WithWeight 

func WithWeight(weight float64) PathFindingConfigOptions

type PathFindingType 

type PathFindingType string
const (
	Undefined      PathFindingType = ""
	AStar          PathFindingType = "AStar"
	IdAStar        PathFindingType = "IdAStar"
	Dijkstra       PathFindingType = "Dijkstra"
	BestFirst      PathFindingType = "BestFirst"
	BreadthFirst   PathFindingType = "BreadthFirst"
	JumpPoint      PathFindingType = "JumpPoint"
	BiAStar        PathFindingType = "BiAStar"
	BiBestFirst    PathFindingType = "BiBestFirst"
	BiBreadthFirst PathFindingType = "BiBreadthFirst"
	BiDijkstra     PathFindingType = "BiDijkstra"
)

func GetPathFindingType 

func GetPathFindingType(dest string, cfg *PathFindingConfig) PathFindingType

type PathPoint 

type PathPoint struct {
	X, Y int
}

type TracePoint 

type TracePoint struct {
	PathPoint
	IsJumpPoint bool
}

Source Files

View all Source files

Directories

Path Synopsis
example
demo
demo/grid_map
demo/ui
path_finding

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.