我要发帖 回复

管理员

735

主题

2万

积分

30

专家分

忠于职守杰出贡献鼓励

兴趣点(最多三项):

建模技术

私信
发表时间 : 2009-8-17 23:01:54 | 浏览 : 4267    评论 : 7
用A*算法寻路有个比较郁闷的问题,虽然每一步都可以选择到最优路径,但是并不是起点到终点的最优路径,特别是在有障碍物的时候,可以饶开障碍物,但也会走“冤枉路”。

我个人认为的解决方法:

1、确定障碍范围。障碍物所围成的凸多边形内的可走路径会成为“冤枉路”的陷阱。

2、障碍物所围成的凸多边形的众横向延伸范围应为低可走优先级。

下图中,橘红色的线是用A*算法做的,很明显,不是最优路径,绿色和紫色是两条最优路径,但是黑色如果都到当前的位置它应该怎么选择下一步呢?
bst.jpg
或则通过计算,如果在某路径下遇到不合理情况(代价+目标距离大于了前一步的代价+目标距离),那么退回到前一个岔口选择另一个路径,但是这样的计算会比较复杂,而且在路径长并且障碍多的时候效率会很低。

以下是在网上找到的一篇比较简要明了的文章

如果通过图像模拟搜索点,可以发现:非启发式的寻路算法实际上是一种穷举法,通过固定顺序依次搜索人物周围的路点,直到找到目的地,搜索点在图像上的表现为一个不断扩大的矩形。如下:

p.jpg
很快人们发现如此穷举导致搜索速度过慢,而且不是很符合逻辑,试想:如果要从(0,0)点到达(100,0)点,如果每次向东搜索时能够走通,那么干吗还要搜索其他方向呢?所以,出现了启发式的A*寻路算法,一般通过 已经走过的路程 + 到达目的地的直线距离 代价值作为搜索时的启发条件,每个点建立一个代价值,每次搜索时就从代价低的最先搜索,如下:

ax.jpg

综上所述,以上的搜索是一种矩阵式的不断逼近终点的搜索做法。优点是比较直观,缺点在于距离越远、搜索时间越长。

最近VR访客

美娜 评论于2010-6-25 12:33:26
        专业制作各类礼品笔,咨询电话13044161111 。网址www.fudinggift.cn 上海福定文具有限公司,专业的礼品笔公司。承接各类礼品笔订单。品牌包括:德国公爵笔,派克笔,毕加索笔,花花公子笔,德国万宝龙笔,鳄鱼笔,梦特娇笔,高丝笔等各类礼品笔品牌。可以制作激光,印刷,烫印等各种工艺,满足不同客户的需求。
联系电话: 13044161111 龚先生 qq:448206496 网址:
www.fudinggift.cn
邮箱:13044161111@163.com


       我们一直都很注重与其他公司的合作,因为长时间的合作能达到真正的双赢。同时公司的产品线的深度和宽度在不断延伸,希望能够适应给与我们的各种礼品笔订单,我们致力于更高,更远,更专业,更有价格优势方向发展。在我们付出努力的同时最终希望得到您的认可!!
jccjccjcc 评论于2011-4-8 16:39:26
{:2_63:}{:2_72:}{:2_74:}
奶罐 评论于2011-4-11 19:41:33
不错真好
xiaoyaoyou002 评论于2011-9-6 13:40:45
学习了,很不错
25669468 评论于2012-2-26 09:17:45
谢谢楼主分享
jialuhero专家组 评论于2012-5-17 15:35:11
不错,学习了
PcOYe 评论于2013-4-29 22:13:15
正在 学习 这个啊

手机版|VR开发网 ( 津ICP备18009691号 ) 统计 网安备12019202000257

GMT+8, 2020-9-30 01:07 PM

返回顶部