问题标签 [path-finding]

Hi I was wondering what the best container for inserting elements in order in? A map I think is unnecessary since I am just going to be accessing the element at the front, popping it and then inserting more elements (I'm implementing a pathfinding algorithm (Dijkstra) with weights)

I could probably have used a list and inserted in order myself, but the inability to bisect (because you start accessing at the front or back) would be hindering to performance.

给定一个可以在给定 X,Y 点向前、向后、向左和向右移动的对象。如何使用给定的运动机制以最有效和最人性化的方式有效地将对象引导到 X、Y 点。

对象可以实时移动，你可以告诉他们“startMoving”和“stopMoving”。虽然作为一个额外的转折和我遇到的问题，对象的朝向是永远未知的，只有它的当前位置是已知的，所以算法必须“检测”方向。对象的位置以 500-1 秒的间隔在单独的线程中更新。可以在任何时候提出更新算法内位置的“请求”，但它不是立即可用的，算法必须考虑到这一点。执行 requestAndWaitForCoordUpdate() 之类的操作是完全可以接受的，但可能不需要。

这是一些示例代码：

给定一个可以在给定 X,Y 点向前、向后、向左和向右移动的对象。如何使用给定的运动机制以最有效和最人性化的方式有效地将对象引导到 X、Y 点。

对象可以实时移动，你可以告诉他们“startMoving|Direction|()”和“stopMoving|Direction|()”。虽然作为一个额外的转折和我遇到的问题，对象的朝向是永远未知的，只有它的当前位置是已知的，所以算法必须“检测”方向。对象的位置以 500-1 秒的间隔在单独的线程中更新。可以在任何时候提出更新算法内位置的“请求”，但它不是立即可用的，算法必须考虑到这一点。执行 requestAndWaitForCoordUpdate() 之类的操作是完全可以接受的，但可能不需要。

此外，没有障碍物出现，可以假设您在一个非常开放的平面上，偏离路径之间的直线距离很远，您可能会遇到障碍物。可以安全地假设，在给定的直接路径上，目标和源之间距离的 1/4 的宽度应该是可用的。

我还要提一下，我不确定 A* 是否适用于这种情况，如果确实如此，我不确定如何在给定约束的情况下实现它。这里唯一真正的变量是对象的朝向。

这是一些示例代码：

作为我第 4 年软件工程学位的一部分，我正在做一个项目，在该项目中我将可视化几个路径查找算法（用于多个代理）。我项目的第一部分是构建一个可调整大小的网格环境并实现 2-3 种不同的寻路算法。

第二部分涉及地理地图。我希望能够向用户展示真实的地理地图，例如路线图，并为算法提供道路数据作为输入，以便算法可以处理这些数据（我相信它被称为矢量图中的图层）和生成路径作为输入。所以最终我将能够根据计算出的路径在地图上显示代理的移动。

我们实现的算法在它们可以使用的状态和数据方面非常通用，所以我最大的问题是弄清楚如何将地图文件显示为应用程序的一部分，以及从哪里获取我的算法的输入数据。

一开始我想到了 GoogleMaps API 之类的东西，但我不确定我在寻找什么，因为 Google 地图是用于网络的，而且我不确定它们是否可以访问道路图层。

所以我认为我需要的是某种开源 GIS，我可以轻松地将其集成到 Java 应用程序中，而且我还需要示例数据，即背景图像（我认为是栅格地图）和道路图层用作我的算法的输入（例如 A*）。

我以前从未使用过这样的系统，所以如果有人能给我一些指导并向我推荐一个可以在我的项目中使用的好的 GIS 库（它必须是开源的），那真的会对我有帮助

我整天都在努力让这个算法启动并运行，但我一辈子都做不到。我在网上阅读了很多教程，以及AS3、javascript和C++的源代码；但我无法将我所看到的内容适应我自己的代码。

我创建了一个 AStar 类，它有一个名为 Node 的嵌套类。该地图是一个名为 MAP 的二维数组。

我遇到的最大问题是在寻路函数中提取 F 值。

我已经实现了 F = G + H，我的问题是实际的 AStar 算法。有人可以帮忙吗，这是我到目前为止的进展：

这是我使用探路者功能所能获得的最远距离：

我正在设计一款塔防游戏，为此我使用 A* 寻路算法从我的出生区域到达我的目的地。

这里的问题是所有单元都堆叠在一起，这在视觉上看起来并不好。有没有办法让它们以某种方式分组，如果没有足够的空间，可以传播更多？

该算法的工作原理是所有单元一次移动一个图块。

我目前正在为研究生代理论文做一个项目。对于我的项目，我有一个想法，可以随时扩展搜索，例如 ARA* ADA* 和 DLite*。我想通过在机器人上模拟来测试这个想法。在过去的几个晚上，我一直在寻找不同的软件，但没有运气。

最终，我需要一个有机器人的东西，它可以随时以离散的方式提供以下信息：

坐标 (x,y,z) 速度

我还需要机器人有某种方式从其环境中收集坐标，例如拥有一个红外扫描仪，它将用（可通过/不可通过）映射 x、y 坐标。

最后，我需要能够在算法中编程，这些算法将使用环境信息来建议在到达目标坐标的路径中要通过哪些状态。

我的问题是是否有软件可以让我轻松实现所有这些。我不想花超过 7 个晚上的时间来编写这个程序，理想情况下，我希望在一两个晚上内获得一些可见的结果。

我为我的论文编写了很多启发式搜索算法（即周界搜索、BiMaxf、BS*、A*、我自己的双向搜索算法以及一些从前到前的搜索）所有这些都基于 8/ 15 个谜题，可以在几秒钟内用 Java 解决相当困难的问题。我很喜欢使用 C 语言或脚本语言，因为我需要的只是 ADT 的哈希表和优先级队列。

那么是否有任何开源软件可以让我（实时）轻松地实现模拟。如果没有，创建我自己的模拟器听起来不可能吗？如果我要这样做，那么它很可能只是一个 2D 模拟器，它知道给定半径内的周围环境......在已经存在的东西上做它会很好，因为实验不会（如）有偏见...

在我的“项目/存储库”中，我有两个 MS Visual Studio 项目，一个用于主代码，一个用于测试。我有一些共同的文件（在复制和粘贴意义上），我想看看/检查它们是哪些。

什么是正确的 Git 命令（或 Gui 菜单点击）来查看我是否在整个 repo 树中使用了两次相同的内容 blob？如果我正确阅读了所有教程，git 应该有一个 SHA1 用于相同文件内容的两个副本并且已经知道它。我希望 Git 有一个命令可以找到并显示这些重复的使用文件路径。

最终，当存在共同的祖先 blob SHA1（但不是共同的位置）时，我希望能够找出版本之间的差异。[即在测试期间，一个版本在另一个版本之前更新......]

我知道拥有这样的副本并不是最佳做法，但这是工作的最终结果:-(

我在 Windows 上有 Msysgit 和 GitExtensions ......

我正在重新制作一个旧的魔兽争霸 3 自定义游戏，我曾经在 iPhone 上玩过该游戏。基本上，您有一定的时间从一定数量的块中构建迷宫，并且爬行者运行迷宫所需的时间越长，您获得的积分就越多。

我正在使用 cocos2d 进行这一切，现在我正在使用 a* 寻路算法。我正在使用Justin Heyes-Jones 的实现并正在处理节点类。

但是，有几件事让我感到困惑。该类如下所示：

我只是不确定 GetCost 是什么意思。在这个示例迷宫中，X 是墙壁，_ 是可步行区域，从 (3, 1) 到 (3, 2) 的成本是否为 0？那么从 (3, 1) 到 (4, 1) 的成本是多少，因为这是不可能的？

然后我想我可以通过使用距离公式来实现 GoalDistanceEstimate，对吗？

我正在尝试使用 Java Pathfinder，并且我正在使用路径查找器。

我需要使用 Verify.random 函数。谁能告诉我如何解决这个问题？我真的不明白我假设的 URL 的导入是如何工作的。