gameloft-数学算法.doc

1 Introduction PurposeandScope Abbreviation Reference Other 42 Mathematicsin2DGames 定点数 定点数的的应用 定点数算法 距离的计算 点到点 点到直线 三角函数 碰撞和裁剪 点和矩形 直线和矩形 矩形和矩形 剪裁区域 其他算法 平方根 排序 环行队列 5ListofTablesTable21Thefirsttable’scaption. 4Table22Thesecondtable’scaption. 4ListofFiguresFigure21Thefirstfigure’scaption. 4Figure22Thesecondfigure’scaption. 4IntroductionPurposeandScopeAbbreviation<Forexample:>GD GameDesignReference<Informof:No.,AuthorNameor/panyName,DocumentName,DocumentVersion,DocumentID(optional).Forexample:>YuFei,Gameloft,“GameDesignSpecification”,<Optional><Ifyouhaveanyintroductioninformationspecifictothisdocument,pleasewritethemhereoraddanew“Heading2”toholdthem.>Mathematicsin2DGames定点数定点数就是用整数来表示浮点数。方法是把浮点数扩大一定倍数,取整成整数。在计算机里,这个倍数通常是2的幂,这样方便快速计算。定点数的的应用由于手机通常不支持浮点数,J2ME也不支持,所以定点数被大量用于模拟浮点数。在2D游戏中,定点数主要用于存坐标值,这样移动速度就可以是半个象素,四分之一个象素,等等。定点数算法以下都假设a,b是两个定点数,c是计算结果,f是因子,就是扩大的倍数。浮点数转换到定点数定点数=浮点数*转换因子(倍数)加法c=a+b减法c=a–b乘法c=a*b/f,如果f是2的幂,那么可以用右移做除法除法c=a/b,这里假设小数部分会被抵消,精确的计算比较麻烦,在2D游戏里基本不用。其实除法在2D游戏里用得也很少。距离的计算点到点假设有两点(X0,Y0),(X1,Y1)dx=X1-X0;dy=Y1-Y0计算两点间距离的精确算法是distance2D=sqt(abs(dx)+abs(dy))。由于J2ME不支持浮点运算,在J2ME2D游戏中也可以用近似算法计算两点间距离,一方面能取得较快速度,精度上也不会有太大损失。intapprox_distance2D(intdx,intdy){intmin,max;if(dx<0)dx=-dx;if(dy<0)dy=-dy;if(dx<dy){min=dx;max=dy;}else{min=dy;max=dx;}//coefficientsequivalentto(123/128*max)and(51/128*min)return(((max<<8)+(max<<3)-(max<<4)-(max<<1)+(min<<7)-(min<<5)+(min<<3)-(min<<1))>>8);}如果在游戏需要经常计算点到点的距离,同时对精度要求也不太高,我们可以损失一点精度而取得更快的速度。这就是下面的快速近似算法。intfastDistance2D(intdx,intdy){//putesthedistancefrom0,0tox,%error//putetheabsolutevalueofx,yif(dx<0)dx=-dx;if(dy<0)dy=-dy;//computetheminimumofdx,dy//intmn=(dx,dy);intmn=dx;if(dy<dx)mn=dy;//returnthedistancereturn((dx+dy)-(mn>>1)-(mn>>2)+(mn>>3));}两种算法测试:用1000和10000组随机数据做测试,结果表明approx_distance2D平均误差为1%,fastDistance2D平均误差为3%-%,点到直线基于上一小节两点间距离的快速近似算法,通过推导,可以得出点到直线的快速近似