navmesh

Documentation

Index

• type NavMesh
  • func NewNavMesh(shapes []geometry.Polygon, meshShrinkAmount float64) *NavMesh
  • func (m *NavMesh) Find(point geometry.Point, maxDistance float64) (distance float64, findPoint geometry.Point, findPolygon geometry.Polygon)
  • func (m *NavMesh) FindPath(start, end geometry.Point) (result []geometry.Point)
  • func (m *NavMesh) GetNeighbours(node *shape) []*shape
  • func (m *NavMesh) GetNodeId(node *shape) int

Examples

• NavMesh.FindPath

Types

type NavMesh

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

func NewNavMesh

func NewNavMesh(shapes []geometry.Polygon, meshShrinkAmount float64) *NavMesh

NewNavMesh 创建一个新的导航网格，并返回一个指向该导航网格的指针。

参数：

• shapes: 形状切片，类型为 []geometry.Shape[V]，表示导航网格中的形状。
• meshShrinkAmount: 网格缩小量，类型为 V，表示导航网格的缩小量。

返回值：

• *NavMesh[V]: 指向创建的导航网格的指针。

注意事项：

• 导航网格的形状可以是任何几何形状。
• meshShrinkAmount 表示导航网格的缩小量，用于在形状之间创建链接时考虑形状的缩小效果。
• 函数内部使用了泛型类型参数 V，可以根据需要指定形状的坐标类型。
• 函数返回一个指向创建的导航网格的指针。

使用建议：

• 确保 NavMesh 计算精度的情况下，V 建议使用 float64 类型

func (*NavMesh) Find

func (m *NavMesh) Find(point geometry.Point, maxDistance float64) (distance float64, findPoint geometry.Point, findPolygon geometry.Polygon)

Find 用于在 NavMesh 中查找离给定点最近的形状，并返回距离、找到的点和找到的形状。

参数：

• point: 给定的点，类型为 geometry.Point，表示一个 V 维度的点坐标。
• maxDistance: 最大距离，类型为 V，表示查找的最大距离限制。

返回值：当 distance 为 -1 时表示未找到最近的形状，否则返回距离、找到的点和找到的形状。

• distance: 距离，类型为 float64，表示离给定点最近的形状的距离。
• findPoint: 找到的点，类型为 geometry.Point，表示离给定点最近的点坐标。
• findPolygon: 找到的多边形，类型为 geometry.Polygon，表示离给定点最近的形状。

注意事项：

• 如果给定点在 NavMesh 中的某个形状内部或者在形状的边上，距离为 0，找到的形状为该形状，找到的点为给定点。
• 如果给定点不在任何形状内部或者形状的边上，将计算给定点到每个形状的距离，并找到最近的形状和对应的点。
• 距离的计算采用几何学中的投影点到形状的距离。
• 函数返回离给定点最近的形状的距离、找到的点和找到的形状。

func (*NavMesh) FindPath

func (m *NavMesh) FindPath(start, end geometry.Point) (result []geometry.Point)

FindPath 函数用于在 NavMesh 中查找从起点到终点的路径，并返回路径上的点序列。

参数：

• start: 起点，类型为 geometry.Point[V]，表示路径的起始点。
• end: 终点，类型为 geometry.Point[V]，表示路径的终点。

返回值：

• result: 路径上的点序列，类型为 []geometry.Point[V]。

注意事项：

• 函数首先根据起点和终点的位置，找到离它们最近的形状作为起点形状和终点形状。
• 如果起点或终点不在任何形状内部，且 NavMesh 的 meshShrinkAmount 大于0，则会考虑缩小的形状。
• 使用 A* 算法在 NavMesh 上搜索从起点形状到终点形状的最短路径。
• 使用漏斗算法对路径进行优化，以得到最终的路径点序列。

Example

package main

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

func main() {
	fp := geometry.FloorPlan{
		"=================================",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"X                               X",
		"=================================",
	}

	var walkable []geometry.Polygon
	walkable = append(walkable,
		geometry.NewPolygon(
			geometry.NewPoint(5, 5),
			geometry.NewPoint(15, 5),
			geometry.NewPoint(15, 15),
			geometry.NewPoint(5, 15),
		),
		geometry.NewPolygon(
			geometry.NewPoint(15, 5),
			geometry.NewPoint(25, 5),
			geometry.NewPoint(25, 15),
			geometry.NewPoint(15, 15),
		),
		geometry.NewPolygon(
			geometry.NewPoint(15, 15),
			geometry.NewPoint(25, 15),
			geometry.NewPoint(25, 25),
			geometry.NewPoint(15, 25),
		),
	)

	for _, shape := range walkable {
		for _, edge := range shape.GetEdges() {
			sx, bx := maths.MinMax(edge[0].GetX(), edge[1].GetX())
			sy, by := maths.MinMax(edge[0].GetY(), edge[1].GetY())

			for x := sx; x <= bx; x++ {
				for y := sy; y <= by; y++ {
					fp.Put(geometry.NewPoint(x, y), '+')
				}
			}
		}
	}

	nm := navmesh.NewNavMesh(walkable, 0)
	path := nm.FindPath(
		geometry.NewPoint(6, 6),
		geometry.NewPoint(18, 24),
	)
	for _, point := range path {
		fp.Put(geometry.NewPoint(point.GetX(), point.GetY()), 'G')
	}

	fmt.Println(fp)

}

Output:

=================================
X                               X
X                               X
X                               X
X                               X
X    +++++++++++++++++++++      X
X    +G        +         +      X
X    +         +         +      X
X    +         +         +      X
X    +         +         +      X
X    +         +         +      X
X    +         +         +      X
X    +         +         +      X
X    +         +         +      X
X    +         +         +      X
X    ++++++++++G++++++++++      X
X              +         +      X
X              +         +      X
X              +         +      X
X              +         +      X
X              +         +      X
X              +         +      X
X              +         +      X
X              +         +      X
X              +  G      +      X
X              +++++++++++      X
X                               X
X                               X
=================================

func (*NavMesh) GetNeighbours

func (m *NavMesh) GetNeighbours(node *shape) []*shape

GetNeighbours 实现 astar.Graph 的接口，用于向 A* 算法提供相邻图形

func (*NavMesh) GetNodeId

func (m *NavMesh) GetNodeId(node *shape) int

GetNodeId 实现 astar.Graph 的接口，用于返回给定形状的唯一标识。