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

　　在游戏编写中不可避免出现很多应用数据结构地方有些简单游戏只是由几个数据结构组合所以说数据结构在游戏编程中扮演着很重要角色
　　 本文主要讲述数据结构在游戏中应用其中包括对链表、顺序表、栈、队列、 2叉树及图介绍读者在阅读本文以前应对数据结构有所了解并且熟悉C/C语言各种功用好了现在我们由链表开始吧！

1、链表
　　 在这节中我们将通过个类似雷电飞机射击游戏来讲解链表在游戏中应用在飞机游戏中链表主要应用在发弹模块上首先飞机子弹是要频繁出现消除其个数也是难以预料链表主要优点就是可以方便进行插入删除操作我们便将链表这数据结构引入其中首先分析下面源代码在其中我们定义了坐标结构和子弹链表

　　 =ColorCode>struct CPOINT
　　 {
　　　　 x;　　=ColorCatchword>// X轴坐标
　　　　=ColorCode> y;　　=ColorCatchword>// Y轴坐标
　　=ColorCode>};

　　 struct BULLET
　　 {
　　　　 struct BULLE* next;　　=ColorCatchword>// 指向下个子弹
　　　　=ColorCode>CPOINT bulletpos;　　　=ColorCatchword>// 子弹坐标
　　　　=ColorCode> m_ispeed;　　　　　=ColorCatchword>// 子弹速度
　　=ColorCode>};

　　 接下来代码清单是飞机类中有关子弹定义:

　　 =ColorCode> CMYPLANE
　　 {
　　 public:
　　　　 void AddBullet(struct BULLET*);　　=ColorCatchword>// 加入子弹每隔定时间加弹
　　　　=ColorCode>void RefreshBullet;　　　　　　　=ColorCatchword>// 刷新子弹
　　=ColorCode>privated:
　　　　 struct BULLET *st_llMyBullet;　　　=ColorCatchword>// 声明飞机子弹链表
　　=ColorCode>};

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

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

　　 Void RefreshBullet中我们只要将链表历遍次就行将子弹各种数据更新其中主要源代码如下:

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

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

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

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

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

　　 =ColorCode>TILE TheMapTile[10][5];

　　 并且我们在其中添入此图块是否可以通过可用循环将数值加入其中,进行地图化
　　 如图表示:
0 1 2 3 4 5 6 7 8 9
0 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1 0
2 0 0 0 0 0 1 1 1 1 0
3 0 0 0 0 0 1 1 1 1 0
4 1 1 1 1 1 1 1 1 1 1




图1




　　从上图看到这个地图用顺序表表示非常直接当我们控制人物在其中走动时把人物将要走到下个图块进行判断看其是否能通过比如当人物要走到(10)这个图块我们用如下代码判断这个图块是否能通过:

　　 =ColorCode> IsAcesse(x,y)
　　 {
　　　　 TheMapTile[x,y].m_iAcesse;　　=ColorCatchword>// 返回图块是否通过值
　　=ColorCode>}

　　 上述只是简单地图例子通过顺序表我们可以表示更复杂砖块地图并且现在流行整幅地图中也要用到大量顺序表在整幅中进行分块
　　 好了现在我们进入下节:

3、栈和队列
　　 栈和队列是两种特殊线性结构在游戏当中般应用在脚本引擎操作界面数据判定当中在这节中主要通过个简单脚本引擎来介绍栈队列和栈使用方法很相似便不再举例
　　 我们在设置脚本文件时候通常会规定些基本语法这就需要个解读语法编译这里列出是个语法检查主要功能是检查“()”是否配对实现思想:我们规定在脚本语句中可以使用“()”嵌套那么便有如下规律左括号和右括号配对定是先有左括号后有右括号并且在嵌套使用中左括号允许单个或连续出现并和将要出现有括号配对销解左括号在等待右括号出现过程中可以暂时保存起来当右括号出现后找不到左括号则发生不配对现象从实现角度讲左括号连续出现则后出现左括号应和最先到来右括号配对销解左括号这种保存和和右括号配对销解过程和栈中后进先出原则是致我们可以将读到左括号压入设定栈中当读到右括号时就和栈中左括号销解如果在栈顶弹不出左括号则表示配对出错或者当括号串读完栈中仍有左括号存在也表示配对出错
　　 大致思想便是这样请看代码片断:

　　 =ColorCode>struct　　=ColorCatchword>// 定义栈结构
　　=ColorCode>{
　　　　 m_iData[100];　　=ColorCatchword>// 数据段
　　　　=ColorCode> m_iTop;　　　　　=ColorCatchword>// 通常规定栈底位置在向量低端
　　=ColorCode>}SeqStack;

