寻路与空间划分共100题

说明：

A*、NavMesh、动态避障、四叉树、八叉树、BVH、KD-Tree、碰撞检测粗筛。

题型统计

题型	数量
单选题	35
多选题	20
判断题	15
填空题	10
C++ 代码阅读题	10
C++ 代码填空题	5
简答题	3
场景分析题	2
合计	100

一、单选题

1. A* 算法中的 f 值通常等于？

A. g + h
B. g - h
C. h / g
D. 随机数

答案：A

解析：g 是从起点到当前点的实际代价，h 是到终点的启发式估计。

题目图示

2. A* 中 g 值通常表示？

A. 起点到当前节点的已知路径代价
B. 当前节点到终点的估计代价
C. 地图总面积
D. 障碍物数量

答案：A

解析：g 是已经走过的真实代价。

3. A* 中 h 值通常表示？

A. 当前节点到目标节点的估计代价
B. 起点到当前节点的真实代价
C. 队列容量
D. 对象半径

答案：A

解析：h 是 heuristic，用于引导搜索方向。

4. A* 每次从 open set 中通常取出哪个节点扩展？

A. f 值最小的节点
B. 坐标最大的节点
C. 随机节点
D. 最后加入的节点

答案：A

解析：open set 常用最小堆或优先队列维护 f 最小节点。

5. closed set 的主要作用是？

A. 记录已经处理过的节点，避免重复扩展
B. 保存最终路径的贴图
C. 保存所有敌人 AI
D. 计算网速

答案：A

解析：closed set 能减少重复搜索；若启发函数不一致，可能还要处理重新打开节点。

6. 当 A* 的启发函数 h 恒为 0 时，算法退化为？

A. Dijkstra
B. DFS
C. 快速排序
D. 二分查找

答案：A

解析：h=0 时没有方向引导，只按已走代价扩展，等价于 Dijkstra 的思想。

7. 可采纳启发函数 admissible heuristic 的关键条件是？

A. 不高估真实最短代价
B. 一定等于真实代价
C. 必须随机
D. 必须大于真实代价

答案：A

解析：不高估可以保证 A* 在合适条件下找到最优路径。

8. 四方向网格寻路中，常用的启发函数是？

A. 曼哈顿距离
B. 字符串编辑距离
C. 哈希值
D. 贴图面积

答案：A

解析：只能上下左右移动时，曼哈顿距离与移动约束匹配。

9. 八方向网格允许斜向移动时，更常见的启发函数是？

A. 对角距离或欧氏距离
B. 只用 x 坐标
C. 随机距离
D. 内存地址差

答案：A

解析：允许斜走时，启发函数要考虑对角移动代价。

10. Weighted A* 常见做法是？

A. 增大启发项权重以加快搜索，但可能不再保证最优
B. 删除 open set
C. 只走随机方向
D. 禁用障碍物

答案：A

解析：权重越大越偏向目标方向，速度可能更快，但路径质量可能下降。

11. C++ `std::priority_queue<int>` 默认行为是？

A. 大顶堆
B. 小顶堆
C. 队列先进先出
D. 自动去重集合

答案：A

解析：默认比较器是 less，top 是最大元素。

12. A* 最终回溯路径通常依赖？

A. 每个节点记录 parent
B. 每帧截图
C. 随机数种子
D. 音频采样率

答案：A

解析：从终点沿 parent 回溯到起点，再反转得到路径。

13. 网格寻路中，障碍格的处理通常是？

A. 邻居扩展时跳过不可走格
B. 把障碍格优先扩展
C. 让障碍格代价为负
D. 忽略地图边界

答案：A

解析：不可走格不能进入，也不能作为路径节点。

14. NavMesh 的核心含义是？

A. 用于表示可行走区域的导航网格
B. UI 图集
C. 音频混响区域
D. 网络包缓存

答案：A

解析：NavMesh 用多边形近似可行走区域，适合角色导航。

题目图示

15. NavMesh Link/OffMesh Link 常用于表示？

A. 跳跃、开门、跨沟等不连续可通行连接
B. C++ 头文件依赖
C. UI 透明度
D. Shader 变体

答案：A

解析：普通可走面无法表达跳跃、梯子等动作时，可以用 Link 连接区域。

16. NavMesh Agent 的 radius 主要影响？

A. 角色能否通过狭窄通道及避让距离
B. 纹理压缩质量
C. C# 装箱次数
D. 网络端口

答案：A

解析：半径越大，需要越宽的通行空间。

17. NavMesh Area Cost 的作用是？

