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

EpPathFinding.cs - C# 中基于网格的快速寻路算法（跳点搜索）

Chris La
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.82/5 (45投票s)

2013 年 8 月 6 日

MIT

5分钟阅读

viewsIcon

112416

downloadIcon

4785

C# 中基于网格的游戏的跳点搜索算法

 

目录

  1. 引言 
  2. Unity 集成指南
  3. 基本用法
  4. 高级用法
  5. 结论
  6. 参考

简介

我正在用 C# 开发我的基于网格的游戏，我的游戏 AI 需要一个快速的寻路算法。在寻找一个好的算法时（因为我对 A* 或 Dijkstra 不满意），我找到了 D. Harabor 的一篇很棒的 文章（跳点搜索）以及 Xueqiao Xu 的一个 JavaScript 实现。我有个想法，“为什么不为 C# 也做一个呢？”于是乎，EpPathFinding.cs 就诞生了！

EpPathFinding.cs 的工作方式与 PathFinding.js 非常相似。

（如果您对跳点搜索算法的更多细节以及原始的 JavaScript 实现感兴趣，请参阅 D. Harabor 的 文章 和 Xueqiao Xu 的 实现。）

Unity 集成指南

将 EpPathFinding.cs\PathFinder 文件夹添加到您的 Unity 项目的 Assets 文件夹中。然后，在您想使用 EpPathFinding.cs 的脚本文件中，在文件顶部添加 using EpPathFinding.cs; 命名空间，并按照下面的指南使用它。

（如果编译时遇到问题，请参考 Unity 论坛）

基本用法

为了方便使用，用法和演示已尽可能地与 PathFinding.js 保持一致。

您首先需要构建一个网格地图。（例如：宽度 64，高度 32）

BaseGrid searchGrid = new StaticGrid(64, 32);

默认情况下，网格中的所有节点都不能通行。要设置给定坐标处的节点是否可通行，请使用 SetWalkableAt 函数。

例如，要将节点 (10 , 20) 设置为可通行，其中 10 是 x 坐标（从左到右），20 是 y 坐标（从上到下）

searchGrid.SetWalkableAt(10, 20, true);
 
// OR
 
searchGrid.SetWalkableAt(new GridPos(10,20),true);    

 您也可以在实例化 StaticGrid 类时使用二维数组。它将使用数组中指示的可通行性初始化网格中的所有节点。（true 表示可通行，否则不可通行）

bool [][] movableMatrix = new bool [width][];
for(int widthTrav=0; widthTrav< 64; widthTrav++)
{
   movableMatrix[widthTrav]=new bool[height];
   for(int heightTrav=0; heightTrav < 32;  heightTrav++)
   { 
      movableMatrix[widthTrav][heightTrav]=true; 
   }  
}
 
BaseGrid searchGrid = new StaticGrid(64,32, movableMatrix);

为了搜索从 (10,10) 到 (20,10) 的路径，您需要创建一个 JumpPointParam 类，并传入网格和起始/结束位置。（注意：起始点和结束点都必须是可通行的）

GridPos startPos=new GridPos(10,10); 
GridPos endPos = new GridPos(20,10);  
JumpPointParam jpParam = new JumpPointParam(searchGrid,startPos,endPos );

您也可以稍后设置/更改起始点和结束点。（但是，必须在实际搜索之前设置起始点和结束点）

JumpPoinParam jpParam = new JumpPointParam(searchGrid);
jpParam.Reset(new GridPos(10,10), new GridPos(20,10));

要查找路径，只需使用上面创建的 JumpPointParam 对象运行 FindPath 函数即可。

List<GridPos> resultPathList = JumpPointFinder.FindPath(jpParam);

与 PathFinding.js 不同，JumpPointParam 类可以被多次使用，并支持不同的起始/结束位置。

jpParam.Reset(new GridPos(15,15), new GridPos(20,15));
resultPathList = JumpPointFinder.FindPath(jpParam);

高级用法

即使终点不可通行，也能找到路径

在实例化 JumpPointParam 时，您可以传入额外的参数，使搜索能够找到即使终点不可通行的网格的路径。

（请注意，如果未指定该参数，则默认设置为 true。）

JumpPointParam jpParam = new JumpPointParam(searchGrid, true); 

如果 iAllowEndNodeUnWalkable 为 false，当终点不可通行时，FindPath 将返回空路径。

JumpPointParam jpParam = new JumpPointParam(searchGrid, false); 

跨角    

在实例化 JumpPointParam 时，您可以传入额外的参数，使搜索能够在一个侧面是不可通行网格时仍能对角线行走： 

（请注意，如果未指定该参数，则默认设置为 true。） 

JumpPointParam jpParam = new JumpPointParam(searchGrid,true,true);

