标签: a-star

我正在研究A*路径寻找算法的定义,它似乎在不同的地方有所不同.

不同之处在于在遍历节点的后继者时执行的操作,并且发现后继者在关闭列表上.

• 一种方法(由维基百科和本文建议)说:如果后继者在封闭列表中,则忽略它
• 另一种方法(例如,此处和此处建议)说:如果后继者在封闭列表中,则检查其成本.如果它高于当前计算的分数,则从关闭的列表中删除该项目以供将来检查.

我很困惑 - 哪种方法是正确的？直觉上,第一个对我来说更有意义,但我想知道定义的差异.其中一个定义是错误的,还是它们在某种程度上是同构的？

我正在尝试为15平方拼图构建一个A*求解器.

替代文字http://i49.tinypic.com/343r8ki.jpg

目标是重新排列瓷砖,使它们出现在自然位置.您一次只能滑动一个图块.拼图的每个可能状态是搜索图中的节点.

对于h(x)函数,我在所有图块中使用了图块与目标状态的错位的总和.在上面的图像中,5位于位置0,0,它属于位置1,0,因此它对h(x)函数贡献1.下一个区块是11,位于0,1,属于2,2,因此它对h(x)贡献3.等等.编辑:我现在明白这就是他们所谓的"曼哈顿距离",或" 出租车距离 ".

我一直在使用g(x)的步数.在我的实现中,对于状态图中的任何节点,g只是来自先前节点g的+1.

为了找到连续的节点,我只是检查在哪里可以移动拼图中的"洞".显示的拼图状态(aka节点)有3个邻居:洞可以向北,向西或向东移动.

我的A*搜索有时会收敛到20s,有时是180s的解决方案,有时根本不收敛(等待10分钟或更长时间).我认为我是合理的.我想知道我是否正确地模拟了g.换句话说,我的A*函数是否可能通过不是最短路径的路径到达图中的节点？

也许我没有等待足够长的时间？也许10分钟不够长？

对于完全随机的安排,(假设没有奇偶校验问题),A*解决方案将检查的平均排列数是多少？(请显示数学)

我将在我的代码中查找逻辑错误,但在此期间,任何提示？

(ps:它是用Javascript完成的).

另外,不,这不是CompSci的功课.这只是个人探索的事情.我只是想学习Javascript.

编辑:我发现运行时间高度依赖于启发式.我从有人提到的文章中看到了10x因子应用于启发式,它让我想知道 - 为什么10x？为何线性？因为这是在javascript中完成的,所以我可以修改代码以使用当前正在考虑的节点动态更新html表.这允许我在算法进展时查看算法.使用常规的出租车距离启发式,我看到它没有收敛.

排在前排有5个和12个,他们一直闲逛.我看到1,2,3,4爬进了最上面的一行,但随后它们会退出,其他数字会向上移动.我希望看到的是1,2,3,4爬到顶部,然后呆在那里.

我心想 - 这不是我亲自解决这个问题的方式.手动执行此操作,我解决了顶行,然后是2ne行,然后是第3行和第4行.

所以我调整了h(x)函数来对更高的行和"lefter"列进行更大的权重.结果是A*收敛得更快.它现在运行3分钟而不是"无限期".通过我所谈到的"偷看",我可以看到较小的数字爬到更高的行并留在那里.这不仅是正确的事情,它运行得更快.

我正在尝试一系列变化.很明显,A*运行时对启发式非常敏感.目前我发现的最佳启发式使用了dislocation * ((4-i) + (4-j))i和j是行和列的总和 ,而位错是出租车距离.

我得到的结果的一个有趣的部分:使用特定的启发式,我很快找到了一条路径,但它显然不是最短的路径.我认为这是因为我正在加权启发式.在一个案例中,我在10s内获得了178步的路径.我自己的手动努力产生了87个动作的解决方案.(超过10秒).更多的调查需要保证.

所以结果是我看到它收敛必须更快,并且路径绝对不是最短的.我不得不考虑更多.

码:

