标签: path-finding

我正在寻找一种算法用于我正在制作的赛车游戏.地图/关卡/轨道是随机生成的,所以我需要找到两个位置,即开始和目标,它们利用了大部分地图.

• 该算法是在二维空间内工作
• 从每个点,只能遍历四个方向的下一个点; 上下左右
• 点数既可以是阻止的也可以是非阻塞的,只能遍历非阻塞点

关于距离的计算,它不应该是缺乏更好词的"鸟道".如果它们之间存在墙(或其他阻挡区域),则A和B之间的路径应该更长.

我不确定从哪里开始,非常欢迎评论,并且建议的解决方案在伪代码中是首选.

编辑:对.在查看了gs的代码后,我又给了它一个镜头.我这次用C++写的,而不是python.但是,即使在阅读了Dijkstras算法,洪水填充和Hosam Alys解决方案后,我也没有发现任何重要的区别.我的代码仍然有效,但没有你想要运行的那么快.完整的消息来源是牧场.唯一有趣的线(我猜)是第78-118行的Dijkstra变体.

但速度不是这里的主要问题.如果有人能够指出算法中的差异,我真的很感激帮助.

• 在Hosam Alys算法中,他是从边界而不是每个节点扫描的唯一区别吗？
• 在Dijkstras你跟踪和覆盖走的距离,但不是在洪水填充,但这就是它？

通常认为A*是解决寻路问题的最佳算法.

当A*不是找到解决方案的最佳算法时,是否存在任何情况？

与BFS,DFS,UCS等相比,A*有多好？

我遇到了这个非常有趣的问题,我们有一个4x4的迷宫和一个机器人试图进入目标.问题是,您必须找到一系列预定义命令,这些命令将始终导致机器人到达目标.

假设我们有一个像这样的迷宫:

x . . .
. # # .
. # # .
. . . g

这种特殊的迷宫可以用例如命令序列来解决,DDDRRR或者RRRDDD,其中R =右,L =左,U =上,D =下(duh).

然而,这些序列都不会解决这个迷宫:

x . # .
. . . .
# . . .
. . . g

机器人总是从左上角开始,目标总是在右下方,迷宫始终是2D 4x4矩阵.

我已经实现了一个算法,让我获得了78个命令的获胜序列.我确信至少存在29个命令的解决方案(其他人完成了这个).

这个问题实际上已经有几年了,所以我丢失了当时使用的算法,但基本的想法是在我生成的所有迷宫中搜索,并始终选择导致解决最多的路线迷宫.这实际上让我得到了一个略长于78的序列; 我手动减少了一些命令,我​​发现这些命令是多余的.

是的,暴力迫使需要几年的时间.

如果我的记忆服务,可能的迷宫少于4000(可能的迷宫是左上角和右下角之间的路径存在).

哦!机器人在执行命令期间至少一次访问目标就足够了.也就是说,在最后一个命令之后,它不必坐在目标上.

我有没有抓住任何人的兴趣？我应该如何处理这个问题以获得更有效的答案？谢谢你考虑:)

好玩的东西:Pastebin

这是一个(非常)匆忙拼凑的Java片段.它应该编译运行:)程序有点同时播放~4000个迷宫.程序对UP,LEFT,DOWN和RIGHT进行输入(w,a,s,d),然后模拟移动,显示一些统计数据.如果你尝试的话,你可以在屏幕上看到的是每个位置的每个迷宫中的障碍物总量,以及每个迷宫的当前位置总量.这很难解释:)问我是否有问题.

再说一遍......不要介意可怕的代码.它是在20分钟内写成的

进展

我从这个用户的答案中间接得到了这个想法(之后由于某种原因被删除),并在聊天中进一步用Mooing Duck建模.我们的想法是找到一个解决迷宫右侧的序列.也就是说,解决所有迷宫中至少一半的解决方案,并且从一开始就镜像并再次运行解决剩余的迷宫.

插图:

首先找到一个序列,其第一个命令是RIGHT,它解决了这个迷宫:

0 1 0 0
0 1 0 …

我有一个公共汽车/火车/ ...站的数据库和每个日期的到达/离开时间等等.我正在寻找一种方法来搜索两个位置之间的最快(最短/最便宜/最少过渡)之旅.我希望将来有任意位置,使用OpenStreetMap数据在停靠点之间以及从停止点到开始/结束之间行走,但是暂时我只想在数据库中的两个停靠点之间找到路径.

问题是我似乎无法找到关于这个主题的更多信息,例如这个维基百科页面有很多文本,其中绝对没有有用的信息.

我发现的是Google Transit中使用的GTFS格式.虽然我的城市没有提供公共数据源(甚至不是私人数据源),但我已经掌握了GTFS包含的所有重要信息,并且进行转换将是微不足道的.

有一些基于GTFS的软件,比如OpenTripPlanner,它也可以使用OpenStreetMap进行行人/汽车/自行车路由.

但是,路由代码没有很好地记录(至少从我发现的那个),我不需要整个事情.

我正在寻找的是对我可以使用的算法,它们的性能,可能是一些伪代码的一些很好的概述.

