游戏开发中常用的数据结构和算法

转载Loving_初衷

前言

   时间流逝，物是人非，就好像涌动的河流，永无终焉，幼稚的心智将变得高尚，青年的爱慕将变得深刻，清澈之水折射着成长。

                                                                                                           ----------《塞尔塔传说》

PS：为了方便大家阅读，个人认为比较重要的内容-------红色字体显示

---------------------------------------------------------------------------

--------------------------------------------------分-割-线-----------------------------------------

       在游戏的制作过程之中，总是少不了使用到一些数据结构，或者说使用了一些比较高效的算法，尤其是游戏引擎之中的一些很高深的算法，让人匪夷所思，当然我们主要讲一讲游戏之后简单的一些算法以及常用到的数据结构。让我们一步一步来，首先是常用的数据结构，之后再来讲一讲常用的一些算法。

                                                              常用的数据结构

       数据结构是计算机存储、组织数据的方式，是相互存在一种或者多种特定关系的数据元素的集合。当然在软件的开发过程之中，数据机构设计的合理可以带来更高的运行或者存储效率。而且游戏软件有一个特点，就是它要求相应更加快速，计算要更加精确，而且有很多的多媒体资源需要去组织和管理。由此可见，游戏软件的设计需要强大的数据结构在背后支撑！好了，我们来看一看常用的数据结构：

                                                                   不可或缺的数组

       虽然说数组是一种最简单的数据结构，而且也很容易理解，可以说每个编程爱好者都用过不知道多少次数组了。所以每个人都很清楚，在程序设计过程之中，常常把相同类型的若干变量按照数组的形式组织起来。数组元素的查找要按照索引的顺序依次进行，根据已知索引来读取数据会显得很方便，不过插入或者删除的时候就会稍微麻烦一些，需要移动一些元素，原因就是为了维持数组元素原来的约定。这里指的一提的就是数组之中的元素也可以是数组类型，这样就构成了二维数组、多维数组。

       具体数组在游戏之中是怎么使用的呢？其实数组在游戏之中很常见，比如游戏之中某种分值排行的功能、对某种属性选取最值的功能等，都可以用一维数组来实现，不过这里不仅仅使用到了数组，而且使用到了数组的排序。

       二维数组在游戏之中用的还是挺多的，很多游戏之中都有体现，最常见的一种方式就是二维数组表示地图（在3D游戏的制作之中，可能会涉及到三维地形的加载，其实三维地形是由灰度图来描述的，把每个像素映射为一个高度，其实原理上也类似吧！），像酷跑类的游戏、推箱子的游戏、棋盘类游戏的棋盘设计都是二维数组的体现。这样说不够直观，来看一张图吧：

在上述例子之中二维数组可以得到很好的应用，用它来描述地图数据，可以很好地完成游戏之中界面的实时变化，在对地图之中所有的元素进行分析之后，我们可以得到八种类型。之后根据地图的大小，设计m*n大小的二维数组，它里面的数据就是这八种类型的编码，在游戏进行过程之中，需要玩家进行实时的输入，在玩家进行输入之后，需要根据相应的逻辑修改地图信息，或者说是更新地图信息。但是需要注意的是地图的原始数据不能变化，否则下次游戏不能正常进行，这里修改的应该是原始地图的临时拷贝。

