在有限的圆范围内找到 2 点之间的可能路径（算法）
Finding a possible path between 2 points with limited circle-ranges (algorithm)
我目前正在努力寻找一种算法，无论路径是否可行。
我有一个点域，这些点的位置是完全随机的。我也有一个起点，一个终点。在我的起点上，我可以在有限的半径内跳到起点周围的任何一点，然后从那里继续，但跳跃次数有限。这种情况下的表现很重要！像 Dijkstra 这样的现有算法在这里帮不了我。
有什么想法吗？
你可以构造一个以点为顶点的无向图。每条边连接两个不超过跳跃距离限制的点。这张图建好后，用传统算法就可以找到最短路径了。
要构建图形，您可以将点分配给二维矩阵单元格的网格。单元格的高度和宽度是跳跃半径限制。给定点的边的候选点必须属于其矩阵单元或直接相邻的单元。这减少了构建时间。
进一步的加速可能是将图形的第一个版本限制为位于起点和终点之间的直接视线附近的那些网格单元。只有搜索不成功，才可以扩大搜索范围再试。
如果起点和终点的距离大于半径限制乘以跳跃限制，则不存在可行路径。
以防万一有人想要解决方案：
由于跳跃的数量是有限的，我创建了一个径向网格，其中最大半径是圆的数量乘以它们自己的半径。
之后，我只是使用 A-star 路径查找器。 （我用了 http://www.rapidfirestudio.com 的一个 existant）
我目前正在努力寻找一种算法，无论路径是否可行。
我有一个点域，这些点的位置是完全随机的。我也有一个起点，一个终点。在我的起点上，我可以在有限的半径内跳到起点周围的任何一点，然后从那里继续，但跳跃次数有限。这种情况下的表现很重要！像 Dijkstra 这样的现有算法在这里帮不了我。
有什么想法吗？
你可以构造一个以点为顶点的无向图。每条边连接两个不超过跳跃距离限制的点。这张图建好后，用传统算法就可以找到最短路径了。
要构建图形，您可以将点分配给二维矩阵单元格的网格。单元格的高度和宽度是跳跃半径限制。给定点的边的候选点必须属于其矩阵单元或直接相邻的单元。这减少了构建时间。
进一步的加速可能是将图形的第一个版本限制为位于起点和终点之间的直接视线附近的那些网格单元。只有搜索不成功，才可以扩大搜索范围再试。
如果起点和终点的距离大于半径限制乘以跳跃限制，则不存在可行路径。
以防万一有人想要解决方案： 由于跳跃的数量是有限的，我创建了一个径向网格，其中最大半径是圆的数量乘以它们自己的半径。 之后，我只是使用 A-star 路径查找器。 （我用了 http://www.rapidfirestudio.com 的一个 existant）