数据结构在游戏中的简单应用

在游戏的编写中，不可避免的出现很多应用数据结构的地方，有些简单的游戏，只是由几个数据结构的组合，所以说，数据结构在游戏编程中扮演着很重要的角色。
　　本文主要讲述数据结构在游戏中的应用，其中包括对链表、顺序表、栈、队列、二叉树及图的介绍。读者在阅读本文以前，应对数据结构有所了解，并且熟悉C/C++语言的各种功用。好了，现在我们由链表开始吧！
数据结构在游戏中的简单应用
1、链表
　　在这一节中，我们将通过一个类似雷电的飞机射击游戏来讲解链表在游戏中的应用。在飞机游戏中，链表主要应用在发弹模块上。首先，飞机的子弹是要频繁的出现，消除，其个数也是难以预料的。链表主要的优点就是可以方便的进行插入，删除操作。我们便将链表这一数据结构引入其中。首先，分析下面的源代码，在其中我们定义了坐标结构和子弹链表。

　　struct CPOINT
　　{
　　　　int x;　　// X轴坐标
　　　　int y;　　// Y轴坐标
　　};

　　struct BULLET
　　{
　　　　struct BULLE* next;　　// 指向下一个子弹
　　　　CPOINT bulletpos;　　　// 子弹的坐标
　　　　int m_ispeed;　　　　　// 子弹的速度
　　};

　　接下来的代码清单是飞机类中关于子弹的定义：

　　class CMYPLANE
　　{
　　public:
　　　　void AddBullet(struct BULLET*);　　// 加入子弹的函数，每隔一定时间加弹
　　　　void ***Bullet();　　　　　　　// 刷新子弹
　　privated:
　　　　struct BULLET *st_llMyBullet;　　　// 声明飞机的子弹链表
　　};

　　在void AddBullet(struct BULLET*)中，我们要做的操作只是将一个结点插入链表中，并且每隔一段时间加入，就会产生连续发弹的效果。
　　这是加弹函数主要的源代码：

　　void AddBullet(struct BULLET*)
　　{
　　　　struct BULLET *st_llNew,*st_llTemp;　　// 定义临时链表
　　　　st_llNew=_StrucHead;　　　　　　　　　 // 链表头（已初始化）
　　　　st_llNew->(BULLET st_llMyBullet *)malloc(sizeof(st_llMyBullet));　　// 分配内存
　　　　st_llTemp= =_NewBullet;　　　　　　　　// 临时存值
　　　　st_llNew->next=st_llTemp->next; st_llTemp->next=st_llNew;
　　}

　　函数Void ***Bullet()中，我们只要将链表历遍一次就行，将子弹的各种数据更新，其中主要的源代码如下：

　　while(st_llMyBullet->next!=NULL)
　　{
　　　　// 查找
　　　　st_llMyBullet->bulletpos.x-=m_ispeed;　　// 更新子弹数据
　　　　………
　　　　st_llMyBullet=st_llMyBullet->next;　　　 // 查找运算
　　}

　　经过上面的分析，在游戏中，链表主要应用在有大规模删除，添加的应用上。不过，它也有相应的缺点，就是查询是顺序查找，比较耗费时间，并且存储密度较小，对空间的需求较大。
　　如果通过对游戏数据的一些控制，限定大规模的添加，也就是确定了内存需求的上限，可以应用顺序表来代替链表，在某些情况下，顺序表可以弥补链表时间性能上的损失。当然，应用链表，顺序表还是主要依靠当时的具体情况。那么，现在，进入我们的下一节，游戏中应用最广的数据结构 — 顺序表。

2、顺序表
　　本节中，我们主要投入到RPG地图的建设中，听起来很吓人，但是在RPG地图系统中（特指砖块地图系统），却主要使用数据结构中最简单的成员 — 顺序表。
　　我们规定一个最简单的砖块地图系统，视角为俯视90度，并由许多个顺序连接的图块拼成，早期RPG的地图系统大概就是这样。我们这样定义每个图块：

　　struct TILE　　// 定义图块结构
　　{
　　　　int m_iAcesse;　　// 纪录此图块是否可以通过
　　　　……　　　　　　　// 其中有每个图块的图片指针等纪录
　　};

　　当m_iAcesse=0,表示此图块不可通过，为1表示能通过。
　　我们生成如下地图：

　　TILE TheMapTile[10][5];

　　并且我们在其中添入此图块是否可以通过，可用循环将数值加入其中,进行地图初始化。
　　如图表示：

表1

　　根据条件，我们可以用如下普通算法来判定怪物的反应：

　　if(d<100) state=嘲笑，单挑;
　　else if(d<200) state=单挑;
　　　　else if(d<300) state=嗜血魔法;
　　　　　　else if(d<400) state=呼唤同伴;
　　　　　　　　else state=逃跑;

　　上面的算法适用大多数情况，但其时间性能不高，我们可以通过判定树来提高其时间性能。首先，分析主角生命值通常的特点，即预测出每种条件占总条件的百分比，将这些比值作为权值来构造最优二叉树（哈夫曼树），作为判定树来设定算法。假设这些百分比为：

表2

　　构造好的哈夫曼树为：

图2

　　对应算法如下：

　　if(d>=200)&&(d<300) state=嗜血魔法;
　　else if(d>=300)&&(d<500) state=呼唤同伴;
　　　　else if(d>=100)&&(d<200) state=单挑;
　　　　　　else if(d<100) state=嘲笑，单挑;
　　　　　　　　else state=逃跑;

　　通过计算，两种算法的效率大约是2:3，很明显，改进的算法在时间性能上提高不少。
　　一般，在即时战略游戏中，对此类判定算法会有较高的时间性能要求，大家可以对二叉树进行更深入的研究。现在，我们进入本文的最后一节：图的介绍，终于快要完事了。

5、图
　　在游戏中，大多数应用图的地方是路径搜索，即关于A*算法的讨论。由于介绍A*算法及路径搜索的文章很多，这里介绍图的另一种应用：在情节脚本中，描述各个情节之间的关系。
　　在一个游戏中，可能包含很多分支情节，在这些分支情节之间，会存在着一定的先决条件约束，即有些分支情节必须在其他分支情节完成后方可开始发展，而有些分支情节没有这样的约束。
　　通过分析，我们可以用有向图中AOV网（Activity On Vertex Network）来描述这些分支情节之间的先后关系。好了，现在假如我们手头有这样的情节：

图3