astar

Documentation

Index

• func Find[I constraints.Ordered, T any](graph Graph[I, T], start, end T, cost, heuristic func(a, b T) float64) []T
• type Graph

Examples

• Find

Functions

func Find

func Find[I constraints.Ordered, T any](graph Graph[I, T], start, end T, cost, heuristic func(a, b T) float64) []T

Find 使用 A* 算法在导航网格上查找从起点到终点的最短路径，并返回路径上的节点序列。

参数：

• graph: 图对象，类型为 Graph[Node]，表示导航网格。
• start: 起点节点，类型为 Node，表示路径的起点。
• end: 终点节点，类型为 Node，表示路径的终点。
• cost: 路径代价函数，类型为 func(a, b Node) V，用于计算两个节点之间的代价。
• heuristic: 启发函数，类型为 func(a, b Node) V，用于估计从当前节点到目标节点的启发式代价。

返回值：

• []Node: 节点序列，表示从起点到终点的最短路径。如果找不到路径，则返回空序列。

注意事项：

• graph 对象表示导航网格，其中包含了节点和连接节点的边。
• start 和 end 分别表示路径的起点和终点。
• cost 函数用于计算两个节点之间的代价，可以根据实际情况自定义实现。
• heuristic 函数用于估计从当前节点到目标节点的启发式代价，可以根据实际情况自定义实现。
• 函数使用了 A* 算法来搜索最短路径。
• 函数内部使用了堆数据结构来管理待处理的节点。
• 函数返回一个节点序列，表示从起点到终点的最短路径。如果找不到路径，则返回空序列。

Example

package main

import (
	"fmt"
	"github.com/kercylan98/minotaur/toolkit/geometry"
	"github.com/kercylan98/minotaur/toolkit/navigate/astar"
)

type Graph struct {
	geometry.FloorPlan
}

type Entity struct {
	geometry.Vector2
}

func (g *Graph) GetNodeId(node *Entity) int {
	x, y := node.GetXY()
	a, b := int(x), int(y)
	mergedNumber := (a << 16) | (b & 0xFFFFFFFF)
	return mergedNumber
}

func (g *Graph) GetNeighbours(t *Entity) []*Entity {
	var neighbours []*Entity
	for _, direction := range geometry.Direction2D4() {
		next := geometry.CalcOffsetInDirection2D(t.Vector2, direction, 1)
		if g.FloorPlan.IsFree(next) {
			neighbours = append(neighbours, &Entity{
				Vector2: next,
			})
		}
	}
	return neighbours
}

func main() {
	graph := Graph{
		FloorPlan: geometry.FloorPlan{
			"===========",
			"X XX  X   X",
			"X  X   XX X",
			"X XX      X",
			"X     XXX X",
			"X XX  X   X",
			"X XX  X   X",
			"===========",
		},
	}

	paths := astar.Find[int, *Entity](
		&graph,
		&Entity{geometry.NewVector2(1, 1)},
		&Entity{geometry.NewVector2(8, 6)},
		// 曼哈顿距离
		func(a, b *Entity) float64 {
			return a.Sub(b.Vector2).Length()
		},
		func(a, b *Entity) float64 {
			return a.Sub(b.Vector2).Length()
		},
	)

	for _, path := range paths {
		graph.Put(path.Vector2, '.')
	}

	fmt.Println(graph)

}

Output:

===========
X.XX  X   X
X. X   XX X
X.XX .....X
X.....XXX.X
X XX  X  .X
X XX  X ..X
===========

Types

type Graph

type Graph[I constraints.Ordered, T any] interface {
	// GetNodeId 返回节点的唯一标识。
	GetNodeId(node T) I
	// GetNeighbours 返回与给定节点相邻的节点列表。
	GetNeighbours(t T) []T
}

Graph 适用于 A* 算法的图数据结构接口定义，表示导航网格，其中包含了节点和连接节点的边。