QuadPath Lab 是一个在浏览器里运行的路径规划实验台。它把空间划分、图搜索和交互可视化接成一条完整流程：先将栅格地图构建成四叉树，再从可通行的叶节点生成邻接图，最后交给 A* 或 Dijkstra 寻找路径。
三个概念分别负责什么
四叉树解决的是“怎样表示空间”。 普通栅格会把每个单元格都当作独立节点；四叉树则从整张地图开始递归四分。如果一个区域内部状态一致，就保留为一个较大的叶节点；只有同时包含空闲与障碍的混合区域才继续分割。空旷区域因此可以被一个节点概括，而障碍边缘仍然保留细节。
Dijkstra 解决的是“怎样保证找到最短路径”。 它从起点开始，始终扩展当前累计代价最小的节点，不猜测终点方向。只要边权非负，它就能得到最短路径；代价是通常会向四周展开更多节点。
A* 解决的是“怎样更有方向地寻找同一条最短路径”。 它在 Dijkstra 的累计代价 g(n) 上加入到终点的启发式估计 h(n)，按照 f(n) = g(n) + h(n) 决定扩展顺序。Lab 使用几何距离作为启发式，因此搜索会更集中地朝终点推进。
可以把它们的关系简单理解为：
栅格地图
↓ 递归划分
四叉树叶节点
↓ 建立空间邻接与移动代价
可搜索的图
├─ Dijkstra：只看已经走过的代价
└─ A*：已走代价 + 到终点的估计四叉树不是第三种寻路算法，也不会代替 A* 或 Dijkstra。它负责减少和组织搜索节点；两种算法负责在这些节点之间选择路线。
它们如何被整合到一起
每次编辑地图后，Lab 都会重新构建四叉树，并收集所有可通行叶节点。只要两个自由叶节点在空间上共享边界，就在它们之间建立连接；连接的权重来自节点中心之间的几何距离。起点和终点会被映射到各自所在的叶节点，然后两种算法在完全相同的图上运行。
这让对比变得公平：空间结构、起点、终点和边权全部一致，变化的只有节点扩展策略。运行结果会记录访问顺序、最终路径、扩展节点数、路径长度与计算时间。
地图中的蓝色区域表示搜索过程已经扩展的空间节点，橙色折线表示最终路线。右侧的树结构用于查看地图区域怎样被递归划分；弹出的 D3 力导向图展示的是四叉树父子层级，而不是寻路使用的邻接图。紫色连线标出从根节点到当前节点的层级路径。
怎样使用这个 Lab
- 从测试场景中选择错位通道、连通房间或开放平原，也可以调整行列数量。
- 使用障碍、擦除、起点和终点工具直接编辑地图；四叉树会随地图实时重建。
- 在 A* 与 Dijkstra 之间选择当前算法，点击“运行”开始搜索动画。
- 使用底部播放、单步和速度控制检查节点扩展顺序，再到“算法结果”比较两次真实运行的数据。
- 在观察模式中点击地图区域，右侧会定位到对应树节点；沿四分导航器继续深入，可以看到每一层怎样覆盖原地图。
- 点击“拓扑图”打开可移动窗口。拖动节点、缩放画布、折叠子树或重新布局，同时仍能对照背景地图。
- 右上角可以切换中文、英文以及浅色、深色主题。所有计算都留在当前浏览器，不上传地图数据。
这个项目想展示的不是“某个算法跑出一条线”，而是空间表示如何改变搜索规模，以及同一张图上不同搜索策略为什么会呈现不同的探索过程。