标签: path-finding

(这不是我所遇到的问题,但它是同构的,我认为这种解释对其他人来说是最容易理解的.)

假设我在n维空间中有一组点.使用3个维度,例如:

A : [1,2,3]
B : [4,5,6]
C : [7,8,9]

我还有一组向量来描述这个空间中可能的运动:

V1 : [+1,0,-1]
V2 : [+2,0,0]

现在,给定一个点dest,我需要找到一个起点p和一组向量移动,它将以最有效的方式将我带到dest.效率定义为"最少的动作",不一定是"至少直线距离":它允许选择一个p进一步的从DEST比其他候选人,如果此举集是这样,你可以在更少的移动那里.移动中的向量必须是可用向量的严格子集; 除非在输入集中出现多次,否则不能多次使用同一个向量.

我的输入包含~100个起点和~10个矢量,我的维数是~20.起点和可用矢量将在应用程序的生命周期内得到修复,但我会找到许多不同目标点的路径.我想优化速度,而不是内存.算法失败(找不到dest的可能路径)是可以接受的.

更新w/Accepted Solution

我采用的解决方案非常类似于下面标记为"已接受"的解决方案.我遍历所有点和向量,并构建一个包含所有可到达点的列表以及到达它们的路径.我将此列表转换为< dest,p + vectors > 的哈希值,为每个目标点选择最短的向量集.(对于散列大小也有一点优化,这在这里不相关.)后续的dest查找在恒定时间内发生.

我知道我的问题看起来很模糊,但我想不出更好的方式来表达它,所以我将首先解释我正在尝试做什么.

我目前正在开展一个项目,我已经获得了一张地图,我正在编写一个应该能够在地图上导航的"小动物"; 生物有各种其他功能,但那些与当前问题无关.整个程序和解决方案都是用C#编写的.

我可以控制生物的速度,并通过返回当前的X和Y位置来检索它在地图上的当前位置,我还可以在它与阻挡它的地形碰撞时设置它的方向.

我唯一的问题是我无法想到一种智能地在地图上导航的方法; 到目前为止,我一直把它放在小动物与地形碰撞时所面对的方向上,这绝不是在地图上移动的好方法!

我不是游戏程序员,这是一个软件任务,所以我对AI技术没有任何线索.

这里是地图和小动物图像的链接:

地图和小动物图像

我绝不在寻找任何人给我一个完整的解决方案,只是推动地图导航的大方向.

我正在尝试实现D*-Lite寻路算法,如Koenig和Likhachev在2002年的文章中描述的Boost :: Graph.我认为我已经掌握了它背后的基本思想和理论,但是在理解Pred和Succ更新集合时我遇到了问题.

我猜它是在这Move to sstart一步中发生的Main,但是第一次调用ComputeShortestPath会毫无意义吗？该Succ套装是否应该同时插入Pred？然后Pred,Succ可以实现为双链表？

我在下面插入了算法的伪代码.这些Pred和Succ集合分别是前辈和后继者.g,h,rhs并c有不同的成本和重量.U是要访问的顶点的优先级队列.

procedure CalculateKey(s)
{01’} return [min(g(s), rhs(s)) + h(sstart, s) + km; min(g(s), rhs(s))];

procedure Initialize()
{02’} U = ?;
{03’} km = 0;
{04’} for all s ? S rhs(s) = g(s) = ?;
{05’} rhs(sgoal) = 0;
{06’} …

我在Java中实现了一个基于A*pathfindinder的基本网格.我想制作一个基于导航网格/多边形的探路者,但我遇到的问题是:

如果我找到橙色路线,那么我可以使用类似漏斗算法的东西来拉直它以获得所需的路线(蓝色).但是,如果程序计算每条路线的成本,红色和橙色,那么它会说红色路线的价格更便宜.如何编程我的A*算法和/或创建我的网格,以便不会发生这种情况.

我需要一个算法,它会给我一条从起始节点到结束节点的路径,但路径必须有一个确切数量的节点,否则路径查找应该失败.

为了扩展,我有一个瓷砖网格.移动只能是紧邻的上,下,左或右平铺(意思是没有对角线移动).瓦片在路径中可以使用和不可以使用的规则有很多,但大多数情况下可以归结为简单的布尔来判断瓦片是否可以使用(这可以在开始算法之前计算出来)但是,给我带来麻烦的是,我有一条路径必须具有的距离,这意味着,从一个瓷砖到相邻瓷砖的每一次移动都是一个距离,整个路径应该有一个指定的距离,不多也不少.此外,一旦瓷砖被踩到(但算法开始时所有瓷砖都可用),它不能再次踩到,有点像玩老蛇游戏你我要注意不要吃自己.

