广度优先搜索、Dijkstra和A*是图上的三种典型路径规划算法。它们都可用于图搜索，不同之处在于队列和启发式函数两个参数。

本项目探索并可视化不同算法如何根据选择参数进行图搜索。

算法的一般性原理如下：

将边界初始化为包含起始节点的队列。

当边界队列不为空时，从队列中“访问”并删除一个“当前”节点，同时将访问节点的每个邻居节点添加到队列，其成本是到达当前节点的成本加上从当前节点访问邻居的成本再加上邻居节点和目标节点的启发式函数值。其中，启发式函数是对两个节点的路径成本的估计。

存储访问路径（通常存储在cameFrom图中），以便后续重建路径。如果邻居节点已经在列表中，同时新路径的成本较低，那么更改其成本。

找到目标路径（提前退出）或列表为空时，停止算法。

BFS

使用先进先出队列实现BFS。这种队列会忽略路径中链接的开销，并根据跳数进行扩展，因此可以确保找到最短路径的跳数，而跳数相关的成本。启发式函数的选择是任意的，因为在这个过程中其并不起作用。

使用数组可实现先进先出，即将元素附加到末尾并从头删除。

BFS演示动图。注意边界节点（黄色）是如何在网格中扩展为正方形的。在这里，正方形是相同“跳距”的节点集。

Dijkstra

在图上使用优先级队列和始终返回0的启发式函数，便得到Dijkstra算法。

相比于BFS，Dijkstra最大的不同在于考虑了成本。通过该算法，可以根据节点到节点的成本找到最短路径。

优先级队列使用数组实现，在每次插入新节点后对该数组进行排序。尽管实现优先级队列还有其他更高效的方式，但在我们的场景中，数组是足够快的，而且实现起来也简单。