大量敌人中高效查询攻击范围内或最近的目标
哪些公司问过
答案要点
- 均匀网格:格子边长取攻击半径量级,每格存敌人列表,跨格移动时 O(1) 更新
- 扇形查询先取圆的包围盒覆盖的格子做粗筛,再精确判断
- 距离用平方比较避免开方;角度用点积与 cos 半角比较,120 度扇形对应 cos60° = 0.5
- 最近目标:从所在格逐圈向外扩展,下一圈最小可能距离大于当前最优时停止
- 分布不均或查询尺度差异大时,可改用四叉树、松散四叉树或 BVH
易错点
- 每次查询都遍历全部敌人,复杂度 O(N),在大量 AI 同时查询时成为瓶颈
- 用反三角函数计算角度,性能差且要处理角度回绕
- 只按格子筛选不做精确距离和角度判断,导致误判
- 敌人移动后不更新所在格子,查询结果错误
面试官常见追问
- 格子大小怎么选?
- 网格和四叉树怎么选?
- 大量 AI 每帧都查询,怎么进一步优化?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。