寻路算法整理(转)

寻路算法整理(转)

分类： 其它 2009-10-19 23:01 31人阅读 评论(0) 收藏 举报

整理自《Programming Game AI by example》

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



2.BFS
广度优先地寻找目标节点。
往往可以找到最优路径，但耗时多。



3.Dijkstra
使用了动态规划（原文中称为“边放松”）//该为贪心，本人罪过
速度较快



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


5.创建导航图

分享到：

上一篇：在SQLite中使用索引优化查询速度(转)