探索 WallE 的寻路算法
我之前展示了一种统一实现图遍历算法的方法。现在，我将使其更具视觉吸引力，并研究其性能差异。
引言
作为一个非专业游戏开发者，我一直对各种概念感到好奇，并喜欢探索与我日常工作不直接相关的课题。
纵观我的职业生涯，我经常发现自己会参与一些小型游戏项目，这些项目让我能够练习和学习各种解决问题的技巧。
虽然我可能不会总是完成和打磨我开发的游戏，但我发现即使游戏不完整，在这个过程中也能获得丰富的知识。这些项目让我接触到了一系列有趣的挑战，包括多边形的几何计算、状态机、排序算法、渲染技术、实体建模、文件和数据库操作，以及使用各种图形库（如 XNA、OpenGL、OpenGL ES、GL、WebGL、SDL、SFML 等）。
更令我着迷的是，我意识到游戏编程的概念不仅限于游戏开发本身，它们还可以与其他领域交叉，例如机器人技术和自动驾驶技术。
故事背景
几年前，Yandex 组织了一场名为“机器人快递员”的比赛，奖品丰厚：一张参加“专业人士封闭式自动驾驶会议”的门票。比赛类似一个游戏，参赛者需要在一个地图上寻找最优路线，并优化机器人快递员的配送。
在深入研究这个课题时，我发现尽管路线查找已经是一个已解决的问题，但它仍然引起了专业游戏开发社区的兴趣。在 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 行每行包含 N 个字符，表示城市地图。每个 string 可以由两种类型的字符组成
- '
#' - 表示被障碍物占据的单元格 - '
.' - 表示空闲空间
接下来，将提供两个自然数：T 和 D（T ≤ 100,000，D ≤ 10,000,000）。T 表示交互迭代次数，D 表示总订单数。
输出
您的任务是使用 SFML 图形库可视化地图和最优路线。
地图建模
我喜欢将地图表示为单元格网格。因此，我更喜欢逐个单元格地渲染所有结果和地图本身，作为网格。
还有一个选项可以直接在网格上执行路径搜索，而不使用任何额外的数据结构（我也为学习目的实现了这一点：请参阅代码）。
但是因为是网格，所以以某种方式将地图表示为图是很简单的。与我之前的帖子一样，我使用邻接表来表示大多数算法，如 BFS、Dijkstra 和 A-Star。对于 Bellman-Ford 等算法，使用边列表而不是邻接表可能更有意义。因此，如果您浏览代码库，您会发现所有这些都已实现并且都在运行。
为了分离逻辑和职责，我有一个 Navigator 实体，它负责根据通过 App Config 文件和相关地图文件指定的订单和任务配置来执行路径查找。
App Config 看起来是这样的
{
"font": "../../data/arial.ttf",
"map": "../../data/maps/test_29_yandex_weighten_real_map",
"shadow": false,
"map_": "../../data/maps/test_08_low_res_simple_map",
"map__": "../../data/maps/test_10",
"map___": "../../data/maps/test_07_partially_blocked_map",
...
请注意，“map_”、“map__”等并非真正的配置属性。它们在应用程序运行时被忽略。由于 JSON 文件无法注释部分内容，我使用下划线作为属性名称，这样它们可以保留在配置文件中，但不会被使用。
地图文件 看起来是这样的
25 50 150
#########################
#########################
#########################
###.......#####.......###
###.......#####.......###
###.......#####.......###
###...................###
###.......#####.......###
###.......#####.......###
###...................###
######.###########.######
######.###########.######
######.###########.######
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
######.###########.######
#########################
#########################
#########################
#########################
2 4
2
6 6 4 20
这是最简单的例子之一，包含可通行或不可通行单元格。我准备了大量各种输入的参数和测试数据。从小部分代码（便于调试和学习）到巨大的地图（来自真实城市）不等，这些地图可以用来衡量图算法的性能。
我们如何绘制地图
当地图只包含具有二进制状态的单元格（可通行或不可通行）时，这基本上意味着图中的每条边要么存在，要么不存在。
为了在图中找到路径，我们必须有效地表示它。就像我在上一篇文章中所做的，我使用了邻接表，关系为 Vector[NodeId]->指向->Vector[Neighbor Nodes]
typedef std::vector<std::vector<std::shared_ptr<Cell>>> Graph;
有趣的是，当我们在探索网格时，实际上并不需要使用图。我们可以使用 BFS/DFS 算法逐个单元格地遍历网格，而无需考虑边。请参阅方法_GetPathByBFSOnGrid。
首先，初始化代码逐行逐列地读取文件并将其转换为网格
bool RectangularMap::LoadMap(const std::string& filepath, bool shadow)
{
...
// Fill the grid.
_verticesNumber = 0;
for (int row = 0; row < _height; row++)
{
...
for (int col = 0; col < _width; col++)
{
int x = col;
int y = row;
if (line[col] == BLOCK_CELL)
{
// Create a shared pointer here to safely pass pointers between the classes.
_grid[row][col] = std::make_shared<Cell>(x, y, line[col],
blockColor, shadow, _scaleFactor);
}
else
{
...
}
}
}
// Make a graph
InitialiseGraph();
...
}
然后，它创建一个实际的图，即邻接表
void RectangularMap::InitialiseGraph()
{
MapBase::InitialiseGraph();
...
unordered_set<int> visited;
for (int rr = 0; rr < _grid.size(); rr++)
{
for (int cc = 0; cc < _grid[rr].size(); cc++)
{
if (_grid[rr][cc]->GetId() > -1)
{
for (int i = 0; i < 4; i++)
{
int r = rr + dr[i];
int c = cc + dc[i];
if (r >= 0 && c >= 0 && r < _width && c < _height &&
_grid[r][c]->GetId() > -1)
{
if (_isNegativeWeighten)
{
...
}
else
{
_adjacencyList[_grid[rr][cc]->GetId()].push_back(_grid[r][c]);
}
}
}
}
}
}
}
网格表示对于使用 SFML 库在屏幕上绘制很有用。我们可以通过创建几何对象来绘制（这正是我为小型地图所做的）
...
for (int j = _visibleTopLeftY; j < _visibleBottomRightY; j++)
{
for (int i = _visibleTopLeftX; i < _visibleBottomRightX; i++)
{
_grid[j][i]->Draw(_window, _scaleFactor);
}
}
...
sf::RectangleShape tile;
tile.setSize(sf::Vector2f(_cellSize - 5, _cellSize - 5));
tile.setPosition(sf::Vector2f(_x * _cellSize, _y * _cellSize));
tile.setFillColor(_color);
window.draw(tile);
或者，对于较大的地图，我们可以逐像素高效地绘制
sf::Uint8* pixels = new sf::Uint8[_width * _height * 4];
for (int j = _visibleTopLeftY; j < _visibleBottomRightY; j++)
{
for (int i = _visibleTopLeftX; i < _visibleBottomRightX; i++)
{
int index = (_grid[j][i]->GetY() * _width + _grid[j][i]->GetX());
sf::Color color = _grid[j][i]->GetColor();
pixels[index * 4] = color.r;
pixels[index * 4 + 1] = color.g;
pixels[index * 4 + 2] = color.b;
pixels[index * 4 + 3] = color.a;
}
}
sf::Texture texture;
texture.create(_width, _height);
texture.update(pixels);
sf::Sprite sprite;
sprite.setTexture(texture);
sprite.setScale(cellSize, cellSize);
_window.draw(sprite);
最后，让我们看看由文件 test_25_xmax 定义的地图会是什么样子。
最初，文件定义了这样
..............C.................
..............#.................
.............###................
............#####...............
...........#######..............
..........##1###2##.............
.........###########............
........##3######4###...........
.......###############..........
......#################.........
.....###################........
....#####################.......
.............###................
.............###................
.............###................
使用 SFML 渲染的地图看起来像这样
因为我希望所有这一切都能由用户通过键盘控制，所以我将所有用户行为逻辑保留在 [ main.cpp ] 中。我喜欢称之为“控制器”逻辑。
SFML 库使处理键盘事件变得非常容易
while (window.isOpen())
{
Event event;
while (window.pollEvent(event))
{
if (event.type == Event::Closed)
window.close();
if (event.type == Event::KeyPressed && event.key.code == Keyboard::Space)
{
... Do what you need here
}
}
}
主要思路是用户触发（按下空格键）读取地图文件并渲染地图，然后通过第二次触发（再次按下空格键）加载路由任务并在地图上的两点之间计算最短路径。
...
if (navigator->IsReady())
{
navigator->Navigate(); // Finding route between two points
}
else
{
if (map->IsReady()) // Second SPACE press runs the routing
{
skipReRendering = true;
if (navigator->LoadTasks(filepath))
{
navigator->SetMap(map);
}
}
else // Load and draw map
{
drawLoading(window, font);
if (!map->LoadMap(filepath, shadowed))
{
return 0;
}
drawProcessing(window, font);
}
}
...
我们需要更深入
我想尝试更多的图算法，它们都有各自的局限性，所以我决定也实现多颜色地图，这可以用多权重图表示。
每个单元格都有颜色，颜色表示边不仅存在，而且还施加了一些权重（或费用、罚款，随你怎么说）。所以，边可能被阻塞、半阻塞、未阻塞……你懂的。
因此，我实现了多颜色地图，它们看起来更令人愉悦，更像游戏就绪的（来自文件 test_31_multi_weight_graph_map 的示例）
一些配置文件包含来自真实城市的复杂地图，例如 test_29_yandex_weighten_real_map
作为挑战，现在我们应该处理具有非常灵活配置的地图。RectangularMap.cpp 本质上包含了大量的逻辑，包括所有图算法，甚至比现在需要的更多（因为我喜欢玩各种东西，即使它现在不特别有用）。
我实现了 BFS#第 598 行、Dijkstra#第 299 行、A-Star#第 356 行、Bellman-Ford#第 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 性能上的差异。
结束语
至此，我要让您自己去玩这些代码示例了。我希望您会觉得它很有趣，并且从中学习到很多东西。
链接
历史
- 2023 年 9 月 15 日：初始版本