-------------------------------------------------------------------------------------------------------------

                                                                   方便实用的链表

       链表是一种物理存储上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表之中指针的链接次序实现的。链表之中的每一个元素称为节点，每个节点包括两个部分：一是存储数据的的数据域，另一个是存储下一个节点地址的指针域。链表由一系列节点组成，节点可以在需要的时候动态生成。也正是因为这些特点，链表的查找一定要按照节点依次进行，链表的插入、删除操作十分方便；链表不需要再一开始就占用很多空间，随着程序的运行需要动态创建即可。      

       在游戏之中，很多的游戏元素需要动态的出现、消除，其个数是难以预料的，例如射击游戏之中出现的敌机和子弹，还比如消除游戏之中出现的消除对象以及RPG游戏之中出现的电脑角色等等。根据链表在插入和删除数据，可随程序运行动态创建数据的特点，在游戏开发过程之中常常用链表来维护、管理那些需要频繁产生、消除的游戏对象。

       以射击游戏为例，游戏之中可以用链表来表示游戏之中的敌机和子弹。在游戏的开始的时候，创建一个敌机的链表、一个子弹的链表，其中的元素的个数为0，即敌机的个数为0，子弹的个数为0；随着时间的推进，敌机出现，程序中创建相应的敌机节点放入敌机链表；由于敌机的出现，攻击的子弹也要相应的出现，程序之中创建相应的子弹节点加入子弹链表；当攻击子弹与敌机发生碰撞，子弹和敌机都应该消失，此时根据程序此时的子弹、敌机指针，找到链表相应的节点，然后删除、更新链表。如果敌机、子弹的数量较多，创建、删除操作太频繁，还可以敌机、子弹链表分为存活链表和死亡链表两种，并在节点之中添加存活属性，当需要删除敌机或者子弹节点的时候，将属性修改，放入死亡链表。当需要创建新的敌机或者子弹的时候，先检查死亡链表之中有无该节点，若有，修改存活属性，加入存活链表之中，反之才会申请内存空间，重新创建相应的节点，这样可以将死亡的节点重新利用，大大节省了游戏在

创建、清除方面的开销！

                                                       道具包管理-------线性表

       这样说可能大家已经有点感觉到了数组或者链表在游戏之中的体现，不过数组并不是特别的明显，其实它们衍生出一个叫做线性表的东西在游戏之中有更多的体现。相信我们都玩过RPG游戏，或者说一些网页游戏（不过我并不喜欢玩网页游戏），里面都有一种叫做道具包，或者说是道具栏的东西。道具这种东西似乎在任何RGP游戏之中都有体现，比如国产的仙剑奇侠传系列，你所扮演的人物在游戏过程之中会获得道具（一般来说是战斗结束的时候获得道具），所以我们在程序之中需要把这些数据组织起来，方便管理。在这个时候其实我们可以考虑使用线性表，还是挺方便的，线性表是一组元素以线性的结构组织起来的，如（e1，  e2， e3 …… en）。从大类上分，线性表可以分为链表和数组两大类。

       其实如果真的要使用的话，我们可以使用STL之中的容器，如vector以及list来实现，更加方便。

       数组里的元素以连续的内存空间存放，因此可以用内存地址检索到对应的数据元素，访问元素很方便。但如果要进行插入／删除数据元素，就要做一些内存移动了，效率比较低。而链表的数据元素存放在任意的物理内存位置，相邻的元素以指针作为“链扣”串连起来。如单向链表，元素e1有一个指针指向它的后继节点e2，这个指针就是它们之间的“链扣”。当进行插入／删除数据元素时，只要改变相应的“链扣”就可以，不需要做内存移动，效率相对于数组要高，有时候甚至要高得多。

