-
2 votesanswersviews
提升隐式图和astar_search_no_init
我想实现机器人的路径规划子系统 . 我将使用来自boost库的A * . 我需要隐式图 . 我必须使用 astar_search_no_init 函数（它写在文档中） . 不幸的是，我找不到使用 astar_search_no_init 和隐式图的示例 . 我找到了"A* Graph Search Within the BGL Framework" . 作者使用 astar_s... -
1 votesanswersviews
找到BGL图中路径中使用的平行边？
任何人都可以通过一个工作示例来显示如何确定在类型图形上从 astar_search() 获得的路径所使用的实际边缘： parallel edges （当相同的相邻源和目标顶点之间存在多条路径时）可能存在（与"costs"不同？ location 和 route 是我作为顶点和边的捆绑属性的自定义结构 . 我原本打算使用 listS （特别是std :: list）作为outEd... -
5 votesanswersviews
Boost Graph Library astar和导航网格
我正在研究SFML / C项目，我需要生成一个图形来连接它们之间的障碍以方便寻路，所以我有兴趣生成一个导航网格，我将应用boost A *算法 . 有点像这样： 但是我在使用Boost Graph Library实现这个问题时遇到了很多问题（如果你有一个我认为更合适的库） . 首先，我创建一个具有适当结构的adjacency_list： struct WayPoint{ sf::Vecto... -
1 votesanswersviews
如何使用get（）boost图
我正在尝试实现自己的A星算法 . 但是，我只想通过迭代器获得边缘权重值 . 由于迭代器按顺序访问属性映射，我不能优先考虑边缘，需要为每个顶点做一个完整的循环以找到邻居，这会使算法真的变慢 . 有没有办法使用get（），put（）...没有迭代器，选择我要检查边缘的顶点？ 这是我目前的计划： struct Point {//struct point with vertex properties ... -
-1 votesanswersviews
A *或双向广度优先搜索？
不确定这是否是正确的地方，但是， 我在Java中编写了双向广度优先搜索算法，该算法同时从图中的起始节点和图中的目标节点进行搜索 . 在具有3000000（300万）个节点的图中，其中所有节点都与平均4个其他节点连接（与双向/双向边连接），在平庸的CPU上平均只需0.5秒即可找到最短路径任何两个随机节点，大约10秒是我发现超过30次测试运行的最坏情况时间 . 假设只需要搜索一条路径（例如，在绘制起点... -
4 votesanswersviews
使用Depth / Breadth first / A *算法在图树中搜索
关于在图形/树中搜索，我有几个问题： 让我们假设我有一个空棋盘，我想从A点到B点移动一个棋子 . A.当使用深度优先搜索或广度优先搜索时，我们必须使用打开和关闭列表吗？这是一个包含要检查的所有元素的列表，以及其他已经检查过的所有元素的列表？没有这些清单，甚至可以做到这一点吗？ A *怎么样，需要它吗？ B.使用列表时，在找到解决方案后，如何获得从A到B的状态序列？我假设你在开放和关闭列表中有项目，... -
1 votesanswersviews
8拼图的有缺点汉明距离启发式（A *搜索）
不可接受的启发式可能导致A *无法找到目标的最佳路径 . 例如，假设搜索树只有两个分支： A -1-> B -1-> C A -3-> D 也就是说，从A到B的步骤成本为1，从B到C的步骤成本为1，从A到D的步骤成本为3. A是根，C和D都是目标 . 如果不允许的启发式算法给出B的估计值为3，则A *搜索将在C之前扩展D，从而找到不是最便宜的目标的路径（3而不是2） . 现在，... -
17 votesanswersviews
为什么内存中A *指数的复杂性？
维基百科在A *复杂性上说以下（link here）： 比时间复杂度更有问题的是A *的内存使用率 . 在最坏的情况下，它还必须记住指数数量的节点 . 我没有看到这是正确的，因为： 假设我们探索节点A，后继B，C和D.然后我们将B，C和D添加到开放节点列表中，每个节点都附带一个A的引用，我们将A从开放节点移动到关闭节点 . 如果在某个时候我们找到另一条到B的路径（比如通过Q），这比通过A的路径... -
5 votesanswersviews
列车寻路算法
我正试图找到一种解决方案，用于在火车游戏中进行寻路，其中存在不同类型的分叉 . 我希望火车从一个铁路到另一个铁路，除路径寻找外，一切都已实施 . 我需要得到一个铁路列表，以便火车可以跟随 . 现在，问题是我如何获得列表 . 我've tried A*, didn'工作，因为它停止搜索是否已访问节点（铁路） . 这是一个问题，因为可能达到某一点的方法是通过最长的路线 . 试过洪水填充，这一次... -
1 votesanswersviews
自顶向下游戏中多线程A *寻路冻结
我一直在做一个自上而下的射击游戏，当我产生多个 HostileEntity （包含所有寻路函数的任何"enemy"的超级类）时，敌人要么： 不要从游戏开始移动 游戏开始后开始移动，但是一旦我移动玩家，所有都会冻结 . 我已经想到位于我的Algorithm类中它冻结在这个函数 public Path backtrackPath(Node fromNode) { ... -
1 votesanswersviews
A *使用潇洒技工寻路
如果我有一个可以向四个方向移动的2D环境，但除了那些方向之外，我可以冲向一个方向，直到我撞到墙壁，我将如何计算一个可接受的启发式算法呢？无论是移动还是破折号，每个都有一个G成本为1，所以冲刺和行走的权重相等 . 我应该使用A *吗？如果在某些情况下，多次冲刺会比移动更快到达目的地，即使在某些时候你在冲刺后离目的地更远，哪种寻路方式能够计算出最佳路径？ -
1 votesanswersviews
棋子寻路的A星算法
我的A *算法有问题 . 这必须在n * m板上找到最短路径 . 我的算法适用于国王和骑士，如下： public List<Node> aStar(int[,] chessBoard , Tuple<int , int> startXY , Tuple<int , int> endXY , int piece) { //Tuple<int[] , in... -
6 votesanswersviews
寻路 - A *最少转弯
是否可以修改A *以返回最短路径 with the least number of turns ？ 一个复杂因素：节点不能再仅仅通过它们的位置来区分，因为它们的父节点与确定未来转弯相关，因此它们也必须具有与它们相关联的方向 . 但我遇到的主要问题是如何将轮数转换为部分路径成本（g） . 如果我乘以乘以（t）的匝数，奇怪的事情就会发生：在接近末端的N转弯的较长路径优于较短的路径，在开始附近有N圈 .... -
18 votesanswersviews
A *六边形网格中的寻路
任何人都可以指向一个简单的例子，在 hexagonal 网格上实现A* path-finding algorithm（在JS中） . 我已经使它在正方形网格上工作，但是我在六边形网格上工作的所有尝试都失败了 . 这就是我的网格的样子： 我使用相同的技术绘制网格并生成坐标，如topic所示 . 这是网格坐标数据以及开始，结束坐标： [0, 0] , [0, 1], [0, 2], [1,... -
4 votesanswersviews
使用A星查找路径的启发式函数
我正在尝试为以下问题找到最佳解决方案 每个节点内表示的数字表示为 (x,y) . 节点的相邻节点始终具有 y 值（当前节点y值为1） . 当我们从一个节点到另一个节点时， x 值的变化成本为1 如果 x 的值没有变化，则从节点到其相邻节点没有任何成本 . 具有相同 y 值的2个节点被认为是相邻的 . 最优解是成本最低的解决方案，我正在考虑使用A *路径寻找算法来寻找最优解... -
3 votesanswersviews
通过四维数据寻路
问题是找到通过四维风的平面的最佳路线（不同高度的风和随着旅行而变化的风（预测风模型）） . 我已经使用了传统的A *搜索算法并将其破解以使其在3维和风向量中工作 . 它适用于很多情况，但速度非常慢（即时处理大量数据节点）并且对某些边缘情况不起作用 . 我觉得我的工作“很好”，但它感觉非常黑了 . 通过这样的数据（可能是遗传算法或神经网络），或者我甚至没有考虑过的东西，是否有更好的更有效的路径查找途... -
1 votesanswersviews
使用航点的Unity A *寻路
我正在尝试使用我在地形上使用单独脚本生成的路标创建A *寻路算法 . 地形上的可穿越和不可穿越的航点由其颜色定义 - 绿色可穿越 . 通过以下链接可以看到节点的布局：https://i.stack.imgur.com/JDZdx.jpg 可遍历的航路点存储在列表中 . 为了启动寻路算法，我创建了一个字典，将每个可遍历的航路点存储为一个唯一的密钥（type = gameobject） . 每个键的值... -
1 votesanswersviews
是明星搜索必不可少的开放和封闭列表 .
我正在尝试在Unity中使用星形搜索算法制作寻路系统 . 我的问题是，是否可以在没有打开和关闭列表的情况下实现算法？ 我的代码目前以下列方式工作： 当前节点最初设置为起始节点 . 搜索当前节点的相邻节点的列表，并返回具有最低f cost的节点（使用以下公式计算：f（n）= g（n）h（n） 具有最低代码的节点被设置为nodeToMoveToNext . 当前节点设置为nodeToM... -
3 votesanswersviews
在2D整数数组Java中查找最短路径
我正在进行蛇形游戏，其中蛇穿过2D int数组作为其地形 . 存储在2D数组中的值表示跨越所需的时间（以秒为单位） . 例如， int[][] MAP = { { 1, 1, 1, 2, 2 }, { 1, 2, 2, 2, 2 }, { 3, 2, 2, 3, 1 }, { 1, 1, 3, 2, 1 }, { 1, 1, 3, 2, 1 } }; ... -
3 votesanswersviews
为什么我的a *算法不采用最短路径？
我的a *算法并不总是采用最短的路径 . 在这张图片中，机器人必须穿过黑色方块，河流和树木都是障碍物 . 黑线是它所采用的路径，显然不是最短的路径，因为它不应该浸入 . http://imgur.com/GBoq9py 这是我的代码*和我正在使用的启发式： def HeuristicCostEstimate(start, goal): (x1, y1) = start (x2, y... -
8 votesanswersviews
路径寻找算法：A * Vs跳转点搜索
我知道A *比Dijkstra的算法更好，因为它考虑了启发式值，但是从A *和Jump Point搜索这是在有障碍的环境中找到最短路径的最有效算法？有什么区别？ -
0 votesanswersviews
可以对AnyTime加权A *算法进行哪些改进？
首先，对于那些不知道的人 - Anytime Algorithm是一种算法，它可以获得它可以运行的时间量作为输入，它应该在那个时间提供最佳解决方案 . 加权A *与A *相同，f函数中有一个差异： （其中g是节点的路径成本，h是到达目标之前到路径末端的启发式） Original = f(node) = g(node) + h(node) Weighted = f(node) = (1-w)g(... -
34 votesanswersviews
Python - 加速星寻路算法
我编写了我的第一个稍微复杂的算法，这是A Star Pathfinding算法的一个实现 . 我在实现图形时遵循了一些Python.org advice，因此字典包含每个节点也链接的所有节点 . 现在，因为这是游戏的全部，每个节点实际上只是节点网格中的一个区块，因此我如何计算启发式和偶尔引用它们 . 感谢timeit我知道我可以成功运行这个功能一秒钟一百多次 . 可以理解这让我有点不安，这是没有任... -
5 votesanswersviews
大规模的寻路探测
我正在尝试用Javascript创建塔防游戏 . 除了探路之外，这一切都很顺利 . 我正在使用来自这个网站的astar代码：http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript它使用二进制堆（我认为这是相当优化的） 我遇到的问题是我想让人们阻止“攻击者”的路径 . 这意味着每个“攻击者”都需要能够自己找到出口... -
6 votesanswersviews
立方体表面的星寻路算法启发式算法
我正在构建一个在立方体表面上播放的snake game . 目前它使用Dijkstra的算法进行寻路 . 尽管使用set和priority队列数据结构进行了优化，但它仍然有点太慢 . 当蛇吃食物并开始寻找新食物时，你会注意到延迟 . 我找到了一个很好的启发式方法 . 在有4个运动方向的平面网格上，我会使用曼哈顿距离 . 我已经尝试过使用3D曼哈顿距离 abs(dx) + abs(dy) + abs... -
-2 votesanswersviews
什么寻路算法适用于小网格和硬编码点？
我制作了一个A *探路者，看看它是否适用于我正在尝试做的事情，但我认为它不够好 . 我的网格不是太大而且有一些硬编码点，所以我要做的就是只检查硬编码点以找到它们之间的路径;例如： ┌──────────┐ │A B│ ├───────── │ │D C│ └──────────┘ 因此，从A点到D点，探路者功能应该告诉你从A - > B - > C ... -
1 votesanswersviews
.NET A *寻路优化，序列化？
几个月前，我为RTS游戏构建了一个基于网格的A *系统 . 我使用HashSets和启发式方法应用了基本的优化，但很快我会考虑进一步优化它，因为当多个单元同时请求路径时，它往往会减慢速度 . 无论如何我注意到Aron Granberg的A *系统有一个图形数据的序列化类，我的图只是一个Node类的二维数组，Node（）包含各种数据，例如它是否可以步行 . 我假设这个序列化用于保存/加载图形，但我是... -
2 votesanswersviews
用于隐式图的Boost Graph Library astar_search
我想将 astar_search() 算法应用于随时间生成的隐式图 . 因此，图中新顶点的初始化非常复杂，并且需要在另一个数据结构中进行外部查找 . 我已经研究了很多使用 astar_search() 的示例，但是使用隐式图表却找不到很多 . 从使用隐式图的所有示例来看，[1]看起来最有希望 . 提出的解决方案的问题是， astar_search() 将const图引用（ const Vertex... -
0 votesanswersviews
多目标的最短路径
我遇到了一个具有以下约束条件的送货员问题，我想听听您应该创建一个新算法的现有算法，或者希望只修改现有算法 . 具有偶数顶点的加权边的顶点图，具有顶点对，并且每个顶点具有15的权重 - 拾取和丢弃包需要时间 . 一对顶点包含“拾取位置”和“下降位置”Pn和Dn . 送货员可以在图表的任何地方 . 送货员必须到一对的Pn顶点 - “拾取位置” - 然后是Dn . 顶点具有到所有其他顶点的加权边 . ... -
4 votesanswersviews
寻路，A星和速度惯性
有's a duplicate question with an answer that I'试图在这里实施并遇到困难 . How to do pathfinding when a unit has inertia? 我有一个带有障碍物的网格，计算机可以在四个主要方向上移动，并使用A-star或Djikstra算法实现路径寻找 . 但后来我也想添加"velocity"，所以不...