问题标签 [path-finding]

假设我有一个二维网格。寻路是我的问题的第二步。

我的事情是，假设我在网格中间有一个单元。我希望能够告诉用户“这些都是您可用的目的地。”。

根据单位可以走多少个方格，我想告诉用户，“这些都是你可以到达的方格。” 然后寻找用户选择的目的地。

进行第一次搜索以显示可到达目的地的最佳方式是什么？

根据地形，地形也可以有限制 och 奖励。

我不知道这被称为什么，因此将不胜感激在哪里寻找或谷歌什么的指针。

干杯! :)

/E

我对 OpenGL 真的很陌生，但是对基本的三角学有很好的掌握（从学校开始就被遗忘了很多！）但是我遇到了麻烦。

我有一个在 Z 轴上前后移动的角色。要向左和向右移动，而不是扫射，我希望它们旋转（分别按下左右箭头键时），然后当它们再次向前/向后按下时，它们会朝它们所面对的方向移动。

所以我所做的是将左/右函数添加/减去少量到用于绘制角色旋转的角度变量。然后向前/向后函数向 x 和 z 轴变量添加/减去少量。它们如下（向后）：

航向变量是由左右箭头键操作的角度。

我认为这会起作用，因为当玩家直线前进时，航向为 0，因此 cos(0) = 1 和 sin(0) = 0，这意味着他们在 X 上无处移动，但在 Z 上向前移动了 0.005 的全部量。我想我的基本三角学知识并不完全正确，因为如果我转动一点然后向前移动它们会朝那个方向移动，但是如果我移动一点然后向前移动它们会在旋转 90 度的情况下沿同一条线移动，并继续然后又好像是 180 度然后是 270 度等等。

编辑：我会尝试更好地解释一下，基本上如果我在向左转后向前按它会朝我想要的方向前进，但是如果我放开向前，再转一点然后再向前按，角度已经增加了，但方向与它应该去的方向成 90 度。抱歉，我无法很好地解释这一点。

编辑：好的，我遇到了一些奇怪的问题，我认为这些问题可能会导致奇怪的“90 度”问题，当我让角色看起来左/右 90 度（通过硬编码标题 = 90）时，cos（标题) 应该是 0 吧？但由于某种原因，它的输出为 -0.44，如果我 cos-1(-0.44) 我得到 116.1，这与 Math.cos() 想要以弧度为单位的角度有关吗？我完全迷失在这里。

这是解决这个问题的正确方法吗？我完全陷入了反复试验与减号的困境......

任何回复表示赞赏，

谢谢

英菲尼迪菲兹

（另外，我知道我应该使用 deltaTime 作为字符的速度/旋转值，而不是硬编码的 0.005f，但我想在排序之前先解决这个问题）。

在许多 A* Start Pathfinding 教程中，最后一部分总是这样；

保存路径。从目标方格向后工作，从每个方格到其父方格，直到到达起始方格。那是你的道路。

我真的不明白我应该做什么来在我的 A * 星寻路中实现这一点。我正在使用的当前方法如下；我保存路径，反转它，再次运行路径查找器，但我通过检查它们是否在原始路径列表中来获取相邻节点，如果它们在列表中则添加它们。

这种方法的问题是我有时会遇到一些奇怪的路径。

考虑 A* 算法。

在 Google 中可以找到一个很好的伪代码：

好吧，我不明白一件事：考虑一下图中的情况：

A* 如何能够从 a->b->c 变为 a->d... ??? 好吧，我的意思是，A* 从一个节点开始并通过节点导航。在某一点，一个节点有多个邻居，嗯，A* 能够遵循由邻居生成的路径，但在某一点它能够切换......并从前一个开始返回它的步骤节点并走另一条路，即使废弃的路径没有穿过那条路......

在代码中，启用此环境的条件是什么？

有人在 PHP 中实现了A* 算法吗？我知道维基百科有一个伪代码和一个 C++ 的链接，但我似乎找不到一个已经用 PHP 编写的。

我也在寻找一种高效的书面 A* 算法

