|
《Windows游戏编程大师技巧》（第二版）第11章(1)
第三部分：核心游戏编程
第11章 算法、数据结构、内存管理和多线程
第12章 人工智能
第13章 游戏物理
第14章 文字时代
第15章 综合运用：编写游戏！
第11章 算法、数据结构、内存管理和多线程
"You think I can get a hug after this?"
—Bear, Armageddon（电影《世界末日》）
本章将讨论在其他游戏编程参考书常常会中疏漏的细节问题。我们将涉及编写可保存进度的游戏、演示的制作、优化理论等所有内容。本章将帮您掌握这些必需的编程细节。这样，当我们在下一章讨论人工智能的时候，你已很好地掌握了一些游戏编程的一般概念，甚至连3D运算都不再能难倒你！ 本章主要内容如下：
• 数据结构
• 算法分析
• 优化理论
• 数学运算技巧
• 混合语言编程
• 游戏的保存
• 多人游戏的实现
• 多线程编程技术
数据结构
“游戏所应当采用哪种数据结构？”，这几乎是我最常被问到的问题。答案是：最快速最有效率的数据结构。然而，在大多数情况下，你并不需要采用那些所谓最先进也最复杂的数据结构。正相反，你应该尽可能将其简化。在速度比内存更重要的今天，我们宁可先牺牲内存！ 记住这一点，我们先来看几个最常用于游戏的数据结构，并给你何时以及如何使用这些数据结构的建议。 静态结构和数组 数据结构最基本的形式，当然就是一个数据项单独出现的形式，如一个结构或类。如下所示：
typedef strUCt PLAYER_TYP // tag for forward references
{
int state; // state of player
int x,y; // position of player
// ...
} PLAYER, *PLAYER_PTR;
C++
在C++中，你不必使用typedef来定义一个结构类型；当你使用到关键字struct时，编译器会自动为之创建一个类型。此外，C++的struct甚至可以包含方法、公有和私有部分。 PLAYER player_1, player_2; // create a couple players
在这个例子中，一个带有两个静态定义的记录的数据结构就解决问题了。另一方面，如果游戏玩家多于三个，那么较好的做法是采用如下所示的数组：
PLAYER players[MAX_PLAYERS]; // the players of the game
这样，你便可以用一个简单的循环来处理所有的游戏玩家了。Okay，非常好，但是如果在游戏运行以前你不知道会有多少玩家或记录参数，那又该如何呢？
当出现这种情况时，我们应计算出数组所可能具有的元素个数的最大值。如果数目较小，如256或更小，并且每个数组元素也相当的小（少于256字节），我通常会采用静态分配内存，并使用一个计数器来计算某个时刻已激活的元素的数目。
你也许觉得这对于内存而言是一种浪费。但是它比遍历一个链表或动态结构要容易和快速得多。关键在于，如果你在游戏运行前知道数组元素的数目，并且数目不是太大，那么就在游戏启动时通过调用函数malloc()或new()来静态地预先分配内存。
| 
