65.9K
CodeProject 正在变化。 阅读更多。
Home

一个简单的路径查找实验室

Robert Vandenberg Huang
starIconstarIconstarIconstarIconstarIcon

5.00/5 (10投票s)

2018年6月30日

CPOL

4分钟阅读

viewsIcon

23577

downloadIcon

383

试验、运行和比较不同的寻路算法和启发式函数

引言

在本文中，我们将介绍一个简单的寻路实验室——一个Web应用程序，用户可以在其中编辑地图并比较不同寻路算法和启发式函数找到的路径。该项目基于以下框架和技术：

  • ASP.NET Core MVC 和 Web API - 用于常规网站功能
  • Bootstrap、jQuery、TypeScript、HTML5 - 用于整体前端展示
  • SVG DOM - 用于地图渲染和路径动画
  • LINQ to A* - 用于Web API背后的寻路算法，项目核心部分

源代码可从CodeProject和GitHub下载。

在开始之前，让我们简要了解一下项目核心部分——LINQ to A*。

什么是LINQ to A*

LINQ to A* 是一个实验性库，旨在将LINQ表达式集成到A*及其他启发式搜索算法中。使用该库，用户可以使用LINQ作为查询表达式来陈述条件并获取算法找到的最短路径。这使得算法的工作方式非常简单和灵活，就像通过LINQ to SQL或LINQ to Entities从数据库中搜索数据一样。

下面的代码片段在20 * 20的地图上搜索start和goal之间的最短路径

var start = new Point(3, 13); 
var goal = new Point(15, 4); 
var boundary = new Rectangle(0, 0, 20, 20); // The 20 * 20 map
var queryable = HeuristicSearch.AStar(start, goal, (s, i) => s.GetFourDirections(unit));
var solution = from p in queryable.Except(GetMapObstacles()) 
               where boundary.Contains(p)
               orderby p.GetManhattanDistance(goal) 
               select p;

其中

  1. HeuristicSearch.AStar<TStep>()方法创建一个可查询实例，并提供一个回调函数，该函数可以获取当前位置附近的四个位置。
  2. Except()会消除地图上的所有障碍物。
  3. where子句会消除无效位置。在此代码片段中，它用于检查位置是否超出边界。
  4. orderby子句陈述了一个启发式函数，该函数评估位置的成本。在此代码片段中，我们使用曼哈顿距离作为我们的启发式函数。

solution是一个IEnumerable<Point>实例，它枚举路径的每个位置。如果未找到路径，结果为空。

LINQ to A*的稳定版本可在NuGet上获取。该项目使用此库作为其核心部分来计算路径。用户也可以在Web应用程序上看到等效的LINQ表达式。

玩转实验室

让我们开始使用这个实验室。Web应用程序看起来像这样：

左侧是一个绿色的20 * 20图块地图，我们可以在其中放置障碍物（左键单击）并使用我们选择的算法和启发式函数查找路径（右键单击）。在右下方，显示了三个等效的LINQ表达式（SelectMany()、Except()和Where()）作为示例，用户可以尝试在自己的应用程序中使用。

现在让我们放置一些障碍物并用不同的设置查找几条路径。

找到路径后，将在地图上绘制路线。单击右下角的相应历史记录按钮，将在地图上显示动画叠加层，并在右侧显示其算法设置和LINQ表达式。下面是A*搜索算法以及曼哈顿距离找到的路径：

我们可以使用此功能来比较不同算法找到的多个路径。以下是使用最佳优先搜索算法在相同start和goal之间找到的另一条路径：

正如您所见，最佳优先搜索找到的路径（红色路径）与A*的路径明显不同。而且由于算法的设计，前者比后者花费更多的步骤。

在编辑地图时，您可以随时保存、加载或重新开始。该应用程序使用localStorage来存储您的进度。

多个启发式函数

您可能已经注意到，实验室中可以存在多个启发式函数。这是LINQ to A*中不同于传统寻路实现的一种灵活功能。当使用多个启发式函数时，仅当前一个函数将两个位置估计为相等时，才会调用后续函数。这对于以下场景非常有用：

var start = new Point(8, 14);
var goal = new Point(11, 8);
var boundary = new Rectangle(0, 0, 20, 20);
var queryable = HeuristicSearch.AStar(start, goal, (s, i) => s.GetFourDirections(unit)); 
var solution = from p in queryable 
               from obstacle in GetMapObstacles() 
               where boundary.Contains(p) && p != obstacle 
               orderby p.GetManhattanDistance(goal), p.GetEuclideanDistance(goal) 
               select p;

在此代码片段中，GetEuclideanDistance()是继GetManhattanDistance()之后的第二个启发式函数。由于计算欧几里得距离很昂贵且比曼哈顿距离慢得多，因此并非总是需要它，除非我们想进行进一步比较。OrderBy()和ThenBy()子句可以帮助我们。

理论上，您可以在表达式中附加任意数量的启发式函数。

闭运算

这仅仅是一个简单的实验室，并且有很大的改进潜力。如果您对此感兴趣，有几种方式可以参与到项目中：

  • 如果您遇到问题，或对Web应用程序有新想法，请向GitHub上的存储库提交一个问题。
  • 如果您遇到有关算法和LINQ表达式的问题，请向GitHub上的LINQ to A*存储库提交一个问题。
  • 如果您有一个很棒的寻路过程的想法并想在项目中尝试，LINQ to A*允许用户定义算法，您可以在其中实现自己的算法并对其应用相同的LINQ表达式。

所有反馈都表示赞赏。

历史

  • 2018-07-01：初始发布
  • 2018-07-15：更新布局，用SVG重写地图（以前是canvas），添加路径动画
  • 2018-08-08：将软件包引用更新为稳定版本
© . All rights reserved.