------------------------------------------------------------------------------------------------------------

                                                             "无处不在"的栈和队列

       栈和队列在游戏之中的出现频率也是很高的，栈和队列其实也是一种“特殊”的线性表，怎么特殊呢？他们都是操作受限的、特殊的线性表。栈的特点就是只能在栈顶插入和删除元素，特点是后进先出（LIFO）；队列只能是在队尾插入元素，在队头删除元素，其特点就是先进先出（FIFO），因此，栈和队列都非常适合用来用来解决递归、排队类的问题。

       递归设计在游戏开发中应用很普遍，简单地举几个例子，像迷宫类的游戏、棋类的游戏等，而为了提高效率，减少递归函数的多次调用，游戏程序之中常常利用对于栈的操作来代替直接的递归函数设计。

        我们可以以迷宫类游戏为例子简单讲解一下，在通常情况之下，我们利用回溯法（也叫试探法）求解一个问题，这种方法将问题的候选解按照某种顺序逐一枚举和检索。当发现当前的候选解不可能是解的时候，就放弃它而选择下一个候选解。当然如果当前的候选解不能满足求解的要求，则扩大候选解的规模继续求解；一直到最终的成功求解。在回溯法求解问题的时候常常使用递归的方法来进行试探、回溯，实际应用中使用栈的相应操作来完成。例如，在迷宫之中某一个特定位置向前试探的时候，就是把所有可能的下一个位置压栈；之后一次出栈，对其进行检测；如果是墙壁，表明不可能是迷宫的出口，那么放弃当前的位置，继续出栈检验；如果当前的位置可以通过（也就是说是通道）但是又不是出口，那么就把当前位置的所有可能的下一个位置入栈；如此循环，一直到栈为空或者说是找到迷宫的出口。

       像这样循环下去，最终的结果只有两种：1.找到迷宫的出口；2.迷宫没有出口（栈为空）。

      栈是一种“先进后出”的数据结构。就好像是叠盘子，叠在最上面的盘子最先拿来使用。队列和栈可能是使用频率最高的数据结构了。在匹配表达式应用中，栈发挥了巨大的作用。还有经典的汉诺塔问题，如果没有栈的帮助，你可不知道要搬碟子搬到什么时候了。这里我想举一个Word的例子，这个例子比较形象。谁都会有失误，在Word里发生了误操作一点也不需要惊慌，因为Word有“撤消”的功能，可以撤消你之前的操作。把用户的操作压入栈里，要撤消操作时就从栈弹出最近发生的操作。这样可以很方便地实现这个功能。

       对于队列，举一个简单的例子，不知道大家是否玩过《梦幻西游》这样的游戏（我虽然没怎么玩过，倒是看身边的人玩过），在玩《梦幻西游》的时候，你在城里逛了几圈之后在城里走了几圈就接了满身的任务。这让我很烦恼，不知从哪个任务开始做起，这时我想到了队列。队列是一种“先进先出（first-in-first out, FIFO）”的数据结构。就好像是在银行里排队，排在前面的先服务。每次接到任务就把该任务压进任务队列里，要做任务时就从任务队列里取出一个任务，这样哪个任务先接到就先做哪个任务。       但是也有可能你比较缺钱，你不喜欢这样方式，你想哪个任务报酬多的就先做哪个任务。这样普通的队列就满足不了你的需求了，你需要的是优先级队列。优先级队列在插入元素时，优先高的元素插入队列前面。把任务的报酬设成是优先级数据，那么你每次在任务队列里取出任务时，就能保证这个任务是你现接的任务里报酬最高的。

----------------------------------------------------------------------------------------------------------

                                                         做游戏界面的设计者----树 　　 先来简单说一说普遍的树，树是一种一对多的数据结构。非空树只有一个根节点。而树中的任意节点都可以有多个子节点。也就是说，树之中的任意节点，只可能有一个前驱，但是可能有多个后继。数的存储一般使链式结构，父节点总是有多个指向子节点的指针，而子节点最多有一个指向父节点的指针。

       树跟上面介绍的数据结构不一样，树是一种非线性的数据结构。树的实现与应用都要比线性数据结构复杂，C++标准库也没有实现树这种数据结构（这里说的是一棵普通的树）。但其实树的应用很广泛，很常用到，但是由于它的复杂性，很多程序员都回避使用。如果能有效地使用树，你的程序效率将会得到很大的提高。

       在来简单说一说树在游戏之中的应用吧！其实最直接的感觉就是由于树结构的特点，它非常适合解决游戏之中的分支选择判断类问题，例如竞猜类的游戏。典型的实现是，用一个二叉树来保存竞猜的数据，叶子结点是竞猜结果，其他结点都是竞猜条件。在游戏的过程之中，如果当前的条件满足，就继续沿着当前结点的左子树继续竞猜；否则沿着右子树继续竞猜。

