公告

联系我:我的126邮箱: billhsu。 Locations of visitors to this page
<2022年12月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

统计

  • 随笔 - 41
  • 文章 - 0
  • 评论 - 82
  • 引用 - 0

常用链接

留言簿(16)

随笔分类

随笔档案

相册

Game Dev

搜索

  •  

最新评论

阅读排行榜

评论排行榜

寻路算法整理
整理自《Programming Game AI by example》

1.DFS
优先深入每个图,直到找到目标节点
往往可以找到到达路线,可往往不是最优的。
09-1-23-DFS.JPG


2.BFS
广度优先地寻找目标节点。
往往可以找到最优路径,但耗时多。
09-1-23-BFS.JPG


3.Dijkstra
使用了动态规划(原文中称为“边放松”)//该为贪心,本人罪过
速度较快
09-1-23-Dijkstra.JPG


4.A*
与Dijkstra相似,使用启发因子(F=G+H),速度是以上算法里最快的。
可以看看:
http://hi.baidu.com/probill/blog/item/80d71f1b19e2fe1e8718bfe5.html
09-1-23-Astar.JPG

5.创建导航图
09-1-23-Nav.JPG

posted on 2009-01-23 17:22 Bill Hsu 阅读(5535) 评论(3)  编辑 收藏 引用 所属分类: Game DevAlgorithm

评论

# re: 寻路算法整理 2009-01-23 19:20 winsty

dijkstra并不是动态规划
是基于贪心的算法
  回复  更多评论    

# re: 寻路算法整理 2009-01-24 13:49 imnobody

算法实现代码发一下?
  回复  更多评论    

# re: 寻路算法整理 2009-01-26 20:35 mango-young

导航系统? 已经gis 了?
  回复  更多评论    

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理