A. 影响路径对不同区域的偏好
B. 改变角色贴图颜色
C. 改变脚本编译顺序
D. 关闭碰撞检测

答案：A

解析：成本越低越容易被路径选择，成本高的区域会被尽量绕开。

18. 大量单位同时寻路时，较合理的策略是？

A. 分帧/分批请求路径
B. 同一帧全部同步计算
C. 每帧重建整个地图
D. 删除 closed set

答案：A

解析：寻路开销容易形成尖峰，分时处理更稳定。

19. 路径平滑常见目的是什么？

A. 减少网格路径的折线感，使移动更自然
B. 让路径更长
C. 增加节点数量
D. 破坏可行走约束

答案：A

解析：平滑前要确保平滑段仍在可通行区域内。

20. 层次寻路 HPA* 的主要用途是？

A. 在大地图中先搜索粗层级，再细化局部路径
B. 替代所有碰撞检测
C. 压缩图片
D. 播放动画

答案：A

解析：层次化能降低大规模地图搜索成本。

21. 四叉树最适合描述哪类空间划分？

A. 二维空间递归四分
B. 三维空间递归八分
C. 字符串前缀划分
D. 音频频谱划分

答案：A

解析：四叉树常用于 2D 地图、区域查询、碰撞粗筛。

题目图示

22. 八叉树最适合描述哪类空间划分？

A. 三维空间递归八分
B. 二维空间递归四分
C. 栈内存划分
D. HTTP 路由划分

答案：A

解析：八叉树常用于 3D 场景空间查询。

23. BVH 的全称和核心思想是？

A. Bounding Volume Hierarchy，用包围体层级组织对象
B. Binary Vector Hash，只存哈希值
C. Basic View Hierarchy，只管 UI
D. Build Version Header，只管版本号

答案：A

解析：BVH 将对象包围盒组织成树，用于快速剔除不相交分支。

24. KD-Tree 的常见划分方式是？

A. 按某个坐标轴交替或选择性划分空间
B. 每层固定分成八份
C. 只按字符串排序
D. 只按对象名字分组

答案：A

解析：KD-Tree 是二叉空间划分树。

25. 空间哈希常见做法是？

A. 把空间离散成格子，用哈希表记录每个格子的对象列表
B. 把所有对象放同一个数组不分类
C. 只记录对象名字
D. 只用于音频采样

答案：A

解析：空间哈希适合动态对象多、查询局部邻居的场景。

26. 碰撞检测 broad phase 的主要目标是？

A. 快速减少可能碰撞的候选对
B. 直接计算最精确接触点
C. 播放受击动画
D. 修改材质球

答案：A

解析：粗筛只找候选，精确判断放在 narrow phase。

题目图示

27. narrow phase 主要负责？

A. 对候选对做精确碰撞判断
B. 给所有对象排序
C. 加载场景资源
D. 生成导航网格

答案：A

解析：精筛会使用更精细的几何测试。

28. 两个 AABB 在 x/y/z 三轴上都重叠时，通常说明？

A. AABB 相交或接触
B. 一定没有碰撞
C. 一定是球体
D. 一定发生网络丢包

答案：A

解析：AABB 相交测试就是检查各轴投影是否重叠。

29. 两个球体是否相交，常用判断是？

A. 中心距离是否小于等于半径和
B. 名字是否相同
C. 材质是否相同
D. 纹理大小是否相同

答案：A

解析：可比较平方距离避免开方。

30. 射线与 AABB 快速相交常见算法是？

A. slab 方法
B. 冒泡排序
C. KMP
D. Prim

答案：A

解析：slab 方法按轴求进入/离开区间。

31. Loose Quadtree 相比普通四叉树常用于改善？

A. 跨边界或较大对象频繁插入多个节点的问题
B. 字符串拼接
C. HTTP 请求
D. 音频混音

答案：A

解析：松散边界能减少对象在树中频繁移动或重复挂载。

32. AOI 中使用格子划分的主要目的是？

A. 快速找附近玩家/对象，减少无关同步或显示
B. 提高贴图分辨率
C. 让所有消息广播给全服
D. 替代渲染管线

答案：A

解析：AOI 关注兴趣范围，常结合网格或九宫格邻域。

33. 动态对象频繁移动时，空间树的一个主要成本是？

A. 插入、删除、更新节点
B. 字符串转大写
C. 纹理采样
D. DNS 查询

答案：A

解析：动态对象太多时，固定网格或空间哈希有时更简单。

34. 在地图大小固定且对象分布较均匀时，碰撞粗筛常用哪种结构？

