标签: path-finding

我试图使用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*寻路,立方体由6个网格组成,为​​了保持简单,我有4种方法GetXPlus,GetXMinus,GetYPlus,GetYMinus.每个方法检查下一个tile是否在当前网格空间内,如果它不是切换到适当的网格.

我遇到的问题是当试图从当前网格中另一个方向翻转的网格中获取一个图块时,返回的图块位于另一侧.是否有一种方法或方法可以避免为每个原始网格和方向编写独特的逻辑？

为了帮助清楚地表达我的问题,在这里,我来自(紫色)网格,并使用GetXPlus方法:

我当前实现的一个snippit(每个网格是64乘64):

public Tile GetXPlus( int currentX, int currentY )
{
    var newX = currentX + 1;
    var tile = GetTile( newX , currentY );

    if( newX > 64 ) //Get adjacent XPlus Grid 
    { 
        currentGrid = SetCurrentGrid( XPlusGridIndex );
        tile = GetTile( newX - 64, currentY );
    }

    return tile;
}

背景

此实现源于对此处建议的不同问题的出色答案:https://gamedev.stackexchange.com/questions/53866/pathfinding-on-a-uneven-planetary-surface

我正在编写一个模拟,其中生物对象应该能够朝向环境中的其他任意对象移动,在障碍物周围滑动而不是进行任何智能寻路.我不是想让它计划一条路 - 只是向一个大方向移动,并在障碍物周围反弹.

它是一个2D环境(俯视图),每个对象都有一个用于碰撞检测的边界矩形.没有网格,我不是在寻找A*解决方案.

我无法找到关于这种"哑"基于碰撞的寻路的任何教程,所以我可能不会用最常用的术语来描述它.

有关如何实现这一点的任何建议(或指向教程的链接)？

我正在开发一个简单的基于2d网格的SIM游戏,并且具有完整功能的路径查找功能.

我使用上一个问题中找到的答案作为实现A*路径查找的基础.(寻路2D Java游戏？).

为了向您展示我真正想要的东西,我需要向您展示我制作的这个视频截屏.我只是在测试,看看这个人将如何移动到某个位置并再次返回,这就是结果......

http://www.screenjelly.com/watch/Bd7d7pObyFo

不同的路径选择取决于方向,意外的结果.有任何想法吗？

我需要在google appengine中存储一个大而动态的无向图,这是最好的方法吗？图形表示必须能够支持快速拉出一组顶点(用于在页面上渲染)和来自特定顶点的所有链接,以及跨图形的路径寻找(尽管最佳路径并不是真正需要的,只是一个公平的好的一个)

我对这个主题的看法:最明显的方法是有一个顶点模型和一个引用两个顶点的边缘模型,但听起来它最终会为每个操作使用大量的查询,我想知道是否有一种更好的方法(可能以某种方式将链接信息构建到每个顶点)

我正在开发一款僵尸在沼泽中奔跑的游戏.我希望AI拥有"追逐这个目标"或"逃跑"等功能.一个主要障碍是寻路.在XNA中是否有一个好的寻路/ AI引擎,或者我应该自己动手？

有没有人有这方面的经验:http://www.codeplex.com/simpleAI？

假设我们有一个DIRECTED,WEIGHTED和CYCLIC图表.

假设我们只对总重量小于MAX_WEIGHT的路径感兴趣

找到总重量小于MAX_WEIGHT的两个节点A和B之间的不同路径数量的最合适(或任何)算法是什么？

PS:这不是我的功课.只是个人的非商业项目.

我正在寻找一种寻路算法,用于AI控制2D网格中的实体,需要找到从A到B的路径.它不一定是最短路径,但需要非常快速地计算.网格是静态的(永远不会改变),一些网格单元被障碍物占用.

我目前正在使用A*,但它对我的目的来说太慢了,因为它总是试图计算最快的路径.当路径不存在时会出现主要的性能问题,在这种情况下,A*将尝试探索太多的单元.

如果路径不必是最短路径,我可以使用不同的算法找到比A*更快的路径吗？

谢谢,

鲁米

在此cypher查询中,将返回与STATUS ="on"属性相互关联的节点之间的最长路径/路径,但我还想获得路径/路径的最后一个节点.

查询:

START n=node(*)
MATCH p=n-[rels:INCLUDE*]->m 
WHERE ALL (rel IN rels 
  WHERE rel.status='on') 
WITH COLLECT(p) AS paths, MAX(length(p)) AS maxLength 
RETURN FILTER(path IN paths 
  WHERE length(path)= maxLength) AS longestPaths

我该如何将其添加到查询中？谢谢.

我知道A*比Dijkstra的算法更好,因为它考虑了启发式值,但是从A*和Jump Point搜索这是在有障碍的环境中找到最短路径的最有效算法？有什么区别？