Documentation
¶
Overview ¶
Package quadtree 提供自适应四叉树空间索引,用于实体密度不均匀的 2D 场景。
与同级 spatial 包(均匀网格)的区别:
- 均匀网格:当实体分布均匀时性能最优,但如果地图一角聚集大量玩家(如主城), 该网格单元退化为全量遍历。
- 四叉树:递归细分拥挤区域、合并空旷区域,自动适应密度分布。代价是维护成本 略高(插入/删除 O(log N))和锁粒度更粗,但范围查询在密度不均场景下远优。
适用:MMO 主城/野外混合场景、大逃杀(安全区收缩时玩家聚集)、2D 射击弹幕检测、 SLG 大地图单元可见性查询。
泛型 ID 为实体标识(comparable)。坐标 float64。 并发安全(单读写锁)。零值不可用,用 New 构造。
Index ¶
- type Entity
- type Rect
- type Tree
- func (t *Tree[ID]) Add(id ID, x, y float64)
- func (t *Tree[ID]) KNN(x, y float64, k int, radius float64, exclude ...ID) []Entity[ID]
- func (t *Tree[ID]) Len() int
- func (t *Tree[ID]) Move(id ID, x, y float64)
- func (t *Tree[ID]) Nearby(x, y, radius float64, exclude ...ID) []Entity[ID]
- func (t *Tree[ID]) Pos(id ID) (x, y float64, ok bool)
- func (t *Tree[ID]) QueryRect(r Rect, exclude ...ID) []Entity[ID]
- func (t *Tree[ID]) Remove(id ID)
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 }
Entity 查询返回的实体信息。
type Tree ¶
type Tree[ID comparable] struct { // contains filtered or unexported fields }
Tree 四叉树空间索引。零值不可用,用 New 构造。并发安全。
func New ¶
func New[ID comparable](bounds Rect, capacity, maxDepth int) *Tree[ID]
New 创建四叉树。bounds 定义地图总边界,capacity 为节点分裂阈值(推荐 8~16), maxDepth 限制递归深度(防止退化,推荐 8~12)。
Source Files
Click to show internal directories.
Click to hide internal directories.