首页 文章

查找tile网格中两个点之间的所有长度为n的路径

提问于
浏览 次
0

我有一个基于2D拼贴的 Map ，其中两个点彼此相邻 . 我想找到这两个点之间所有长度为n的路径（这些点总是相邻的，n的值总是至少为3，因此这些路径永远不会是最短路径），可以排除任何通过的路径通过一个或多个任意定义的点 .

我已经研究了许多寻路算法，但是我很难想出一种方法来修改它们以返回具有精确长度的所有路径 . 有人能指出我正确的方向吗？

algorithm path-finding

2 回答

  • 0

    只需进行详尽的搜索即可 . 你可以修剪一些永远不会到达目的地的分支：

    search(from, to, n):
    if from is outside boundaries: return
    if distance(from, to) > n: return
    if n == 0:
        if from == to:
            do something with your path
        return
    search(left of from,  to, n-1)
    search(right of from, to, n-1)
    search(up of from,    to, n-1)
    search(down  of from, to, n-1)

    如果您的路径不需要重复点，只需按照通常使用DFS的方式进行跟踪，但请记住在退出节点时取消标记为已访问（因此您可以在另一个路径中再次访问它） .

    回复于
  • 1

    找到所有路径是不寻常的，因此寻路算法可能对您没有帮助 . 你真的在寻找一个慢速详尽的搜索 .

    我首先使用Dijkstra算法在n个步骤中找到终端节点和每个节点之间的最短路径 . 这将在以后有用，因为它找到每个节点的最短路径 . 之后，我们可以用它来修剪无用的路径 .

    然后我会开始迭代搜索网格 . 在每一步，跟踪到达那里的路径，调用长度m . 请记住，您将有许多路径（可能是循环路径）到达同一节点 . 你会想要保留所有这些 . 在每次迭代中，查看当前节点的邻居，并将新路径推送到搜索中，该搜索将以n-m步长到达可以到达 endpoints 的每个邻居 .

    最终，您将耗尽可能到达 endpoints 的节点，您只需查看到达 endpoints 的所有路径 .

    回复于

相关问题