标签: path-finding

如何在没有节点或单元格的无网格2D平面上实现A*算法？我需要物体以目标的方式围绕相对大量的静态和移动障碍物进行操纵.我目前的实现是在对象周围创建八个点,并将它们视为可能是对象的潜在位置的虚构相邻正方形的中心.然后我计算每个的启发函数并选择最佳.起点和运动点之间的距离,以及运动点和目标之间的距离我用毕达哥拉斯定理计算正常方式.问题在于,通过这种方式,物体通常会忽略所有障碍物,甚至更常被卡在两个位置之间来回移动.我意识到看起来多么愚蠢的问题,但任何帮助都表示赞赏.

我一直在尝试创建一个 jQuery 代码，该代码将扫描带有 id 的 divmap及其中的.map所有内容，并在尝试避免交叉/触摸 的同时找到从#Ato的最短路径，但我对如何做后者一无所知.#B#blockings

非常感谢任何帮助。

插图：

这是我的代码：

computeTrack('#a','#b', '#map');

function computeTrack(A, B, MAP){
  
  var bag = [];
  var obstacle = [];
  
  bag = getDistance(A, B);
  obstacle = scanning(A, B, MAP);
  moveAtoB(A, B, MAP, obstacle, bag);
}

function moveAtoB(A, B, MAP, obstacle, bag){
  var clone;
  $(A).append('<div id="clone" style="position:fixed;width:5px; height:5px; background-color:#F00; top:'+$(A).position().top+'; left:'+$(A).position().left+';"></div>');
  
  clone = '#clone';
  generatePath(clone, A, B, MAP, obstacle, bag);
}

function generatePath(clone, A, B, MAP, obstacle, bag){ …

我试图解决类似于GeeksforGeeks这个问题的问题,但是不同的是:
给定一个矩形的2-d网格,每个单元格中都有一些硬币值,任务是从左上角和右下角开始向右或者向下,从左下角到左上角向左或向上,最大化拾取的硬币总量.每个单元格中的硬币只能被挑选一次.
链接中的解决方案是同时启动两个遍历,但这不会在这里工作.
我该怎么解决这个问题？执行此操作的蛮力方式是枚举所有路径并选择两条路径,以最大化所拾取的硬币总和,但这对于大输入不起作用.

我正在尝试实施Pacman.它运行正常,但到目前为止,鬼魂没有使用任何寻路,而是在每个路径交叉点上随机决定采用哪条路径.所以你可以想象,Pacman赢得比赛并不困难;)

所以我在Pacman中阅读了一些关于路径查找算法的内容,在这里我发现了一个非常好的答案:Pacman的寻路算法

答案是指http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#Chapter%204

这一切都很好,但在我的Pacman实施中,有两个Pacman由两个不同的玩家玩.所以我想知道如何调整寻路算法,以便幽灵并不总是追逐一个玩家.

有关如何修改算法的任何想法,以便幽灵对两个玩家或多或少同等公平？

我已经在C#中成功实现了A*pathfinding,但它很慢,我不明白为什么.我甚至尝试不对openNodes列表进行排序,但它仍然是相同的.

地图是80x80,有10-11个节点.

我从维基百科那里拿了伪代码

这是我的实施:

 public static List<PGNode> Pathfind(PGMap mMap, PGNode mStart, PGNode mEnd)
    {
        mMap.ClearNodes();

        mMap.GetTile(mStart.X, mStart.Y).Value = 0;
        mMap.GetTile(mEnd.X, mEnd.Y).Value = 0;

        List<PGNode> openNodes = new List<PGNode>();
        List<PGNode> closedNodes = new List<PGNode>();
        List<PGNode> solutionNodes = new List<PGNode>();

        mStart.G = 0;
        mStart.H = GetManhattanHeuristic(mStart, mEnd);

        solutionNodes.Add(mStart);
        solutionNodes.Add(mEnd);

        openNodes.Add(mStart); // 1) Add the starting square (or node) to the open list.

        while (openNodes.Count > 0) // 2) Repeat the following:
        {
            openNodes.Sort((p1, p2) => p1.F.CompareTo(p2.F));

            PGNode current = openNodes[0]; …

在我的'project/repo'中,我有两个MS Visual Studio项目,一个用于主代码,另一个用于测试.我有一些共同的文件(在复制和粘贴意义上),我想看/检查它们是哪些.

什么是正确的Git命令(或Gui菜单点击),看看我是否在整个repo树中使用了两次相同的内容blob？如果我已经正确阅读了所有教程,git应该有一个SHA1用于相同文件内容的两个副本并且已经知道它.我希望Git有一个命令可以找到并显示这些重复的使用文件路径.

最后,当有共同的祖先blob SHA1(但不是常见位置)时,我希望能够找出版本之间的差异.[即在测试期间,一个版本会在另一个版本之前更新...]

我知道这样的副本不是最佳做法,但这是工作结束的方式:-(

我在Windows上有Msysgit和GitExtensions ...

我一直在阅读有关路径寻找算法的文章,我现在正在寻找一种像A*一样工作但是代理不能沿对角方向移动的算法.节点是否仍然沿对角线扩展还是以其他方式扩展？也许它根本与A*无关？另外请考虑下面的图像,其中显示三角形是我们的代理,棕色矩形是网格方块之间的障碍,箭头只是为了清楚地表明你仍然可以穿过在它们的"边界"上有障碍物的方块,当没有面对那个障碍时.您会建议我使用哪种算法作为具有这些特征的路径查找问题的基础？原谅我,如果这样的事情已经发布,我找不到它.

所以我使用Slick2D,我正在制作游戏.它有一个TiledMap和实体(和任何其他游戏一样),我想要一种使用A*的方法.我真的不知道如何使用它因为我找不到解释.

对于那些不使用Slick的人来说,它已经有了我使用的AStarPathFinding和TiledMap类.

计划在2D RTS上工作,我试图了解Astar是如何工作的.实际上,我发现文章解释了如何优化Astar与二进制堆的耦合,以及利用Path对称性的算法,如Jump Poin Search算法.我试图实现跳转点搜索,它运行正常.我甚至用MovingAI的地图做了一些基准测试.

然而,有一个问题.允许对角线移动时,一切运行正常.禁用时,不返回任何路径...

它可能与我实现它的方式有关,然后我都在问......一般来说,你如何要求算法(JPS)搜索仅涉及直线移动(不是对角移动)的路径才能达到目标？

我目前正在尝试实施我自己的公共交通路径查找器,以便通过电车/公共汽车等找到具有给定时间表的连接.所有数据都是由我生成的(只需在谷歌地图中添加停止坐标).多亏了它,我可以自由选择存储数据和处理数据的方式.整个运输网络由加权图表示.所以问题就出现了:如何将公共交通数据存储在标准SQL数据库中,以便通过某些选择的算法轻松处理？如何轻松地将其转换为时间扩展图形,以便简单的Dijkstra算法就足够了？