　　树的另外一个比较形象的应用是游戏中的UI（User Interface用户界面）。在UI里的菜单一般是分级的，如在主UI里可能会有“进入游戏”、“选项”、“退出游戏”这几项菜单，在“进入游戏”里又会有其它菜单项，而进入“选项”后会有“音频”、“视频”、“游戏设置”等等，特别是在某些游戏之中，比如《三国志13》（今天过年时候刚刚推出的），它里面有很多的选项，在开始游戏里面又有很多的剧本，每个剧本点进去之后又有很多其他的内容，对于这种一个主页面可以衍生出很多的子页面的时候使用树来管理这些菜单是很合适的做法，不过有些游戏并没有这么复杂的界面，只有几个界面，像这样的游戏，那么也可以不用树来管理，只有几个页面的用树来管理有点小题大做了！就比如我之前做的一个游戏界面就根本没有用到树这种结构：

       如果需要看的这里贴出：游戏界面传送门　　最后来说一说树的其他一些小知识----树在应用时又分很多种类型，我们在这里只介绍二叉树（也是最常用的一种树的结构，不过在游戏之中还有其他四叉树、八叉树也使用的很多）。二叉树对后继节点进行了一项约束——每个二叉树的节点最多只能有二个后继节点。红黑树是一种特殊的二叉树，C++标准库的set和map就是用红黑树实现的，因此它们的排序查找效率很高，红黑树的使用十分广泛。　　由于树是一种非线性的数据结构，因此它对元素的遍历并不像线性数据结构那么简单。二叉树一般常用的有三种遍历算法：前继遍历、中继遍历和后继遍历。前继遍历先访问父节点，然后是左节点，右节点；中继遍历先访问左节点，再到父节点，最后是右节点；后继遍历先访问左节点，再到右节点，最后是父节点。

如下图就是一棵红黑树：

-----------------------------------------------------------------------------------------------------------                                                                                              地图数据管理-----图　

       图是一种复杂的数据结构，相对于树要更复杂一些（个人感觉图是所有数据结构之中最难的部分）。跟树一样，图是一种非线性的数据结构，C++标准库同样没有实现图。图就像一个网一样，各个节点用边线连接起来，每条边线有一个权值，可以理解成两个节点间的距离。研究图对游戏开发很有意义，游戏地图是图的应用的一个很好的例子。游戏中的地图一般会被分成一块块的格子，每一块都会有一个坐标值。那么可以使用二维数组把地图的数据记录起来，这是最简单的方法。但大家都知道，鱼与熊掌是不能兼得的，这种方法只能用在很小型的地图，而较专业的做法是使用图记录地图数据，图的每一个节点对应的是地图的一个坐标。

       来看几张简单的地图：

       图的标准搜索算法有两种：广度优先搜索与深度优先搜索。广度优先搜索从开始节点的周围节点一层一层地往外搜索；深度优先搜索以开始节点为始点对一条路径搜索到尽头后再搜索另一条路径，直到所有的路径都搜索完为止。　　图论是一门很大的课题，有兴趣的读者可以找相关的专业书籍进行深入研究。

                                                                   常见的算法

