探索实验室:一个地图编辑和路径比较的Web应用

探索实验室是一个创新的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地图上搜索从起点到终点的最短路径的代码片段: var start = new Point(3, 13); var goal = new Point(15, 4); var boundary = new Rectangle(0, 0, 20, 20); // 20*20地图 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; 其中: - HeuristicSearch.AStar()方法创建一个可查询的实例,回调函数获取当前位置附近的四个位置。 - Except()排除地图上的所有障碍物。 - where子句排除无效位置。在这个片段中,它用于检查位置是否超出边界。 - orderby子句声明一个启发式函数,评估位置的成本。在这个片段中,使用曼哈顿距离作为启发式函数。 - solution是一个IEnumerable实例,枚举路径的每个位置。如果找不到路径,结果为空。

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

在实验室中玩耍

让开始使用实验室。Web应用看起来像这样:左侧的绿色20*20瓦片地图是放置障碍物(左键点击)和使用选择的算法和启发式函数找到路径(右键点击)的地方。右下角有三个等效的LINQ表达式(SelectMany()、Except()和Where())作为示例,用户可以在自己的应用中尝试。

现在让放置一些障碍物,并使用不同的设置找到几条路径: - 一旦找到路径,就会在地图上绘制出来。点击右下角相应的历史按钮,可以切换地图上的动画覆盖层以及右侧的算法设置和LINQ表达式。下面是使用A*搜索算法找到的路径,以及曼哈顿距离:

可以使用这个功能来比较多个算法找到的路径。以下是使用相同起点和终点但使用最佳优先搜索算法的另一条路径:

如所见,最佳优先搜索(红色路径)找到的路径与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()子句可以帮助。

理论上,可以在表达式中附加尽可能多的启发式函数。

沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485