A. 均匀网格/空间哈希
B. 完整遍历所有对象
C. 递归下降语法树
D. 链式前向星只能用于网络

答案：A

解析：均匀网格实现简单，适合动态对象和局部查询。

35. 高速子弹容易穿过薄物体时，常见处理方式是？

A. 使用射线/扫掠体/连续碰撞检测
B. 只在终点做一次点检测
C. 降低所有碰撞体精度
D. 关闭碰撞系统

答案：A

解析：高速物体离散采样可能发生隧穿，需要连续检测思路。

二、多选题

1. 实现 A* 通常需要哪些数据结构或信息？

A. open set
B. closed set
C. gScore/代价表
D. parent/前驱节点

答案：A、B、C、D

解析：open set 选候选，closed set 防重复，gScore 更新最短已知代价，parent 用于回溯路径。

2. A* 启发函数设计较稳的特性包括？

A. 不高估真实代价
B. 有方向指导性
C. 尽量和移动规则匹配
D. 越随机越好

答案：A、B、C

解析：启发函数既要安全，又要有区分度。

补充考法：旧文件中还出现过“可用于排序 open set”这类选项。更严谨地说，open set 通常按 f=g+h 排序，启发函数 h 参与排序，但不是单独排序依据。

题目图示

3. 四方向网格的合法邻居通常包括？

A. 上
B. 下
C. 左
D. 右

答案：A、B、C、D

解析：四方向不包含对角邻居。

4. 八方向网格寻路中需要额外注意？

A. 对角移动代价
B. 斜穿墙角问题
C. 启发函数匹配
D. 完全不需要障碍判断

答案：A、B、C

解析：对角移动不能穿过两个相邻障碍的夹角，代价也常与直走不同。

5. 优化 A* 性能的常见方式有？

A. 优先队列
B. 复用数组/对象池
C. 时间戳代替每次清空大数组
D. 每帧重建所有节点对象

答案：A、B、C

解析：节点复用和时间戳能减少分配和清空成本。

6. 大地图寻路可能使用哪些策略？

A. 分层寻路
B. 导航网格
C. 路径缓存
D. 全部单位每帧完整重算

答案：A、B、C

解析：完整重算容易造成帧耗时尖峰。

7. NavMesh 相关概念包括？

A. 可行走面
B. NavMesh Agent
C. Area Cost
D. NavMesh Link

答案：A、B、C、D

解析：这些都是导航网格系统里的常见概念。

8. 动态障碍处理可能采用？

A. 局部避障
B. 障碍 carve
C. 触发重新寻路
D. 每移动一厘米全量烘焙整张大地图

答案：A、B、C

解析：动态障碍通常局部处理，避免频繁全量重建。

9. 常见空间划分结构有？

A. 均匀网格
B. 四叉树
C. 八叉树
D. BVH

答案：A、B、C、D

解析：它们都能用于不同场景下的空间查询加速。

10. 碰撞 broad phase 可用的方法包括？

A. AABB 粗筛
B. Sweep and Prune
C. 空间哈希
D. 所有三角形两两精确求交

答案：A、B、C

解析：三角形精确求交属于更重的精筛。

补充考法：旧文件中还把“四叉树”作为正确选项之一；四叉树、八叉树、空间哈希这类空间划分都可用于 broad phase，目标是先减少候选碰撞对。

题目图示

11. 均匀网格/空间哈希适合哪些情况？

A. 对象分布较均匀
B. 动态对象较多
C. 查询邻近对象
D. 对象尺寸差异极端且跨越巨大区域

答案：A、B、C

解析：尺寸差异极大时，单一网格粒度会变难选。

12. 四叉树可能遇到的问题有？

A. 树不平衡
B. 对象跨节点边界
C. 动态更新成本
D. 只能处理字符串

答案：A、B、C

解析：实际工程常用 loose quadtree 或限制深度缓解。

13. BVH 更常用于哪些场景？

A. 射线检测
B. 静态场景三角形查询
C. 渲染/物理中的层级剔除
D. 保存账号密码

答案：A、B、C

解析：BVH 的核心是层级包围体剔除。

14. KD-Tree 与 Octree 的区别可能包括？

A. KD-Tree 通常二分空间
B. Octree 每层固定八分三维空间
C. KD-Tree 可按数据分布选择切分轴
D. 二者完全相同

答案：A、B、C

解析：二者都是空间结构，但划分方式不同。

15. AOI 九宫格常见处理包括？

