Documentation
¶
Overview ¶
Package spatial 提供网格空间索引:把实体按坐标分桶到固定大小的网格单元, 支持"范围查询"(附近的人/实体)与 KNN(最近的 N 个),避免全量遍历。
适用:LBS「附近的人/店铺/开播」、MMO 的 AOI(兴趣区域,只把可视范围内的 实体变化推给玩家)、大地图分区广播、碰撞粗筛。
原理:平面按 cellSize 切成网格,每个实体落在一个单元里。查询半径 r 时只需 扫描"覆盖该半径的若干相邻单元"(通常 (2*ceil(r/cell)+1)^2 个),再对候选做 精确距离过滤——把 O(N) 全表扫描降到 O(近邻单元内实体数)。适合实体分布较均匀、 查询半径远小于地图尺寸的场景(绝大多数游戏/LBS)。
泛型 ID 为实体标识(comparable,如 string/int64)。坐标用 float64。 并发安全(单锁,读多写少;超高并发可在上层分区)。零值不可用,用 New 构造。
Example ¶
package main
import (
"fmt"
"github.com/rushteam/beauty/pkg/spatial"
)
func main() {
ix := spatial.New[string](100)
ix.Add("alice", 10, 10)
ix.Add("bob", 20, 15)
ix.Add("carol", 500, 500)
for _, e := range ix.Nearby(0, 0, 50, "alice") {
fmt.Printf("%s at (%.0f,%.0f) dist=%.1f\n", e.ID, e.X, e.Y, e.Dist)
}
}
Output: bob at (20,15) dist=25.0
Index ¶
- type Entity
- type Index
- func (ix *Index[ID]) Add(id ID, x, y float64)
- func (ix *Index[ID]) KNN(x, y float64, k int, radius float64, exclude ...ID) []Entity[ID]
- func (ix *Index[ID]) Len() int
- func (ix *Index[ID]) Move(id ID, x, y float64)
- func (ix *Index[ID]) Nearby(x, y, radius float64, exclude ...ID) []Entity[ID]
- func (ix *Index[ID]) Pos(id ID) (x, y float64, ok bool)
- func (ix *Index[ID]) Remove(id ID)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Entity ¶
type Entity[ID comparable] struct { ID ID X, Y float64 Dist float64 // 到查询点的欧氏距离(Nearby/KNN 填充;其余为 0) }
Entity 一次查询返回的实体及其坐标、到查询点的距离。
type Index ¶
type Index[ID comparable] struct { // contains filtered or unexported fields }
Index 网格空间索引。零值不可用,用 New 构造。并发安全。
func New ¶
func New[ID comparable](cellSize float64) *Index[ID]
New 创建空间索引。cellSize 为网格单元边长——建议设为"典型查询半径"量级: 太小则单元多、跨单元查询扫描面广;太大则单元内实体多、精确过滤成本高。
func (*Index[ID]) KNN ¶
KNN 返回距 (x,y) 最近的 k 个实体,按距离升序。radius 限定搜索范围 (<=0 表示不限,但那会退化为全表扫描,建议给合理上界)。exclude 排除指定 ID。
func (*Index[ID]) Nearby ¶
Nearby 返回距 (x,y) 半径 radius 内的所有实体(含边界),按距离升序。 exclude 中的 ID 被排除(常用于排除查询者自己)。
Source Files