寻路算法：找到NPC最好的行走路径
寻路就是一个看似简单问题的解：给定点A 和B，AI 该怎么智能地在游戏世界中行走？这个问题的复杂来自于实际上A 和B 之间存在大量的路径可走，但只有一条是最佳的。只是找到一条两点之间的有效路径是不够的。理想的寻路算法需要查找所有可能的情况，然后比较出最好的路径。
本文将从搜索空间，可接受的启发式算法、贪婪最佳优先算法进行探讨。
搜索空间的表示
最简单的寻路算法设计就是将图作为数据结构。一个图包含了多个节点，连接任意邻近的点组成边。在内存中表示图有很多种方法，但是最简单的是邻接表。在这种表示中，每个节点包含了一系列指向任意邻近节点的指针。图中的完整节点集合可以存储在标准的数据结构容器里。下图演示了简单的图的可视化形象和数据表示。
这意味着在游戏中实现寻路的第一步是如何将游戏世界用图来表示。这里有多种方法。一种简单的方法就是将世界分区为一个个正方形的格子（或者六边形）。在这种情况下，邻近节点就是格子中邻近的正方形。这个方法在回合制策略游戏中很流行，比如《文明》或者XCOM。
但是，对于实时动作游戏，NPC 通常不是在网格上一个正方形一个正方形地走。由此，在主流游戏中要么使用路点要么使用导航网格。上面两种方法，都可以手工在场景编辑器中构造数据。
但是手工输入数据不仅烦琐而且容易出错，所以大多数引擎都会让这个过程自动化。自动生成数据的算法超出了本书的范围，但是更多的信息可以在本书的参考资料中找到。
寻路节点最早在第一人称射击游戏（FPS）中使用，由id Software 在20 世纪90 年代早期推出。通过这种表示方法，关卡设计师可以在游戏世界中摆放那些AI 可以到达的位置。这些路点直接被解释为图中的节点。而边则可以自动生成。比如让设计师手动将节点组合在一起，可以自动处理判断两个点之间是否有障碍。如果没有障碍，那么边就会在两点之间生成。
路点的主要缺点是AI 只能在节点和边缘的位置移动。这是因为即使路点组成三角形，也不能保证三角形内部就是可以行走的。通常会有很多不能走的区域，所以寻路算法需要认为不在节点和边缘上的区域都是不可走的。
实际上，当部署路点之后，游戏世界中就会要么有很多不可到达的区域要么有很多路点。前者是不希望出现的状况，因为这样会让AI 的行为显得不可信而且不自然。而后者缺乏效率。越多的节点就会有越多的边缘，寻路算法花费的时间就会越长。通过路点，在性能和精确度上需要折中。
一个可选的解决方案就是使用导航网格。在这种方法中，图上的节点实际上就是凸多边形。邻近节点就是简单的任意邻近的凸多边形。这意味着整个游戏世界区域可以通过很少数量的凸多边形表示，结果就是图上的节点特别少。下图所示的是用游戏中同一个房间同时表示为路点和导航网格的结果比较。
通过导航网格，在凸多边形内部的任意位置都认为是可走的。这意味着AI 有了大量的空间可以行走，因此寻路可返回更自然的路径。
导航网格还有其他一些优点。假设游戏中有牛和小鸡在农场中行走。由于小鸡比牛小很多，因此有一些区域只有小鸡可到达，而牛却不行。如果这个游戏使用路点，它通常需要两份图：每份图对应一种生物。这样，牛只能在自己相应的路点行走。与之相反，由于导航网格中每个节点都是凸多边形，计算牛能否进入不会花太多时间。因此，我们可以只用一份导航网格，并且计算哪些地方牛可以到达。
还有一点就是导航网格完全可以自动生成，这也是今天为什么使用路点的游戏越来越少的原因。比如说，多年来虚幻引擎使用路点作为寻路空间的表示。其中一款使用路点的虚幻引擎的游戏就是《战争机器》。而且，最近几年的虚幻引擎已经使用导航网格替代路点。在后来的《战争机器》系列，比如《战争机器3》就使用的是导航网格，这个转变引起工业上大量转用导航网格。
话虽这么说，但是寻路空间的表示并不完全会影响寻路算法的实现。在本节中的后续例子中，我们会使用正方形格子来简化问题。但是寻路算法仍不关心数据是表示为正方形格子、路点，或是导航网格。
可接受的启发式算法
所有寻路算法都需要一种方法以数学的方式估算某个节点是否应该被选择。大多数游戏都会使用启发式，以h(x) 表示，就是估算从某个位置到目标位置的开销。理想情况下，启发式结果越接近真实越好。如果它的估算总是保证小于等于真实开销，那么这个启发式是可接受的。如果启发式高估了实际的开销，这个寻路算法就会有一定概率无法发现最佳路径。对于正方形格子，有两种方式计算启发式。
曼哈顿距离是一种在大都市估算城市距离的方法。某个建筑可以有5 个街区远，但不必真的有一条路长度刚好为5 个街区。
曼哈顿距离认为不能沿对角线方向移动，因此也只有这种情况下才能使用启发式。如果对角线移动是被允许的，则曼哈顿距离会经常高估真实开销。
在2D 格子中，曼哈顿距离的计算如下：
第二种计算启发式的方法就是欧几里得距离。这种启发式的计算使用标准距离公式然后估算直线路径。不像曼哈顿距离，欧几里得距离可以用在其他寻路表示中计算启发式，比如路点或者导航网格。在我们的2D 格子中，欧几里得距离为：
贪婪最佳优先算法
在有了启发式之后，可以开始实现一个相对简单的算法：贪婪最佳优先算法。一个算法如果没有做任何长期计划而且只是马上选择最佳答案的话，则可以被认为是贪婪算法。在贪婪最佳优先算法的每一步，算法会先看所有邻近节点，然后选择最低开销的启发式。
虽然这样看起来理由充足，但是最佳优先算法通常得到的都是次优的路径。看看下图中的表示。绿色正方形是开始节点，红色正方形是结束节点，灰色正方形是不可穿越的。箭头表示贪婪最佳优先算法的路径。
路径上存在不必要的向右移动，这是因为这在当时就是最佳的访问节点。一个理想的路径应该是一开始就往下走，但是这要求一定程度的计划，这是贪婪算法所不具备的。大多数游戏都需要比贪婪最佳优先算法所能提供的更好的寻路。但是本章后续的寻路算法都基于贪婪最佳优先算法，所以先理解贪婪算法才能往下继续，先看看如何实现这个贪婪算法。
首先，先看看我们每个节点所需要存储的数据。为了能够将这些数据构造成图，需要有额外的邻近信息。对于这个算法，我们只要一些额外的数据：
struct Node
Node parent
那个parent 成员变量用于跟踪哪个节点是当前访问的。注意到像C++ 那样的语言，parent可能是个指针，而在其他语言中（比如C#），类可能天然地以引用传递。parent 成员的价值在于构造链表，能够从终点回到起点。当算法完成的时候，parent 链表就可以通过遍历得到最终路径。
浮点数h 存储了某个节点的h(x) 的值，这个值导致在选择节点的时候会偏向于h 值最小的节点。
算法的下一个组件就是用于临时存储节点的容器：开放集合和封闭集合。开放集合存储了所有目前需要考虑的节点。由于找到最低h(x) 值开销节点的操作是很常见的，所以对于开放集合可以采用某种类似于二叉堆或者优先级队列的容器。
而封闭集合则包含了所有已经被算法估值的节点。一旦节点在封闭集合中，算法不再对其进行考虑。由于经常会检查一个节点是否存在于封闭集合里，故会使用搜索的时间复杂度优于o(n) 的数据结构，比如二叉搜索树。
现在我们就有了贪婪最佳优先算法所需要的组件。假设有开始节点和结束节点，而且我们需要计算两点之间的路径。算法的主要部分在循环中处理，但是，在进入循环之前，我们需要先初始化一些数据：
currentNode = startNode
add currentNode to closedSet
当前节点只是跟踪哪个邻居节点是下一个估值的节点。在算法开始的时候，我们除了开始节点没有任何节点，所以需要先对开始节点的邻居进行估值。
在主循环里，我们首先要做的事情就是查看所有与当前节点相邻的节点，而且把一部分加到开放集合里：
foreach Node n adjacent to currentNode
if closedSet contains n
n.parent = currentNode
if openSet does not contain n
compute n.h
add n to openSet
loop // 结束循环
注意任意已经在封闭集合里的节点都会被忽略。在封闭集合里的节点都在之前进行了估值，所以不需要再进一步估值了。对于其他相邻节点，这个算法会把parent 设置为当前节点。然后，如果节点不在开放集合中，我们计算h(x) 的值并且把节点加入开放集合。
在邻近节点处理完之后，我们再看看开放集合。如果开放集合中再也没有节点存在，意味着我们把所有节点都估算过了，这就会导致寻路失败。实际上也不能保证总有路径可走，所以算法必须考虑这种情况：
if openSet is empty
break // 退出主循环
但是，如果开放集合中还有节点，我们就可以继续。接下来要做的事情就是在开放集合中找到最低h(x) 值开销节点，然后移到封闭集合中。在新一轮迭代中，我们依旧将其设为当前节点。
currentNode = Node with lowest h in openSet
remove currentNode from openSet
add currentNode to closedSet
这也是为什么有一种合适的容器能让开放集合变得简单。比起做o(n) 复杂度的搜索，二叉堆能够以o(1) 时间找到最低h(x) 值节点。
最后，我们要有循环退出的情况。在找到有效路径之后，当前节点等于终点，这样就能够退出循环了。
until currentNode == endNode //end main do...until loop
如果在成功的情况下退出do...until 循环，我们会得到一条链表通过parent 从终点指向起点。由于我们想要得到从起点到终点的路径，所以必须将其反转。有很多种方法反转链表，最简单的方法就是使用栈。
下图显示了贪婪最佳优先算法作用在示例数据集的开始两次迭代。在(a) 中，起点加入封闭集合，而邻接节点则加入开放集合。每个邻接节点（蓝色）都有用曼哈顿距离算出来的自己到达终点的h(x) 开销。箭头表示子节点指向父节点。这个算法的下一步就是选择最低h(x) 值节点，在这里会选择h = 3 的节点。然后这个节点就会作为当前节点，放到封闭集合里。(b) 显示了下一步的迭代，将当前节点（黄色）的邻接节点放入开放集合中。
在目标节点（红色）加到封闭集合之后，我们会得到从终点到起点的链表。这个链表可以通过反转得到之前贪婪最佳优先路径。
完整的贪婪最佳优先算法如下。注意这个实现假设h(x) 的值在执行过程中总是不变的。
curentNode = startNode
add currentNode to closedSet
// 把邻接节点加入开放集合
foreach Node n adjacent to currentNode
if closedSet contains n
n.parent = currentNode
if openSet does not contain n
compute n.h
add n to openSet
// 所有可能性都尝试过了
if openSet is empty
// 选择新的当前节点
currentNode = Node with lowest h in openSet
remove currentNode from openSet
add currentNode to closedSet
until currentNode == endNode
// 如果路径解出， 通过栈重新构造路径
if currentNode == endNode
Stack path
Node n = endNode
while n is not null
push n onto path
n = n.parent
// 寻路失败
如果我们不想用栈构造路径，另一个方案就是直接计算起点到终点的路径。这样，在寻路结束的时候就能得到从起点到终点的路径，可以节省一点计算开销。
本文选自《游戏编程算法与技巧》一书。
想及时获得更多精彩文章，可在微信中搜索“博文视点”或者扫描下方二维码并关注。
版权声明：本文内容由互联网用户自发贡献，本社区不拥有所有权，也不承担相关法律责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件至： 进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容。
用云栖社区APP，舒服~
【云栖快讯】红轴机械键盘、无线鼠标等753个大奖，先到先得，云栖社区首届博主招募大赛9月21日-11月20日限时开启，为你再添一个高端技术交流场所&&
用于实时预测用户对物品偏好，支持企业定制推荐算法，支持A/B Test效果对比
大数据开发套件（Data IDE），提供可视化开发界面、离线任务调度运维、快速数据集成、多人协同工作等功能，为您...
以阿里云成熟的商业化云服务为基础，为游戏开发者、运营企业提供专属集群、尊享VIP服务、专项扶持基金、及多场景多类...
为您提供简单高效、处理能力可弹性伸缩的计算服务，帮助您快速构建更稳定、安全的应用，提升运维效率，降低 IT 成本...
安全技术百问
Loading...32被浏览3725分享邀请回答309 条评论分享收藏感谢收起21 条评论分享收藏感谢收起查看更多回答游戏制作中的大宝剑---常用的数据结构与算法
时间： 18:24:27
&&&& 阅读：114
&&&& 评论：
&&&& 收藏：0
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&前言
&&&时间流逝，物是人非，就好像涌动的河流，永无终焉，幼稚的心智将变得高尚，青年的爱慕将变得深刻，清澈之水折射着成长。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
----------《塞尔塔传说》
PS：为了方便大家阅读，个人认为比较重要的内容-------红色字体显示
&&&&&&&&&&&&&&& & & & & & & & & & & & && 个人认为可以了解的内容-------紫色字体显示
---------------------------------------------------------------------------
--------------------------------------------------分-割-线-----------------------------------------
&&&&&& 在游戏的制作过程之中，总是少不了使用到一些数据结构，或者说使用了一些比较高效的算法，尤其是游戏引擎之中的一些很高深的算法，让人匪夷所思，当然我们主要讲一讲游戏之后简单的一些算法以及常用到的数据结构。让我们一步一步来，首先是常用的数据结构，之后再来讲一讲常用的一些算法。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& & &&&&常用的数据结构
&&&&&& 数据结构是计算机存储、组织数据的方式，是相互存在一种或者多种特定关系的数据元素的集合。当然在软件的开发过程之中，数据机构设计的合理可以带来更高的运行或者存储效率。而且游戏软件有一个特点，就是它要求相应更加快速，计算要更加精确，而且有很多的多媒体资源需要去组织和管理。由此可见，游戏软件的设计需要强大的数据结构在背后支撑！好了，我们来看一看常用的数据结构：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&不可或缺的数组
&&&&&& 虽然说数组是一种最简单的数据结构，而且也很容易理解，可以说每个编程爱好者都用过不知道多少次数组了。所以每个人都很清楚，在程序设计过程之中，常常把相同类型的若干变量按照数组的形式组织起来。数组元素的查找要按照索引的顺序依次进行，根据已知索引来读取数据会显得很方便，不过插入或者删除的时候就会稍微麻烦一些，需要移动一些元素，原因就是为了维持数组元素原来的约定。这里指的一提的就是数组之中的元素也可以是数组类型，这样就构成了二维数组、多维数组。
&&&&&& 具体数组在游戏之中是怎么使用的呢？其实数组在游戏之中很常见，比如游戏之中某种分值排行的功能、对某种属性选取最值的功能等，都可以用一维数组来实现，不过这里不仅仅使用到了数组，而且使用到了数组的排序。
&&&&&& 二维数组在游戏之中用的还是挺多的，很多游戏之中都有体现，最常见的一种方式就是二维数组表示地图（在3D游戏的制作之中，可能会涉及到三维地形的加载，其实三维地形是由灰度图来描述的，把每个像素映射为一个高度，其实原理上也类似吧！），像酷跑类的游戏、推箱子的游戏、棋盘类游戏的棋盘设计都是二维数组的体现。这样说不够直观，来看一张图吧：
在上述例子之中二维数组可以得到很好的应用，用它来描述地图数据，可以很好地完成游戏之中界面的实时变化，在对地图之中所有的元素进行分析之后，我们可以得到八种类型。之后根据地图的大小，设计m*n大小的二维数组，它里面的数据就是这八种类型的编码，在游戏进行过程之中，需要玩家进行实时的输入，在玩家进行输入之后，需要根据相应的逻辑修改地图信息，或者说是更新地图信息。但是需要注意的是地图的原始数据不能变化，否则下次游戏不能正常进行，这里修改的应该是原始地图的临时拷贝。
-------------------------------------------------------------------------------------------------------------
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&方便实用的链表
& & && 链表是一种物理存储上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表之中指针的链接次序实现的。链表之中的每一个元素称为节点，每个节点包括两个部分：一是存储数据的的数据域，另一个是存储下一个节点地址的指针域。链表由一系列节点组成，节点可以在需要的时候动态生成。也正是因为这些特点，链表的查找一定要按照节点依次进行，链表的插入、删除操作十分方便；链表不需要再一开始就占用很多空间，随着程序的运行需要动态创建即可。
&&&&&& 在游戏之中，很多的游戏元素需要动态的出现、消除，其个数是难以预料的，例如射击游戏之中出现的敌机和子弹，还比如消除游戏之中出现的消除对象以及RPG游戏之中出现的电脑角色等等。根据链表在插入和删除数据，可随程序运行动态创建数据的特点，在游戏开发过程之中常常用链表来维护、管理那些需要频繁产生、消除的游戏对象。
&&&&&& 以射击游戏为例，游戏之中可以用链表来表示游戏之中的敌机和子弹。在游戏的开始的时候，创建一个敌机的链表、一个子弹的链表，其中的元素的个数为0，即敌机的个数为0，子弹的个数为0；随着时间的推进，敌机出现，程序中创建相应的敌机节点放入敌机链表；由于敌机的出现，攻击的子弹也要相应的出现，程序之中创建相应的子弹节点加入子弹链表；当攻击子弹与敌机发生碰撞，子弹和敌机都应该消失，此时根据程序此时的子弹、敌机指针，找到链表相应的节点，然后删除、更新链表。如果敌机、子弹的数量较多，创建、删除操作太频繁，还可以敌机、子弹链表分为存活链表和死亡链表两种，并在节点之中添加存活属性，当需要删除敌机或者子弹节点的时候，将属性修改，放入死亡链表。当需要创建新的敌机或者子弹的时候，先检查死亡链表之中有无该节点，若有，修改存活属性，加入存活链表之中，反之才会申请内存空间，重新创建相应的节点，这样可以将死亡的节点重新利用，大大节省了游戏在
创建、清除方面的开销！
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&道具包管理-------线性表
&&&&&& 这样说可能大家已经有点感觉到了数组或者链表在游戏之中的体现，不过数组并不是特别的明显，其实它们衍生出一个叫做线性表的东西在游戏之中有更多的体现。相信我们都玩过RPG游戏，或者说一些网页游戏（不过我并不喜欢玩网页游戏），里面都有一种叫做道具包，或者说是道具栏的东西。道具这种东西似乎在任何RGP游戏之中都有体现，比如国产的仙剑奇侠传系列，你所扮演的人物在游戏过程之中会获得道具（一般来说是战斗结束的时候获得道具），所以我们在程序之中需要把这些数据组织起来，方便管理。在这个时候其实我们可以考虑使用线性表，还是挺方便的，线性表是一组元素以线性的结构组织起来的，如（e1，&
e2， e3 …… en）。从大类上分，线性表可以分为链表和数组两大类。
&&&&&& 其实如果真的要使用的话，我们可以使用STL之中的容器，如vector以及list来实现，更加方便。
&&&&&& 数组里的元素以连续的内存空间存放，因此可以用内存地址检索到对应的数据元素，访问元素很方便。但如果要进行插入／删除数据元素，就要做一些内存移动了，效率比较低。而链表的数据元素存放在任意的物理内存位置，相邻的元素以指针作为“链扣”串连起来。如单向链表，元素有一个指针指向它的后继节点，这个指针就是它们之间的“链扣”。当进行插入／删除数据元素时，只要改变相应的“链扣”就可以，不需要做内存移动，效率相对于数组要高，有时候甚至要高得多。
------------------------------------------------------------------------------------------------------------
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&无处不在&的栈和队列
&&&&&& 栈和队列在游戏之中的出现频率也是很高的，栈和队列其实也是一种“特殊”的线性表，怎么特殊呢？他们都是操作受限的、特殊的线性表。栈的特点就是只能在栈顶插入和删除元素，特点是后进先出（LIFO）；队列只能是在队尾插入元素，在队头删除元素，其特点就是先进先出（FIFO），因此，栈和队列都非常适合用来用来解决递归、排队类的问题。
&&&&&& 递归设计在游戏开发中应用很普遍，简单地举几个例子，像迷宫类的游戏、棋类的游戏等，而为了提高效率，减少递归函数的多次调用，游戏程序之中常常利用对于栈的操作来代替直接的递归函数设计。
&&&&&&& 我们可以以迷宫类游戏为例子简单讲解一下，在通常情况之下，我们利用回溯法（也叫试探法）求解一个问题，这种方法将问题的候选解按照某种顺序逐一枚举和检索。当发现当前的候选解不可能是解的时候，就放弃它而选择下一个候选解。当然如果当前的候选解不能满足求解的要求，则扩大候选解的规模继续求解；一直到最终的成功求解。在回溯法求解问题的时候常常使用递归的方法来进行试探、回溯，实际应用中使用栈的相应操作来完成。例如，在迷宫之中某一个特定位置向前试探的时候，就是把所有可能的下一个位置压栈；之后一次出栈，对其进行检测；如果是墙壁，表明不可能是迷宫的出口，那么放弃当前的位置，继续出栈检验；如果当前的位置可以通过（也就是说是通道）但是又不是出口，那么就把当前位置的所有可能的下一个位置入栈；如此循环，一直到栈为空或者说是找到迷宫的出口。
&&&&&& 像这样循环下去，最终的结果只有两种：1.找到迷宫的出口；<span style="color:#.迷宫没有出口（栈为空）。
&&&&&&栈是一种“先进后出”的数据结构。就好像是叠盘子，叠在最上面的盘子最先拿来使用。队列和栈可能是使用频率最高的数据结构了。在匹配表达式应用中，栈发挥了巨大的作用。还有经典的汉诺塔问题，如果没有栈的帮助，你可不知道要搬碟子搬到什么时候了。这里我想举一个Word的例子，这个例子比较形象。谁都会有失误，在Word里发生了误操作一点也不需要惊慌，因为Word有“撤消”的功能，可以撤消你之前的操作。把用户的操作压入栈里，要撤消操作时就从栈弹出最近发生的操作。这样可以很方便地实现这个功能。
&&&&&& 对于队列，举一个简单的例子，不知道大家是否玩过《梦幻西游》这样的游戏（我虽然没怎么玩过，倒是看身边的人玩过），在玩《梦幻西游》的时候，你在城里逛了几圈之后在城里走了几圈就接了满身的任务。这让我很烦恼，不知从哪个任务开始做起，这时我想到了队列。队列是一种“先进先出（first-in-first
out, FIFO）”的数据结构。就好像是在银行里排队，排在前面的先服务。每次接到任务就把该任务压进任务队列里，要做任务时就从任务队列里取出一个任务，这样哪个任务先接到就先做哪个任务。
&&&&&& 但是也有可能你比较缺钱，你不喜欢这样方式，你想哪个任务报酬多的就先做哪个任务。这样普通的队列就满足不了你的需求了，你需要的是优先级队列。优先级队列在插入元素时，优先高的元素插入队列前面。把任务的报酬设成是优先级数据，那么你每次在任务队列里取出任务时，就能保证这个任务是你现接的任务里报酬最高的。
----------------------------------------------------------------------------------------------------------
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&做游戏界面的设计者----树
　　 先来简单说一说普遍的树，树是一种一对多的数据结构。非空树只有一个根节点。而树中的任意节点都可以有多个子节点。也就是说，树之中的任意节点，只可能有一个前驱，但是可能有多个后继。数的存储一般使链式结构，父节点总是有多个指向子节点的指针，而子节点最多有一个指向父节点的指针。
树跟上面介绍的数据结构不一样，树是一种非线性的数据结构。树的实现与应用都要比线性数据结构复杂，C&#43;&#43;标准库也没有实现树这种数据结构（这里说的是一棵普通的树）。但其实树的应用很广泛，很常用到，但是由于它的复杂性，很多程序员都回避使用。如果能有效地使用树，你的程序效率将会得到很大的提高。
&&&&&& 在来简单说一说树在游戏之中的应用吧！其实最直接的感觉就是由于树结构的特点，它非常适合解决游戏之中的分支选择判断类问题，例如竞猜类的游戏。典型的实现是，用一个二叉树来保存竞猜的数据，叶子结点是竞猜结果，其他结点都是竞猜条件。在游戏的过程之中，如果当前的条件满足，就继续沿着当前结点的左子树继续竞猜；否则沿着右子树继续竞猜。
　　树的另外一个比较形象的应用是游戏中的UI（User Interface用户界面）。在UI里的菜单一般是分级的，如在主UI里可能会有“进入游戏”、“选项”、“退出游戏”这几项菜单，在“进入游戏”里又会有其它菜单项，而进入“选项”后会有“音频”、“视频”、“游戏设置”等等，特别是在某些游戏之中，比如《三国志13》（今天过年时候刚刚推出的），它里面有很多的选项，在开始游戏里面又有很多的剧本，每个剧本点进去之后又有很多其他的内容，对于这种一个主页面可以衍生出很多的子页面的时候使用树来管理这些菜单是很合适的做法，不过有些游戏并没有这么复杂的界面，只有几个界面，像这样的游戏，那么也可以不用树来管理，只有几个页面的用树来管理有点小题大做了！就比如我之前做的一个游戏界面就根本没有用到树这种结构：
&&&& &&如果需要看的这里贴出：
　　最后来说一说树的其他一些小知识----树在应用时又分很多种类型，我们在这里只介绍二叉树（也是最常用的一种树的结构，不过在游戏之中还有其他四叉树、八叉树也使用的很多）。二叉树对后继节点进行了一项约束——每个二叉树的节点最多只能有二个后继节点。红黑树是一种特殊的二叉树，C&#43;&#43;标准库的set和map就是用红黑树实现的，因此它们的排序查找效率很高，红黑树的使用十分广泛。
　　由于树是一种非线性的数据结构，因此它对元素的遍历并不像线性数据结构那么简单。二叉树一般常用的有三种遍历算法：前继遍历、中继遍历和后继遍历。前继遍历先访问父节点，然后是左节点，右节点；中继遍历先访问左节点，再到父节点，最后是右节点；后继遍历先访问左节点，再到右节点，最后是父节点。
如下图就是一棵红黑树：
-----------------------------------------------------------------------------------------------------------&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&地图数据管理-----图　
&&&&&& 图是一种复杂的数据结构，相对于树要更复杂一些（个人感觉图是所有数据结构之中最难的部分）。跟树一样，图是一种非线性的数据结构，C&#43;&#43;标准库同样没有实现图。图就像一个网一样，各个节点用边线连接起来，每条边线有一个权&#20540;，可以理解成两个节点间的距离。研究图对游戏开发很有意义，游戏地图是图的应用的一个很好的例子。游戏中的地图一般会被分成一块块的&#26684;子，每一块都会有一个坐标&#20540;。那么可以使用二维数组把地图的数据记录起来，这是最简单的方法。但大家都知道，鱼与熊掌是不能兼得的，这种方法只能用在很小型的地图，而较专业的做法是使用图记录地图数据，图的每一个节点对应的是地图的一个坐标。
&&&&&& 来看几张简单的地图：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
图的标准搜索算法有两种：广度优先搜索与深度优先搜索。广度优先搜索从开始节点的周围节点一层一层地往外搜索；深度优先搜索以开始节点为始点对一条路径搜索到尽头后再搜索另一条路径，直到所有的路径都搜索完为止。
　　图论是一门很大的课题，有兴趣的读者可以找相关的专业书籍进行深入研究。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& & & &&&常见的算法
-----------------------------------------------与数组相关的算法---------------------------------------------- &&&&&
&&&&&& 关于游戏之中常见的算法，我这里根据所说的数据结构分开来将，首先就是最开始讲的数组，对于数组来说常用的算法无非就是排序了，常见的排序有冒泡排序、插入排序、选择排序以及快速排序，当然这是常见的排序算法，在游戏之中常用的排序算法有以下几种：
&&&&&& 常用排序算法一：快速排序-----快排算的上是最有名的排序算法，不过也不是任何条件下都是最好的，取决于你怎么使用了，可以这样会说快排就像开车一样，不会开的人开再好的也没用，会的人能充分的利用它。不过在平均状况下，排序
n 个项目要Ο(n*logn)次比较。在最坏状况下则需要Ο(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n*log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的上很有效率地被实现出来。
&&&&&& 快排的核心思想：采用分治法（Divide and conquer）的策略来把一个串行（list）分为两个子串行（sub-lists）
&&&&&&&来简单地说一下快排的步骤和思路吧（一共分为三步）：
&&&&&& 首先：要从数列（数组）之中挑出一个元素，称为基准&#20540;（pivot）。当然这个基准&#20540;选的好与不好影响还是很大的，下面会有提到。
&&&&&& 其次：需要重新排列数组，所有比基准&#20540;小的元素都放在基准前面，所有比基准&#20540;大的元素都放在基准&#20540;后面（相同的数可以到任一边），当然在这个分区退出之后这个基准&#20540;就位于数组中间的位置，这个称谓分区（partition）操作，当然这里有一点还需要跑提一下，通常在写快排的时候，总是喜欢把这个基准&#20540;放在数组的最后一个元素，循环交换元素&#8;完了之后，再把这个元素取回来，然后进行第三步。
&&&&&& 最后递归地（recursive）把小于基准&#20540;元素的子数列和大于基准&#20540;元素的子数列排序，递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
在这里我需要简单地提几个注意点：
&(1). 快速排序的key&#20540;的选择，key的&#20540;若是一直是极端&#20540;，程序的时间复杂度会下降到O（N^2），这样的快速排序还不如不写，所以我给出了三数取中法来保证每次选择的key&#20540;不至于是极端&#20540;。
&(2). 快速排序的区间选择很重要，区间大于13适合使用快排，区间小于13使用插入排序，这样的效率比较高(是经过测试得出的)，因为小区间插入排序可以降低快速排序的递归次数，而且数量越多优化的效果越明显。
&(3). 快速排序还能用于链表的排序，这点很重要，但是链表不能使用三数取中法，导致效率不能满足要求，这也是STL中的List的sort函数为什么选择归并排序的原因
&&&&&& 常用的排序算法二：堆排序----堆排序我个人觉得比较重要，需要好好掌握一下，因为它的用处很特别，我们&#20284;乎经常遇到这样的题目，比如求多少的数之中最大（最小）的K个数，这样的题目我们都需要使用堆排序来做，根据要找的是最大的K个数字还是最小的K个数字来选择建立最大堆还是最小堆。
&&&&&& 堆排序的核心思想：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。当然堆积是一种类&#20284;于完全二叉树的结构，并且同时满足堆积的性质，即子节点的键&#20540;或者说是索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(n*logn)。
&&&&&& 好了，接下来还是说一说堆排序的步骤和思路吧，一共分为以下几步：
&&&&&& 第一步：创建一个堆Heap[0……n-1]，当然在建堆的过程之后还是需要不断的向下调整。
&&&&&& 第二步：把堆首元素和最后一个元素堆尾互换。
&&&&&& 第三步：把堆的尺寸缩小1，并调整Adjustdown（），目的是把新的堆顶元素向下移动（因为堆顶元素要么是最大的要么是最小的），由于不断的减小尺寸，所以一直到0为止，元素就接近有序了，所以这一步需要重复。
还是照例说几个注意点吧：
建堆(其数组看成完全二叉树),从最后一个&根节点&起，依次向下调整，调整完以后最大堆或最小堆就建立起来了
& (2).每次将筛选出来的最大&#20540;或最小&#20540;放到数组最后一位(其实是将数组第一位与最后一位交换)，然后将堆的规模减小1，当规模为1的时候，数组里面就是排好序的了。
& (3). 其实堆排序最重要的是用来找出k个最小数或k个最大数。思路：遍历堆，然后遍历数组，置换出堆中的数据，遍历完的时候堆中的数据就是所要求的结果了。至于 创建最大堆还是最小堆，这有个技巧，就是与你所求的相反，即：找最小用打大堆，找最大用小堆。最后注意堆的使用场合。
&&&&&& 常用的排序算法三：归并排序----还是一种经常被用到的算法，是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide
and Conquer）的一个非常典型的应用。
&&&&&& 归并排序的核心思想：分治的思想
&&&&&&&同样的说一说归并排序简单的步骤和思路吧：
&&&&&& 第一步：申请空间，申请空间的大小为与你需要归并排序的数组大小相同（如果你是对两个已经排好序数组进行归并排序的话，申请的大小就要为两个数组长度之和），再把数据拷贝到新数组上，不过我这里主要讲的是在一个数组之内进行归并排序，所以这里申请的空间就是一个临时空间。
&&&&&& 第二步：调用doMerge（），这个函数主要就是为了进行递归的划分区间（一直到该区间只剩一个元素），递归返回之后这时候需要进行区间内的排序，让每一个区间都有序，最后整体有序，可以考虑在每一个区间之中使用插入排序。
&&&&&& 第三步：此时在这个临时数组空间里面有两部分，前一部分已经排好序，后一部分也已经排好序，所以现在需要做的就是把这两部分内容写回到原来的数组空间之中。
关于归并排序方面也没什么特别要说的：归并排序是一种空间换取时间的排序。
----------------------------------------------与树有关的算法--------------------------------------------------
&&&&&& 有关于栈和队列的算法这里就不说了（栈里面有个有趣背包问题可以去看一下）。我们直接讲一讲与树相关的算法，先来看一张图：
正如图之中所描述的，在这个场景之中有1000个小球在运动，程序需要在它的每一帧检测他们的碰撞信息，之后需要进行下一步的绘制（其实如果小球在小一点，可以看成是一系列粒子的运动状态）。不过在这里我们还是看成小球吧！这么多小球是怎么来描述他们运动的呢？而且游戏又要追求高效，所以我们很容易想到一种数据结构，就是树。但是如果采用二叉树，效率不够高又应该怎么办呢？这时候我们可以用一种四叉树的结构（在一些3D场景之中，甚至有一些会使用八叉树的数据结构用来检测物体间的碰撞）
&&&&&&首先所有的小球都是存在于叶子结点上的，而其他的结点只是方便我们找到合适的叶子结点。其次，我们需要根据问题的规模设计一个合适的高度（层数），使得在最终的叶子结点上，小球的数量比较合适。在这个图之中，我们可以设计为五层，一层是一个结点，两层就有五个结点，四个叶子结点，同理可知五层的话，叶子结点就有4^4
= 256个，那么在最终的叶子结点上，小球的平均数量是，大约为4个，数量比较合适，最后对256个叶子结点进行循环，然后再对其中4个左右的小球进行二层循环，就可以计算当前帧小球的碰撞的次数。
&&&&&& 最后我们来比较一下，如果我们不使用四叉树这种结构，那么如果我们使用传统的方式，那么就需要 =<span style="color:#FF0次碰撞检测，但是画面每一帧都需要刷新，游戏场景肯定不仅仅只有小球，很显然这种方式性能上肯定不满足，那么我们再来看一看如果使用四叉树，那么只需要256*4*4
=<span style="color:#FF次碰撞检测，效率足足提高了250倍（如果场景更加复杂，我们可以考虑使用八叉树，这也是3D场景之中经常使用的数据结构）。
-----------------------------------------人工智能的体现--图---------------------------------------------
&&&&&& 我们在平时制作游戏的过程之中，肯定会遇到这么一种情况，我们想让自己设计的AI更加智能一些，比如我们设计的AI，它可以追踪玩家，并且它还可以很巧妙的避开墙壁和障碍物。说到寻路算法，那么大家基本都知道或者听说过一种算法叫做A*寻路算法，也可以说这种算法是现在在游戏场景之中使用最广泛的一种寻路算法吧！不过寻路算法可不止A*寻路算法。
&&&&&& 我们先来讲几个简单的寻路算法，然后提一提A*寻路算法（由于A*寻路算法需要篇幅很大，所以准备之后专门写一篇关于A*寻路算法的文章，所以这里简单提一提）。
&&&&&& 说这个之前，先说一说什么叫做寻路算法。
&&&&&& 关于寻路算法在游戏关卡中常常会放置一些怪物（即NPC），这些怪物通常在一个区域内走来走去，这个区域被称为“巡逻区域”;一旦玩家的角色进入怪物的“视
野”，怪物就会发现玩家角色，并主动向其所在的位置移动，这个区域称为“警戒区域”；当玩家角色和怪物更加靠近时，会进入到怪物的“攻击区域”，这时怪物 会对玩家角色进行伤害。在某些RPG（Real-TimeStrategy Game，即时战略游戏）中，NPC 在不利的情况下还会选择主动逃跑。如何模拟这些行为逻辑，目前游戏业已经有一些比较成熟的方法。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
第一种：随机寻路算法
&&&&&& 随机寻路算法适合模拟游戏中那些没有什么头脑的生物，它们总是在场景中漫无目的地走来走去。可以用以下的代码进行模拟：
npc_x_velocity = -5 + rand() %10；
npc_y_velocity = -5 + rand() %10；
int npc_move_count=0；
while(++npc_move_count&num)
npc_x+ = npc_x_velocity；
npc_y+ = npc_y_velocity；
} //end while
&&&&&& 在上例中，NPC
（非玩家操纵角色）会选取一个随机方向和速率运动一会儿，然后再选取另一个。当然，还可以加上更多的随机性，如，改变运动方向的时间不是固定的num个周期，或者更倾向于朝某个方向（或者也可以是来回行走）等。实际编程中还必须考虑到碰撞检测，当NPC不管是遇到障碍物还是遇到了边界，都会随机选取一个前进的方向，继续行走。&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
第二种：跟踪算法
&&&&& 当游戏中的主角进入到NPC 的“警戒区域”后，游戏的AI 可轻易获得目标的位置，然后控制NPC 对象移向被跟踪的对象。跟踪算法可以模拟这一行为：
void Bat_AI(void)
if(ghost.x & bat.x)
else if(ghost.x & bat.x)
if(ghost.y & bat.y) bat.y++；
elseif(ghost.y & bat.y) bat.y--；
//其他代码
&&&&&& 但是这段代码放到程序中实际运行时不难发现，NPC会迅速地追踪到目标。这种跟踪非常精确，而且十分快速，玩家很难避开（如果AI的移动速度够快的话），但是在游戏中过于精确却不一定是一件好事，因为这会使NPC的行为看上去显得有点假，而且玩家难以避开的话影响玩家的体验性，不过我在之前写单回合制小游戏的时候，里面的AI设计的就是这种算法，所以感觉设计的不是很合理，这里给出链接：。当然有一种更自然的跟踪方式是使跟踪者的方向矢量与从跟踪目标的中心到跟踪者的中心所定义的方向矢量靠拢。这个算法可以这样设计：假设AI
控制的对象称作跟踪者（tracker）并有以下属性：
struct NPC
Position：(tracker.x，tracker.y)
Velocity：(tracker.xv，tracker.yv)
}&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;
被跟踪对象称作跟踪目标（target），有如下属性：
Position：(target.x，target.y)
Velocity：(target.xv，target.yv)
&&&&&&&基于上面的定义，下面是调整跟踪者的速度向量的常用逻辑循环：
第一步：计算从跟踪者到跟踪目标的向量，关于向量的加减法，高中就已经学过，这里不多说了。
TV = (target.x -tracker.x, target.y-tracker.y) = (tvx, tvy)，
规&#26684;化TV——也就是说 (tvx,tvy)/Vector_Length(tvx，tvy)使得最大长度为1.0，记其为NewTV。记住Vector_Length()只是计算从原点(0，0)开始的矢量长度。所以如果你需要得到不是从原点开始的矢量长度，那么需要简单转化一下。
第二步：调整跟踪者当前的速度向量，加上一个按rate比例缩放过的NewTV
tracker.x += rate*tvx；
tracker.y += rate*tvy； &&&&&& 需要注意的一点就是这个rate的选取，当rate &1.0时，跟踪向量会合得更快，跟踪算法对目标跟踪得更紧密，并更快地修正目标的运动。
第三步：跟踪者的速度向量修改过之后，有可能向量的速度会溢出最大&#20540;，就是说，跟踪者一旦锁定了目标的方向，就会继续沿着该方向加速。所以，需要设置一个上界，让跟踪者的速度从某处慢下来。可做如下改进：
tspeed = Vector_Length(tracker.xv, tracker.yv)；
if(tspeed&max_SPEED)
tracker.xv*=0.7；
tracker.yv*=0.7；
关于这个讲的小数选取，可以自由选取，这里暂且就选择0.7吧！
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 第三种：闪避算法
&&&&&& 关于这个算法，虽然听着很高端，但是真的很简单，与之前的跟踪代码很相&#20284;，这个技术是让游戏的NPC 能避开玩家角色的追击，跟踪算法的对立面就是闪避算法，只要把上例中的等式翻转，闪避算法就成了，下面是转换后的代码：if(ghost.x & bat.x)
else if(ghost.x & bat.x)
if(ghost.y & bat.y)
else if(ghost.y & bat.y)
& 好了，简单的算法就说到着了，以上介绍的3 个算法可以模拟NPC 的一些简单的寻路、跟踪和闪避行为，在小游戏中会经常用到。但是，在较大型的游戏中使用这样简单的算法就大大影响效果了！
&&&&& 最后，简单的说一说A*寻路算法（由于A*寻路算法要说的太多了，后面我会专门写一篇关于A*寻路的博客，这里先简单说一说思路）
&&&&&& 关于A*寻路算法，假设A点是NPC所在的位置，B是玩家所在的位置，那么如果NPC想要找到玩家，A*寻路算法可以分为以下三步：
第一步： 从起点A开始, 把它作为待处理的方&#26684;存入一个&开启列表&, 开启列表就是一个等待检查方&#26684;的列表.
第二步： 寻找起点A周围可以到达的方&#26684;, 将它们放入&开启列表&, 并设置它们的&父方&#26684;&为A.
第三步：从&开启列表&中删除起点 A, 并将起点 A 加入&关闭列表&, &关闭列表&中存放的都是不需要再次检查的方&#26684;
&&&&&& 关于里面涉及到的一些概念，这次由于篇幅原因先不说了，下回专门讲一讲A*寻路算法。
----------------------------------------------------------------------------------------------------------- &&&&&
&&&&&& 最后总结一下，数据结构在游戏开发过程之中使用真的很广泛，好的数据结构能把游戏之中复杂的问题很高效地解决，所以我们应该在游戏的开发过程之中合理地使用数据结构。
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&原文：http://blog.csdn.net/loving_forever_/article/details/
教程昨日排行
&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！}