A. 当前格子
B. 周围相邻格子
C. 进入/离开事件
D. 全地图广播

答案：A、B、C

解析：AOI 的价值就是减少无关对象集合。

题目图示

16. 高速弹道检测常见方案有？

A. 上一帧到当前帧做 Raycast
B. 扫掠球/胶囊体
C. 连续碰撞检测
D. 只检测当前点坐标

答案：A、B、C

解析：只检测离散点容易漏掉薄物体。

17. 路径平滑时必须注意？

A. 平滑后的线段仍可通行
B. 不能穿过障碍
C. 角色半径要纳入考虑
D. 只看视觉好看即可

答案：A、B、C

解析：平滑不能破坏寻路约束。

18. 多单位寻路常见优化包括？

A. 错峰计算
B. 共享部分路径
C. 缓存同区域路径
D. 所有单位每帧重新 A*

答案：A、B、C

解析：错峰和缓存能降低瞬时开销。

19. 碰撞检测流程中常见阶段包括？

A. 粗筛
B. 精筛
C. 碰撞响应
D. 完全不需要空间结构

答案：A、B、C

解析：空间结构主要用于粗筛，不等于完整物理系统。

20. 游戏客户端空间查询常见用途有？

A. 查找附近敌人
B. 技能范围检测
C. 视野/AOI
D. UI 文案翻译

答案：A、B、C

解析：空间查询服务于战斗、AI、同步、渲染裁剪等系统。

三、判断题

1. A* 在所有地图上一定比 Dijkstra 更快。

答案：错

解析：启发函数质量、地图结构和实现都会影响速度。

2. 可采纳启发函数不应高估真实最短代价。

答案：对

解析：这是 A* 保证最优性的关键条件之一。

3. 四方向网格一般可以用曼哈顿距离作为启发函数。

答案：对

解析：上下左右移动时，曼哈顿距离与移动模型匹配。

4. 允许斜向移动时，仍无脑使用曼哈顿距离一定最优。

答案：错

解析：如果斜向代价更低，曼哈顿可能高估。

5. C++ priority_queue 默认是小顶堆。

答案：错

解析：默认是大顶堆。

6. A* 的 parent 信息通常用于回溯最终路径。

答案：对

解析：终点找到后沿 parent 回到起点。

7. 四叉树用于三维空间递归八分。

答案：错

解析：三维递归八分是八叉树。

8. 八叉树每个节点最多划分为 8 个子空间。

答案：对

解析：对应三维空间的八个象限。

9. BVH 通过层级包围体减少无关几何测试。

答案：对

解析：不相交的包围体分支可以整体跳过。

10. broad phase 的结果一定就是最终碰撞结果。

答案：错

解析：粗筛只产生候选对，还要精筛确认。

11. AABB 相交测试通常检查各坐标轴投影是否重叠。

答案：对

解析：任一轴分离则不相交。

12. NavMesh 可以表示角色可行走区域。

答案：对

解析：导航网格用于路径搜索和空间推理。

13. NavMesh Link 可用于连接跳跃、门、断层等特殊通行关系。

答案：对

解析：普通可走面无法表达的连接可用 Link。

14. 局部避障可以完全替代全局路径搜索。

答案：错

解析：局部避障处理短距离冲突，全局寻路负责到达目标。

15. AOI 只可能用于服务端，客户端没有使用价值。

答案：错

解析：客户端也可用 AOI 思路做显示、音效、AI、特效和查询裁剪。

四、填空题

1. A* 常用评价函数为 f(n)=______(n)+h(n)。

答案：g

解析：g 是起点到当前节点的真实代价。

2. 四方向网格从 `(x1,y1)` 到 `(x2,y2)` 的曼哈顿距离为 `abs(x1-x2)+______`。

答案：abs(y1-y2)

解析：曼哈顿距离是两个坐标轴差值绝对值之和。

3. A* 中用于保存待扩展节点的集合通常称为 ______ set。

答案：open

解析：open set 是候选节点集合。

4. A* 中用于避免重复扩展的集合通常称为 ______ set。

答案：closed

解析：closed set 保存已处理节点。

5. 回溯路径时，每个节点通常记录它的 ______ 节点。

答案：parent

解析：沿 parent 回溯得到路径。

6. 二维空间递归四分的数据结构叫 ______。

答案：四叉树

解析：四叉树用于 2D 空间划分。

7. 三维空间递归八分的数据结构叫 ______。

答案：八叉树

解析：八叉树用于 3D 空间划分。

8. AABB 的中文常写作轴对齐 ______。

答案：包围盒

