游戏中对象选取的方法
作者：Panic
原文出处：Panic在本站的Blog
对于PC游戏，在鼠标大行其道的今天，如何由鼠标的位置判定其下的对象是什么，是几乎所有游戏都必须面对的问题。
以下提供几种方法，仅供参考。
1，包围框法。一般的，对游戏中的每个对象创建一个伴随的包围框，通过遍历所有可见对象，判定鼠标坐标点是否落在某个包围框的内部来获取其选取的对象。
这种方法的优点是简单，算法容易理解，当使用矩形包围框，而对象数量又比较有限的时候，效率也是很好的。缺点是选取不够精确，无法对对象的细节做选取。
在2D游戏中，包围框一般是矩形，或者是若干个矩形的组合，而3D游戏使用包围盒，或者包围球或其组合等方式。无论具体方式如何，其算法实质都是一样的。
2，枚举法。效率最低的方法之一。
和1，包围框法类似，它也需要遍历所有可见对象，但是由于缺少包围盒机制，只能检测对象位于鼠标下的那个位置是否有有效象素，或者有效的alpha值，对3D对象而言，就是检查鼠标点形成的选取射线是否穿越对象的某个面片。
这种方法可以实现很精确的选取，但是由于效率太低，所以很少直接使用，一般先使用方法1减少遍历对象的数量之后，再使用这个方法达到精确的选取。
3，反馈法。这是一个很有效，也很快捷的方法，尤其在3D游戏中，有无可比拟的优越性。
反馈法的实现很简单，首先要维护一个后台缓冲区，当绘制目标对象的时候，同时将对象的可见信息(一般是对象图片的Alpha值，或者Z值)
写入后台缓冲，然后检测鼠标对应的缓冲区的位置的值是否有变化，如果变化了，表明刚才绘制的对象可以被鼠标选中。当缓冲使用了复杂一些的Z运算的时候，我们在绘制完成之后，就可以得到一个鼠标可以选取的对象列表，然后只要简单的根据一定的原则从这个列表中提取需要的对象就可以了。这个机制在2D下，一般不维护额外的缓冲区而直接使用绘图缓冲区。3D下，像OpenGL提供了内置的反馈方法，更方便了用户的使用。实际也可以利用Z
buffer，模板缓冲等实现类似的机制。
这种方法可以实现精确到象素级的选取，而几乎不影响运行效率。缺点是需要对绘制部分的代码有很高的控制权限。
4，直接映射法。这也是一个高效算法，可以达到O(1)的时间复杂度。常见于2D战棋类游戏中。
在这类游戏中，场景是用一个二维表存储的，表的每个项，保存着它上面的对象信息，我们可以通过一个简单的算法，由当前的鼠标位置得到表的索引，然后直接读取索引对应的项就完成了选取。
在固定视角的3D游戏甚至非固定视角的3D游戏中，也可以使用这种方法。这种方法的缺点是对象在场景中，只能是按二维表，或者多层二维表排布的。这种方法对内存空间的需求也比较大。棋牌类游戏比较适合使用这种方法。
由于每种方法都有其固有的优缺点，而对游戏而言，场景又千变万化，复杂纷繁。为了能适应实际的需求，上面的方法可以组合使用，从而扬长避短，更好的达成需求。
其他一些复杂的选取，比如范围选取(框选)等，也可以由以上几种基本的方法演化而来。
以下是对前面反馈法的补充-反馈法的2D基本实现：
这里直接使用后台绘制缓冲区作为选取缓冲区。
首先规定一种透明色，这种颜色不允许出现在对象和背景的任何非透明部分，例如规定
trans = RGB(0,0,0);
为透明色。
假设绘图缓冲区为一个二维数组：
color buf[h][w];
当前鼠标对应的缓冲区坐标为
(x,y)
需要绘制的对象列表为一维数组
object array[count];
最终获取选中的对象的栈
objstack;
伪代码如下：
color old = buf[y][x];
buf[y][x] = trans;
for( int i = 0; i < count; i++ )
{
draw(array[i]);
if( buf[y][x] != trans )
{
old = buf[y][x];
buf[y][x] = trans;
objstack.push(array[i]);
}
}
buf[y][x] = old;
完成这个步骤之后，objstack中保存的就是按照绘制顺序排序的，鼠标下面所有对象的集合。你只要从中提取需要的对象就可以了。
