标签: path-finding

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

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

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

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

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

谢谢.

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

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

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

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

我正在使用python中的实时等距RPG,并希望将移动设备作为平台.我遇到困难的主要领域是我的寻路.我尝试了一些算法,包括A*和一些调整,以更好地适应我正在使用的地图.

我对我的算法的结果感到满意 - 它们在确定性的同时给出了一些智能的错觉,并且在任一方向上都是一致的,这样两个以两个角色为目标的角色就会在中间碰撞.

我的问题是虽然PC上的结果看起来很好,我可以要求所有的处理能力,在我的手机上它是另一个故事,并且在计算算法时经常会有第二次或更多延迟.出于这个原因,我正在考虑用C编写的性能最密集的代码为此编写一个库,但是如果有一个现有的解决方案,或者更好的方法我可以做到这一点,我会全力以赴.

我偶然发现了python-pathfinding,但这似乎比我为自己的用例构建的更慢.

我的用例:

我的地图是从水平建造的,这些水平被墙壁(可见或不可见)包围,并且必须通过门(可见或不可见)链接.

我目前的方法是有两种不同的算法:

• 在一个房间内,我将单个图块搜索为节点,每个边界作为等成本边缘,在目标位置的方向上使用深度优先

• 在每个门都是节点的房间之间.使用第一算法计算通过房间(从门到门)的最短可能路径,并将其存储在哈希表中作为这些节点之间的边缘成本.然后计算可以遍历从一个节点到另一个节点的边集,并将其存储在散列表中,并且不允许在同一路径中多次包含相同的边.

我在启动时产生了一个单独的过程,它使用第一个算法生成第二个算法的图形,这解决了我的许多问题,房间往往相对较小,因此保留了即时路径查找的惩罚低于其他情况,然后长距离:

• 第一种算法用于计算从当前位置到当前房间中每扇门的距离.
• 第一种算法用于计算目标房间中每扇门到目标位置的距离.
• 第二种算法的输出用于获取房间之间的路径集
• 这些费用加到了第一扇门和最后一扇门的费用上
• 该组解决方案按成本分类,使得相同成本的路径顺序始终保持一致
• 选择解决方案集中的第一项.

我正在研究一个小的prolog应用程序,以解决摩天大楼和栅栏难题.

一个未解决的难题:

一个解决的难题:

当我通过程序已经解决的谜题时,它很快,几乎是即时的,为我验证它.当我通过程序真正的小谜题(例如,2x2,当然有修改的规则),找到解决方案也很快.

问题在于计算具有6x6"原生"大小的谜题.我让它在中止前运行了5个小时左右.太多时间了.

我发现花费时间最长的部分是"围栏",而不是"摩天大楼".分别运行"摩天大楼"可以快速解决问题.

这是我的栅栏算法:

• 顶点用数字表示,0表示路径不通过该特定顶点,> 1表示顶点在路径中的顺序.
• 约束每个单元格以使其周围有适当数量的线条.
  • 这意味着如果它们具有连续数字,则连接两个顶点,例如,1 - > 2,2 - > 1,1 - > Max,Max- > 1(Max是路径中最后一个顶点的数字.计算通过maximum/2)
• 确保每个非零顶点至少有两个具有连续数字的相邻顶点
• 约束Max等于(BoardWidth + 1)^2 - NumberOfZeros(BoardWidth+1是沿边缘的顶点数,并NumberOfZeros通过计算count/4).
• 使用nvalue(Vertices, Max + 1)以确保不同值的数量Vertices是Max(即顶点的路径数)加1(零个值)
• 找到包含a的第一个单元格3并强制路径开始和结束,以提高效率

我该怎么做才能提高效率？代码包含在下面以供参考.

skyscrapersinfences.pro

:-use_module(library(clpfd)).
:-use_module(library(lists)).

:-ensure_loaded('utils.pro').
:-ensure_loaded('s1.pro').

print_row([]).

print_row([Head|Tail]) :-
    write(Head), write(' '),
    print_row(Tail).

