Author: orient

2D渲染引擎中的脏矩形技术

Posted on by orient

2D游戏技术其实都已经很古老了，主要包括像素运算，Blt，脏矩形等一些技术。 所谓脏矩形技术，就是哪里脏了，就（仅仅）把脏了的那块区域重绘。而不是每次直接性的重绘。 其基本条件是：脏矩形的计算和绘制的代价小于直接性重绘。换句话说，如果一个屏幕每一帧变化的东西太多的话，就不值得用这个古老的算法了。 脏矩形要解决的两个问题是： （1） 什么叫脏，即什么情况下会弄脏 当我们的游戏中的元素（通常是RenderObject）发生位置，大小，方向，动画，添加，删除等操作时，那么该元素原来对应的区域会弄脏，同时，新对应的区域也同样被弄脏。 （2） 弄脏的区域该怎么办 把场景分成一个一个的格子（比如12864或者6432,矩形格或菱形格）； 每个格子，有一个是否脏的标记，以及其上的RenderObject列表； 每个RenderObject，可以保存一个对应的格子列表(当然，也可以计算，并且，实际上有两个格子列表，变化之前和变化之后分别对应一个格子列表，对于变化前的，对应的格子列表中的每个格子应当删除该物体，对于变化后的，对应的格子列表中的每个格子应当添加该物体) 每次绘制时，按照某种顺序，绘制脏了的格子； 每个脏了的格子，按照某种顺序，将其上的RenderObject裁剪绘制到格子的区域上; 关于脏矩形技术的必要性，cloud在《我的编程感悟》一书中已经有了详细的论证。此外，书中提到的关于Blt的汇编优化，逆向画家算法，图像压缩，精灵优化，滚屏优化,以及限制内存大小的思想，都是2D游戏值得借鉴的。

异或运算XOR的一些相关技巧

Posted on by orient

异或运算(XOR)特点： X xor X = 0 X xor 0 = X X xor Y = Y xor X (X xor Y) xor Z = X xor (Y xor Z) 利用异或可以巧妙地实现一些玩意，例如： 不用中间临时变量交换两个整数； XOR linked list：只用一个指针实现双向链表

stl之争

Posted on by orient

以前，是否使用STL是有争议的，因此很多公司都实现了自己的一套STL。 其实STL有很多有意思的设计，比如实现了数据结构和算法的分离，这也是STL设计的核心思想。 在实现上，STL源代码也是能够给人一些启发的。比如sort算法的实现(这应该不是STL的开创)，sort主要采用快速排序，对于初步有序的短系列，采用插入排序，对于快速排序的极端情况，还可能使用堆排序。 性能方面，STL作为通用库，一般来说效率还是比较高的。但是，在大型游戏领域和内存受限领域，以及由于STL在不同平台上的实现不同，其性能还需要改进。关于这一点，可以参考http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html这篇论文，论文还提供了一个性能对比图。 扩展性上，个人认为，仿函数，适配器还是有比较好的扩展性，Allocator（1998 ISO C++）则争议很大，上述论文和http://www.openstd.org/jtc1/sc22/wg21/docs/papers/2005/n1850.pdf这篇论文有比较详细的解释。 易用性上，STL同样备受争议。这主要表现在： （1）需要对库的实现有相当的理解，由于依赖于模版与泛型，然后又加上C++语言，滥用极可能带来性能的严重损失，难以发现的一些Bug等。 （2）调试的不方便，源码也缺乏文档和注释。 （3）一些局部的瑕疵, 比如缺少像树这种层级结构的容器，比如list的sort函数也违背了数据结构和算法的分离思想。 总而言之，作为通用库，STL还是比较不错的，而在某些对性能要求更高的领域，最好慎用。 对STL的改进和替换方面方面，可以参考： EASTL: EASTL依然沿用STL的基本思想，在实现上改进了STL，是一个性能更高，更易于调试的STL。 Doom3: 完全抛弃了迭代器，是一个比较简单，但是非常实用的STL。