整理自《Programming Game AI by example》
1.DFS
优先深入每个图,直到找到目标节点
往往可以找到到达路线,可往往不是最优的。
![09-1-23-DFS.JPG](/images/cppblog_com/billhsu/09-1-23-DFS.JPG)
2.BFS
广度优先地寻找目标节点。
往往可以找到最优路径,但耗时多。
![09-1-23-BFS.JPG](/images/cppblog_com/billhsu/09-1-23-BFS.JPG)
3.Dijkstra
使用了动态规划(原文中称为“边放松”)//该为贪心,本人罪过
速度较快
![09-1-23-Dijkstra.JPG](/images/cppblog_com/billhsu/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](/images/cppblog_com/billhsu/09-1-23-Astar.JPG)
5.创建导航图
![09-1-23-Nav.JPG](/images/cppblog_com/billhsu/09-1-23-Nav.JPG)