文档介绍：游戏编程中寻路算法的优化探讨
1背景
近年来，游戏产业的快速发展带动了游戏中人工智能（Artificial Intelligence, AI）的发展，越来越多的游戏采用人工智能技术提高游戏的可玩性。
一个在市场上畅销的成功的游戏，必须既要有华丽的画面视觉效果和悦耳的听觉感受，又要有高超逼真的人工智能控制系统。游戏开发者把AI应用在计算机或者游戏机的游戏中，就会使广大玩家感到他们所面对的由电脑AI系统控制的敌人（即NPC）跟现实中的敌人一样拥有人类智能，让玩家留下如临实境的体验。如果一个游戏的人工智能做得一团糟的话，那么绝大多数游戏玩家宁愿在网络上跟真人进行对战了，或者就转投向其他拥有更高智能的游戏去了，这将给游戏制作公司带来承重的打击甚至破产。
在电子游戏中，玩家操控主要角色，而其他角色的行为逻辑由人工智能操纵, 这些角色我们称之为NPC （Non-Player Character,非玩家控制角色）。大部分游戏在开发过程中都会遇到路径探索问题，快速、准确地计算出游戏角色从地图中的A点到达B点的一条路径，一直是游戏开发者追求的目标，同时也是游戏人工智能研究的一个重要方面。
一般游戏AI系统都是从搭建最基本的寻路系统开始,一步步修改和完善后而成的。本文重点阐述了游戏AI开发中最基本寻路算法及其优化。
2游戏编程中的简单寻路算法

考虑以下图1-1：
图1-1
该单位的初始位置（start）在地图的下方，想要到达地图的目标位置（goal）。如果物体所能侦测到的地方（粉色部分所示）并没有障碍，那么物体就会直接向上走到它的目标位置。但在距离顶端较近的位置时，物体侦测到了障碍，因而改变了方向。该物体将不得不行进一个“U”形的路径绕过障碍物（如红色路径所示）o通过对比可知，寻路系统能够通过搜索一个更大的范围（如蓝色区域所示），
并寻找一个更短的路线（如蓝色路径所示），使物体避免绕这条由凹陷障碍物造成的远路。
我们可以通过改进物体的移动算法解决上图所示的陷阱。即可以避免在地图上创建有凹陷的物体，或者标记整个凹陷物体的整个凸包为危险区域（即除非目标在该区域内，否则避免进入该区域），如下图1-2：
1
图1-2
寻路系统则会让路径的决定提前，而不是如上图一样，物体直到移动到最后一刻才发现问题所在。对于“改进物体移动算法”和“使用寻路系统规划路径”两种方式有以下的折中：规划路径一般来说更慢，但效果更好；改进移动算法则会快一些，但有时候会卡住。如果游戏地图经常改变，那么路径规划的方式可能没有较大意义。
A*寻路算法
将寻路问题简化在二维网格中。大部分在AI和算法领域的寻路算法都是针对作为数学结构的“图”本身，而并非针对这种网格化游戏地图。我们希望寻找一种能利用游戏地图自身特征的方法。其实有些在二维网格图中我们认为是常识的事情，一些在普通图上使用的寻路算法本身可能并没有考虑到。例如如果两个物体距离较远，那么可能从一个物体到另一个物体的移动的时间和路径会较长。对于方向来说，如果方向是朝东，那么最优路径的路径也应当是大体往东走，而不是向西去。在网格中还可以从对称中获取信息，即先向北再向西，大部分情况下和先向西再向北等价。这些额外的信息可以让寻路算法更加快速。
在