Hexo游戏人工智能编程 ---- 图的秘密生命 2014-11-06

要点

主要是讲了以下一个方面：

• 图的表示，邻接表，邻接矩阵
• 图的作用，导航图，依赖图，状态图
• 图的搜索，BSF，DFS，Dijkstra，A*

图的表示

书上的例子是用list<vector<EdgeType>>来表示一个图的边集，直接用vector<NodeType>来表示点集。

图的作用

导航图

说白了就是在一个图里面找一条最短路。（真是心酸，现在才知道，为毛要学最短路）

书里面举了神偷的一个例子：

一个秘密游戏的导航图的边所带的权值由角色在其发出的声响的大小决定。例如在地毯上移动的权值就较小，在木板上的权值就较大。
如果有这么一个导航图，那么就可以知道最安静的路线。

依赖图

书中讲了一个关于物品合成的例子：

如果发现一个敌人的步兵端着枪，这表示：

• 敌人有铸造厂和木材工厂
• 敌人一定开发了制造火药的技术
• 敌人一定正在生产木材和铁

根据依赖图，可以猜测敌人可能已经拥有了大炮或是正在制造大炮。
这时或许就可以生产一个刺客去攻击敌人的铁匠以达到削弱敌人的目的。

图的搜索

BFS，DFS就一个队列和栈咯。书中还讲到了IDDFS（迭代加深深度优先搜索），即规定DFS的深度从1到n。

在讲Dijkstra之前，书中提到了边松弛技术，Dijkstra在于SPT，A*算法还是F=G+H。

总结

看书看书看书！