动态单位频繁移动时空间索引如何选择
哪些公司问过
答案要点
- 均匀网格更新O(1)、实现简单,适合密度较均匀、单位尺寸相近的场景
- 普通四叉树适应密度不均,但跨边界移动需删除重插,频繁移动代价高
- 松散四叉树扩大节点边界,减少移动导致的重插,查询稍多检查节点
- 开放世界可用哈希网格只存非空格,节省内存
- 根据单位尺寸差异、分布密度和更新查询比例选择
易错点
- 频繁移动的单位用普通四叉树,每帧大量删除重插
- 圆形查询只遍历格子不做精确距离判断,结果多出范围外的单位
- 单位跨格存储却不去重,同一单位被重复处理
面试官常见追问
- 圆形范围查询为什么不能只遍历外接矩形?如何避免漏查和重复?
- 网格大小怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。