print_board(Board, BoardWidth) :-
    print_board(Board, BoardWidth, …

如何使用双向BFS查找最短路径？假设有一个6x6网格.起点在(0,5),终点在(4,1).使用双向bfs的最短路径是什么？没有路径成本.它是无向的.

假设有一个网格包含两个墙(被阻挡的单元格)以及放置在网格上任何位置的食物.

现在假设我们正在尝试确定将蚁群放置在该网格上的最佳位置,使得蚂蚁必须行进最小距离(在任何方向上往/来自群体的起始点)以获得最大量的食物.

到目前为止,我提出的最佳方法如下:

for each square on the grid
    use a shortest path algorithm to find the distance to/from each food source from this square
    sum these distances to find a number and put the number in that square
select the square with the smallest number

这种方法是否有效？有更有效的解决方案吗？

我不明白如何IDA*节省内存空间.从我的理解IDA*是A*迭代加深.

什么是内存量之间的差额A*使用VS IDA*.

最后一次迭代的IDA*行为是否完全相同A*并且使用相同数量的内存.当我跟踪时,IDA*我意识到它还必须记住低于f(n)阈值的节点的优先级队列.

我知道ID-Depth第一次搜索有助于深度优先搜索,允许它首先像搜索一样进行广度,而不必记住每个节点.但我认为它的A*行为首先就像深度一样,因为它忽略了沿途的一些子树.迭代加深如何使用更少的内存？

另一个问题是使用迭代加深的深度优先搜索允许您通过使其首先表现为宽度来找到最短路径.但A*已经返回最佳最短路径(假设启发式是可接受的).迭代加深如何帮助它.我觉得IDA*的最后一次迭代与之相同A*.

我一直在寻找一种强大的寻路方法,我正在开发基于平台游戏的游戏,A*看起来像是最好的方法.我注意到有一个关于Godot中AStar实现的演示.然而,它是为基于网格/磁贴的游戏编写的,我无法适应平台,其中Y轴受到重力的限制.

我找到了一个非常好的答案,描述了A*如何应用于Unity中的平台游戏.我的问题是......是否可以在Godot中使用AStar来实现上述答案中描述的相同内容？如果不使用内置的AStar框架,可以做得更好吗？在GDscript中它是如何工作(有或没有AStar)的一个非常简单的例子是什么？

虽然我已经发布了100点奖金(它已经过期),但我仍然愿意发布另外100点赏金并奖励它,等待回答这个问题.

PS:如果你在这个问题的正文中看到一些你觉得不合适的东西,需要注意或澄清......不要贬低我的投票!展示一些诚信并发表评论.你所做的一切都在伤害那些投票给我的其他人,并且实际上对这个问题的答案感兴趣.

我试图使用Dijkstra和A Star算法(在有向NetworkX图中)计算2点之间的最短路径.

目前它工作正常,我可以看到计算的路径,但我想找到一种限制某些路径的方法.

例如,如果我们有以下节点:

节点= [1,2,3,4]

有这些边缘:

edges =((1,2),(2,3),(3,4))

有没有办法阻止/限制 1 - > 2 - > 3但仍允许2 - > 3&1 - > 2.

这意味着:

• 可以从1到2旅行

• 可以从2到3旅行

• 不能直接或间接地从1到3行进(即限制1-> 2-> 3路径).

这可以在NetworkX中实现..如果没有在Python中有另一个图形库允许这个吗？

谢谢.

我有一个应用程序将受益于使用A*; 但是,由于遗留原因,我需要它继续生成与之前有多个最佳路径可供选择的路径完全相同的路径.

例如,考虑这个迷宫

...X
FX.S
....

S = start
F = finish
X = wall
. = empty space

方向优先级Up; 对; 下; 离开了.使用广度优先,我们将找到路径DLLLU; 然而,使用A*我们立即离开,最终找到路径LULLD.

我一直试着确保在打破领带时始终朝着正确的方向扩展; PreviousNode从更重要的方向移动时覆盖指针,但在该示例中都不起作用.有没有办法做到这一点？