解析：AABB 是 Axis-Aligned Bounding Box。

9. Bounding Volume Hierarchy 通常缩写为 ______。

答案：BVH

解析：BVH 是包围体层次结构。

10. 碰撞检测中，先快速筛候选对的阶段称为 ______ phase。

答案：broad

解析：broad phase 后再做 narrow phase。

五、C++ 代码阅读题

1. priority_queue 默认顺序

阅读代码，写出输出或说明问题：

cpp

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int> q;
    q.push(3);
    q.push(1);
    q.push(5);

    while (!q.empty())
    {
        cout << q.top() << " ";
        q.pop();
    }
    return 0;
}

答案：5 3 1

解析：priority_queue<int> 默认是大顶堆，top 返回当前最大值。

2. 小顶堆取最小 f

阅读代码，写出输出或说明问题：

cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    priority_queue<int, vector<int>, greater<int>> q;
    q.push(30);
    q.push(10);
    q.push(20);
    cout << q.top();
    return 0;
}

答案：10

解析：greater<int> 让 priority_queue 表现为小顶堆。

3. 曼哈顿距离计算

阅读代码，写出输出或说明问题：

cpp

#include <iostream>
#include <cmath>
using namespace std;

int H(int x1, int y1, int x2, int y2)
{
    return abs(x1 - x2) + abs(y1 - y2);
}

int main()
{
    cout << H(1, 2, 5, 8);
    return 0;
}

答案：10

解析：|1-5| + |2-8| = 4 + 6 = 10。

4. AABB 接触是否算相交

阅读代码，写出输出或说明问题：

cpp

#include <iostream>
using namespace std;

struct AABB
{
    int minX, maxX, minY, maxY;
};

bool Overlap(const AABB& a, const AABB& b)
{
    return a.minX <= b.maxX && a.maxX >= b.minX &&
           a.minY <= b.maxY && a.maxY >= b.minY;
}

int main()
{
    AABB a{0, 10, 0, 10};
    AABB b{10, 20, 3, 6};
    cout << Overlap(a, b);
    return 0;
}

答案：1

解析：这里使用 <= 和 >=，边界接触也算重叠。

5. 球体相交平方距离

阅读代码，写出输出或说明问题：

cpp

#include <iostream>
using namespace std;

bool Hit(int dx, int dy, int r1, int r2)
{
    int dist2 = dx * dx + dy * dy;
    int r = r1 + r2;
    return dist2 <= r * r;
}

int main()
{
    cout << Hit(3, 4, 2, 3);
    return 0;
}

答案：1

解析：距离为 5，半径和为 5，接触算相交。

6. 空间哈希格子坐标

阅读代码，写出输出或说明问题：

cpp

#include <iostream>
using namespace std;

int main()
{
    int cellSize = 10;
    int x = 25;
    int y = 39;
    cout << x / cellSize << "," << y / cellSize;
    return 0;
}

答案：2,3

解析：整数除法得到对象所在格子坐标。

7. 路径回溯顺序

阅读代码，写出输出或说明问题：

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> parent = {-1, 0, 1, 2};
    vector<int> path;
    for (int cur = 3; cur != -1; cur = parent[cur])
    {
        path.push_back(cur);
    }
    reverse(path.begin(), path.end());

    for (int v : path)
    {
        cout << v << " ";
    }
    return 0;
}

答案：0 1 2 3

解析：先从终点回溯到起点，再反转。

8. 优先队列旧节点问题

阅读代码，写出输出或说明问题：

cpp

#include <queue>
#include <vector>
using namespace std;

struct Node
{
    int id;
    int f;
};

struct Cmp
{
    bool operator()(const Node& a, const Node& b) const
    {
        return a.f > b.f;
    }
};

// 同一个 id 可能因为更短路径被再次 push 进 priority_queue。
// 旧的较大 f 节点仍可能留在堆里。

答案：弹出时需要判断是否为过期节点

解析：C++ priority_queue 不支持直接 decrease-key，常见做法是重复入堆，弹出时用当前 g/f 表过滤旧节点。

9. 网格 BFS 最短步数

阅读代码，写出输出或说明问题：

cpp

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    int dist[3][3];
    for (auto& row : dist)
    {
        for (int& v : row)
        {
            v = -1;
        }
    }

    queue<pair<int, int>> q;
    q.push({0, 0});
    dist[0][0] = 0;
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        for (auto& d : dirs)
        {
            int nx = x + d[0];
            int ny = y + d[1];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3 || dist[nx][ny] != -1)
            {
                continue;
            }
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }

    cout << dist[2][2];
    return 0;
}

