游戏开发论坛

 找回密码
 立即注册
搜索
查看: 5136|回复: 15

A*算出来的不是最优解???

[复制链接]

187

主题

6490

帖子

6491

积分

论坛元老

团长

Rank: 8Rank: 8

积分
6491
发表于 2007-1-8 15:07:00 | 显示全部楼层 |阅读模式
好像是这样的,感觉有些很近的路却又绕远的走了,但是最优解又是怎么计算呢??

谢谢解答。

[em14]

9

主题

688

帖子

688

积分

高级会员

Rank: 4

积分
688
发表于 2007-1-8 17:11:00 | 显示全部楼层

Re:A*算出来的不是最优解???

理论上可以证明,所选取的代价估计函数h(n)总是<=实际的代价值时,一定能找到最优解,否则则不一定。

22

主题

371

帖子

387

积分

中级会员

Rank: 3Rank: 3

积分
387
发表于 2007-1-8 19:20:00 | 显示全部楼层

Re:A*算出来的不是最优解???

取决于你的估价函数。A*的优点在于均衡了算法速度和寻路结果的关系,广泛运用于即时战略类的游戏。如果是求最短路径,例如战棋,那就不必用A*了,得用遍历法。

187

主题

6490

帖子

6491

积分

论坛元老

团长

Rank: 8Rank: 8

积分
6491
 楼主| 发表于 2007-1-9 11:25:00 | 显示全部楼层

Re:A*算出来的不是最优解???

我这里是些40*40左右的地图,速度方面问题不是太大吧??
遍历法的确有些麻烦,怎么遍历??穷举每一条路??

26

主题

537

帖子

537

积分

高级会员

Rank: 4

积分
537
发表于 2007-1-9 14:16:00 | 显示全部楼层

Re:A*算出来的不是最优解???

一直以为通路表方法是最优最快的(估计事实也如此),但是最近才发现它不能用于需要计算移动消耗的地图

9

主题

688

帖子

688

积分

高级会员

Rank: 4

积分
688
发表于 2007-1-9 16:34:00 | 显示全部楼层

Re:A*算出来的不是最优解???

通路表方法我还未听说过,楼上可以简单介绍一下吗?谢谢。

26

主题

537

帖子

537

积分

高级会员

Rank: 4

积分
537
发表于 2007-1-10 09:25:00 | 显示全部楼层

Re:A*算出来的不是最优解???

其实理论文章就在本站
http://dev.gameres.com/Program/Abstract/FindPathIdea.doc
文章只给了一种设想,实现起来需要改进该设想,但并不很难,记得以前讨论时有人说正在实现。
其核心理论是:如果A到B不能直达,那么必然要绕经一系列障碍物的顶点,于是这一系列顶点到顶点间的直线路径组合起来,就是A到B的最优路径。
实现起来更是高效,因为在地图生成时,所有固定障碍物顶点之间的可直达路径就被计算出来,并保存为一张通路表,游戏中寻路时只要算得A到最近的可直达顶点C的路径,和B到最近的可直达顶点D的路径,C到D间的最优路径则可从通路表中很容易算得,A到B的路径就这样快速组合出来。
前几天我也试了试,正当进展很令人满意时,忽然发现如果计算移动消耗,这种算法很可能得不到最优路径,原因也正在于该算法必须依赖顶点,真是成也萧何,败也萧何。

9

主题

688

帖子

688

积分

高级会员

Rank: 4

积分
688
发表于 2007-1-10 13:33:00 | 显示全部楼层

Re:A*算出来的不是最优解???

多谢高手指教。想不到高新技术远在天边,近在眼前。

26

主题

537

帖子

537

积分

高级会员

Rank: 4

积分
537
发表于 2007-1-10 13:42:00 | 显示全部楼层

Re:A*算出来的不是最优解???

在游戏方面我只算业余新手。
本以为这种方法能够在多数地方取代A*,可惜难以解决移动消耗带来的优选问题,所以似乎只适合不计消耗的地图,但这也很有用武之地了。

9

主题

688

帖子

688

积分

高级会员

Rank: 4

积分
688
发表于 2007-1-10 22:33:00 | 显示全部楼层

Re:A*算出来的不是最优解???

关键是它只能处理静态的障碍物,对于会移动的障碍似乎无能为力。但对于开阔的大地图,确实是一种可以替代A*的算法。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作品发布|文章投稿|广告合作|关于本站|游戏开发论坛 ( 闽ICP备17032699号-3 )

GMT+8, 2026-1-26 08:06

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表