问题标签 [path-finding]

背景
有一张方形地图，上面有一些障碍物。障碍物由多边形表示。我实现了以下寻路算法：
1）选择精度（用k表示）
2）将地图划分为kxk个正方形。
3）根据以下规则从这些正方形中制作图形：
- 每个节点代表一个正方形
- 当且仅当它们相邻且没有任何障碍物时，两个节点才连接。
4）使用A *算法（或Dijkstra或其他一些......）找到最短路径

如果地图不是动态的，这个算法效果很好。这意味着无法移动障碍物。

问题
1) 那是有效的方法吗？
2）如果障碍物可以移动怎么办？
3）如何对待其他代理？让我们考虑一下房间里有 100 个代理的情况。有两个存在。所有代理都在一个组中，并且该组靠近一个出口。如果所有代理都去最近的出口，那么它将导致瓶颈。他们中的一些人应该去另一个出口，以尽量减少退出所需的时间。如何得到这样的结果？

我正在寻找一个基于 Postgis 和 pgRouting 的库，它将提供行车路线以及任何两个给定点之间的路线。第二部分使用 pgRouting 可以正常工作，但似乎找不到任何可以从 pgRouting 输出的路线中提供行车路线的东西。有谁知道我在哪里可以找到这样的项目？如果有人感兴趣，或者我可以获得足够的牵引力来启动这样的项目，我将寻求启动一个新的开源项目，以在 pgRouting 旁边提供这样的库。

我编写了一个基本的 Java 小程序，可用作游戏爱好者网站的地图查看器（如 Google 地图）。

在其中，我在具有 16 个不同楼层的 2D 地图上实现了 A* 寻路算法，在某些点上“连接”。楼层存储在 PNG 图像中，这些图像在需要时下载并转换为字节数组。从像素 RGB 值中检索节点成本并放入字节数组中。

该地图包含大约 200 万块瓷砖，分布在 16 个楼层。图像大小为 1475 x 2000（PNG 图像为 15-140 KB），因此某些楼层包含很多空瓷砖。

字节数组在内存中会很大，导致大多数 JVM 配置出现“java.lang.OutOfMemoryError: Java heap space”错误。

所以我的问题是

• 有没有办法减少这些字节数组的大小并且仍然有正确的探路者功能？
• 我是否应该采取不同的方法来找到最佳路径，而不是在内存中保存图块？

我认为在 Web 服务器上查找路径会占用过多的 CPU。

最好的问候，

我正在开发一款僵尸在沼泽中奔跑的游戏。我希望 AI 具有“追逐这个目标”或“逃跑”之类的功能。一个主要的绊脚石是寻路。XNA 中是否有一个好的寻路/AI 引擎，或者我应该自己开发？

有没有人有这方面的经验：http: //www.codeplex.com/simpleAI？

我正在寻找路径，我用力将身体推到航点。但是，一旦它们足够接近航点，我想取消力量。我怎样才能做到这一点？我是否需要分别保持我对相关身体施加的所有力？

我正在使用 Box2dx (C#/XNA)。

这是我的尝试，但它根本不起作用：

更新

如果我确实记录了我施加了多少力，它就无法解释可能作用于它的其他力。

我可以使用反射并_force直接设置为零，但这感觉很脏。

我想实现游戏吃豆人。对于 AI，我正在考虑使用 A* 算法，在许多论坛上都看到过。但是，我为一些简单的寻路（从 a 点到 b 点，中间有某些障碍物）实施了广度优先搜索，并发现它总是给出最佳路径。我想这可能是因为在像吃豆人这样使用简单寻路的游戏中，图表中没有成本的概念。那么，如果我在 Pacman 中使用 BFS 而不是 A* 进行寻路可以吗？

您将如何在 Silverlight 中实现这种类型的地图？地图将是交互式的，车站将是可点击的。

http://www.afn.org/~alplatt/tube.html

你会画它混合吗？导入矢量图像？我想这个选择非常重要，因为寻路算法需要能够计算车站之间的距离/票价（基于它们的 XY 位置，大概还没有决定）。

只是寻找不同的想法和意见。

谢谢

我正在为一个需要我将 AI 放入 Flash AS3 中自上而下的战术策略游戏的课程组合一个项目。

我决定使用基于节点的寻路方法，因为游戏基于圆周运动方案。当玩家移动一个单位时，他实质上会绘制一系列线段，这些线段连接玩家单位将跟随。

我试图通过创建一个节点列表来遍历目标节点，从而为我们游戏中的 AI 单元组合一个类似的操作。因此我使用了 Astar（生成的路径可用于创建这条线）。

这是我的算法

现在这个函数创建的路径通常不是最优的或给定目标完全不准确，这通常发生在我有无法路径的节点时，我不太确定我现在做错了什么。

如果有人可以帮助我纠正这个问题，我将不胜感激。

一些笔记

我的 OpenSet 本质上是一个优先队列，所以这就是我按成本对节点进行排序的方式。这是那个功能

谢谢！

我知道我的问题似乎很模糊，但我想不出更好的表达方式，所以我将首先解释我想要做什么。

我目前正在做一个项目，我得到了一张地图，我正在编写一个应该能够在地图上导航的“小动物”；小动物还有其他各种功能，但这些功能与当前问题无关。整个程序和解决方案都是用 C# 编写的。

我可以控制小动物的速度，并通过返回它当前的 X 和 Y 位置来检索它在地图上的当前位置，我还可以在它与阻挡它的地形碰撞时设置它的方向。

我唯一的问题是我想不出一种智能地在地图上导航的方法。到目前为止，我一直根据小动物与地形碰撞时所面对的方向来确定它，这绝不是在地图上移动的好方法！

我不是游戏程序员，这是一个软件作业，所以我对人工智能技术一无所知。

这是地图和小动物外观图像的链接：

地图和小动物图像

我绝不在寻找任何人给我一个完整的解决方案，只是在地图导航的大方向上推动。

我有一个复杂的多边形（可能是凹面的），它的一些边缘标记为入口/出口点。这个多边形内部有可能存在一个或多个任意形状的封锁。我可以使用哪些方法来确定一对入口/出口边缘之间是否存在一定宽度的路径？

通读了这个问题，它看起来像一个家庭作业类型 - 它不是。我只是希望至少有一些我可以追求的线索，因为这对我来说是新的。