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

数据结构在游戏中的简单应用 /Program/Control/datastruct.htm作者:源代码之光 | 日期:2005-07-26 　　在游戏的编写中，不可避免的出现很多应用数据结构的地方，有些简单的游戏，只是由几个数据结构的组合，所以说，数据结构在游戏编程中扮演着很重要的角色。　　本文主要讲述数据结构在游戏中的应用，其中包括对链表、顺序表、栈、队列、二叉树及图的介绍。读者在阅读本文以前，应对数据结构有所了解，并且熟悉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 RefreshBullet();　　　　　　　// 刷新子弹　　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 RefreshBullet()中，我们只要将链表历遍一次就行，将子弹的各种数据更新，其中主要的源代码如下：　　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表示能通过。　　我们生成如下地图：　　TI