　　 =ColorCode> Check(SeqStack *stack)　　=ColorCatchword>// 语法检查
　　=ColorCode>{
　　　　 char sz_ch;
　　　　 boolean; Push(stack,\'# \');　　=ColorCatchword>// 压栈#为判断数据
　　　　=ColorCode>sz_ch=getchar;　　　　　　　　　=ColorCatchword>// 取值
　　　　=ColorCode>boolean=1;
　　　　 while(sz_ch!=\'\\n\'&&boolean)
　　　　 {
　　　　　　 (sz_ch= =\'(\')
　　　　　　　　 Push(stack,ch);
　　　　　　 (sz_ch= =\')\')
　　　　　　　　 (gettop(stack)= =\'#\')　 =ColorCatchword>// 读栈顶
　　　　　　　　　　=ColorCode>boolean=0;
　　　　　　　　
　　　　　　　　　　 Pop(stack);　　　　　 =ColorCatchword>// 出栈
　　　　　　=ColorCode>sz_ch=getchar;
　　　　 }
　　　　 (gettop(stack)!=\'#\') boolean=0;
　　　　 (boolean) cout<<\"right\";　　　 =ColorCatchword>// 输出判断信息
　　　　=ColorCode>
　　　　　　 cout<<\"error\";

　　 这里只是介绍脚本读取以后我们在图介绍中会对脚本结构进行深入研究
　　 总的凡在游戏中出现先进后出(栈)先进先出(队列)情况就可以运用这两种数据结构例如帝国时代中地表中间过渡带

4、 2叉树
　　 树应用及其广泛 2叉树是树中个重要类型在这里我们主要研究 2叉树种应用方式:判定树其主要应用在描述分类过程和处理判定优化等方面上
　　 在人工智能中通常有很多分类判断现在有这样个例子:设主角生命值d在省略其他条件后有这样条件判定:当怪物碰到主角后怪物反应遵从下规则:
\" width=450 border=0>
表1




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

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

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

\" width=451 border=0>


表2




　　构造好哈夫曼树为:

\" width=203 border=0>
图2




　　对应算法如下:

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

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

5、图
　　 在游戏中大多数应用图地方是路径搜索即有关A*算法讨论由于介绍A*算法及路径搜索文章很多这里介绍图另种应用:在情节脚本中描述各个情节的间关系
　　 在个游戏中可能包含很多分支情节在这些分支情节的间会存在着定先决条件约束即有些分支情节必须在其他分支情节完成后方可开始发展而有些分支情节没有这样约束
　　 通过分析我们可以用有向图中AOV网(=English>Activity _disibledevent=> 情节编号 情节 先决条件
C1 遭遇强盗 无
C2 受伤 C1
C3 买药 C2
C4 看医生 C2
C5 治愈 C3,C4


　　 注意:在AOV网中不应该出现有向环路否则顶点先后关系就会进入死循环即情节将不能正确发展我们可以采取拓扑派序来检测图中是否存在环路拓扑排序在般介绍数据结构书中都有介绍这里便不再叙述
　　 那么以上情节用图形式表现为(此图为有向图先后关系在上面表格显示):
\" width=210 border=0>
图3




　　现在我们用邻接矩阵表示此有向图请看下面代码片断:

　　 =ColorCode>struct MGRAPH
　　 {
　　　　 Vexs[MaxVex];　　　　　　=ColorCatchword>// 顶点信息
　　　　=ColorCode> Arcs[MaxLen][MaxLen];　　=ColorCatchword>// 邻接矩阵
　　　　=ColorCode>……
　　 };

　　 顶点信息都存储在情节文件中
　　 将给出情节表示成邻接矩阵:

0 1 0 0 0
0 0 1 1 0
0 0 0 0 1
0 0 0 0 1
0 0 0 0 0




图4




　　 我们规定各个情节的间有先后关系但没有被玩家发展用1表示当情节被发展话就用2表示比如我们已经发展了遭遇强盗情节那么C1和C2顶点的间关系就可以用2表示注意并不表示C2已经发展只是表示C2可以被发展了
　　 请看下面代码:

　　 =ColorCode> CRelation
　　 {
　　 public:
　　　　 CRelation(char *filename);　　　　　　　 =ColorCatchword>// 构造将情节信息文件读入到缓存Cache中
　　　　 =ColorCode>void SetRelation( ActionRelation);　　=ColorCatchword>// 设定此情节已经发展
　　　　 =ColorCode>BOOL SearchRelation( ActionRelation); =ColorCatchword>// 寻找此情节是否已发展
　　　　 =ColorCode>BOOL SaveBuf(char *filename);　　　　　　=ColorCatchword>// 保存缓存Cache到文件中
　　　　=ColorCode>……
　　 privated:
　　　　 char* buf;　　　　　　　　　　　　　　 　=ColorCatchword>// 邻接矩阵内存缓冲
　　　　 =ColorCode>……
　　 };

　　 在这里我们将表示情节先后关系邻接矩阵放到缓冲内通过接口进行情节关系修改在BOOL SearchRelation( ActionRelation)中我们可以利用广度优先搜索思路方法进行搜索介绍这方面书籍很多代码也很长在这里我就不再举例了
　　 我们也可以用邻接链表来表示这个图不过用链表表示会占用更多内存邻接链表主要优点是表示动态图在这里并不适合
　　 另外图另个应用是在寻路上著名A*算法就是以此数据结构为基础人工智能也需要它基础好了本节结束
　　 终于可以歇歇了经过这么 5节路程想必大家对数据结构在游戏中用途有了大致了解数据结构其实在游戏中应用方面很多这里只是介绍了小部分希望大家和我起多交流游戏编程经验由于作者本人经验有限难免在文章中出现疏漏还望大家指教我电子邮箱([email protected])

Tags:  数据结构图的应用 数据结构算法与应用 数据结构的应用 数据结构应用

延伸阅读

• 2008-12-13-- 数据结构的特点:数据结构的合理化
• 2009-2-12-- 数据结构应用:数据结构在游戏中的简单应用
• 2010-3-21-- 韩国人的意淫:有关更松散开放的数据结构的意淫