我读了一些关于四叉树的文章，并试图利用它们进行寻路。为此，我尝试使用四叉树来创建一个连通图，其中每个“最小矩形”（无子节点）都直接连接到其相邻的最小矩形。为了说明......如果你看一下http://en.wikipedia.org/wiki/File:Point_quadtree.svg的右下角矩形，那个矩形是树中的一个无子节点，它应该是直接的连接到它周围的三个矩形，它们也是无子节点。

创建四叉树非常简单，但我不确定如何检测与它的连接。谁能给我一些见解？

提前致谢！

请花一点时间了解我的情况。如果不能理解，请在评论中告诉我。

我有一个航点的 ArrayList。这些航点没有任何顺序。航点具有以下属性：
{int type, float z, float y, float x, float rotation}

这适用于 3 维世界，但由于我的寻路不应该关心高度（因此将世界视为 2 维世界），因此忽略 y 值。旋转对于这个问题并不重要。

• 在这个二维世界中，x 代表 x 轴，z 代表 y 轴。
• 如果 x 增加，则世界中的物体向东移动。如果 x 减小，则世界中的物体向西移动。
• 如果 z 增加，则世界中的物体向北移动。如果 z 减小，则世界中的物体向南移动。

因此，这些“新”航点可以简化为waypoint = {float x, float y}：

现在，这些航路点代表对象的 X 轴 (x) 和 Y 轴 (z) 位置。此外，还有一个当前位置：curLocation = {float x, float y}和一个目标位置：tarLocation = {float x, float y}。

这就是我想要得到的：在以下严格条件下将导致从到的
所有航路点组合（又名：路径或路线） ：curLocationtarLocation

1. 每个航路点之间的距离不得大于(float) maxInbetweenDistance。这包括从到第一个航路点的初始距离curLocation和从最后一个航路点到 的距离tarLocation。如果不可能有这样的航路点组合，则应返回 null。
2. 当maxInbetweenDistance从通向目标航路点的航路点中找到多个航路点时，应选择最近的航路点（如果稍微远一点的替代航路点会导致一条距离更长的新路径也返回）。
3. 返回的航路点组合（路径）的顺序应该是从最短路线（最小距离）到最长路线（最大距离）

最后，请考虑以下几点：

1. 这是我唯一需要明智地进行 AI/寻路的事情，这就是为什么我不希望使用完整的寻路或 AI 框架。我相信一个功能应该能够处理上述问题。
2. 如果返回所有可能的航路点组合会导致过多的开销，那么如果可以指定最大数量的组合（但仍然从最近到最远排序）也很好。例如。5 个最近的路径。

我将如何实现这一目标？任何反馈表示赞赏。

我在这里询问了最短路径算法： 2D waypoint pathfinding:combinations of WPs to go from curLocation to targetLocation

（要了解我的情况，请阅读该问题以及此问题。）

看来 Dijkstra 最短路径算法能够满足我的需要。但是，我的路线图中大约有 500 到 1000 个节点。

到目前为止，我看到的实现将节点的数量限制在 50 以下。我的问题是：我应该仍然使用 Dijkstra 最短路径算法，还是替代方案？Java中是否有任何实现？

在询问了一些关于最短路径算法的一般建议（2D 航路点寻路：从 curLocation 到 targetLocation 的 WP 组合），然后询问更具体的实现（500 多个航路点/节点的最短路径算法（例如 Dijkstra 的）？）已决定使用 JUNG 库（http://jung.sf.net/）。

我现在的目标是通过使用点列表（大小〜1000）中的任意点组合来获得从点 A 到点 B 的最短路径，其中每个点都直接连接到 x 距离内的所有点。

为此，我需要设置一个树形图。我相信这是一个树图实现列表：http: //jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/class-use/Hypergraph.html#edu.uci.ics。 jung.algorithms.shortestpath

那是对的吗？现在，所有这些实现都仅限于稀疏树图，但我必须创建一个相当密集的树图。

那么，我应该在 JUNG 中使用什么树形图来实现我的目标？

我目前正在研究 A* 寻路，但我遇到了一些问题。在采取最佳路径之前，它会走错路。我究竟做错了什么？

源代码：http ://basic.apayostudios.com/AStar.zip

在线的：

Game.cs http://pastie.org/1656955

Node.cs http://pastie.org/1656956

枚举：

谢谢！