Recast Navigation (Go 翻译版)

将 recastnavigation/recastnavigation 从 C++ 翻译为 Go 语言的实现。

原项目：一个用于游戏和实时应用的导航网格生成与路径寻路库，行业标准级方案，被 Unity、Unreal、Godot 等引擎采用。

包结构

Go 包	对应 C++ 目录	功能
recast	Recast/	导航网格生成（从原始几何体构建导航网格）
detour	Detour/	运行时路径寻路与导航网格查询（A*、光线投射、多边形查询）
detour_crowd	DetourCrowd/	智能体群体移动、碰撞避免与人群仿真
detour_tile_cache	DetourTileCache/	导航网格分块流式加载（适用于大世界）
debug_utils	DebugUtils/	调试可视化绘制接口

原项目同步

• 原仓库：https://github.com/recastnavigation/recastnavigation
• 当前同步基线：commit 9f4ce64 (Fix crash on large-scale navmesh generation (#796))
• 分支：main

原项目版本跟踪

原项目 commit	翻译同步状态	说明
9f4ce64 (main HEAD)	✅ 已同步	当前对应最新代码
v1.6.0	✅ 已翻译	基础版本

当前状态

包	状态	说明
recast	✅ 完成	导航网格生成核心功能，已移植 C++ 单元测试
detour	✅ 完成	路径寻路与查询，含序列化，寻路0 alloc，算法逻辑与 C++ 完全一致
detour_crowd	✅ 完成	群体移动与碰撞避免，已移植 C++ 单元测试
detour_tile_cache	✅ 完成	分块流式加载与动态障碍，含 Go/C++ 对比测试
debug_utils	✅ 基本完成	调试绘制

性能基准

寻路性能（i5-13400, 20×20 网格, 800 个多边形，0 alloc）

测试	耗时 (ns/op)	vs C++	分配 (B/op)	分配次数
FindPath (5 格)	580	×1.39	0	0
FindPath (10 格)	1,210	×1.34	0	0
FindPath (19 格)	2,200	×1.39	0	0
FindStraightPath (20 多边形路径)	840	×2.26	0	0
Raycast (5 格)	164	×4.0	0	0
Raycast (10 格)	392	×9.3	0	0
Raycast (19 格)	710	×17.8	0	0
FindPolysAroundCircle (r=50)	11,750	×1.70	0	0
FindPolysAroundCircle (r=100)	33,250	×2.84	0	0
FindPolysAroundCircle (r=150)	37,700	—	0	0

导航网格构建

网格规模	多边形数	耗时 (ns/op)	分配 (B/op)
10×10	200	16,800	48,008
50×50	5,000	387,000	1,163,641
100×100	20,000	1,676,000	4,571,518

运行基准测试：

go test -bench=. -benchtime=500ms -benchmem ./detour/

示例程序

独立可运行的示例代码位于 examples/ 目录：

示例	涉及的包	功能
quickstart	recast + detour	完整 NavMesh 构建管线 + A* 寻路
crowd	detour_crowd + detour	多智能体群体移动仿真
tilecache	detour_tile_cache + detour	动态障碍物添加/移除与瓦片重建

直接运行：

go run ./examples/quickstart/
go run ./examples/crowd/
go run ./examples/tilecache/

安装

go get github.com/actfuns/recastnavigation

完整示例

以下是一个不经过 recast 管线、直接构建 Detour 网格并进行寻路的精简示例。完整的（含 recast 管线）示例请参考 examples/quickstart/main.go。

package main

import (
	"fmt"

	"github.com/actfuns/recastnavigation/detour"
)

func main() {
	// 直接构建 10×10 网格导航网格
	const gridSize = 10
	const stride = gridSize + 1

	verts := make([]uint16, 0, stride*stride*3)
	for z := 0; z <= gridSize; z++ {
		for x := 0; x <= gridSize; x++ {
			verts = append(verts, uint16(x), 0, uint16(z))
		}
	}

	polys := make([]uint16, 0, gridSize*gridSize*12)
	flags := make([]uint16, 0, gridSize*gridSize)
	areas := make([]uint8, 0, gridSize*gridSize)
	const boundaryMask uint16 = 0x800f

	for z := 0; z < gridSize; z++ {
		for x := 0; x < gridSize; x++ {
			idx := z*stride + x
			polys = append(polys,
				uint16(idx), uint16(idx+1), uint16(idx+gridSize+2),
				uint16(idx), uint16(idx+gridSize+2), uint16(idx+gridSize+1),
			)
			if z > 0 {
				polys = append(polys, uint16((z-1)*gridSize+x))
			} else {
				polys = append(polys, boundaryMask)
			}
			if x < gridSize-1 {
				polys = append(polys, uint16(z*gridSize+x+1))
			} else {
				polys = append(polys, boundaryMask)
			}
			polys = append(polys, boundaryMask, boundaryMask)
			if z < gridSize-1 {
				polys = append(polys, uint16((z+1)*gridSize+x))
			} else {
				polys = append(polys, boundaryMask)
			}
			if x > 0 {
				polys = append(polys, uint16(z*gridSize+x-1))
			} else {
				polys = append(polys, boundaryMask)
			}
			flags = append(flags, 0xffff)
			areas = append(areas, 63)
		}
	}

	params := &detour.NavMeshCreateParams{
		Verts:          verts,
		VertCount:      stride * stride,
		Polys:          polys,
		PolyAreas:      areas,
		PolyFlags:      flags,
		PolyCount:      gridSize * gridSize,
		Nvp:            6,
		WalkableHeight: 2.0,
		WalkableRadius: 0.6,
		WalkableClimb:  1.0,
		Cs:             1.0,
		Ch:             0.2,
		BuildBvTree:    false,
		Bmin:           [3]float32{0, 0, 0},
		Bmax:           [3]float32{gridSize, 1, gridSize},
	}

	data, _, ok := detour.CreateNavMeshData(params)
	if !ok || data == nil {
		panic("CreateNavMeshData 失败")
	}

	nav := &detour.NavMesh{}
	if err := nav.Init(&detour.NavMeshParams{
		Orig:       [3]float32{0, 0, 0},
		TileWidth:  gridSize,
		TileHeight: gridSize,
		MaxTiles:   2,
		MaxPolys:   4096,
	}); err != nil {
		panic(fmt.Sprintf("NavMesh.Init: %v", err))
	}
	if _, err := nav.AddTile(data, 0, 0); err != nil {
		panic(fmt.Sprintf("AddTile: %v", err))
	}

	query := detour.NewNavMeshQuery()
	if err := query.Init(nav, 4096); err != nil {
		panic(fmt.Sprintf("NavMeshQuery.Init: %v", err))
	}

	filter := &detour.QueryFilter{}
	filter.IncludeFlags = 0xffff
	for i := range filter.AreaCost {
		filter.AreaCost[i] = 1.0
	}

	halfExtents := [3]float32{2, 4, 2}
	startRef, startPt, _ := query.FindNearestPoly([3]float32{1, 0, 1}, halfExtents, filter)
	endRef, endPt, _ := query.FindNearestPoly([3]float32{9, 0, 9}, halfExtents, filter)

	path := make([]detour.PolyRef, 4096)
	npath, _ := query.FindPath(startRef, endRef, startPt, endPt, filter, path)
	path = path[:npath]

	straightPath := make([]float32, 4096*3)
	straightFlags := make([]uint8, 4096)
	straightRefs := make([]detour.PolyRef, 4096)
	nstraight, _ := query.FindStraightPath(startPt, endPt, path, npath,
		straightPath, straightFlags, straightRefs, 4096, 0)

	fmt.Printf("找到路径，%d 个路点\n", nstraight)
	for i := 0; i < nstraight; i++ {
		fmt.Printf("  %d: (%.2f, %.2f, %.2f)\n",
			i, straightPath[i*3], straightPath[i*3+1], straightPath[i*3+2])
	}
}

完整性检查

go vet ./...
go test ./...

与原 C++ 版本差异

• 使用 Go 的 [3]float32（定长数组）代替 C++ 的 float* 和 float[3]，避免切片索引越界
• 函数返回值风格：C++ 使用输出参数 + 返回状态码，Go 使用多返回值（result, err），热路径函数使用指针参数减少拷贝（如 getPortalPoints）
• 使用 encoding/binary + 手动序列化代替 C++ 的 memcpy 结构体序列化，确保二进制兼容
• 使用 Go 的垃圾回收代替 C++ 的手动内存池管理
• 去除了 C++ 的虚函数回调机制，改用 Go 接口
• 使用 Go 泛型实现 Min/Max/Abs/Swap 等工具函数
• 算法逻辑与 C++ 完全一致（所有核心函数已逐行对比确认）

License

同原项目 — Zlib License