游戏 AOI 的常见算法与设计
哪些公司问过
答案要点
- AOI 决定每个实体需要同步给哪些玩家,核心是快速求视野内对象集合
- 九宫格:按格子划分,只同步所在格及周围八格,简单稳定但密集时格内对象多
- 十字链表:X、Y 两条有序链表,移动时局部调整,适合不同视野半径
- 四叉树、八叉树、空间哈希适合分布不均或三维场景
- 切换格子时用新旧集合差集计算进入和离开,减少消息量
易错点
- 格子太小导致频繁跨格,或太大导致单格对象过多
- 只考虑进入事件,忘了处理离开视野时的删除
- 边界抖动没有滞回处理,进出消息来回刷
面试官常见追问
- 实体进入视野时它正在放技能怎么办?
- 在格子边界来回走动导致频繁进出怎么办?
- 同屏人数太多怎么优化?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。