图的表示
学习算法的首要任务是理解数据。什么是输入？什么是输出？
- 输入
- 输出
- 权衡
对于游戏地图有很多种图的表示方法
图的属性
- 基于图的寻径算法需要知道当前的位置，以及位置之间的相互连接关系。
事实上算法并不知道这些，它只知道位置之间的连接关系。 - 图的布局并不是图的一部分
- 路径搜索算法并不知道网格图的布局和属性，它只知道网格之间的连接关系。
算法
关键思想: 跟踪一个被称为边界的扩展环
- 广度优先搜索
平等的探索所有可能的路径 - Dijstra算法
优先向低成本路径探索，需要跟踪移动的成本（move cost）
根据移动成本去选择下一个位置 - A算法
A是对Dijkstra算法的修改，针对单个目标进行优化
参考
A*算法介绍：https://www.redblobgames.com/pathfinding/a-star/introduction.html
