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

数据结构在游戏中的简单应用2010-06-09在游戏的编写中,不可避免的出现很多应用数据结构的地方,有些简单的游戏,只是由几个数据结构的组合,所以说,数据结构在游戏编程中扮演着很重要的角色。

本文主要讲述数据结构在游戏中的应用,其中包括对链表、顺序表、栈、队列、二叉树及图的介绍。读者在阅读本文以前,应对数据结构有所了解,并且熟悉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;  // 查找运算
  }

经过上面的分析,在游戏中,链表主要应用在有大规模删除,添加的应用上。不过,它也有相应的缺点,就是查询是顺序查找,比较耗费时间,并且存储密度较小,对空间的需求较大。

如果通过对游戏数据的一些控制,限定大规模的添加,也就是确定了内存需求的上限,可以应用顺序表来代替链表,在某些情况下,顺序表可以弥补链表时间性能上的损失。当然,应用链表,顺序表还是主要依靠当时的具体情况。那么,现在,进入我们的下一节,游戏中应用最广的数据结构 — 顺序表。