首页 文章

是明星搜索必不可少的开放和封闭列表 .

提问于
浏览 次
1

我正在尝试在Unity中使用星形搜索算法制作寻路系统 .

我的问题是，是否可以在没有打开和关闭列表的情况下实现算法？

我的代码目前以下列方式工作：

  • 当前节点最初设置为起始节点 .

  • 搜索当前节点的相邻节点的列表，并返回具有最低f cost的节点（使用以下公式计算：f（n）= g（n）h（n）

  • 具有最低代码的节点被设置为nodeToMoveToNext .

  • 当前节点设置为nodeToMoveToNext . 重复进程直到currentNode为targetNode .

这段代码工作正常，我能够移动到目标目标，为什么我需要打开和关闭列表？

c# unity3d path-finding a-star

2 回答

  • 1

    关闭列表可用于确保您不检查同一节点两次（并再次退回） . 这取决于您如何设置Node结构 . 假设您将“邻居”定义为节点上方，下方，左侧和右侧的节点 .

    Node1有邻居：

    节点2（f = 2），节点3（f = 10），节点4（f = 15）和节点5（f = 20） .

    所以你步入Node2 .

    • Node2有以下邻居：

    节点5（f = 20），节点6（f = 24），节点7（f = 30）和节点1（f = 2）

    =>你回到Node1并反复做同样的事情 .

    所以它几乎取决于你如何为你的案例定义它 . 您还可以在每个节点上使用bool，例如它已经被评估过 .

    你可能想检查一下

    https://en.wikipedia.org/wiki/A * _search_algorithm

    以及伪代码后的“备注”注释 .

    回复于
  • 1

    您不需要此处的列表，因为您不使用星型搜索算法 .

    至于移动到目标目标的能力，在我看来，你的代码不处理一个简单的障碍（点，1和2是空节点，S是开始，G是目标，星是墙）：

    ...S...
..*1*..
..*2*..
..***..
...G...

    如果仅针对当前节点的相邻节点，则直接进入死胡同并永远保持上下 . 当您处于位置1时，2将是具有最低代码的节点 . 当你在2，1将是 . 等等等等 .

    回复于

相关问题