问题标签 [path-finding]

如果您需要一个干净且一致的沙箱来进行寻路，您会使用什么？

我想通过在几何平面上的障碍物周围发送虚拟单元（机器人）来试验不同的寻路算法。

但我不需要像游戏引擎或 Flash 那样的过度杀伤功能，只需要动画报告和原生碰撞检测器。

我更喜欢用 python 编写脚本，但如果有 java 或 C++ 替代品，我也会很感激。

真正让我吃惊的是，当从 Windows 迁移到 OS X 时，Finder 中缺少一些基本功能。其中之一是可以将存档作为文件夹打开，即保留在目录树中并能够拖放文件从存档到树中的文件夹，侧边栏等。

你会怎么做才能启用这样的功能？

更新

Path Finder是一个很棒的共享软件应用程序，我将使用它来代替标准的 Finder（就像很多 Mac 用户所做的那样），所以我对 Path Finder 浏览档案的插件更感兴趣。有可能浏览包（检查查看选项），所以我相信可以将它扩展到档案。还有一个用于为 Path Finder 制作插件的SDK。唯一的问题 - 如何制作插件，让所有苦苦挣扎的人最终获得快乐？

我正在设计一个城市建设游戏并遇到了一个问题。

想象一下 Sierra 的Caesar III游戏机制：您有许多城区，每个城区都有一个市场。距离上有几个粮仓与有向加权图相连。区别：人（这里是汽车）是形成交通拥堵的单位（这里是图权重）。

注：在凯撒系列游戏中，人们收割粮食并将其储存在几个大粮仓中，而许多市场（小商店）从粮仓中取出食物并运送给市民。

任务：告诉每个地区他们应该从哪里获取食物，同时花费最少的时间并尽量减少城市道路上的拥堵。

地图示例

假设黄色区域相应地需要 7、7 和 4 个苹果。相应地，蓝色粮仓有 7 个和 11 个苹果。

假设边权重与其长度成正比。然后，解决方案应该类似于边缘上指示的灰色数字。例如，第一个区从第一个粮仓获得 4 个苹果，从第二个粮仓获得 3 个苹果，而最后一个区从第二个粮仓获得 4 个苹果。

在这里，垂直道路首先被占用到最大，然后剩余的工人被送到对角线路径。

问题

我应该使用什么实用且非常快速的算法？我正在查看一些描述拥塞游戏的论文（拥塞游戏：竞争优化等），但无法了解全局。

或类似语言的版本。一种适用于所有类型的地图，而不仅仅是 2d。

I'm sure you've all heard of the "Word game", where you try to change one word to another by changing one letter at a time, and only going through valid English words. I'm trying to implement an A* Algorithm to solve it (just to flesh out my understanding of A*) and one of the things that is needed is a minimum-distance heuristic.

That is, the minimum number of one of these three mutations that can turn an arbitrary string a into another string b: 1) Change one letter for another 2) Add one letter at a spot before or after any letter 3) Remove any letter

Examples

I've tried many algorithms out; I can't seem to find one that gives the actual answer every time. In fact, sometimes I'm not sure if even my human reasoning is finding the best answer.

Does anyone know any algorithm for such purpose? Or maybe can help me find one?

(Just to clarify, I'm asking for an algorithm that can turn any arbitrary string to any other, disregarding their English validity-ness.)

这是我的节点网格：

我正在使用 A* 寻路算法在其上移动一个对象。它通常可以正常工作，但有时会出现错误：

• 从 3 移动到 1 时，它正确地通过 2。但是，当从 1 移动到 3 时，它通过 4。
• 在 3 和 5 之间移动时，它会在任一方向上通过 4，而不是通过 6 的较短路径

有什么问题？这是我的代码（AS3）：

NodeGridNode::distanceTo()

我的一位同事从在线法官网站向我提出了一个练习，该练习基本上是一个解决小镇疏散计划的图形问题。

我不需要答案（我也不想要）我只需要一个建议，因为我对这类问题有点陌生。

问题包括有工人的城镇建筑和核袭击时的辐射避难所。我必须建立一个算法，将每栋建筑物的工人分配到一个或多个辐射避难所，但在某种程度上，一些避难所不会变得过于拥挤，而其他避难所几乎是空的（否则我只会让工人去最近的一个） .

问题是这样的：http ://acm.timus.ru/problem.aspx?space=1&num=1237

如果它的离线继承它的谷歌缓存版本：http ://webcache.googleusercontent.com/search?q=cache:t2EPCzezs7AJ:acm.timus.ru/problem.aspx%3Fspace%3D1%26num%3D1237+vladimir+ kotov+疏散+问题&cd=1&hl=pt-PT&ct=clnk&gl=pt

到目前为止，我所做的是为每栋建筑物找到最近的庇护所，并将工人数量从该建筑物中移出，使其等于庇护所的容量。然后搬到下一栋楼。但有时工人的数量大于庇护所的容量，在这种情况下，在我遍历每座建筑物之后，我只是迭代然后再次应用相同的算法，直到每座建筑物中有 0 名工人，问题是这几乎不是最好的方法解决这个问题。

欢迎任何提示，请不要觉得我在寻求答案，我只是想要一个正确方向的建议来解决它。

提前致谢。

假设您有一个像这样的网格（随机制作）：

现在假设您有一辆汽车随机从其中一个白框出发，通过每个白框的最短路径是什么？您可以根据需要多次访问每个白框，并且不能跳过黑框。黑匣子就像墙壁。简而言之，您只能从白盒移动到白盒。

你可以向任何方向移动，甚至是对角线。

两个子问题：

1. 假设您在移动之前知道所有黑盒的位置。
2. 假设您只有在与黑盒相邻的白盒中时才知道黑盒的位置。

这里有一些关于 D* 的论文的链接，但它们对我来说有点过于数学化了。有没有关于 D*/D* Lite 更适合初学者的信息？

I'm trying to get a faster pathfinding mechanism in place in a game I'm working on for a connected node graph. The nodes are classed into two types, "Networks" and "Routers."

In this picture, the blue circles represent routers and the grey rectangles networks.

Each network keeps a list of which routers it is connected to, and vice-versa. Routers cannot connect directly to other routers, and networks cannot connect directly to other networks.

Networks list which routers they're connected to



Routers do the same

I need to get an algorithm that will map out a path, measured in the number of networks crossed, for each possible source and destination network excluding paths where the source and destination are the same network. I have one right now, however it is unusably slow, taking about two seconds to map the paths, which becomes incredibly noticeable for all connected players.

The current algorithm is a depth-first brute-force search (It was thrown together in about an hour to just get the path caching working) which returns an array of networks in the order they are traversed, which explains why it's so slow. Are there any algorithms that are more efficient?

As a side note, while these example graphs have four networks, the in-practice graphs have 55 networks and about 20 routers in use. Paths which are not possible also can occur, and as well at any time the network/router graph topography can change, requiring the path cache to be rebuilt.

What approach/algorithm would likely provide the best results for this type of a graph?