所以,问题是,给定一个停靠点,路线和到达/离开/出行时间列表,如何轻松找到从A站到B站的最快路径？

我有一个应用程序,我需要在屏幕上随机移动一些对象,他们不能互相撞击.我正在寻找一种算法,它允许我生成不会产生冲突的路径并且可以无限期地继续(即:对象一直移动直到用户驱动的事件将它们从程序中移除).

我不是游戏程序员,但我认为这看起来像AI问题,你们可能会闭着眼睛解决它.从我读过的内容来看,A*似乎是推荐的'基本理念',但我真的不想在没有确认的情况下投入大量时间.

任何人都可以对方法有所了解吗？反重力运动可能吗？

1. 如果这很重要,这将在iOS上实现
2. 需要在每个路径的末尾生成新路径
3. 没有可见的'网格'.2D空间中的运动完全免费
4. 物体是在屏幕上走动直到它们被杀死的昆虫

我正在用曼哈顿距离实现一个星型算法来解决8-puzzle(在C中).它似乎工作得非常好并且通过了大量的单元测试,但是在一个案例中找不到最短路径(它找到了27个步骤而不是25个步骤).

当我将启发式函数更改为汉明距离时,它会找到25个步骤.当我使曼哈顿距离函数返回实际成本的一半时,还可以找到25个步骤.

这就是为什么我认为这个问题存在于曼哈顿距离函数的某个地方,并且它过度估算成本(因此不可接受).我想在C程序中可能还有别的东西出错了,所以我写了一个小的Python脚本来测试和验证曼哈顿距离函数的输出,它们都产生完全相同的结果.

我真的很困惑,因为启发式函数似乎是唯一的失败点,它似乎同时是正确的.

你可以试试这个求解器,然后像"2,6,1,0,7,8,3,5,4"这样选择格式顺序.选择算法曼哈顿距离,它可以找到25步.现在将其更改为曼哈顿距离+线性冲突,它会找到27个步骤.

但我的曼哈顿距离(没有线性冲突)分为27步.

这是我的一般算法:

manhattan_distance = 0
iterate over all tiles
if the tile is not the blank tile:
find the coordinates of this tile on the goal board
manhattan_distance += abs(x - goal_x) + abs(y - goal_y)

我认为如果某些重要部分出现了严重错误,那么它将无法通过所有25个以上的测试,因此这可能是某种边缘情况.

这里评论C中的曼哈顿距离函数:

int ManhattanDistance(Puzzle p, State b){
   State goal = getFinalState(p);
   int size = getSize(b);
   int distance = 0;
   if (getSize(goal) == size){ // both …

我正在开发一个连接物体和电线的软件.该布线具有这样的规则:这些线不能通过其他物体并且不接受对角线移动.

我所知道的所有最短路径算法(A*,dijkstra等)都找到了这种类型的路径:

我不希望在第二个屏幕截图中出现不必要的曲折.我如何实现这一目标？

注意:任何想要尝试算法的人都可以使用此应用程序.

另一个注意:这是我不想要的确切情况.它找到了之字形路径,而不是"向右移动,直到你到达目标的x位置,向上移动直到你到达目标的y位置",这与Z字形的成本相同.

我有一个DAG(每边的成本/权重),并希望找到两组节点之间的最长路径.与图中的节点总数相比,两组起始节点和目标节点是不相交的并且尺寸较小.

我知道如何在一个开始节点和目标节点之间有效地执行此操作.使用多个,我可以列出从每个开始到每个目标节点的所有路径并选择最长的路径 - 但这需要二次数的单路径搜索.有没有更好的办法？

除了A*,BFS,DFS等之外,Pacman中常用的其他优秀路径寻找算法/启发式算法是什么？我不认为我提到的那些将会起作用,如果有多个水果供pacman找到.

我需要一些好的寻路算法,PacMan可以用它来尽可能少地完成迷宫.我试图寻找指南,但到目前为止还没有运气.到处都提到了与曼哈顿距离的A*,但它只适用于只有一个(或两个？或者可能多达几个？)果实的迷宫.

顺便说一句,为了保持简单,假设周围没有鬼魂.

原始PacMan问题的一些例子: 第一,第二和第三

我正在创建一个10,000到10,000张地图的游戏.
我希望用户能够设置位置并让计算机立即找到最佳路径.
然而,由于地图是10,000乘10,000,有100,000,000个节点,并且通过诸如A*或Dijkstra之类的传统方法找到该路径将需要大量存储器并且需要很长时间.
所以我的问题是:我怎样才能找到最好的路径？
我正在考虑的算法将世界划分为100个部分,每个部分有1,000,000个节点.然后将每个部分分成100个小节.这将重复进行,直到每个子部分包含100个节点.然后,算法将找到段的最佳路径,然后是子段,然后是子子段,直到找到最佳节点集.这会有效吗？还有更好的方法吗？
我也在考虑跳点搜索,但我不知道,只是发现它无法做到这一点并不痛苦.

编辑:我试图添加A*.但是,运行大约需要5秒钟,比理想时间长约4秒.