定点数
定点数就是用整数来表示浮点数。方法是把浮点数扩大一定倍数，取整成整数。在计算机里，这个倍数通常是2的幂，这样方便快速计算。& C( T& }$ i& i2 s% l) n( [
定点数的的应用
由于手机通常不支持浮点数，J2ME也不支持，所以定点数被大量用于模拟浮点数。在2D游戏中，定点数主要用于存坐标值，这样移动速度就可以是半个象素，四分之一个象素，等等。
定点数算法
以下都假设a, b是两个定点数，c是计算结果，f是因子，就是扩大的倍数。开发者社区论坛" @% d7 l+ [- /! i
浮点数转换到定点数
定点数 ＝ 浮点数 * 转换因子（倍数）
加法中国移动开发者社区/ a- V# _7 ^0 F+ f& o- L$ P
c = a + b0 f( ?) i; _, E- f: F
减法3 ?; X6 Z7 s, K. {' t+ g0 @- e
c = a – b开发者社区论坛& m, i' K& Q2 D5 o
乘法开发者社区论坛$ I- B9 |( J" Z& j3 k9 Y m d1 ~
c = a * b / f，如果f是2的幂，那么可以用右移做除法
除法开发者社区论坛4 A% _/ e5 z# l+ }! k' p8 y- X
c = a / b，这里假设小数部分会被抵消，精确的计算比较麻烦，在2D游戏里基本不用。其实除法在2D游戏里用得也很少。
距离的计算. ^9 I' W& ` ]. D% Y& z
点到点1 [" [. _& |) [* L; c
假设有两点（X0,Y0）,(X1,Y1)
dx = X1-X0 ; dy= Y1-Y0dev.chinamobile.com7 U |% p6 X+ y& m. _6 M
计算两点间距离的精确算法是 distance2D ＝sqt（abs（dx）＋abs（dy））。中国移动开发者社区/ w( Q W5 W. J, A+ p6 X; n" G
由于J2ME不支持浮点运算，在J2ME 2D游戏中也可以用近似算法计算两点间距离，一方面能取得较快速度，精度上也不会有太大损失。
int approx_distance2D( int dx, int dy )
{中国移动开发者社区! {% u y" H( i3 X1 U% s4 P: I
int min, max;" f" n2 G% M! X+ x# P7 ~$ V& x; n
if ( dx < 0 ) dx = -dx;
if ( dy < 0 ) dy = -dy;5 l9 @( A" a4 E- P8 u
if ( dx < dy )
{开发者社区论坛* }) O* B7 w8 c Q
min = dx;
max = dy;7 /2 L# s2 f$ ]- U+ u0 _
} else {8 [8 H( C; j- U9 a
min = dy;开发者社区论坛: f. F# w" h" r ?- t
max = dx;
}
// coefficients equivalent to ( 123/128 * max ) and ( 51/128 * min )- W( {$ _% T6 }9 x/ l
return ((( max << 8 ) + ( max << 3 ) - ( max << 4 ) - ( max << 1 ) +dev.chinamobile.com9 L9 U% |+ K) |* L: m
( min << 7 ) - ( min << 5 ) + ( min << 3 ) - ( min << 1 )) >> 8 );中国移动开发者社区/ t4 t9 /: m3 e( q* s O+ {
}dev.chinamobile.com: P- ]! o$ |' ~& k0 B
如果在游戏需要经常计算点到点的距离，同时对精度要求也不太高，我们可以损失一点精度而取得更快的速度。这就是下面的快速近似算法。
int fastDistance2D(int dx, int dy)' V$ H3 N& j1 }2 ?: S4 L
{中国移动开发者社区, a$ K$ _ O7 S3 m
// this function computes the distance from 0,0 to x,y with 3.5% error
// first compute the absolute value of x,y
if(dx < 0) dx = -dx;
if(dy < 0) dy = -dy;5 V0 f1 L: y; a4 d
) i# x4 s, L7 I# W$ f! ]
// compute the minimum of dx,dy* C+ F$ R* B5 X
//int mn = Math.min(dx, dy);dev.chinamobile.com! n q& L- D# v4 d3 `
int mn = dx;
if(dy < dx) mn = dy;dev.chinamobile.com u- Q! W# y) z1 s; s+ O6 R
8 k; y1 n2 ~* N+ F) J
// return the distance
return ((dx + dy) - (mn >> 1) - (mn >> 2) + (mn >> 3));
}0 Y7 p0 J' L8 H& O) c# K5 V: R& Q
2 R5 C; ~: n0 |6 X% _
两种算法测试：
用1000和10000组随机数据做测试，结果表明
approx_distance2D平均误差为1%，fastDistance2D平均误差为3% － 3.5%，
' d0 N/ U4 [! /! ]) O$ l# ~- J
点到直线- T$ F% / e: _& ^3 B
基于上一小节两点间距离的快速近似算法，通过推导，可以得出点到直线的快速近似算法。如下：
/**1 S: }0 a8 e0 d! @
* Calculate distance of a point to a line. <br>开发者社区论坛8 f2 s2 c& U) w- a* i7 N
* Point is (x0, y0). <br>4 u5 ?: ^. t, T9 L; l4 I
* Line is linked by (x1, y1) and (x2, y2).
*/
public static int distPointToLine(int x0, int y0, int x1, int y1, int x2, int y2)
{' u8 v, f( j$ j3 ]8 b8 c! i6 ?/ U
// get the line formula: Ax + By + C = 0开发者社区论坛4 T* G% e; l3 o1 l2 w3 y
int A = y2 - y1;: Z% E, A( r( R. ]
int B = x1 - x2 = -(x2-x1);
int C = x2*y1 - x1*y2;
// the distance: abs(A*x0 + B*y0 + C) / sqrt(A*A + B*B):参看下面推导
//if fastDistance2D(A, B) == 0, ……….dev.chinamobile.com( w2 v6 b( r, ], F
return Math.abs(A*x0 + B*y0 + C) / fastDistance2D(A, B);% F& `: G1 e5 }0 n# D+ |
}
推导开发者社区论坛* K7 X' [9 i& Z
6 B2 s6 M* y8 P$ p, x1 ], b' l
直线方程是 y = (A / B) * x + C / B
所以 在点 (x0, y0)出做向X轴的直线，那么和直线的交点就是
(x4, y4) = (x0, (A/B) * x0 + C / B)1 ~9 H( _+ }8 v" h* T' |# }: S2 o8 C
所以垂直距离是 (y4 – y0) * B / DistanceAB ＝（(A/B) * x0 + C / B －y0）* B / DistanceAB
＝（A*x0－y0*B+C）/DistanceAB6 p* w& i8 `: S3 p$ G+ F, d
! d$ p2 i4 g+ @" Y/ B3 c
三角函数dev.chinamobile.com1 e8 i2 X9 x4 u# U
快速计算sin和cos的方法
1. Splinter Cell PT里面提供的一种算法
Sin（angle）＝ angle - angle*angle*angle / (6*100*100);
Cos (angle) ＝ 1*100 - angle*angle / (2*100);
这儿的angle是以弧度为单位，由于J2ME不支持浮点运算，把Pi扩大了一百倍（314）。
该方法比较实用，也比较精确
2．Zeng Xiao Bing提供的一种算法. f7 c0 k! L" b& g" Y7 O3 } V, I: N
单位是角度，扩大了8100倍dev.chinamobile.com4 O4 y% r0 D% _7 q- K* I
public final static int SIN = 0;
public final static int COS = 1;dev.chinamobile.com' b4 C# |# A) d* w. Z K
开发者社区论坛 l. r$ C( t) s4 K- P: N7 B! Z, _
public static int sc(int op, int dir)
{dev.chinamobile.com2 U1 _" b; a: h5 M$ V7 ]4 e
int sign = 1;
//while(dir < 0) dir += 360;
while(dir > 360) dir -= 360;
if(dir >= 180)
{开发者社区论坛! f5 P6 p Q5 d2 L" [
dir -= 180;6 N" e" `) f* p8 X2 S0 p, a
sign = -1;中国移动开发者社区: C8 R' N- [# N
}
if(dir > 90)2 T3 Q# C1 r9 B' M& }
{
dir = 180 - dir;6 ?! B- _3 ~8 D
if (op == COS)
sign *= -1;
}: T0 C ~: C! X0 T1 v& I! n; {$ E
if (op == COS)
dir = 90 - dir;开发者社区论坛5 t0 s* y1 /7 f. |4 b* C
// return sign * SIN_VALUE[(dir+5)/10];# w; X& |$ ?& z, e) I+ M
return sign * (8100 - (90 - dir)*(90 - dir));
// use parabola to simulate sine curvedev.chinamobile.com) q. g6 V _/ s
}' G& @5 `, `5 @' d; s
原理是用抛物线来模拟正弦曲线。中国移动开发者社区8 s2 l. a) d% i
注意：PT版本的cos函数，在0-45度（0- 157 /2）内准确度是很高的，但在45-90度间，准确度极度下降(误差%6.7)，而且当angle大于141后，会出现负数的情况。所以，建议只在0-45度间使用，超过45度的，用sin(157 – angle)求余弦，用cos(157 – angle)求正弦。
2 f7 m# V" G4 `
碰撞和裁剪dev.chinamobile.com+ w4 F% e: y i6 }/ a- z
点和矩形
点和矩形是否碰撞，只需判断该点位于矩形得内部区域就可以了。
static public final int CS_TOP = 0x01;$ S G, M/ M& x
static public final int CS_BOTTOM = 0x02;
static public final int CS_RIGHT = 0x04;% u6 t* L- j& }8 }; D- R% T
static public final int CS_LEFT = 0x08;
public static int CompOutcode(int x, int y, int xmin, int ymin, int xmax, int ymax)7 k- d9 j1 [6 ]1 H9 P D1 Q9 b+ J6 W8 ~
{
int code = 0;
if(y > ymax) code |= CS_TOP;
if(y < ymin) code |= CS_BOTTOM;2 K5 A' /0 k6 f2 b
if(x > xmax) code |= CS_RIGHT;5 ^/ _3 p- g p0 E5 Z2 v
if(x < xmin) code |= CS_LEFT;
return code; g# Z1 V% E& Z. H9 Z; z
}% J* ^) T3 X5 w; M. h
如果返回得code得值为0就可以判断点和矩形发生了碰撞。
; R; i- E1 G: h6 y( f- K. p
直线和矩形开发者社区论坛+ H6 r! P1 n' w9 ^- K7 |
判断直线（线段）和矩形相交的算法。对于大多数游戏都没用，但如果允许任意角度的射线（比如子弹轨迹），那么它就很有用了。这个算法的核心思想就是把坐标按照矩形分为九个小的区域，然后依据直线端点所在的区域分别进行计算，这样可以大大减少计算量。
/**
* Cohen Sutherland line clipping algorithm
* @param x0, y0, x1, y1: two point of the segment: V- // Q& r# D0 |$ C- k" c
* @param xmin: Rectangle left
* @param ymin: Rectangle top中国移动开发者社区7 o- t; M. g. r- Y: V! V4 b
* @param xmax: Rectangle right开发者社区论坛# T3 X$ T; D0 M; G( k) Y
* @param ymax: Rectangle bottom9 g. {( Z0 ?' b9 r/ M
* @return
*/中国移动开发者社区1 o1 R. u9 O. o0 X- `
public static boolean Cohen_Sutherland_LineClipping(int x0, int y0, int x1, int y1,
int xmin, int ymin, int xmax, int ymax)
{
int outcode0, outcode1, outcode;
int x = 0, y = 0;) @8 i0 l4 y6 w* Q1 f: d8 j2 B. Y
dev.chinamobile.com n( r8 j, V! |
outcode0 = CompOutcode(x0, y0, xmin, ymin, xmax, ymax);
outcode1 = CompOutcode(x1, y1, xmin, ymin, xmax, ymax);
while(true) {" e& T5 e' B0 [0 v7 ]+ p
if((outcode0 | outcode1) == 0) return true;中国移动开发者社区6 S, /; A S2 X H; R) s( o% M
if((outcode0 & outcode1) != 0) return false;
outcode = (outcode0 != 0) ? outcode0 : outcode1;0 j/ O w: t( K. /5 V# {( e! ^$ U
if((outcode & CS_TOP) != 0) {
x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
y = ymax;
}) |0 `) /# V' h6 F- N/ /& N
else {
if((outcode & CS_BOTTOM) != 0) {
x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
y = ymin;开发者社区论坛( l9 ?8 J7 }5 c: o% i5 ?. O. a0 l
}
else {
if((outcode & CS_RIGHT) != 0) {
y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);中国移动开发者社区" J3 w( z3 M; p) z; v' e
x = xmax;
} B6 P4 j# B" N& U" U4 R6 I H
else {2 a( ~! F5 J1 S) x1 u( q' u
if((outcode & CS_LEFT) != 0) {' [2 t, T! S: R! K
y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
x = xmin;
}7 f* {+ _! T) /; z9 Z
}
}
}
if(outcode == outcode0) {
x0 = x;
y0 = y;
outcode0 = CompOutcode(x0, y0, xmin, ymin, xmax, ymax);! m8 E7 P# Y8 Q% s
}
else {
x1 = x;dev.chinamobile.com# l; x/ f! e! Q( U
y1 = y;8 g# t/ `' M* ]- {, U4 F
outcode1 = CompOutcode(x1, y1, xmin, ymin, xmax, ymax);开发者社区论坛. i7 ?2 V& z8 a& G- E5 V4 f
}
}( V4 ^/ q0 i* C% p1 u% q
}
矩形和矩形
AABB algorithm to check matrix collision. The rectangles intersect only when (e < c) and (g > a) and (f > d) and (h < b)开发者社区论坛' O) e' ?5 P/ W. F+ M
中国移动开发者社区3 {) v) V: n, _; w) }6 M2 K! B
- Q" L/ `! p- E; ^6 N
Figure AABB algorithm