-----------------------------------------------与数组相关的算法----------------------------------------------      

       关于游戏之中常见的算法，我这里根据所说的数据结构分开来将，首先就是最开始讲的数组，对于数组来说常用的算法无非就是排序了，常见的排序有冒泡排序、插入排序、选择排序以及快速排序，当然这是常见的排序算法，在游戏之中常用的排序算法有以下几种：

       常用排序算法一：快速排序-----快排算的上是最有名的排序算法，不过也不是任何条件下都是最好的，取决于你怎么使用了，可以这样会说快排就像开车一样，不会开的人开再好的也没用，会的人能充分的利用它。不过在平均状况下，排序 n 个项目要Ο(n*logn)次比较。在最坏状况下则需要Ο(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n*log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

       快排的核心思想：采用分治法（Divide and conquer）的策略来把一个串行（list）分为两个子串行（sub-lists）

       来简单地说一下快排的步骤和思路吧（一共分为三步）：

       首先：要从数列（数组）之中挑出一个元素，称为基准值（pivot）。当然这个基准值选的好与不好影响还是很大的，下面会有提到。

       其次：需要重新排列数组，所有比基准值小的元素都放在基准前面，所有比基准值大的元素都放在基准值后面（相同的数可以到任一边），当然在这个分区退出之后这个基准值就位于数组中间的位置，这个称谓分区（partition）操作，当然这里有一点还需要跑提一下，通常在写快排的时候，总是喜欢把这个基准值放在数组的最后一个元素，循环交换元素完了之后，再把这个元素取回来，然后进行第三步。

       最后递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序，递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

在这里我需要简单地提几个注意点：

 (1). 快速排序的key值的选择，key的值若是一直是极端值，程序的时间复杂度会下降到O（N^2），这样的快速排序还不如不写，所以我给出了三数取中法来保证每次选择的key值不至于是极端值。

 (2). 快速排序的区间选择很重要，区间大于13适合使用快排，区间小于13使用插入排序，这样的效率比较高(是经过测试得出的)，因为小区间插入排序可以降低快速排序的递归次数，而且数量越多优化的效果越明显。

 (3). 快速排序还能用于链表的排序，这点很重要，但是链表不能使用三数取中法，导致效率不能满足要求，这也是STL中的List的sort函数为什么选择归并排序的原因

       常用的排序算法二：堆排序----堆排序我个人觉得比较重要，需要好好掌握一下，因为它的用处很特别，我们似乎经常遇到这样的题目，比如求多少的数之中最大（最小）的K个数，这样的题目我们都需要使用堆排序来做，根据要找的是最大的K个数字还是最小的K个数字来选择建立最大堆还是最小堆。

       堆排序的核心思想：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。当然堆积是一种类似于完全二叉树的结构，并且同时满足堆积的性质，即子节点的键值或者说是索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(n*logn)。

       好了，接下来还是说一说堆排序的步骤和思路吧，一共分为以下几步：

       第一步：创建一个堆Heap[0……n-1]，当然在建堆的过程之后还是需要不断的向下调整。

       第二步：把堆首元素和最后一个元素堆尾互换。

       第三步：把堆的尺寸缩小1，并调整Adjustdown（），目的是把新的堆顶元素向下移动（因为堆顶元素要么是最大的要么是最小的），由于不断的减小尺寸，所以一直到0为止，元素就接近有序了，所以这一步需要重复。

还是照例说几个注意点吧：

  (1). 建堆(其数组看成完全二叉树),从最后一个"根节点"起，依次向下调整，调整完以后最大堆或最小堆就建立起来了

  (2).每次将筛选出来的最大值或最小值放到数组最后一位(其实是将数组第一位与最后一位交换)，然后将堆的规模减小1，当规模为1的时候，数组里面就是排好序的了。

  (3). 其实堆排序最重要的是用来找出k个最小数或k个最大数。思路：遍历堆，然后遍历数组，置换出堆中的数据，遍历完的时候堆中的数据就是所要求的结果了。至于 创建最大堆还是最小堆，这有个技巧，就是与你所求的相反，即：找最小用打大堆，找最大用小堆。最后注意堆的使用场合。

       常用的排序算法三：归并排序----还是一种经常被用到的算法，是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

       归并排序的核心思想：分治的思想

       同样的说一说归并排序简单的步骤和思路吧：

       第一步：申请空间，申请空间的大小为与你需要归并排序的数组大小相同（如果你是对两个已经排好序数组进行归并排序的话，申请的大小就要为两个数组长度之和），再把数据拷贝到新数组上，不过我这里主要讲的是在一个数组之内进行归并排序，所以这里申请的空间就是一个临时空间。

       第二步：调用doMerge（），这个函数主要就是为了进行递归的划分区间（一直到该区间只剩一个元素），递归返回之后这时候需要进行区间内的排序，让每一个区间都有序，最后整体有序，可以考虑在每一个区间之中使用插入排序。

       第三步：此时在这个临时数组空间里面有两部分，前一部分已经排好序，后一部分也已经排好序，所以现在需要做的就是把这两部分内容写回到原来的数组空间之中。

关于归并排序方面也没什么特别要说的：归并排序是一种空间换取时间的排序。

----------------------------------------------与树有关的算法--------------------------------------------------

       有关于栈和队列的算法这里就不说了（栈里面有个有趣背包问题可以去看一下）。我们直接讲一讲与树相关的算法，先来看一张图：

       正如图之中所描述的，在这个场景之中有1000个小球在运动，程序需要在它的每一帧检测他们的碰撞信息，之后需要进行下一步的绘制（其实如果小球在小一点，可以看成是一系列粒子的运动状态）。不过在这里我们还是看成小球吧！这么多小球是怎么来描述他们运动的呢？而且游戏又要追求高效，所以我们很容易想到一种数据结构，就是树。但是如果采用二叉树，效率不够高又应该怎么办呢？这时候我们可以用一种四叉树的结构（在一些3D场景之中，甚至有一些会使用八叉树的数据结构用来检测物体间的碰撞）

      首先所有的小球都是存在于叶子结点上的，而其他的结点只是方便我们找到合适的叶子结点。其次，我们需要根据问题的规模设计一个合适的高度（层数），使得在最终的叶子结点上，小球的数量比较合适。在这个图之中，我们可以设计为五层，一层是一个结点，两层就有五个结点，四个叶子结点，同理可知五层的话，叶子结点就有4^4 = 256个，那么在最终的叶子结点上，小球的平均数量是1000/256，大约为4个，数量比较合适，最后对256个叶子结点进行循环，然后再对其中4个左右的小球进行二层循环，就可以计算当前帧小球的碰撞的次数。

       最后我们来比较一下，如果我们不使用四叉树这种结构，那么如果我们使用传统的方式，那么就需要1000*1000 =1000000次碰撞检测，但是画面每一帧都需要刷新，游戏场景肯定不仅仅只有小球，很显然这种方式性能上肯定不满足，那么我们再来看一看如果使用四叉树，那么只需要256*4*4 =4096次碰撞检测，效率足足提高了250倍（如果场景更加复杂，我们可以考虑使用八叉树，这也是3D场景之中经常使用的数据结构）。

-----------------------------------------人工智能的体现--图---------------------------------------------

       我们在平时制作游戏的过程之中，肯定会遇到这么一种情况，我们想让自己设计的AI更加智能一些，比如我们设计的AI，它可以追踪玩家，并且它还可以很巧妙的避开墙壁和障碍物。说到寻路算法，那么大家基本都知道或者听说过一种算法叫做A*寻路算法，也可以说这种算法是现在在游戏场景之中使用最广泛的一种寻路算法吧！不过寻路算法可不止A*寻路算法。

       我们先来讲几个简单的寻路算法，然后提一提A*寻路算法（由于A*寻路算法需要篇幅很大，所以准备之后专门写一篇关于A*寻路算法的文章，所以这里简单提一提）。

       说这个之前，先说一说什么叫做寻路算法。

       关于寻路算法在游戏关卡中常常会放置一些怪物（即NPC），这些怪物通常在一个区域内走来走去，这个区域被称为“巡逻区域”;一旦玩家的角色进入怪物的“视 野”，怪物就会发现玩家角色，并主动向其所在的位置移动，这个区域称为“警戒区域”；当玩家角色和怪物更加靠近时，会进入到怪物的“攻击区域”，这时怪物 会对玩家角色进行伤害。在某些RPG（Real-TimeStrategy Game，即时战略游戏）中，NPC 在不利的情况下还会选择主动逃跑。如何模拟这些行为逻辑，目前游戏业已经有一些比较成熟的方法。

                                                             第一种：随机寻路算法        随机寻路算法适合模拟游戏中那些没有什么头脑的生物，它们总是在场景中漫无目的地走来走去。可以用以下的代码进行模拟：

第一步：计算从跟踪者到跟踪目标的向量，关于向量的加减法，高中就已经学过，这里不多说了。

第一步： 从起点A开始, 把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格的列表.

第二步： 寻找起点A周围可以到达的方格, 将它们放入"开启列表", 并设置它们的"父方格"为A.

第三步：从"开启列表"中删除起点 A, 并将起点 A 加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格

-----------------------------------------------------------------------------------------------------------      

       最后总结一下，数据结构在游戏开发过程之中使用真的很广泛，好的数据结构能把游戏之中复杂的问题很高效地解决，所以我们应该在游戏的开发过程之中合理地使用数据结构。