问题标签 [path-finding]

本质上，它是我正在开发的一款 pacman 克隆游戏。我有一个 Enemy 类，并创建了这个类的 4 个实例，它们都代表游戏的 4 个幽灵。

所有的幽灵都在屏幕的随机区域开始，然后他们必须朝着吃豆人角色前进。当玩家控制 pacman 并移动它时，他们应该跟随它并尽可能靠近他。

没有迷宫/障碍（还），所以整个地图（400x400 像素）对他们来说是开放的。

对于玩家和每个 Ghost，我可以检索 X、Y、图像宽度和高度属性。另外，我已经有一个碰撞检测算法，所以不用担心，只是鬼魂找到了吃豆人的路。

所以，我有一个简单的寻路算法，它预先计算到几个目标端点的最短路径，每个目标端点都有不同的权重。这在某种程度上等同于在一个端点和每个端点之间有一个节点，尽管那里的边具有不同的权重。它使用的算法是一种简单的传播算法，在 1d 中看起来是这样的（| 表示墙，- 表示空间）：

• 5 - - - 3 | - - - 2 - - - - 2
• 5 4 - - 3 | - - - 2 - - - - 2 : Handled distance 5 nodes
• 5 4 3 - 3 | - - - 2 - - - - 2 : Handled distance 4 nodes
• 5 4 3 2 3 | - - - 2 - - - - 2 : Handled distance 3 nodes
• 5 4 3 2 3 | - - 1 2 1 - - 1 2 : Handled distance 2 nodes
• Done. Any remaining rooms are unreachable.

所以，假设我有一个像这样的预先计算的寻路解决方案，其中只有 5 个是目标：

- - - - | 5 4 3 2 1 -

如果我把墙改成房间。重新计算很简单。只需重新处理所有距离节点（但忽略已经存在的节点）。但是，我无法找到一种有效的方法来处理如果 4 变成一堵墙该怎么办。显然结果是这样的：

- - - - | 5 | - - - -

但是，在二维解决方案中，我不确定如何有效地处理 4。很容易存储 4 依赖于 5，因此需要重新计算，但是如何安全地确定它的新依赖项和值？我宁愿避免重新计算整个数组。

一种总比没有好的解决方案是（大致）仅重新计算距 5 的曼哈顿距离为 5 的数组元素，并维护源信息。这基本上意味着将算法重新应用于选定区域但是我可以做得更好吗？

我目前正在根据Theme Hospital的想法编写一个非常基本的 Java 游戏。

我对 Java 很陌生，目前正在大学第一年学习。我已经断断续续地做了近两年的 Java，但我终于把时间花在了一个像样的项目上。

我正处于需要创建一个人（患者）才能入院的阶段。他们需要去接待处，然后是GP的办公室，然后回到他们的起始位置。

我已经研究过 A* 路径查找，但对我来说似乎真的很复杂。我理解它是如何工作的，但我不确定如何在我的游戏中实现它。

至此，用户可以放置一个前台，搭建一个全科医生的办公室。每一个都有一个“使用点”，这将是患者必须到达的地方。格子方格只能满或不满，不会有不同的地形。

我对粘贴任何代码犹豫不决，因为在过去几个月中我学习了很多与 GUI 相关的新技术，这很混乱。我的计划是达到里程碑 1，让患者去办公桌，然后办公室，然后离开。一旦我有了这个，我会更多地整理代码。

我见过许多 A* 的实现和许多不同的类型。有人可以给我一个可以合作的起点吗？我应该尝试改编一组已经编写好的类，还是尝试从头开始编写自己的类？

我目前有另一个与 Java 中的路径查找有关的问题。但是我觉得这是一个单独的问题。

我在做游戏。寻路需要能够处理多个可能的端点。我发现的所有寻路算法和教程都只有一个终点。

这种改动会很容易调整到已经存在的代码中，还是我最好尝试从头开始编写自己的代码？

我有一个基于瓷砖的地图，其中几个瓷砖是墙壁，其他瓷砖是可步行的。可步行的瓷砖构成了我想在路径规划中使用的图表。我的问题是他们是否有任何好的算法来找到访问图中每个节点的路径，最大限度地减少重复访问？

例如：

地图示例 http://img220.imageshack.us/img220/3488/mapq.png

如果底部的黄色瓷砖是起点，则访问所有重复次数最少的瓷砖的最佳路径是：

路径示例 http://img222.imageshack.us/img222/7773/mapd.png