答案：4

解析：3x3 空网格从 (0,0) 四方向走到 (2,2) 最少 4 步。

10. 四叉树容量触发分裂

阅读代码，写出输出或说明问题：

cpp

#include <iostream>
using namespace std;

int main()
{
    int capacity = 4;
    int count = 0;
    bool split = false;

    for (int i = 0; i < 5; ++i)
    {
        ++count;
        if (count > capacity)
        {
            split = true;
        }
    }

    cout << split;
    return 0;
}

答案：1

解析：超过单节点容量时，四叉树常触发分裂或下放对象。

六、C++ 代码填空题

1. 补全曼哈顿距离

补全横线处代码：

cpp

int Manhattan(int x1, int y1, int x2, int y2)
{
    return abs(x1 - x2) + ______;
}

答案：abs(y1 - y2)

解析：四方向网格常用曼哈顿距离。

2. 补全小顶堆声明

补全横线处代码：

cpp

priority_queue<Node, vector<Node>, ______> openSet;

答案：Cmp

解析：自定义比较器让 f 小的节点优先弹出。

3. 补全网格越界判断

补全横线处代码：

cpp

bool InBounds(int x, int y, int width, int height)
{
    return x >= 0 && x < width && y >= 0 && ______;
}

答案：y < height

解析：横纵坐标都要在合法范围内。

4. 补全 AABB 一维分离判断

补全横线处代码：

cpp

bool SeparatedOnX(const AABB& a, const AABB& b)
{
    return a.maxX < b.minX || ______;
}

答案：b.maxX < a.minX

解析：一维上互相在对方左侧则分离。

5. 补全空间哈希 key

补全横线处代码：

cpp

long long Key(int cellX, int cellY)
{
    return (static_cast<long long>(cellX) << 32) ^ static_cast<unsigned int>(______);
}

答案：cellY

解析：把两个 32 位格子坐标组合成一个 64 位 key。

七、简答题

1. 比较 BFS、Dijkstra、A* 在寻路中的区别。

参考答案：BFS 适合无权图或所有边代价相同的网格，按层扩展可得到最少步数；Dijkstra 适合非负权图，按已知最小代价扩展；A* 在 Dijkstra 基础上加入启发函数 h，用 f=g+h 引导搜索，启发函数设计得好时能显著减少扩展节点。

题目图示

2. 比较四叉树、八叉树、KD-Tree、BVH 的适用场景。

参考答案：四叉树适合二维区域查询，八叉树适合三维空间递归划分，KD-Tree 适合按轴二分的点或空间查询，BVH 更偏向用层级包围体组织物体或三角形，常用于射线检测、碰撞粗筛和渲染剔除。动态对象很多时，均匀网格或空间哈希可能更简单稳定。

题目图示

3. 简述 NavMesh 寻路的一般流程。

参考答案：先根据场景几何和角色参数生成可行走导航网格，再把起点和终点投影到 NavMesh 上，在多边形邻接图上搜索路径，然后通过拐点或漏斗算法得到路径点。运行时可结合 Agent 半径、Area Cost、NavMesh Link、局部避障和动态障碍处理。

八、场景分析题

1. 场景：一张大地图中有 500 个怪物同时向玩家移动，某一帧全部重新 A*，导致明显卡顿。请分析原因并给出优化方案。

参考答案：问题通常是同一帧寻路请求集中，open set 扩展、节点分配、地图访问造成 CPU 峰值。可做分帧调度和优先级队列，近距离单位高频更新、远距离低频更新；相同目标可共享路径前缀或使用流场/层次寻路；节点数组复用，避免每次 new；路径结果缓存；单位移动阶段使用局部避障，而不是每帧完整重算。

题目图示

2. 场景：战斗场景有上千个投射物和敌人，直接两两检测碰撞导致性能下降。请设计空间划分和碰撞检测流程。

参考答案：先用均匀网格或空间哈希把对象按位置放入格子；每个投射物只查询所在格及相邻格的候选敌人；用 AABB 或圆形先做 broad phase，再做射线、胶囊、球体或精确碰撞等 narrow phase；高速投射物用上一帧到当前帧的扫掠检测防止隧穿；对象移动时更新格子索引，对候选数量、检测耗时和漏检情况做统计。

题目图示

寻路与空间划分 共100题 ​

题型统计 ​

一、单选题 ​

1. A* 算法中的 f 值通常等于？ ​

2. A* 中 g 值通常表示？ ​

3. A* 中 h 值通常表示？ ​