为了避免在一个侧面不可通行时对角线行走，而是绕过拐角。

JumpPointParam jpParam = new JumpPointParam(searchGrid,true,false);

 

跨相邻点

 在实例化 JumpPointParam 时，您可以传入额外的参数来指示要使用的特定策略。

（请注意，如果 CrossCorner 选项为 false，则此选项将被忽略。）

为了使搜索能够跨越两个对角线不可通行节点的拐角进行对角线行走。

JumpPointParam jpParam = new JumpPointParam(searchGrid, true, true, true); 

 

为了使搜索不能跨越两个对角线不可通行拐角进行对角线行走。

JumpPointParam jpParam = new JumpPointParam(searchGrid, true, true, false);   

启发式函数 

预定义的启发式函数有 Heuristic.EUCLIDEAN （默认）、Heuristic.MANHATTAN 和 Heuristic.CHEBYSHEV。

使用 MANHATTAN 启发式函数： 

JumpPointParam jpParam = new JumpPointParam(searchGrid,true,true,true, Heuristic.MANHATTAN);

您始终可以使用 SetHeuristic 函数稍后更改启发式函数。

jpParam.SetHeuristic(Heuristic.MANHATTAN); 

动态网格

对于我的基于网格的游戏，可通行的网格节点比不可通行的网格节点少得多。因此，上面的 StaticGrid 为了存储不可通行的网格节点而浪费了太多内存。为了避免内存浪费，我创建了 DynamicGrid，它只为可通行的网格节点分配内存。

（请注意，内存和性能之间存在权衡。这会降低性能以提高内存使用率。）

BaseGrid seachGrid = new DynamicGrid();   

您也可以在实例化 DynamicGrid 类时使用一个可通行 GridPos 的 List。它将仅初始化网格中可通行性为 true 的节点。

List<GridPos> walkableGridPosList= new List<GridPos>();
for(int widthTrav=0; widthTrav< 64; widthTrav++)
{
   movableMatrix[widthTrav]=new bool[height];
   for(int heightTrav=0; heightTrav < 32;  heightTrav++)
   {
      walkableGridPosList.Add(new GridPos(widthTrav, heightTrav));
   }
}
   
BaseGrid searchGrid = new DynamicGrid(walkableGridPosList);  

其余功能，如 SetWalkableAt、Reset 等，与 StaticGrid 相同。

带缓冲区的动态网格

在许多情况下，您可能希望重复使用相同的网格进行下一次搜索。当与 PartialGridWPool 一起使用时，这会非常有用，因为您不必重新分配网格。

NodePool nodePool = new NodePool();
BaseGrid seachGrid = new DynamicGridWPool(nodePool);   

其余功能，如 SetWalkableAt、Reset 等，与DynamicGrid 相同。  

带缓冲区的局部网格

如上所述，如果您出于性能原因只想搜索网格的局部区域，您可以使用 PartialGridWPool（可以与 DynamicGridWPool 一起使用或不使用）。只需提供 GridRect，它会显示您想在其中搜索的网格部分。

NodePool nodePool = new NodePool();
...
BaseGrid seachGrid = new PartialGridWPool(nodePool, new GridRect(1,3,15,30));   

其余功能，如 SetWalkableAt、Reset 等，与DynamicGridWPool 相同。

使用递归 

您可以使用递归函数或循环函数来查找路径。这可以通过在 JumpPointParam 中设置 UseRecursive 标志来轻松完成。

（请注意，默认值为 false，表示使用循环函数。） 

// To use recursive function
JumpPointParam jpParam = new JumpPointParam(...);
jpParam.UseRecursive = true;  

改回循环函数

// To change back to loop function 
jpParam.UseRecursive = false; 

 

可扩展性 

您还可以创建 BaseGrid 的子类，以创建您自己的Grid 类，从而最好地支持您的情况。   

结论

EpPathFinding.cs 项目的大部分功能和工作最初都来自于 D. Harabor 的 文章 和 PathFinding.js，因此所有辛勤工作和贡献都应归功于 D. Harabor 和 Xueqiao Xu。我之所以展示这个项目，是希望能对那些可能需要在 C# 中使用此算法的人有所帮助。

参考

历史

  • 2015.01.07：- 高级用法再次更新。
  • 2014.02.18：- 高级用法已更新 
  • 2013.08.21：- 在 MIT 许可下重新分发 
  • 2013.08.20：- 文章已更新，包含“DynamicGrid” 
  • 2013.08.19：- 源代码已更新，修复了一个 bug。（感谢 Jacek Gajek）  
  • 2013.08.18：- 源代码已更新，修复了一个 bug。（感谢  Ted Goulden 和 sam.hill） 
  • 2013.08.07：- 源代码已更新 
  • 2013.08.06：- 提交了文章 
© . All rights reserved.