标签: path-finding

假设你有一个2D网格的单元格,其中一些是用墙填充的.角色可以从一个正方形到任何与其一步水平或垂直的正方形,但不能穿过墙壁.

给定起始位置和结束位置,我们可以通过使用具有可允许启发式的A*算法找到从起始位置到结束位置的最短路径.在目前的设置中,曼哈顿距离是可以接受的,因为它永远不会高估到目的地的距离.

现在假设除了墙壁之外,世界上还有成对的传送器.踏上传送器会立即将角色传送到链接的传送器.传送器的存在打破了上面给出的允许启发式,因为通过使用传送器来减少距离,可能比通过最佳曼哈顿距离步行更快地到达目的地.例如,考虑这个线性世界,其中传送器标记为T,开始位置标记为S,结束位置标记为E:

T . S . . . . . . . . . . . . . E . T

在这里,最好的路线是步行到左边的传送器,然后向左走两步.

我的问题是:在带有传送器的网格世界中,A*的一个很好的可接受的启发式算法是什么？

谢谢!

任何人都可以向我指出一个在六边形网格上实现A*路径寻找算法的简单例子(在JS中).我已经使它在正​​方形网格上工作,但是我在六边形网格上工作的所有尝试都失败了.

这就是我的网格的样子:

我正在使用相同的技术绘制网格并生成坐标,如本主题所示.

这是网格坐标数据以及开始,结束坐标:

        [0, 0] , [0, 1],  [0, 2],
    [1, 0],  [1, 1],  [1, 2],  [1, 3],
 [2, 0],  [2, 1],  [2, 2],  [2, 3],  [2, 4],
    [3, 0],  [3, 1], [3, 2],  [3, 3], 
        [4, 0], [4, 1],  [4, 2]


start_point: [0,2]
end_point: [4.0]

将曼哈顿距离计算更新为:

var dx = pos1[0] - pos0[0];
    var dy = pos1[1] - pos0[1];

    var dist;
    if ( Math.sign(dx) == Math.sign(dy) ){
        dist = Math.abs (dx …

我想实现Pacman游戏.对于AI,我正在考虑使用A*算法,已在众多论坛上看到它.然而,我实现了广度优先搜索的一些简单的寻路(从点a到点b,其间有一定的障碍),并发现它始终给出了最佳路径.我想这可能是因为在像pacman这样使用简单寻路的游戏中,图中没有成本概念.那么,如果我在Pacman中使用BFS而不是A*进行寻路,那会没关系吗？

我得到了有向图，其中有n个节点，边为具有向量1（0，-1）的向量（每个向量的长度为m）的维数。我想找到从一个节点到另一节点（我们可以多次访问节点）的任何路径（或者说这种路径不存在），这样其权重之和就等于零向量。我当时在考虑蛮力回溯算法，但不能保证它会结束。我们可以以n和m的方式限制这种路径的长度吗？n = 8，m = 2的图形示例 路径示例

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

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

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

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

假设你有一个这样的网格(随机制作):

现在让我们假设你有一辆汽车从其中一个盒子里随机开始,那么通过每个白盒子的最短路径是什么？您可以根据需要多次访问每个白盒,也不能跳过黑盒子.黑匣子就像墙壁.简单来说,您只能从白框移动到白盒.

您可以向任何方向移动,甚至是对角移动.

两个子问题:

1. 假设您在移动之前知道所有黑匣子的位置.
2. 假设您在与其相邻的白色框中时只知道黑匣子的位置.

我目前正在使用HTML5 <canvas>元素在Javascript中编写2D游戏.它很顺利,但我遇到了一个问题.

我的游戏的关卡设计是一个网格(因此路径成本从一个单元格移动到北/南/东/西单元格为1),各种障碍占据网格中的不同位置 - 很像迷宫,但有很多更多的摆动空间.每个单独的级别大约为400×200个单元.

我试图实现一个敌人,无论他们在哪里都能找到玩家,但是我无法尝试翻译各种寻路算法之一以适合我的情况.我遇到的大多数(如A*和Dijkstra)似乎最适合3D或更复杂的2D情况.我想知道是否有可能大大简化这些算法以更好地适应我的目的,或者如果深度优先搜索的东西在给定级别大小的情况下是更有效的替代方案.

我目前正在根据Theme Hospital的想法编写一个非常基本的Java游戏.

我是Java的新手,我目前正在大学读书.我已经做了近两年的Java,但是我终于把时间花在了一个体面的项目上.

我正处于需要创建一个人(病人)进入医院的阶段.他们需要去接待处,然后去GP的办公室,然后回到他们的起始位置.

我已经研究过A*路径发现,但对我来说这似乎很复杂.我理解它是如何工作的,但我不确定如何在游戏中实现它.

到目前为止,用户可以放置一个接待台,并建立一个GP的办公室.这些中的每一个都具有"使用点",这将是患者必须去的地方.网格方块只能是满的,不会有不同的地形.

我对于粘贴任何代码都犹豫不决,因为它在过去的几个月中学习了很多与GUI相关的新技术,因为它很麻烦.我的计划是到达里程碑1,让病人去办公桌然后离开办公室.有了这个,我会更多地整理代码.

我见过许多A*和许多不同类型的实现.有人可以给我一个我可以使用的起点吗？我应该尝试调整已经编写的一组类,还是尝试从头开始编写自己的类？

我有一个带有开始,结束和一些墙的网格.单位从开始到结束采用最短路径(仅向上/向下/向左/向右移动),而不穿过墙壁.

允许用户添加他们想要更改路径的额外墙.

但是,请注意,无论添加多少墙壁或添加它们的位置,都有一些方块永远不会成为最短路径的一部分!

这些方块永远不会成为最短路径的一部分!

我正在寻找一种方法来检测哪些方块永远不会成为最短路径的一部分.

以上案例很容易找到; 但还有更复杂的案例.考虑:

在上图中,没有带红点的正方形可以成为最佳路径的一部分,因为该区域只有一个入口,并且它只有两个宽度.如果它是三个宽度的空间,或者如果任何一个墙被移除,那么大多数这些正方形可能是最佳路径的一部分.

我一直试图找出一种方法来检测上述情况(主要是使用最小割和洪水填充),但没有成功.有谁知道解决这个问题的方法？

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

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

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

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

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

谢谢.