4. A* 每次从 open set 中通常取出哪个节点扩展？ ​

5. closed set 的主要作用是？ ​

6. 当 A* 的启发函数 h 恒为 0 时，算法退化为？ ​

7. 可采纳启发函数 admissible heuristic 的关键条件是？ ​

8. 四方向网格寻路中，常用的启发函数是？ ​

9. 八方向网格允许斜向移动时，更常见的启发函数是？ ​

10. Weighted A* 常见做法是？ ​

11. C++ std::priority_queue<int> 默认行为是？ ​

12. A* 最终回溯路径通常依赖？ ​

13. 网格寻路中，障碍格的处理通常是？ ​

14. NavMesh 的核心含义是？ ​

15. NavMesh Link/OffMesh Link 常用于表示？ ​

16. NavMesh Agent 的 radius 主要影响？ ​

17. NavMesh Area Cost 的作用是？ ​

18. 大量单位同时寻路时，较合理的策略是？ ​

19. 路径平滑常见目的是什么？ ​

20. 层次寻路 HPA* 的主要用途是？ ​

21. 四叉树最适合描述哪类空间划分？ ​

22. 八叉树最适合描述哪类空间划分？ ​

23. BVH 的全称和核心思想是？ ​

24. KD-Tree 的常见划分方式是？ ​

25. 空间哈希常见做法是？ ​

26. 碰撞检测 broad phase 的主要目标是？ ​

27. narrow phase 主要负责？ ​

28. 两个 AABB 在 x/y/z 三轴上都重叠时，通常说明？ ​

29. 两个球体是否相交，常用判断是？ ​

30. 射线与 AABB 快速相交常见算法是？ ​

31. Loose Quadtree 相比普通四叉树常用于改善？ ​

32. AOI 中使用格子划分的主要目的是？ ​

33. 动态对象频繁移动时，空间树的一个主要成本是？ ​

34. 在地图大小固定且对象分布较均匀时，碰撞粗筛常用哪种结构？ ​

35. 高速子弹容易穿过薄物体时，常见处理方式是？ ​

二、多选题 ​

1. 实现 A* 通常需要哪些数据结构或信息？ ​

2. A* 启发函数设计较稳的特性包括？ ​

3. 四方向网格的合法邻居通常包括？ ​

4. 八方向网格寻路中需要额外注意？ ​

5. 优化 A* 性能的常见方式有？ ​

6. 大地图寻路可能使用哪些策略？ ​

7. NavMesh 相关概念包括？ ​

8. 动态障碍处理可能采用？ ​

9. 常见空间划分结构有？ ​

10. 碰撞 broad phase 可用的方法包括？ ​

11. 均匀网格/空间哈希适合哪些情况？ ​

12. 四叉树可能遇到的问题有？ ​

13. BVH 更常用于哪些场景？ ​

14. KD-Tree 与 Octree 的区别可能包括？ ​

15. AOI 九宫格常见处理包括？ ​

16. 高速弹道检测常见方案有？ ​

17. 路径平滑时必须注意？ ​

18. 多单位寻路常见优化包括？ ​

19. 碰撞检测流程中常见阶段包括？ ​

20. 游戏客户端空间查询常见用途有？ ​

三、判断题 ​

1. A* 在所有地图上一定比 Dijkstra 更快。 ​

2. 可采纳启发函数不应高估真实最短代价。 ​

3. 四方向网格一般可以用曼哈顿距离作为启发函数。 ​

4. 允许斜向移动时，仍无脑使用曼哈顿距离一定最优。 ​

5. C++ priority_queue 默认是小顶堆。 ​

6. A* 的 parent 信息通常用于回溯最终路径。 ​

7. 四叉树用于三维空间递归八分。 ​

8. 八叉树每个节点最多划分为 8 个子空间。 ​

9. BVH 通过层级包围体减少无关几何测试。 ​

10. broad phase 的结果一定就是最终碰撞结果。 ​

11. AABB 相交测试通常检查各坐标轴投影是否重叠。 ​

12. NavMesh 可以表示角色可行走区域。 ​

13. NavMesh Link 可用于连接跳跃、门、断层等特殊通行关系。 ​

14. 局部避障可以完全替代全局路径搜索。 ​

15. AOI 只可能用于服务端，客户端没有使用价值。 ​

四、填空题 ​

1. A* 常用评价函数为 f(n)=______(n)+h(n)。 ​

2. 四方向网格从 (x1,y1) 到 (x2,y2) 的曼哈顿距离为 abs(x1-x2)+______。 ​

