游戏开发中常用的数据结构浅析

李俊琴

摘要：数据结构与算法是计算机软件开发和应用人员必备的专业基础。游戏程序是一种复杂度较高的计算机软件，因此其中的数据结构设计非常重要。该文对游戏开发中常用的方法进行总结，分析了数组、链表、栈、队列、树等等数据结构在游戏中的应用。

关键词：游戏开发；数据结构；链表

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）27-6483-02

Abstract： Data structure and algorithm is a professional basic ability of computer software development and application of personnel necessary. The game program is a kind of high complexity of computer software， so the data structure design is very important. In this paper， the method commonly used in game development are summarized， analyzed the application of array， linked list， stack， queue， tree data structure in game program.

Key words： game program；data struct； linked list

数据结构是计算机存储、组织数据的方式，是相互之间存在一种或多种特定关系的数据元素的集合。在软件开发中，数据结构设计合理可以带来更高的运行或者存储效率。游戏软件区别于一般的普通应用软件，它要求响应更快速，计算更精确，通常要组织、管理更多媒体资源。因此数据结构的设计，在游戏开发中非常重要。该文从常用的数据结构入手，分析它们在游戏开发中的实际应用。

1 数组

数组是最简单的数据结构，很容易理解。在程序设计中，常常把具有相同类型的若干变量按数组的形式组织起来。数组元素的查找要按照索引顺序依次进行；根据已知索引来读取数组元素非常方便；插入删除操作都要维持数组元素原来的约定，因此需要移动较多元素。数组中的元素也可以是数组类型，这就构成了二维数组、多维数组。

数组的排序有很多算法，因此很多游戏中需要排序的功能就可以由数组来实现。例如游戏中的某种分值排行功能、对某种属性选取最值的功能等，都可以用一维数组来实现。

用二维数组来表示地图，是目前很多类型游戏设计中常用的方法。例如推箱子游戏的地图、塔防游戏的地图、酷跑类游戏的地图、棋盘类游戏的棋盘等等，都可以由二维数组的方式来实现。以推箱子游戏为例，图1是某关卡的显示界面，图2是程序代码中二维数组表示的地图：

如图1所示，游戏界面中展示出推箱子游戏中所有的元素，包括通道、墙、箱子、人物等等。在游戏进行中，玩家按下方向键，人物要相应地推动箱子并移动，游戏界面要相应地变化，这是推箱子游戏应该完成的基本功能。使用二维数组来描述地图数据，可以很好地完成这一功能。如图2所示，对地图中所有的元素进行分析，可以得到8种类型，由数字编码0-7来表示。之后根据游戏地图大小，设计m行n列的二维数组，其中各元素就是8种地图类型的编码。按照当前关卡初始地图的样子，就可以得出如图2中的原始地图数据。在游戏进行中，玩家按键导致人物移动后，可以根据推箱子的游戏逻辑相应地修改某些地图数据中的元素，之后游戏按照新的地图数据更新游戏界面即可。需要注意的是，关卡的原始地图数据不能改变，否则下次游戏无法进行，因此在游戏中修改的应该是原始地图的临时拷贝。

2 链表

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

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

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

3 栈和队列

栈和队列都是操作受限的、特殊的线性表。栈只能在栈顶插入和删除元素，特点是后进先出（LIFO）；队列只能在队尾插入元素，在队头删除元素，其特点是先进先出（FIFO）。因此，栈和队列非常适合用来解决递归、排队类的问题。

递归设计在游戏开发中应用很普遍，例如迷宫类游戏、汉诺塔游戏、棋类游戏等。而为了提高效率，减少递归函数的多次调用，游戏程序中通常利用对栈的操作来代替直接的递归函数设计。很多情况下栈和队列要结合使用。

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

4 树

树是一对多的数据结构。非空树只有一个根节点，而树中的任意节点都可以有多个孩子结点。也就是说，树中的任意节点，只可能有一个前驱，但可能有多个后继。树的存储一般采用链式结构，父节点总是有多个指向子节点的指针，而子节点最多有一个指向父节点的指针。

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

除此之外，在一些拥有众多游戏对象的场景中，常使用四叉树来进行管理。例如，在一个游戏场景中有1000个随机运动的小球，程序需要在游戏的每一帧检测它们的碰撞信息，之后进行下一步处理，如下图所示。

5 结束语

数据结构在游戏软件开发中的应用非常广泛，远远超过本文所论述的内容。好的数据结构设计，能将游戏软件中复杂的功能更简单更高效地解决，为游戏的核心逻辑、游戏玩法、游戏规则等提供了很重要的辅助设计作用。希望本文浅显的分析能带给读者一些思考，更多地将数据结构运用到游戏软件开发中去。

参考文献：

[1] 严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2011.

[2] [美]拉莫斯. Windows游戏编程大师技巧[M].北京：人民邮电出版社，2011.

[3] 秦海玉.Windows游戏程序设计基础[M].北京：电子工业出版社，2011.

[4] 王佳婧，冯长宝，孙沫丽.浅谈数据结构在网络游戏程序开发中的应用[J].消费电子，2013（6）.

[5] 葛亚平，李春生，王巧玲.数据结构在游戏中的应用[J].今日科苑，2007（8）.