var stop = false; 
function Astar(start, goal, callback) {
    // start and goal are nodes in the graph, represented by 
    // an array of 16 ints.  The goal is:  [1,2,3,...14,15,0] 
    // Zero represents the hole. 

    // callback is a …

有这么多可用的实现,使用小网格的C++最快执行(最少CPU密集,最小二进制),跨平台(Linux,Mac,Windows,iPhone)A*实现是什么？

实现

谷歌回归:

• http://www.heyes-jones.com/astar.html(该网站上的大多数链接已经死亡.)
• http://www.grinninglizard.com/MicroPather(据说比Heyes-Jones慢.)
• http://www.ceng.metu.edu.tr/~cuneyt/codes.html(通用C++代码.)
• http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
• http://opensteer.sourceforge.net/(对游戏感兴趣,而不是A*.)
• Dijkstra算法的堆栈溢出

还有其他人？

轮

正如所提出的,问题涉及重用(插入游戏),而不是重新发明(至少在性能显示为问题之前).可能会发现Dijkstra实现(或通用寻路算法)更适合,或者最快的实现速度不够快.我很欣赏替代算法的建议,但问题不是,"我应该自己推出A*吗？"

• Joel on Software - Not Invented Here Syndrome
• 编码恐怖:不要重新发明轮子
• 克服"未发明的综合症"

根据我对A*启发式的理解以及Bresenham算法如何工作,这可能是不可能的,因为只有当前状态和目标状态被传递给启发式函数.但也许某人有一个聪明的解决方案来解决这个问题.

我正在使用A*来计划网格上的路径,并且我想要一种启发式方法,当当前状态和目标之间存在自由空间或绕过障碍物时,可以使最佳路径遵循Bresenham线.

这里有一些图像来说明问题.

曼哈顿距离:

如果世界上的运动像一个网格上的棋子一样,这将是完美的,但我最终会将A*路径转换为连续平面上的运动,所以这确实很有效.

欧几里德距离:

更好,但仍然不完美.注意最后的直线.对角线可以很容易地保持对角线,这就是我想要的.

我想要的是:

Bresenham线被吸引到下一个回合或目标.

我在这里找到了一个很好的资源,http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html触及了我正在寻找的东西,但似乎只能用于从开始到目标绘制Bresenham线.我想要的是Bresenham线也被绕到障碍物的下一个转弯.

有什么想法可以很好地解决这个问题吗？

我一直致力于90年代早期冒险游戏的JavaScript实现,并专门绘制从英雄站立位置到玩家点击位置的路径.我的方法是首先确定是否可以绘制一条海峡线(没有障碍物),如果没有,那么使用Brian Grinstead的优秀javascript-astar搜索一条清晰的路径.然而我面临的问题是路径(虽然最佳会转向用户看似无意的空间.这是我所谈论的经典例子(绿色路径是生成的路径,红点每个转向路径方向改变的地方):

现在我知道A*只能保证返回一个不能简单的路径(就步骤而言),但我正在努力实现一个权重转向的启发式算法.这是一张图片,显示了另外两条路径,这些路径也同样简单(步数相同)

蓝色路径将呈现相同数量的步数和转弯,而红色路径具有相同的步数和更少的转弯.在我的代码中,我有一个simplifyPath()函数可以删除方向改变的步骤,所以如果我可以astar从那时获得所有可能的路径,我可以选择转弯最少的路径,但这不是A*从根本上如何工作,所以我正在寻找一种方法将简单性融入启发式算法.

这是我目前的代码:

var img,
    field = document.getElementById('field'),
    EngineBuilder = function(field, size) {
        var context = field.getContext("2d"),
            graphSettings = { size: size, mid: Math.ceil(size/2)},
            engine = {
                getPosition: function(event) {
                    var bounds = field.getBoundingClientRect(),
                        x = Math.floor(((event.clientX - bounds.left)/field.clientWidth)*field.width),
                        y = Math.floor(((event.clientY - bounds.top)/field.clientHeight)*field.height),
                        node = graph.grid[Math.floor(y/graphSettings.size)][Math.floor(x/graphSettings.size)];

                    return {
                        x: x,
                        y: y,
                        node: node
                    }
                },
                drawObstructions: function() {
                    context.clearRect (0, 0, 320, …

我正在使用A-star算法,我有一个2D网格和一些障碍.现在,我只有纵向和横向障碍物,但它们可以密集地变化.

现在,A-star效果很好(即大多数情况下找到的最短路径),但是如果我尝试从左上角到右下角,那么我有时会看到路径不是最短的,即有一些笨拙在路上.

这条道路似乎偏离了最短路径应该是什么.

现在我正在使用我的算法.我从源头开始,在计算邻居的值时向外移动,距离源+目的地的距离,我一直选择最小的单元格,并继续重复直到我遇到的单元格是目的地,此时我停.

我的问题是,为什么A-star不能保证给我最短的路径.或者是吗？我做错了什么？

谢谢.

我正在寻找一个解释为什么AStar/A*算法被称为AStar.所有类似的(最短路径问题)算法通常都被命名为它的开发者,所以AStar代表什么？

免责声明:我没有Java的背景,因为我主要是C#开发人员.

想拥有java实现的A*算法.
是的,我在网上看到了很多相同的版本,我无法在它们之间做出选择.

我正在寻找一个A*算法实现,它使用java的所有新功能,使算法更快(即使有点).原因在于我们正在实施路径查找MMO,因此,性能是首要任务.

任何指针(至少在哪里看)？

关于以下A*搜索示例,我想澄清一些事情:

用红色椭圆突出显示的部分是我不理解的区域; 似乎{S,B} f=2+6=8已从Expand S(上方)采取/移动/复制并使用Expand A.它似乎{S,A,X} f=(1+4)+5=10也被采取/移动/复制Expand A和使用Expand B.

有人可以解释为什么会这样吗？我能够很好地阅读图表并且解释它没有任何问题 - 仅仅是因为我不知道为什么上述路径/路由在其他地方被复制了.

谢谢.

在我的教科书中,我注意到这两种算法几乎完全相同,我试图理解它们之间的主要区别.

教科书使用A*以与最佳优先搜索相同的方式遍历此示例.

任何帮助,将不胜感激.