在游戏的编写中,不可避免的出现很多应用数据结构的地方,有些简单的游戏,只是由几个数据结构的组合,所以说,数据结构在游戏编程中扮演着很重要的角色。
本文主要讲述数据结构在游戏中的应用,其中包括对链表、顺序表、栈、队列、二叉树及图的介绍。读者在阅读本文以前,应对数据结构有所了解,并且熟悉 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的地图系统大概就是这 样。我们这样定义每个图块:[Page]
struct TILE // 定义图块结构
{
int
本文主要讲述数据结构在游戏中的应用,其中包括对链表、顺序表、栈、队列、二叉树及图的介绍。读者在阅读本文以前,应对数据结构有所了解,并且熟悉 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的地图系统大概就是这 样。我们这样定义每个图块:[Page]
struct TILE // 定义图块结构
{
int