我看过Dijkstra/A*并且我用google搜索算法进行寻路,但据我所知,所有这些算法都集中在最短的路径上,这对我没什么好处.只要遵循上述规则,我不关心它是哪条路径.

我错过了什么,这样的算法和算法是否已经存在,或者是否有一种简单的方法来修改Dijkstra/A*来给出这个结果？由于我不是母语为英语的人,我可能使用了错误的术语,所以我欢迎这种算法的关键字建议.

这里是我的意思,当我说它必须是和确切的距离,并不能使用相同的瓷砖两次.

假设距离必须为7.现在让我们用O标记可以在路径中使用的图块,不能使用的图块和X,S的起点和E的目标.

X X X X X X X
X O O E S O O
X O O O O O O

如果没有距离限制,可以向左走,问题就解决了.如果有距离限制,但没有"不能踩到相同的瓷砖"限制,可以下降一次,然后向左,然后向右,然后向左,然后向右,然后向左,然后向上并到达目标.由于存在这两种限制,因此需要向右,向下,向左,向左,向上,向右然后才能到达目标.但是,如果情况是这样的话,就没有有效的路径.

X X X X X X X
X O O E S O O
X X O O O X O

如果它是相关的,我正在用C#开发这个棋盘游戏.

至于最大距离,这是距离所在的范围.玩家将掷骰子并获得数字1-6.如果玩家获得6,他会再次投掷骰子,如果他再次获得6,则一次又一次直到他没有得到6.距离是结果数加上玩家拾取的物品数量,理论上可以最多8,但通常是0-3,maaaybe 4.

另一方面,我刚收到新订单,游戏规则改为允许在相同的路径上两次踩到同一个位置,我相信这个过程很简单,但是我会把这个问题保留为我认为它有很好的答案,可以帮助那些情况下的人.

情况: 我正在尝试将A*算法转换为c ++代码,其中不允许对角线移动,但我有一些奇怪的行为.

我的问题:即使没有对角线移动,也需要考虑对角线成本.当我在没有对角线成本的情况下进行计算时(使用'启发式'因子10),我总是有相同的fscore为80(你可以在我计算fscore,gscore和hscore的第二张图片中看到这一点)这看起来很奇怪我.因此(几乎所有节点都具有80的fscore),algorimth似乎不起作用,因为许多节点具有相同的最小fscore为80.

或者这是正常行为,并且没有对角线的A*星实现必须执行更多工作(因为更多节点具有相同的最小fscore)？

我不认为这个问题与我的代码有什么关系,而不是我的推理,但我仍然发布它:

pathFind.cpp

#include "pathFind.h"
#include <queue>
#include "node.h"
#include <QString>
#include <QDebug>
#include <iostream>

/** Pathfinding (A* algo) using Manhatten heuristics and assuming a monotonic, consistent
*   heuristic (the enemies do not change position)
*
*   TODO: add variable terrain cost
**/

//dimensions
const int horizontalSize = 20;
const int verticalSize = 20;

//nodes sets
static int closedNodes[horizontalSize][verticalSize]; //the set of nodes already evaluated
static int openNodes[horizontalSize][verticalSize]; // the set of nodes to …

我正在使用Lua进行游戏,我需要使用广度优先搜索来实现快速路径搜索算法,该算法找到敌人AI和玩家之间的最短路径.

我将同时使用此算法最多3个敌人,并且地图是基于2维拼图的迷宫.我已经实现了碰撞检测,所以现在剩下要做的就是让敌人以一种可以快速完成并且最好每个敌人每秒约80-90次的方式找到玩家的最短路径.

当我之前实现广度优先搜索时,我在C++中使用了一个队列.从我读到的关于Lua的内容来看,使用表的堆栈实现非常有效,因为在push()(AKA table.insert)和pop()(table.remove)操作之后不需要移动元素.但是,我认为在Lua中大型队列的效率非常低,因为如果要在表的索引1中插入/删除某些内容,则表中的所有其他元素必须向上或向下移动.

因此,我想问一些Lua经验丰富的简单问题.在这种语言中,最简单和/或最快的队列实现是什么？是否有可能在Lua中拥有一个快速队列,或者只是普遍接受Lua总是被迫"移位"所有元素以进行队列操作,例如pop()或append()？

编辑:据我所知,Lua表中"移位元素"的底层实现是用C语言编写的,因此非常优化.在开始编写简单的表实现之前,我只想知道是否有更好的队列选项.

我有一个带有起始节点S和结束节点E的图G.这个图的特殊之处在于,不是边缘有成本,而是具有成本的节点.我想找到S和E之间的方式(一组节点,W),以便最小化(W).(实际上,我对W不感兴趣,只是max(W))等价,如果我删除成本大于k的所有节点,那么最小的k是什么,以便S和E仍然连接？

