Golang实现2D网格的射线投射、阴影投射和路径查找插件库grid的使用

功能特性

• DDA射线投射
• A-Star路径查找
• 基于射线的视线检测
• 递归阴影投射
• Dijkstra地图
• Bresenham直线算法
• 100%测试覆盖率

基本使用

值类型示例

import (
    "image"

    "github.com/s0rg/grid"
)

const mapW, mapH = 100, 100

func valueExample() {
    // 使用值类型很简单
    g := grid.New[int](image.Rect(0, 0, mapW, mapH))

    // 现在网格填充了该类型的零值
    // 你可以用其他值重新填充它：
    g.Fill(func() int {
        return 1
    })
}

指针类型示例

func pointerExample() {
    // 使用指针类型类似，但需要预先填充
    type mycell struct {}

    g := grid.New[*mycell](image.Rect(0, 0, mapW, mapH))

    // 现在网格填充了nil，所以需要预先填充一些值
    // 否则通过Get/MustGet方法访问的将是nil
    g.Fill(func() *mycell {
        return &mycell{}
    })
}

使用示例

func usageExample() {
    type mycell struct {
        wall bool
    }

    g := grid.New[*mycell](image.Rect(0, 0, mapW, mapH))

    g.Fill(func() *mycell {
        return &mycell{}
    })

    pt := image.Pt(10, 10)

    // 设置新值
    g.Set(pt, &mycell{wall: true})

    // 更新现有值
    if v, ok := g.Get(pt); ok {
        v.wall = false
    }

    // 简写形式，如果越界访问会panic
    g.MustGet(pt).wall = true

    // 遍历所有单元格
    g.Iter(func(p image.Point, c *mycell) (next bool) {
        if c.wall {
            // 找到墙
        }

        return true
    })
}

完整示例

package main

import (
	"fmt"
	"image"
	"log"

	"github.com/s0rg/grid"
)

type cell struct {
	wall bool
}

func main() {
	// 创建100x100的网格
	g := grid.New[*cell](image.Rect(0, 0, 100, 100))
	
	// 填充初始单元格
	g.Fill(func() *cell {
		return &cell{}
	})

	// 设置一些墙
	for x := 20; x < 80; x++ {
		g.Set(image.Pt(x, 20), &cell{wall: true})
		g.Set(image.Pt(x, 80), &cell{wall: true})
	}
	for y := 20; y < 80; y++ {
		g.Set(image.Pt(20, y), &cell{wall: true})
		g.Set(image.Pt(80, y), &cell{wall: true})
	}

	// 起点和终点
	start := image.Pt(10, 10)
	end := image.Pt(90, 90)

	// 使用A*算法查找路径
	path, ok := g.Path(
		start,
		end,
		func(p image.Point) bool {
			// 检查点是否可通行
			c, ok := g.Get(p)
			return ok && !c.wall
		},
		grid.Diagonal,
	)
	if !ok {
		log.Fatal("no path found")
	}

	// 打印路径
	fmt.Println("Path from", start, "to", end)
	for _, p := range path {
		fmt.Println(p)
	}

	// 视线检测
	visible := g.LineOfSight(
		start,
		end,
		func(p image.Point) bool {
			c, ok := g.Get(p)
			return ok && !c.wall
		},
	)
	fmt.Println("Is visible:", visible)

	// 阴影投射
	var visibleCells []image.Point
	g.CastShadow(
		start,
		10, // 半径
		func(p image.Point) bool {
			c, ok := g.Get(p)
			return ok && !c.wall
		},
		func(p image.Point) {
			visibleCells = append(visibleCells, p)
		},
	)
	fmt.Println("Visible cells count:", len(visibleCells))
}

性能基准

运行基准测试：

make bench

测试结果示例：

goos: linux
goarch: amd64
pkg: github.com/s0rg/grid
cpu: AMD Ryzen 5 5500U with Radeon Graphics
BenchmarkGrid/Set-12         	1000000000	        0.8108 ns/op	      0 B/op	      0 allocs/op
BenchmarkGrid/Get-12         	641611768	        1.764 ns/op	      0 B/op	      0 allocs/op
BenchmarkGrid/Neighbours-12  	52243890	       23.41 ns/op	      0 B/op	      0 allocs/op
BenchmarkGrid/LineBresenham-12         	4416172	      269.0 ns/op	      0 B/op	      0 allocs/op
BenchmarkGrid/CastRay-12               	3829839	      321.1 ns/op	      0 B/op	      0 allocs/op
BenchmarkGrid/CastShadow-12            	  32648	    36950 ns/op	      0 B/op	      0 allocs/op
BenchmarkGrid/LineOfSight-12           	   9897	   114576 ns/op	      0 B/op	      0 allocs/op
BenchmarkGrid/DijkstraMap-12           	   1029	  1190195 ns/op	  20656 B/op	      3 allocs/op
BenchmarkGrid/Path-12                  	    372	  3225325 ns/op	 997588 B/op	  13643 allocs/op
PASS
ok  	github.com/s0rg/grid	12.098s