s_cherry_e/sr/internal/algorithm/astar6/astar_test.go

package astar6

import (
	"f1-game/internal/types"
	"fmt"
	"testing"
	"time"
)

var (
	config1 = Config{
		Min: types.NewPoint(0, 0),
		Max: types.NewPoint(9, 29),
		MapData: [][]int32{
			// > Column or Height
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}, // v Row ro Width
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1},
			{1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1},
			{1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1},
			{1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1},
			{1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1},
			{1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1},
		},
		IsDebug: true,
	}

	config2 = Config{
		Min: types.NewPoint(0, 0),
		Max: types.NewPoint(9, 4),
		MapData: [][]int32{
			// > Column or Height
			{1, 1, 1, 1, 1}, // v Row ro Width
			{1, 0, 1, 0, 0},
			{1, 1, 0, 1, 1},
			{1, 1, 1, 0, 1},
			{1, 1, 1, 0, 1},
			{1, 1, 0, 0, 1},
			{1, 1, 0, 1, 1},
			{1, 1, 0, 1, 1},
			{1, 0, 1, 1, 1},
			{1, 1, 1, 1, 1},
		},
		IsDebug: true,
	}
)

func TestAstar(t *testing.T) {
	astar := New(config1)
	// astar := New(config2)

	startTime := time.Now().UnixNano()
	fmt.Printf("开始:%d\n", startTime)

	path, ok := astar.FindPath(DefaultFindContext(0, 0, 9, 29))
	// path, ok := astar.FindPath(0, 0, 9, 4)
	// path, ok := astar.FindPath(0, 0, 3, 8)

	endTime := time.Now().UnixNano()
	fmt.Printf("结束:%d\n", endTime)
	fmt.Printf("耗时:%v(ns)\n", endTime-startTime)

	if !ok {
		t.Error("find path failed")
	} else {
		astar.Print(path)
	}

}

// TestAstarVisualStraightPath 测试视觉上更直的路径
// 验证从(1,1)到(7,2)的路径是否更接近视觉直线
func TestAstarVisualStraightPath(t *testing.T) {
	config := Config{
		Min: types.NewPoint(0, 0),
		Max: types.NewPoint(9, 9),
		MapData: [][]int32{
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
		},
		IsDebug: true,
	}

	astar := New(config)

	// 测试从(1,1)到(7,2)的路径
	path, ok := astar.FindPath(DefaultFindContext(1, 1, 7, 2))
	if !ok {
		t.Error("find path failed")
		return
	}

	fmt.Println("\n=== 测试视觉直线路径 (1,1) -> (7,2) ===")
	fmt.Printf("路径: %v\n", path)

	// 打印路径节点
	for i, node := range path {
		fmt.Printf("步骤%d: (%d, %d)\n", i, node.X(), node.Y())
	}

	// 验证路径是否包含(5,3)点，这是视觉上更直的路径标志
	has53 := false
	for _, node := range path {
		if node.X() == 5 && node.Y() == 3 {
			has53 = true
			break
		}
	}

	if has53 {
		fmt.Println("\n✓ 路径包含(5,3)点，这是视觉上更直的路径！")
	} else {
		fmt.Println("\n路径不包含(5,3)点")
	}
}

// BenchmarkFindPath 性能基准测试
func BenchmarkFindPath(b *testing.B) {
	astar := New(config1)

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		astar.FindPath(DefaultFindContext(0, 0, 9, 29))
	}
}

// BenchmarkFindPathParallel 并行性能测试
func BenchmarkFindPathParallel(b *testing.B) {
	astar := New(config1)

	b.ResetTimer()
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			astar.FindPath(DefaultFindContext(0, 0, 9, 29))
		}
	})
}

// TestConcurrentFindPath 并发安全测试
func TestConcurrentFindPath(t *testing.T) {
	astar := New(config1)

	const goroutines = 100
	const iterations = 50

	done := make(chan bool, goroutines)

	for g := 0; g < goroutines; g++ {
		go func() {
			for i := 0; i < iterations; i++ {
				path, ok := astar.FindPath(DefaultFindContext(0, 0, 9, 29))
				if !ok {
					t.Error("concurrent find path failed")
					return
				}
				if len(path) == 0 {
					t.Error("concurrent find path returned empty")
					return
				}
			}
			done <- true
		}()
	}

	// 等待所有goroutine完成
	for g := 0; g < goroutines; g++ {
		<-done
	}

	fmt.Printf("並发测试完成: %d 个goroutine x %d 次迭代 = %d 次寻路\n", goroutines, iterations, goroutines*iterations)
}

