本文译自 Amit’s Game Programming Information，并作为后续文章的目录。

 

寻路，是我们在游戏开发经常面对的问题。

A. 寻路算法 得到的路径可以避开障碍物、躲避敌人，并最大限度地降低开销（燃料，时间，距离，设备，金钱等）。

B. 移动算法 解决了得到路径后移动相关的问题。

有时我们只需要考虑其中一种。

 

有两种极端情况，一种是，复杂的寻路算法 + 简单的移动算法。一开始即寻得一条路径，物体将沿着这条路径行进，而忽视其他一切。

另一种极端情况是指，无寻路算法 + 复杂的移动算法。物体不会搜索最佳路径，而默认是当前点到终点的直线。物体会考虑到当前点周围的局部环境进行移动，一步一次。

将寻路和移动算法综合使用可以获得最佳结果。

 

寻路

1. 简述寻路算法

　　a. 算法

　　b. Dijkstra 算法和最佳优先搜索

　　c.  A* 算法

2. 启发式

　　a. 启发式的 A* 算法

　　b. 速度 or 精确

　　c. 估值因素

　　d.确切的启发式

　　　　i. 预先计算的启发式算法

　　　　ii. 线性启发式

　　e. 网格地图的启发式算法

　　　　i. 曼哈顿距离

　　　　ii. 对角线距离

　　　　iii. 欧式距离

　　　　iv. 欧式距离的平方

　　　　v. 多个目标

　　　　vi. 解决平局

　　f. 近似启发式

3. 实现

　　a. 草图

　　　　i. 连通性

　　b. 性能表现

　　c. 源代码和 Demo

　　　　i. Demos

　　　　ii. 代码

　　d. 设置表现

　　　　i. 未排序的数组或链表

　　　　ii. 排序数组

　　　　iii. 排序链表

　　　　iv. 二叉堆

　　　　v. 排序的跳过列表

　　　　vi. 索引数组

　　　　vii. 哈希表

　　　　viii. 播放数目

　　　　ix. 桶队列

　　　　x. 热门队列

　　　　xi. 配对堆

　　　　xii. 软堆

　　　　xiii.序列堆

　　　　xiv. 数据结构比较

　　　　xv. 混合表示

　　e. 与游戏循环的互动

　　　　i. 提前退出

　　　　ii. 可中断算法

　　　　iii. 集体运动

　　　　iv. 精致

4. A* 变种

　　a. 束搜索

　　b. 迭代加深搜索

　　c. 动态加权

　　d. 带宽搜索

　　e. 双向搜索

　　f. 动态 A* 和终身规划 A*

　　g. 跳点搜索

　　h. Theta*

 5. 处理移动障碍物

　　a. 重新计算路径

　　b. 路径拼接

　　c. 观看地图更改

　　d. 预测障碍物运动

6. 预先计算的路径使用的空间

　　a.地点与方向

　　b. 路径压缩

　　　　i. 位置存储

　　　　ii.方向存储

　　c. 计算航路点

　　d. 路径长度有限

　　e. 摘要

版权声明：本文为xuuold原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/xuuold/p/10022960.html