问题标签 [path-finding]

假设我们有一个矩形海。它非常大 - 10000x20000。

我们也有岛屿。为简单起见，我们假设它们也是矩形的。我们知道它们的确切位置（坐标）。

如果我们有一艘船，在地图上的某个地方 - (x1, y1)，我们如何在不经过任何岛屿的情况下找到到地图上另一点 (x2, y2) 的最短路径？

更新：到目前为止，没有任何限制——无论是船还是海。如果我们可以通过添加一些来简化（并加快）事情 - 这是非常受欢迎的。

这条路甚至不必是最好的——例如，可以享受 10% 的折扣——完全可以接受。

我正在尝试从维基百科的伪代码中实现 A*，但是我得到了一些奇怪的结果。

该实现找到了最初看起来不错的路径，但进一步看，它总是产生相同的路径！

任何人都可以发现任何问题吗？代码用 python 3.1 编写并使用 pygame。

我真的不知道，因为我认为我已经逐句实现了伪代码语句。

这里也是一个截图： http ://andhen.mine.nu/uploads/astar.dib

谢谢！

我正在编写一个简单的游戏，目前正在做 AI 部分。NPC 获得他需要访问的“兴趣点”列表。每个点在地图上都有一个坐标。我需要为角色找到一条最快的路径来访问所有给定的点。

据我了解，该任务可以描述为“在强连接的加权无向图中找到最快的遍历路径”。

我想获得一些算法的名称来计算它，或者如果没有名称 - 我自己编程的一些关键点。

提前致谢。

我们得到一个加权图 G 及其最短路径距离的矩阵增量。所以 delta(i,j) 表示从 i 到 j 的最短路径的权重（i 和 j 是图的两个顶点）。最初给出的 delta 包含最短路径的值。突然边缘 E 的权重从 W 减少到 W'。如何在 O(n^2) 中更新 delta(i,j)？（n = 图的顶点数）问题不在于再次计算具有最佳 O(n^3) 复杂度的所有对最短路径。问题是更新增量，因此我们不需要重新计算所有对最短路径。

更明确：我们所拥有的只是一个图和它的增量矩阵。增量矩阵仅包含最短路径的值。现在我们要根据图形的变化来更新 delta 矩阵：降低边权重。如何在 O(n^2) 中更新它？

我目前正在使用 A* 寻路算法来计算无限网格上的路径（使用 Gridworld 中的 UnboundedGrid，AP CS 案例研究，如果对任何人有帮助的话）。一切都很好，除了因为末端节点完全被墙包围而没有有效路径的情况。正如预期的那样，算法继续无限搜索，永远找不到结束节点。

一个可能的解决方案是在整个寻路区域周围放置不可见的（如用户看不到但算法看到的）墙，确保开始节点、结束节点和所有墙节点都在这些范围内墙壁，有2-3个空格填充左右。就像是：

...想法是最终所有节点都将添加到封闭列表中，开放列表将变为空，此时我将知道不存在有效路径。

这似乎是解决问题的合理方法吗？有什么方法可能会出错吗？我知道另一种解决方案是同时从末端向后寻路，但这似乎可能很昂贵，特别是在末端节点没有那么紧密封闭的情况下。

免责声明：我几乎没有 Java 背景，因为我主要是 C# 开发人员。

想要A*算法的java实现。
是的，我在网上看到了很多相同的版本，我无法在它们之间进行选择。

我正在寻找一种 A* 算法实现，它使用 java 的所有新功能，使算法更快（即使有点）。原因是我们正在实现路径查找MMO，因此性能是重中之重。

任何指针（至少在哪里看）？

我编写了一个小游戏引擎，具有基于图块的地图和用于寻路的 A* 算法。但是我有一个问题，当 2 个物体碰撞并阻挡一个航点时。他们来自相反的方向，所以他们不能再移动，也永远不会到达下一个航路点。我想到了一些可能的解决方案，例如

• 可移动物体不能与其他可移动物体碰撞
• 重新计算标记被阻止图块的路径
• 只需计算到下一个自由航点的路径，将每个带有可移动物体的图块标记为阻塞

我真的不想做第一种可能性，这对于一个不像动作游戏的引擎来说有点破旧。如果地图上有很多可移动的物体，最后两种可能性可能会变得非常慢。你觉得我应该怎么做？顺便说一句，第一种可能性在“要塞”中实现，其他两种可以在任何较新的策略游戏中找到。

我正在尝试获取诸如this的密集点图，并将其转换为连接的凸多边形图。多边形应尽可能大且尽可能简单，同时保持连接。结果图将用于寻路。谁能指出我正确的方向？

我正在设计一个程序，以尽可能高分的方式解决纸牌游戏。比赛按以下计分系统计分：

牌组中的牌一次翻转一张，玩家可以无限次翻转牌组（但是，-20 分扣除仍然适用）。

我找到了各种策略指南，例如Windows Solitaire Game 的 Klondike 策略指南，但这些指南适用于桌牌未知的真实纸牌游戏。

我正在寻找一种算法来解决我所谓的“面朝上”纸牌游戏，在这种游戏中，我在发牌之前就已经了解了套牌。编辑：从下面答案中给出的论文来看，这个游戏似乎被称为“深思熟虑的纸牌”。

到目前为止，我的想法是：某种蛮力，尝试所有可能的动作并得分；一个简单的算法，单独查看每一列并尝试它可以的“最佳”移动；最后是某种类似于寻路的算法，对每一步进行评分并找到最佳“路径”。

蛮力的问题在于它会永远（字面意思）因为你可以无限地重复移动。使用简单的算法，我不能做一些棘手的事情，比如重新排列两列来放置所有的红心和梅花（例如）来释放一个单独的 8 个红心。从我所见，寻路将起作用，但我对这种实现如何工作感到迷茫。

我已经在 C# 中成功实现了 A* 寻路，但是速度很慢，我不明白为什么。我什至尝试不对 openNodes 列表进行排序，但它仍然是一样的。

地图为 80x80，有 10-11 个节点。

我从这里Wikipedia获取了伪代码

这是我的实现：

这是我正在使用的启发式方法：

我究竟做错了什么？我整天都在看相同的代码。