背后的故事
几年前，Yandex组织了一个名为Robots Couriers的比赛，奖品非常诱人：一张前往专业闭门自动驾驶会议的门票。这个比赛类似于一场游戏，参赛者需要在地图上找到最佳路线，并通过机器人快递优化交付。
当我深入研究这个话题时，我发现尽管路径规划是一个已解决的问题，但它仍然对专业游戏开发社区具有吸引力。在2010年至2020年期间，工程师们对A*算法进行了重大优化，特别适用于具有庞大地图的AAA游戏。阅读关于这些优化的文章和研究论文是一次令人激动的经历。
此外，比赛要求的设计使得比赛测试系统可以轻松评估程序的输出。因此，对可视化的重视不高。
我发现探索这个领域并开发一个使用众所周知的图算法在网格地图上找到路径的小应用程序非常有趣。为了可视化我的发现，我使用了SFML图形库。
目标
这个项目基于我之前的一个努力，我在那个项目中展示了四个众所周知的路径规划算法（BFS、DFS、Dijkstra和A*）并没有根本区别，可以用一种通用的方式实现。然而，在那个项目中展示这些算法之间的显著性能差异是具有挑战性的。
在这篇文章中，我希望使用改进的测试数据并设计出一些视觉上令人兴奋的东西。虽然前面提到的Yandex比赛任务与我的目标非常契合，但我不会在这里解决他们的具体问题，因为它严重依赖于他们的测试系统，而该系统目前不可用。
相反，我将从那个比赛中提取一般的输入参数思路，并创建自己的实现。
虚构的世界
想象一个技术先进、创新的城市，未来早已到来。在这个城市中，大部分订单都是由机器人快递员送达，人类从咖啡馆送订单已经成为一种罕见现象。在这个任务中，我们邀请您参与寻找高效交付订单的最佳路线。
让我们将这个城市想象成一个N×N的地图。为了简单起见，我们假设每个机器人都占据一个单元格，每个单元格可以是可通过或不可通过的。在一个步骤中，如果目标单元格是空闲的，机器人可以朝任意四个方向（上、下、左或右）移动。
我忽略了原始任务的其余部分：在测试开始时，您需要输出您想要使用的机器人数量以及它们的初始坐标。每个机器人的构建将花费Costc卢布。
接下来，将进行T次模拟迭代。一次迭代表示一分钟的虚拟时间，由60秒组成。在每次迭代中，您的程序将得到新订单的数量，然后程序应告诉您每个机器人执行的动作（每个机器人60个动作）。
对于每个成功交付的订单，您将获得max(0, MaxTips – DeliveryTime)美元的小费，其中MaxTips是一个订单的最大小费数额，DeliveryTime是从订单出现到交付的时间，以秒为单位。
您在一个测试中获得的总分数由公式TotalTips – R × Costc计算，其中TotalTips是总小费数额，R是使用的机器人数量，Costc是构建一个机器人的成本。每个测试中都会设置Costc和MaxTips的值。如果您获得的小费少于制造机器人的花费，您的总分将为0。如果您执行了任何错误的操作，您也将获得0分。
输入
程序使用标准输入读取参数。这种方法允许我们使用输入文件来指定各种复杂度的测试数据。
输入的第一行包含三个自然数：N（城市地图的大小）、MaxTips（每个订单的最大小费数额）和Costc（构建一个机器人的成本）。在我的第一个实现中，我忽略了MaxTips和Costc参数，也许以后会考虑它们。
接下来，每一行都包含N个字符，表示城市地图。每个字符串可以由两种类型的字符组成：
- ‘#’ – 表示被障碍物占据的单元格。
- ‘.’ – 表示空闲的空间。
接下来，您将得到两个自然数：T和D（T ≤ 100,000，D ≤ 10,000,000）。T表示交互迭代的次数，D表示订单的总数。
输出
您的任务是使用SFML图形库来可视化地图和最佳路径。
地图建模
我喜欢将地图表示为一个单元格网格。因此，我倾向于以单元格为基础，将所有结果渲染并映射为网格。
还有一种选择是在网格上直接执行路径搜索，而不使用任何额外的数据结构（出于学习目的，我也实现了这一点：请参见代码）。
但是由于网格的存在，可以很容易地使用一种或另一种方式将地图表示为图形。我更喜欢使用细胞的邻接表来表示大多数算法，如BFS、Dijkstra和A-Star。对于Bellman-Ford等算法，使用边的列表而不是邻接表可能是有意义的。所以，如果您探索代码库，您将找到所有这些，并且它们都是可行的示例。
为了分割逻辑和责任，我有一个导航器实体，负责根据通过AppConfig文件和相关地图文件指定的订单和任务配置来执行路径查找。
AppConfig的样子如下：
请注意，map_，map__等实际上不是配置属性。它们在应用程序运行期间被忽略。由于无法在JSON文件的部分中添加注释，我在属性名称中使用下划线，以便它可以保留在配置文件中但不被使用。
地图文件的样子如下：
25 50 150
#########################
#########################
#########################
###.......#####.......###
###.......#####.......###
###.......#####.......###
###...................###
###.......#####.......###
###.......#####.......###
###...................###
######.###########.######
######.###########.######
######.###########.######
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
######.###########.######
#########################
#########################
#########################
#########################
2 4
2
6 6 4 20这是最简单的例子之一，其中包含了阻塞或非阻塞的单元格。我准备了很多不同的输入参数和测试数据的例子，从非常小的部分开始，可以帮助您调试和学习代码，到一个巨大的地图（来自现实中存在的城市），可以帮助我们衡量图形算法的性能。
我们如何绘制地图？
当地图只包含具有二进制状态（被阻塞或非阻塞）的单元格时，这基本上意味着图中的任何边或存在或不存在。
为了在图中找到一条路径，我们必须有效地表示它。就像在我之前的帖子中一样，我使用的是具有Vector[NodeId]->指向->Vector[Neighbour Nodes]关系的邻接表：
有趣的是，当我们探索网格时，根本不需要使用图。我们能够使用BFS/DFS算法逐个单元格地遍历网格，而不必考虑边缘。请参见方法_GetPathByBFSOnGrid。
首先，初始化代码逐行逐列地读取文件并将其转换为网格：
然后，它创建一个实际的图形作为邻接表：
网格表示对于使用SFML库绘制在屏幕上非常有用。我们可以通过创建几何对象来绘制（这正是我对小地图所做的）：
或者我们可以高效地以像素为单位进行绘制更大的地图：
最后，让我们看看由文件test_25_xmax定义的地图是什么样子。
最初，文件定义如下：
SFML渲染的地图如下：
因为我希望用户能够通过键盘来控制所有这些，所以我将所有用户行为逻辑留在了main.cpp中。我喜欢称它为“控制器”逻辑。
SFML库非常容易处理键盘事件：
主要思想是，用户触发（按下SPACE键）读取地图文件并渲染地图，然后第二个触发（再次按下SPACE键）加载路由任务并计算地图上两点之间的最短路径：
我们需要深入进去
我想要尝试更多的图算法，它们都有各自的限制，所以我决定实现可以由多权重图表示的多色地图。
每个单元格都有颜色，颜色意味着边不仅存在，而且还应用了一些权重（或费用，或罚款，你随意）。因此，边可以被阻塞、半阻塞、不阻塞…你懂的。
因此，我实现了看起来更加欢乐和准备好游戏的多色地图（来自文件test_31_multi_weight_graph_map的示例）：
一些配置文件包含来自真实存在的城市的更复杂地图，比如test_29_yandex_weighten_real_map：
作为一项挑战，现在我们应该处理非常灵活的配置的地图。RectangularMap.cpp 本质上包含了很多内部逻辑，包括所有的图算法，甚至更多（因为我喜欢尝试事物，即使它现在并不特别有用）。
我实现了BFS#Line 598，Dijkstra#Line 299，A-Star#Line 356，Bellman-Ford#Line 428 算法，以及一些额外的“实用”算法，如拓扑排序、单源路径，它们对于当前应用状态没有用处（因为它们适用于非循环图，而不是我当前使用的图类型），但我有一些想法可以在未来的改进中使用它们。
我没有完善所有的代码，也没有使其足够理想，但它允许我（希望也能让你）与代码进行交互并比较性能指标。
对于一些注释掉的代码行或者一些混乱的代码，我表示抱歉…这是学习的一种方式：）。为了了解内部情况，我建议你查看RectangularMap.h。
还有一些有趣的功能，比如焦点功能，它允许仅渲染地图的特定部分。当用户按下PgDown或PgUp按钮时，它使用观察者模式重新渲染必要的部分来改变焦点。很容易改进这个功能并实现“缩放”功能。如果你喜欢的话，可以把它当作作业来做。
在使用test_29_yandex_weighten_real_map文件的焦点功能中的工作情况：
类图如下：
运行和玩耍
我相信最有趣的部分就是运行这个小应用程序，并玩弄其配置和算法的变化。你可以通过使用不同的地图文件作为输入参数以及改变代码中的逻辑来进行很多实验。
启动后，你需要按下空格键。应用程序将根据配置文件渲染地图，从最简单的测试用例开始探索到最复杂的测试用例是有很多意义的。
再次按下空格键执行路径规划算法，找到起点和最近订单之间的路径。顺便说一句，它还没有完成，但很容易实现读取地图配置文件中的所有剩余订单并对它们执行路径规划。
这是在由test_18_yandex_super_high_res文件定义的地图上找到的路径：
它还可以在模拟现有城市的地图中找到路径，比如test_29_yandex_weighten_real_map：
对于像BFS这样的算法来说，在两个坐标之间找到有效路径是具有挑战性的，但对于A星算法来说很容易实现。
根据地图配置文件中的单元格，应用程序将处理地图作为加权或非加权图，并为其选择正确的算法（你也可以很容易地更改这一点）。BFS和A-Star的性能差异很容易看出：
最后的话
通过这个，我想让你独自一人并玩弄这些代码示例。我希望你会发现它很有趣，并从中学到很多东西。
敬请关注！
链接
- 通用的BFS、DFS、Dijkstra和A-Star算法实现
- JPS+：比A*快100倍，作者：Steve Rabin
- A* 优化和改进，作者：Lucho Suaya