我有一个想法,但想知道它是否正确和最佳.这是我目前的伪代码:

L := Priority Queue of nodes (minimum on top)
L.add(S, S.weight)

while (!L.empty) {
    X = L.poll()
    return X.weight if (X == G)
    mark X visited
    foreach (unvisited neighbour N of X, N not in L) {
        N.weight = max(N.weight, X.weight)
        L.add(N, N.weight)
    }
}

我认为最坏的情况是O(n log n),其中n是节点数.

以下是我的具体问题(渗透)的一些细节,但我也对这个问题的算法感兴趣.节点权重在0和给定的最大值之间随机均匀分布.我的节点是在R²平面上的泊松分布,如果两个节点之间的距离小于给定的常数,则存在两个节点之间的边.可能有很多节点,因此它们是动态生成的(隐藏在伪代码中的foreach中).我的起始节点在(0,0)中,结束节点是距离(0,0)大于R的距离上的任何节点.

编辑:节点上的权重是浮点数.

使用CGAL lib,我正在尝试实现最短路径方法.

我已经取得了一定的成功,但是映射路径所需的时间几乎不可接受,在Release中运行最多需要1.5秒.

我知道输入可能非常大,有50000个面孔,但这是我必须要处理的.

更详细地说明我正在尝试做的是能够通过单击两个不同的位置并沿着网格的表面绘制样条曲线,并从它们生成路径,就像在图像中一样:

我的类型定义是:

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Surface_mesh<Kernel::Point_3> Triangle_mesh;
typedef CGAL::Surface_mesh_shortest_path_traits<Kernel, Triangle_mesh> Traits;
// default property maps
typedef boost::property_map<Triangle_mesh,
    boost::vertex_external_index_t>::type  Vertex_index_map;
typedef boost::property_map<Triangle_mesh,
    CGAL::halfedge_external_index_t>::type Halfedge_index_map;
typedef boost::property_map<Triangle_mesh,
    CGAL::face_external_index_t>::type     Face_index_map;
typedef CGAL::Surface_mesh_shortest_path<Traits> Surface_mesh_shortest_path;
typedef boost::graph_traits<Triangle_mesh> Graph_traits;
typedef Graph_traits::vertex_iterator vertex_iterator;
typedef Graph_traits::halfedge_iterator halfedge_iterator;
typedef Graph_traits::face_iterator face_iterator;

我的代码如下所示:

Traits::Barycentric_coordinates src_face_location = { { p1.barycentric[2], p1.barycentric[0], p1.barycentric[1] } };
face_iterator src_face_it = faces(map->m_cgal_mesh).first;
std::advance(src_face_it, src_faceIndex);

map->m_shortest_paths->remove_all_source_points();
map->m_shortest_paths->add_source_point(*src_face_it, src_face_location);

Traits::Barycentric_coordinates dest_face_location = { { p2.barycentric[2], …

我需要优化带有由贝塞尔线构造的填充形状的矢量图像。输入图像以及形状分离后的外观：

我想通过删除不必要的线条并依靠形状堆叠来保留外观来优化图像，但顶点要少得多。结果形状应如下所示：

这个问题可能可以分解为单独的步骤：

1. 检测堆叠线。这或多或少是简单的：计算沿线的点，沿它们找到顶点。如果顶点堆叠起来，它就变得微不足道了。

2. 寻找穿过其他形状的填充区域的贝塞尔路径。可能已经存在这样的算法，但我不知道。（我在这里真的需要帮助。）而且还不清楚要采用什么形状。也许我应该解决所有的可能性并进行比较。一旦我了解了它，它可能会变得更清楚。（欢迎提供提示/建议。）

3. 找到最佳的堆叠顺序以使顶点数量最少。对于像我这样不太热衷于算法的人来说，这听起来很痛苦，但这似乎是通过不同“路径”的顶点数量的某种最小化，所以可以做到。（如我错了请纠正我。）

4. 如果一个形状中有一个洞，这可能意味着里面的所有东西都会堆叠在它的上面，所以这是一个单独的简单情况，不需要额外的计算。

总的来说，第二点似乎是最有（唯一？）问题的，所以我需要在正确的方向上推动。

就示例图像而言，如何找到绿色形状的潜在遮挡部分穿过蓝色形状（以及可选的黄色形状）的贝塞尔路径，反之亦然，让蓝色形状穿过绿色形状？我不需要路径是最短的，我需要它的顶点最少。

本质上，我需要找到这些具有最少顶点数的路径。请随意忽略其余内容，将其视为不相关的上下文。