人工智能、数理算法

oraclelang

做到这一步，许多游戏的需求都已经满足了。但是，总是有人希望近一步优化，而且方法也是非常陈旧的：继续对物体的各个部分进行细分，对每个部件做AABB的矩形，那这个优化以后的系统就叫做OBB系统。虽然说这个优化以后的系统也不错，但是，许多它可以运用到的地方，别人却不爱使用它，这是后面会继续介绍的地方。

oraclelang

John Carmack不知道看的哪本书，他早在DOOM中已经使用了BSP系统（二分空间分割），再加上一些小技巧，他的碰撞做得就非常好了，再加上他发明的castray算法，DOOM已经不存在碰撞的问题，解决了这样的关键技术，我想他不再需要在什么地方分心了，只要继续研究渲染引擎就可以了。（Windows游戏编程大师技巧P392～P393介绍）（凸多边形，多边形退化，左手定律）SAT系统非常复杂，是SHT（separating hyperplane theorem，分离超平面理论）的一种特殊情况。这个理论阐述的就是两个不相关的曲面，是否能够被一个超平面所分割开来，所谓分割开来的意思就是一个曲面贴在平面的一边，而另一个曲面贴在平面的另一边。我理解的就是有点像相切的意思。SAT是SHT的特殊情况，所指的就是两个曲面都是一些多边形，而那个超平面也是一个多边形，这个超平面的多边形可以在场景中的多边形列表中找到，而超平面可能就是某个多边形的表面，很巧的就是，这个表面的法线和两个曲面的切面是相对应的。接下来的证明，我想是非常复杂的事情，希望今后能够找到源代码直接运用上去。而我们现在讲究的快速开发，我想AABB就足以满足了。

oraclelang

3D碰撞检测

3D的检测就没有什么很标准的理论了，都建立在2D的基础上，我们可以沿用AABB或者OBB，或者先用球体做粗略的检测，然后用AABB和OBB作精细的检测。BSP技术不流行，但是效率不错。微软提供了D3DIntersect函数让大家使用，方便了许多，但是和通常一样，当物体多了以后就不好用了，明显的就是速度慢许多。

oraclelang

碰撞反应

碰撞以后我们需要做一些反应，比如说产生反冲力让我们反弹出去，或者停下来，或者让阻挡我们的物体飞出去，或者穿墙，碰撞最讨厌的就是穿越，本来就不合逻辑，查阅了那么多资料以后，从来没有看到过需要穿越的碰撞，有摩擦力是另外一回事。首先看看弹性碰撞。弹性碰撞就是我们初中物理中说的动量守恒。物体在碰撞前后的动量守恒，没有任何能量损失。这样的碰撞运用于打砖块的游戏中。引入质量的话，有的物体会是有一定的质量，这些物体通常来说是需要在碰撞以后进行另外一个方向的运动的，另外一些物体是设定为质量无限大的，这些物体通常是碰撞墙壁。

oraclelang

当物体碰到质量非常大的物体，默认为碰到了一个弹性物体，其速度会改变，但是能量不会受到损失。一般在代码上的做法就是在速度向量上加上一个负号。

绝对的弹性碰撞是很少有的，大多数情况下我们运用的还是非弹性碰撞。我们现在玩的大多数游戏都用的是很接近现实的非弹性碰撞，例如Pain-Killer中的那把吸力枪，它弹出去的子弹吸附到NPC身上时的碰撞响应就是非弹性碰撞；那把残忍的分尸刀把墙打碎的初始算法就是一个非弹性碰撞，其后使用的刚体力学就是先建立在这个算法上的。那么，是的，如果需要非弹性碰撞，我们需要介入摩擦力这个因素，而我们也无法简单使用动量守恒这个公式

oraclelang

我们可以采取比较简单的方法，假设摩擦系数μ非常大，那么只要物体接触，并且拥有一个加速度，就可以产生一个无穷大的摩擦力，造成物体停止的状态。

基于别人的引擎写出一个让自己满意的碰撞是不容易的，那么如果自己建立一个碰撞系统的话，以下内容是无法缺少的：

•         一个能够容忍的碰撞系统

–     一个从概念上可以接受的物理系统

–     质量

–     速度

–     摩擦系数

–     地心引力

oraclelang

基2快排原理与代码

基2快排实际上是基数排序，因为它速度特别快。是O(n)级的，所以偶叫他基2快排 ：）


它的基本原理是桶排，不过大家想必知道桶排有多么吃内存....想要排32位的整数需要4GB的BUFFER....恐怖吧~所以只好以时间换空间~减少空间开销，多画一点时间了。基数排序其实就是多趟桶排。


什么是基数排序？基数大家都应该知道....比如说10进制的基数就是10。我们比较10进制的数是怎么比较的？肯定是先看最高位，然后向个位发展...基数排序和这个原理是一样的。不过我们比较喜欢选择用2的整数次幂作为基数~因为除以2的整数次幂的时候可以用位移~


OK。废话不多说。来说一下基2快排函数的思路（以下都是伪代码）。


我们假设函数入口传入了原数组src以及长度N。那么，肯定要开一个计数器（因为毕竟是基于桶排的嘛~） count，还有一个临时数组temp[N]。我们以2^8作为基数，排序32位整数为例。


for 4 次(i=0,1,2,3)
{
ZeroMemory(count); //显然是要清空计数器的
memcpy(temp,src,n*4)；//以后的操作都是对temp操作的，最后以temp为原拷贝回src去
For k=0 to N-1
{
  ++count[(temp[k]>>(8*i))&0xFF];//在这里进行桶排
}


entry_point=0;//这个变量记录了每个计数器数据经过排列后在数组中的位置


for k = 0 to 256
{
_temp=count[k];
count[k]=entry_point; //把相应数据个数变成了相应数据在数组中的位置
entry_point+=_temp; //显然是要把BASE ENTRY_POINT推后的~
}


for k=0 To N
src[count[(temp[k]>>(8*i))&0xFF]++]=temp[k]; //这里有点难理解。这个语句的意思是根据数组中这个数字相应“位”（相当于10进制的个位、十位）的位置把这个数字拷贝回原数组中，这样就对这个“位”排过序了


}


最后送上例子代码……可能有错……而且大家可以看到偶的语文水平确实8行，欢迎大家拍偶的砖

oraclelang

一种快速可预制的随机数组产生方法 wxh zt




本文介绍了一种简单、快捷、实用的随机数组产生方法，经调试通过。附件为全部程序代码请审阅。

oraclelang

在工程软件的设计和安全系统设计中，建立模型、产生密码经常需要使用到随机数组。然而计算机不会产生绝对随机的随机数，计算机只能产生“伪随机数”。其实绝对随机的随机数只是一种理想的随机数，即使计算机怎样发展，它也不会产生一串绝对随机的随机数。计算机只能生成相对的随机数，即伪随机数。

oraclelang

伪随机数并不是假随机数，而是指有规律的数，事实上都是由计算机经过一定的算法计算得到的。大家常用的方法是根据一个给定的数作为种子，如采用变化的时间作为种子，调用srand((unsigned)time(NULL))后执行rand()从而获得一个随机数。很显然，相同或相近的种子得到的随机数将会是完全一样或互相接近。