3. A* 中用于保存待扩展节点的集合通常称为 ______ set。 ​

4. A* 中用于避免重复扩展的集合通常称为 ______ set。 ​

寻路与空间划分共100题

题型统计

一、单选题

1. A* 算法中的 f 值通常等于？

2. A* 中 g 值通常表示？

3. A* 中 h 值通常表示？

4. A* 每次从 open set 中通常取出哪个节点扩展？

5. closed set 的主要作用是？

6. 当 A* 的启发函数 h 恒为 0 时，算法退化为？

7. 可采纳启发函数 admissible heuristic 的关键条件是？

8. 四方向网格寻路中，常用的启发函数是？

9. 八方向网格允许斜向移动时，更常见的启发函数是？

10. Weighted A* 常见做法是？

11. C++ `std::priority_queue<int>` 默认行为是？

12. A* 最终回溯路径通常依赖？

13. 网格寻路中，障碍格的处理通常是？

14. NavMesh 的核心含义是？

15. NavMesh Link/OffMesh Link 常用于表示？

16. NavMesh Agent 的 radius 主要影响？

17. NavMesh Area Cost 的作用是？

18. 大量单位同时寻路时，较合理的策略是？

19. 路径平滑常见目的是什么？

20. 层次寻路 HPA* 的主要用途是？

21. 四叉树最适合描述哪类空间划分？

22. 八叉树最适合描述哪类空间划分？

23. BVH 的全称和核心思想是？

24. KD-Tree 的常见划分方式是？

25. 空间哈希常见做法是？

26. 碰撞检测 broad phase 的主要目标是？

27. narrow phase 主要负责？

28. 两个 AABB 在 x/y/z 三轴上都重叠时，通常说明？

29. 两个球体是否相交，常用判断是？

30. 射线与 AABB 快速相交常见算法是？

31. Loose Quadtree 相比普通四叉树常用于改善？

32. AOI 中使用格子划分的主要目的是？

33. 动态对象频繁移动时，空间树的一个主要成本是？

34. 在地图大小固定且对象分布较均匀时，碰撞粗筛常用哪种结构？

35. 高速子弹容易穿过薄物体时，常见处理方式是？

二、多选题

1. 实现 A* 通常需要哪些数据结构或信息？

2. A* 启发函数设计较稳的特性包括？

3. 四方向网格的合法邻居通常包括？

4. 八方向网格寻路中需要额外注意？

5. 优化 A* 性能的常见方式有？

6. 大地图寻路可能使用哪些策略？

7. NavMesh 相关概念包括？

8. 动态障碍处理可能采用？

9. 常见空间划分结构有？

10. 碰撞 broad phase 可用的方法包括？

11. 均匀网格/空间哈希适合哪些情况？

12. 四叉树可能遇到的问题有？

13. BVH 更常用于哪些场景？

14. KD-Tree 与 Octree 的区别可能包括？

15. AOI 九宫格常见处理包括？

16. 高速弹道检测常见方案有？

17. 路径平滑时必须注意？

18. 多单位寻路常见优化包括？

19. 碰撞检测流程中常见阶段包括？

20. 游戏客户端空间查询常见用途有？

三、判断题

1. A* 在所有地图上一定比 Dijkstra 更快。

2. 可采纳启发函数不应高估真实最短代价。

3. 四方向网格一般可以用曼哈顿距离作为启发函数。

4. 允许斜向移动时，仍无脑使用曼哈顿距离一定最优。

5. C++ priority_queue 默认是小顶堆。

6. A* 的 parent 信息通常用于回溯最终路径。

7. 四叉树用于三维空间递归八分。

8. 八叉树每个节点最多划分为 8 个子空间。

9. BVH 通过层级包围体减少无关几何测试。

10. broad phase 的结果一定就是最终碰撞结果。

11. AABB 相交测试通常检查各坐标轴投影是否重叠。

12. NavMesh 可以表示角色可行走区域。

13. NavMesh Link 可用于连接跳跃、门、断层等特殊通行关系。

14. 局部避障可以完全替代全局路径搜索。

15. AOI 只可能用于服务端，客户端没有使用价值。

四、填空题

1. A* 常用评价函数为 f(n)=______(n)+h(n)。

2. 四方向网格从 `(x1,y1)` 到 `(x2,y2)` 的曼哈顿距离为 `abs(x1-x2)+______`。

3. A* 中用于保存待扩展节点的集合通常称为 ______ set。

4. A* 中用于避免重复扩展的集合通常称为 ______ set。