|
《Windows游戏编程大师技巧》（第二版）第11章(13) 提示
我很难形容类树结构在3D图形学中有多重要，希望你已经理解了上述内容。否则，当你构造二分空间分区(????)来解决渲染问题时，你将会陷入指针递归的苦海中。：） 你注意到我省略了如何删除一个节点。我是有意这样做的。因为删除一个节点非常复杂，有可能破坏子树的父节点和其与子节点间的连接。我想，删除节点就留作给读者的一个练习好了。这里我向大家建议一本好的数据结构参考书——由Sedgewick撰写，Addison Wesley 出版社出版的《Algorithms in C++》（该书中文版《算法I~IV（C++实现）——基础、数据结构、排序和搜索（第三版）》已由中国电力出版社出版。——编者），这本书深入讨论了树结构及其相关算法。
最后，读者可以检验一下二叉搜索树的一个实例程序——DEMO11_3.CPPEXE。该程序允许你创建一个二叉搜索树并使用三种算法遍历它。这也是一个控制台程序，因此需要正确地编译它。 优化理论
比起编写任何其他程序来说，编写游戏更重视性能优化。视频游戏永无止境地不断突破硬件和软件的极限。游戏编程人员总是希望加入更多的生物、特效、声音以及更好的智能等等。因此，优化至关重要。
在这一节，我们将讨论一些优化技术以帮助你进行游戏编程。如果你对此有浓厚的兴趣，有很多关于该方面的书可以参考，如由Addison Wesley出版社出版、Rick Booth编著《Inner Loops》，由Coriolis 集团出版、Mike Abrash 编著的《Zen of Code Optimization》，AP出版社出版、Mike Schmit编著的《Pentium Processor Optimization》。 运用你的头脑
编写优化代码的第一要旨是理解编译器和数据结构，以及你编写的C/C++程序是如何被最终转换为可执行的机器代码的。基本思想是使用简单的程序设计技巧和数据结构。你的代码越复杂、设计越精巧，编译器将其变换为机器代码就越困难，所以（在大多数情况下）其执行速度也就越慢。以下是编程时需要遵循的基本原则：
• 尽可能使用32位数据。8位数据虽然占用空间较少，但英特尔的处理器是以32位为基准的，并针对32位数据进行了优化。
• 对于频繁调用的小函数而言，应声明为内联函数。
• 尽可能使用全局变量，但避免产生可读性差的代码。
• 避免使用浮点数进行加法和减法运算，因为整数单元通常比浮点单元运算快。
• 尽可能使用整数。尽管浮点处理器几乎和整数处理一样快，但整数更精确。所以如果你不需要精确的小数位，就使用整数。
• 将所有的数据结构均调整为32个字节对齐。在大多数编译器上你可以使用编译器指示字来手工完成，或在代码中使用#pragma。
• 除非是简单类型的参数，否则尽可能不使用值传递的方式传递参数。应当使用指针。
• 在代码中不要使用register关键字。尽管Microsoft声称它能够加快循环，但这会造成编译器没有足够可用的寄存器，结果是生成糟糕的代码。
• 如果你是位C++程序员，用类和虚函数是可以的。但软件的继承和层次不要过多。
• 奔腾级的处理器使用一个内部数据和代码缓存。了解这一点后，要确保函数代码短小以适应缓存的大小（16KB至32KB以上）。此外，在储存数据时，以其将被访问的方式进行存储。这样可以提高缓存的命中率、从而减少访问主存或二级缓存的次数。须知，主内存或二级缓存的访问速度要比内部缓存的访问速度慢10倍。
•
• 奔腾级的处理器具有类似RISC的内核，因此擅长处理简单指令，并能够在数个执行单元内同时处理二个以上的指令。因此，不推荐在一行代码中书写晦涩难懂的代码，最好编写较简单的代码。即使你可以将这些代码合并成具有同样功能的一行代码，也尽量改成简单的。 数学技巧
由于游戏编程中大量的工作在实质上是数学问题，因此了解执行数学运算的更好方法是非常值得的。有许多通用的技巧和方法可供你利用，以提高程序运行速度：
参与整数运算的数必须是整数，参与浮点运算的数必须是浮点数。类型转换必然降低性能。所以除非是迫不得已，否则不要进行类型转换。
通过左移位操作可以实现整数与2的任何次幂的乘法运算。同样地，通过右移位操作可以实现整数与2的任何次幂的除法运算。对于整数与非2的次幂的数的相乘和相除可以转换为和运算或差运算。例如，640虽不是2的整数次幂，但512和128是2的整数次幂；所以当某整数与640相乘最好的方法是进行如下变换：
| 