// TestDynamicWalkableNode 测试动态设置节点为不可行走
// 验证了 bug 修复：在寻路过程中，应诠节点的可行走状态
func TestDynamicWalkableNode(t *testing.T) {
	config := Config{
		Min: types.NewPoint(0, 0),
		Max: types.NewPoint(9, 9),
		MapData: [][]int32{
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
		},
		IsDebug: false,
	}

	astar := New(config)

	// 第一次寻路：正常的直线路径
	path1, ok1 := astar.FindPath(DefaultFindContext(0, 0, 9, 9))
	if !ok1 {
		t.Error("First path finding failed")
		return
	}
	fmt.Printf("第一次寻路长度: %d\n", len(path1))

	// 动态设置中间节点(5,5)为不可行走
	middleNode := astar.GetNode(5, 5)
	if middleNode != nil {
		middleNode.SetWalkable(false)
		fmt.Println("已设置节点(5,5)为不可行走")
	}

	// 第二次寻路：与上一次不同（应诠中间节点）
	path2, ok2 := astar.FindPath(DefaultFindContext(0, 0, 9, 9))
	if !ok2 {
		t.Error("Second path finding failed after setting node as unwalkable")
		return
	}
	fmt.Printf("第二次寻路长度: %d\n", len(path2))

	// 验证路径有效：设置障碍后的路径应诠(5,5)节点
	for _, node := range path2 {
		if node.X() == 5 && node.Y() == 5 {
			t.Error("Path contains the unwalkable node (5,5), bug not fixed!")
			return
		}
	}

	fmt.Println("✓ 路径不包含不可行走节点(5,5)，bug 修复正确!")

	// 恢复节点可行走状态
	if middleNode != nil {
		middleNode.SetWalkable(true)
		fmt.Println("已恢复节点(5,5)为可行走")
	}

	// 第三次寻路：应诠恢复为path1的类似正常路径
	path3, ok3 := astar.FindPath(DefaultFindContext(0, 0, 9, 9))
	if !ok3 {
		t.Error("Third path finding failed after restoring node as walkable")
		return
	}
	fmt.Printf("第三次寻路长度: %d\n", len(path3))
}

// BenchmarkFindPathWithObstacles 测试优化效果
// 模拟实际游戏场景：1000x1000地图、从(2,1)到(98,97)、有障碍点
func BenchmarkFindPathWithObstacles(b *testing.B) {
	// 创建1000x1000地图
	mapSize := int32(1000)
	mapData := make([][]int32, mapSize)
	for i := range mapData {
		mapData[i] = make([]int32, mapSize)
		for j := range mapData[i] {
			mapData[i][j] = 1
		}
	}

	// 随机放置1000个障碍点
	for i := 0; i < 1000; i++ {
		x := int32(i % 1000)
		y := int32(i / 1000)
		if x > 0 && x < mapSize && y > 0 && y < mapSize {
			mapData[x][y] = 0
		}
	}

	config := Config{
		Min:     types.NewPoint(0, 0),
		Max:     types.NewPoint(mapSize-1, mapSize-1),
		MapData: mapData,
	}

	astar := New(config)

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		// 从(2,1)到(98,97)的寻路
		astar.FindPath(DefaultFindContext(2, 1, 98, 97))
	}
}

// BenchmarkMemoryUsage 内存使用基准测试
// 测试每次寻路的内存分配情况
func BenchmarkMemoryUsage(b *testing.B) {
	astar := New(config1)

	b.ReportAllocs() // 报告内存分配
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		astar.FindPath(DefaultFindContext(0, 0, 9, 29))
	}
}

// BenchmarkShortPath 短距离寻路基准测试
func BenchmarkShortPath(b *testing.B) {
	config := Config{
		Min: types.NewPoint(0, 0),
		Max: types.NewPoint(20, 20),
		MapData: [][]int32{
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
			{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
		},
	}

	astar := New(config)

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		astar.FindPath(DefaultFindContext(0, 0, 19, 19))
	}
}

// BenchmarkMediumPath 中等距离寻路基准测试
func BenchmarkMediumPath(b *testing.B) {
	config := Config{
		Min:     types.NewPoint(0, 0),
		Max:     types.NewPoint(100, 100),
		MapData: make([][]int32, 101),
	}
	for i := range config.MapData {
		config.MapData[i] = make([]int32, 101)
		for j := range config.MapData[i] {
			config.MapData[i][j] = 1
		}
	}

	astar := New(config)

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		astar.FindPath(DefaultFindContext(0, 0, 99, 99))
	}
}

// BenchmarkLargePath 大型地图寻路基准测试
func BenchmarkLargePath(b *testing.B) {
	config := Config{
		Min:     types.NewPoint(0, 0),
		Max:     types.NewPoint(500, 500),
		MapData: make([][]int32, 501),
	}
	for i := range config.MapData {
		config.MapData[i] = make([]int32, 501)
		for j := range config.MapData[i] {
			config.MapData[i][j] = 1
		}
	}

	astar := New(config)

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		astar.FindPath(DefaultFindContext(0, 0, 499, 499))
	}
}