这条路径有两次重复访问。更糟糕的路径是在第一个路口左转，然后在三个已经访问过的瓷砖上回溯。

我不关心结束节点，但开始节点很重要。

谢谢。

编辑：

我在我的问题中添加了图片，但在查看时看不到它们。他们来了：

http://img220.imageshack.us/img220/3488/mapq.png

http://img222.imageshack.us/img222/7773/mapd.png

此外，在图表中我需要这个，因为永远不会出现 min repeats = 0 的情况。也就是说，要踩到地图中的每个图块，玩家必须至少穿过自己的路径一次。

我在（非常少的）空闲时间制作了一个 roguelike。每个级别基本上都是几个由路径连接在一起的矩形房间。然而，我希望房间之间的路径看起来自然且多风。例如，我不会考虑以下自然外观：

我真的想要更像这样的东西：

这些路径必须满足一些属性：

1. 我必须能够指定它们的边界区域，
2. 我必须能够参数化它们的风和长度，
3. 线条不应看起来像是从一条路径开始并在另一条路径结束。例如，上面的第一个例子看起来好像从 A 开始，在 B 结束，因为它基本上反复改变方向，直到它与 B 对齐，然后就直奔那里。

我希望使用 A*，但老实说，我不知道我的启发式方法是什么。我也考虑过使用遗传算法，但我不知道这种方法最终会有多实用。

我的问题是，什么是获得我想要的结果的好方法？请不要只指定“A*”或“Dijkstra 算法”之类的方法，因为我还需要一个好的启发式帮助。

我正在开发一款使用 A-star (A*) 进行路径查找的游戏，但我已经到了这样一个地步，即我有一些大于单个网格正方形的对象。

我在 16*16px 的网格上运行。墙段为 16*16，因此使单个正方形无法通过。我的一些坏人是 32*32，所以他们需要检查一个间隙是否至少有 2 个方格宽，以便能够通过它。

我不能简单地将网格设置为 32*32，因为设计需要薄壁（16 像素），并且有几个较小的坏蛋只占用一个 16*16 的正方形。

如何实现这种多分辨率环境？A-star 仍然是正确的工具吗？

我已经在 AS3 中实现了 A* 算法，它工作得很好，除了一件事。生成的路径通常不会采用最“自然”或最顺畅的路线到达目标。在我的环境中，对象可以像水平或垂直移动一样便宜地沿对角线移动。这是一个非常简单的例子；起点用 S 标记，终点（或终点）用 F 标记。

如您所见，在第一轮查找过程中，节点 [0,2]、[1,2]、[2,2] 都将被添加到可能节点列表中，因为它们的得分均为 N。当我试图决定继续使用哪个节点时，我遇到的问题出现在下一点。在上面的示例中，我使用 possibleNodes[0] 来选择下一个节点。如果我将其更改为 possibleNodes[possibleNodes.length-1] 我得到以下路径。

然后使用 possibleNextNodes[Math.round(possibleNextNodes.length / 2)-1]

所有这些路径都具有相同的成本，因为它们都包含相同数量的步骤，但在这种情况下，最明智的路径如下......

是否有一种正式接受的方法可以使路径看起来更合理，而不仅仅是在数学上正确？

我正在尝试制定一种算法来找到穿过有向图的路径。这不是一条传统的道路，我找不到任何关于已经完成的类似事情的参考。

我想找到具有最大最小权重的路径。

即如果有两条路径的权重为 10->1->10 和 2->2->2，那么第二条路径被认为比第一条路径更好，因为最小权重 (2) 大于第一条的最小权重 ( 1）。

如果有人能想出办法做到这一点，或者只是向我指出一些参考材料的方向，那将非常有用:)

编辑:: 似乎我忘了提到我正试图从一个特定的顶点到另一个特定的顶点。那里很重要：/

EDIT2:: 正如下面有人指出的那样，我应该强调边缘权重是非负的。

我正在编写一个模拟，其中一个生物对象应该能够向环境中的其他任意对象移动，在障碍物周围滑动而不是进行任何智能寻路。我不想让它规划一条路径——只是朝着一个大方向移动，并绕过障碍物。

这是一个 2D 环境（俯视图），每个对象都有一个用于碰撞检测的边界矩形。没有网格，我不是在寻找 A* 解决方案。

我还没有找到任何关于这种“愚蠢的”基于碰撞的寻路的教程，所以我可能没有使用最常用的术语来描述这一点。

关于如何实现这个（或教程链接）的任何建议？