网络游戏开发的灵魂-课件.pptVIP

1游戏程序的灵魂——算法

•程序是什么呢?

•一条著名的公式给了我们答案：

•程序=数据结构+算法

•程序语言(如C++)是一种工具．而算法是

程序的灵魂。

1游戏程序的灵魂——算法

•你在优美如画的游戏世界里休闲地散步，

很不幸，一只妖怪盯上了你，而且它足够

聪明，它会选择一条最短的路径向你杀过。

为什么这只妖怪那么聪明?

•这就是A*(读A星)算法的魔力．A*算法是一种寻找最短路径的寻路算法。

•在游戏场景里．近处的游戏角色会遮挡住

远处的角色。

•要做到这一点．一种方法是可以把所有的

角色按其坐标值进行排序．然后以远到近

把玩家“放”入到游戏场景里。常用的排

序算法有四种：选择排序、冒泡排序、插

入排序和快速排序。

2游戏数据的大管家——数据结构

•经典的数据结构，在网络游戏中都能得到

体现。

•

1．道具包管理——线性表

•在任何网络游戏中．你的道具包里也会放

着许多珍贵的道具。在程序中需要把这些

数据组织起来．方便管理。使用线性表可

以简单方便地做到。

•2．任务管理——队列与堆栈

•我在开始玩《梦幻西游》时，在城里走了几圈就

接了满身的任务。这让我很烦恼，不知从哪个任

务开始做起，这时我想到了队列。队列是一种

“先进先出(first—in—first——out，FIFO)”的数据

结。就好像是在银行里排队，排在前面的先服务。

每次接到任务就把该任务压进任务队列里，要做

任务时就从任务队列里取出一个任务，这样哪个

任务先接到就先做哪个任务。

•也许你不喜欢这样方式．你想做一个赏金

猎人．哪个任务报酬多的就先做哪个任务。

这样普通的队列就满足不了你的需求了。

你需要的是优先级队列。优先级队列在插

入元素时．优先级高的元素插到队列前。

把任务的报酬设成是优先级数据。

•3．游戏菜单设计——树

•树的一个比较形象的应用是游戏中的UI(User

Interface用户界面)。在UI里的菜单一般是分级

的．如在主UI里可能会有“进入游戏”、“选

项”、“退出游戏”这几个菜单项．在“进入游

戏”里又会有“创建新角色”和“使用旧角色”

两个菜单项．而进入“选项”后会有“音频”、

“视频”、“游戏设置”等等。使用树来管理这

些菜单是很合适的做法。

•4．地图数据管理——图

•游戏地图是图的应用的一个很好的例子。游戏中

的地图一般会被分成一块块的格子．每一块都会

有一个坐标值。那么可以使用二维数组把地图的

数据记录起来，这是最简单的方法。但大家都知

道．鱼与熊掌是不能兼得的，这种方法只能用在

很小型的地图上，而较专业的做法是使用图记录

地图数据，图的每一个节点对应的是地图的一个

坐标。

3正确的学习途径

•学习数据结构与算法是很枯燥乏味的，但

不要想找什么捷径，只有理解后反复上机

练习、练习再练习!使用过STL(C++标准模

板库)的读者可能会问：既然已经有人帮我

们实现了各种数据结构与算法。为什么还

要自己去学习呢?我们要学习的是蕴涵在数

据结构与算法中的思想。我们要理解的是

“为什么要这样做”．而不只是停留在

“怎样做”，只有理解了这些思想．才能

写出更加合理、高效的程序。

•学习数据结构从最简单的出发．

•你需要花一个星期的时间在数组线性表．它的难点主要是

在插入数据和删除数据：链表比数组要难一点，但单向链

表也只需要一个星期的学习时间，然后再花一个星期学习

双向链表向强化练习

•队列和堆栈是很常用的数据结构，你要花两个星期的时间

好好理解一下。

•然后就是树了，从二叉树开始学．大概要两个星期的时间

•最后是图，也是最难的，但有了以前所学的知识作为基础。

相信你只要两个星期的时间就够了。数据结构学习得差不

多，加以应用吧。

•最后花一个月的时间好好研究一下各种算法．

夏每

天个

开孩