分類: 算法

AI也就是『人工智能』在遊戲中實現多數使用『狀態機』.通過定義大量狀態.然後通過條件判斷而切換當前狀態.從而實現對外界作出反應. 當『怪物』它會觀察四周.當你接近它時會另轉面走開.

首先定義下面幾個狀態

#define AI_IDLE       0 // 站立

#define AI_RUN        1 // 奔跑

#define AI_DEATH      3// 死亡

初此AI狀態變量設為站立

int ai = AI_IDLE;

『狀態機』判斷結構

if (ai == AI_IDLE) // 站立

{

}

else

if (ai == AI_RUN)// 奔跑

{

}

else

if (ai == AI_DEATH)// 死亡

{

}

 

站立轉身走開AI代碼

1.首先計算兩者距離

VECTOR3D distance = pos – player.pos;

length = Length_VECTOR3D(&distance);

2.計算『怪物』與『玩加』 矢量之間夾角

Normalize_VECTOR3D(&distance);// 長度歸一

VECTOR3D v;

Init_VECTOR3D(&v, 0, 0, -1);

angle = RAD_TO_DEG(Angle_VECTOR3D(&distance, &v0));// 角度

2.若距離小於10米則會轉身離開

if (length < 10  ){

ai = AI_RUN;// 奔跑

rot.y = (angle – 90) + ((rand() % 90) – 45);// 轉身走開.有45度隨機角度

}

 

『物體』運動核心是碰撞.你試想下當『物體』高速運動時有可能會穿越牆壁.這因遊戲世界中CPU會輪詢處理所有『物體』. 並只會分到有限『運算/時間』,所以每一次你都需要準確計算碰撞時間.通過不斷遞歸而確定最後移動位置

通過使用基於時間二維方程式進行碰撞檢測.

x_f=x₀+v₀t+(1/2)at²

ax²+bx+c=0

利用係數替換可得到

a=(1/2)*a

b=v₀

c=x₀-x_f

將其擴展可得到三維方程式

x_t=c_x+b_xt+a_xt²

y_t=c_y+b_yt+a_yt²

z_t=c_z+b_zt+a_zt²

如果將三維方程應用於平面方程可得

Ax_t+By_t+C*z_t+D=0

此方程說面如果物體與平面發生碰撞.其碰撞點位於(x_t,y_t,z_t)通過代數運算可得到

(Aa_x+Ba_y+Ca_z)x²+(Ab_x+Bb_y+Cb_z)x+(Ac_x+Bc_y+Cc_z)+D=0

這其實就是平面二次方程式(ax²+bx+c=0) ,其點積形式為:

ax²=(Aa_x+Ba_y+Ca_z)x2=N•(1/2)A

利用點積得到二次方程係數:

加速度係數: a=N•(0.5A)

速度係數:  b=N•V

距離係數:  c=N•X+D

有上序二次方程係數就可計算碰撞時間

float a = n % (acceleration * 0.5f);// 加速度係數

float b = n % velocity;// 速度係數

float c = n % position + D – radius;// 距離係數

若a=0加速度係數為零,碰撞時間等於距離係數除以速度係數.因為距離係數小於零所以要去負值.

collisionTime = -c/b;

若a!=≠0加速度係數不為零,可以使用二次方程計算碰撞時間:

x=(-b+√(b²-4ac) ) / 2a

在計算碰撞時間之前可先計算D=b²-4ac 若D小於零則無解.若D大於零則有解

float D = b * b – 4 * a*c;

if (D > 0) // 如果判斷式大於等於零

collisionTime = (-b – sqrtf(D)) / (2 * a); // 計算碰撞時間

因為發生碰撞物體會彈開,方向矢量產生返射需要重新計算位置.通過減去碰撞時間進行遞歸.直到『幀時間』為零

 

下面是『曲棍球』碰撞函式.

puck 是曲棍球.

table 是球臺

deltaTime是幀時間

void Update_Puck(PUCK_PTR puck, TABLE_PTR table, float deltaTime){

float  fastestTime = deltaTime;// 最早碰撞時間

float  collisionTime;// 碰撞時間

PLANE3D_PTR plane          = NULL;// 平面

PLANE3D_PTR planeCollision = NULL;// 碰撞平面

if (deltaTime <= 0.000f)// 遞歸

return;

// 對球臺四個圍邊檢查碰撞

for (int i = 0; i < 4; i++){

plane = &table->wall[i];// 平面

// 點積二次方程

float a = plane->n % (puck->acceleration * 0.5f);// 加速度係數

float b = plane->n % puck->velocity;// 速度係數

float c = plane->n % puck->position + plane->D – puck->radius;// 距離係數

if (a == 0 && b != 0 && c != 0){// 如果無加速度

// 碰撞時間等於距離除以速度

collisionTime = -c/b;// 碰撞時間

if (collisionTime >= 0 && collisionTime < fastestTime){// 發生碰撞

fastestTime = collisionTime;// 保存碰撞時間

planeCollision = plane;// 平面

}

}

else

if(a != 0){

// 加速度a不等於零

// 計算判別式

float D = b * b – 4 * a*c;

if (D > 0) {// 如果判斷式大於等於零

// 計算碰撞時間

collisionTime = (-b – sqrtf(D)) / (2 * a);

if (collisionTime >= 0.0f && collisionTime < fastestTime) {// 發生碰撞

fastestTime = collisionTime;

planeCollision = plane;

}

}

}

}// END FOR

// 速度設上限每秒800米

if (Length_VECTOR3D(&puck->velocity) > 800)

puck->velocity = Normalize_VECTOR3D(&puck->velocity) * 800;

// 如果冰球正移動,則應用磨擦力

if (Length_VECTOR3D(&puck->velocity) > 0)

puck->acceleration = -puck->velocity * 0.2f;// 計算加速度

// 計算當前位置

puck->position = puck->position + puck->velocity * fastestTime + puck->acceleration * (fastestTimefastestTime0.5f);

// 應用磨擦力

puck->velocity = puck->velocity + puck->acceleration * fastestTime;

// 如果發生碰撞,反轉速度

if (planeCollision != NULL)// 碰撞平面

puck->velocity = Reflection_VECTOR3D(&puck->velocity, &planeCollision->n);

// 遞歸調用

Update_Puck(puck, table, deltaTime – fastestTime);

}

若3D模型發生碰撞後需要計算碰撞反應,不通物體運動有不同碰撞反應.但物體多數以直線運動.物體彈回角度和碰撞角度相等.

入射角度:桌球運動方向與邊沿平面法線向量之間夾角.

反射角度:垂直於運動方向矢量

例:當桌球撞向邊沿.它將按撞擊角度與之對等『入射角度』彈開

方程並沒有考慮球體旋轉作用力與磨擦力.最終得到計算反射方向方程式

給定運動方向矢量I與垂直法線N求碰撞反射方向F

F = (I – N2 (I % N)) * | I |;

計算反射方向代碼,dir為射線方向,normal為碰撞面法線

VECTOR3D Reflection_VECTOR3D(VECTOR3D_PTR dir,VECTOR3D_PTR normal){

VECTOR3D vec ;

Normalize_VECTOR3D(dir, &vec); // 單為化方向向量

*dir = (vec – *normal * 2.0f * (vec % *normal)) * Length_VECTOR3D(dir);

return *dir;

}

平面是3D圖形學重要部分.平面有兩個重要概念.

1.3D平面都無窮遠延伸

2.所有平面都將整個空間分成兩個半空間.正半空間為法線指向空間,負半空間則是令一則空間.這個特性對於碰撞算法重要

平面描敘如下:

平面法線向量:n=(a,b,c)

平面任意點:p0=(x0,y0,z0)

平面任意點:p=(x,y,z)

平面與原點距離:d平面位移常量(plane-shift constant)

因為法線n與向量(p0->p)垂直. 因兩垂直向量點積為零:

n * (p0->p) = 0

轉為分量表示

(a,b,c)*(x-x0,y-y0,z-z0)=0

轉為『頂點』與『法線』表示

a(x-x0)+b(y-y0)+c*(z-z0)=0

ax+by+cz+(-ax0-by0-cz0)=0

令d=-ax0-by0-c*z0

『平面方程』如下:

ax+by+c*z+d=0

 

這足以定義平面結構

typedef struct PLANE3D_TYP{

VECTOR3D n;//平面法線向量(不必是單位向量)

float dist;//平面到原點最近距離

POINT3D p0;//平面上最近原點的點

}PLANE3D,*PLANE3D_PTR;

 

判斷『點』位於『平面』那個半空

3D世界中『視點』、『角色』並不能穿越牆壁.要做到這步需判斷點位於平正空間(法線指向)還是負空間.

要判斷這點需要下面的平面方程

hs=a(x-x0)+b(y-y0)+c*(z-z0)

只需將點(x,y,z)帶入方程中並計算結果

如果hs=0則該點位於平面之上

如果hs>0則該點位於平面正半空間(法線指向)中

如果hs<0則該點位於平面負半空間中

float Compute_Point_In_Plane3D(PLANE3D_PTR plane,VECTOR3D_PTR pt){

float hs = plane->A * pt->x + plane->B * pt->y + plane->C * pt->z + plane->D;

return(hs); // 返回半空間值

}

 

計算平面與直線之相交點(3D空間)

平面『頂點』與『法線』方程如下:

a(x-x0)+b(y-y0)+c*(z-z0)=0

3D直線方程如下:

(x-x0)/a = (y-y0)/b = (z-z0)/c

計算多邊形法線與直線方向點積

double a = plane->n % (line->v);

若為零則直線與平面平行

VECTOR3D Intersect;

if (a == 0)

Intersect = line->p0;

計算相交點

Intersect = line->p0 – (line->v) * ((plane->n % line->p0 + plane->D) / a);

3D線段與3D平面交點函式:

bool Intersect_Line3D_Plane3D(PLANE3D_PTR plane, PARMLINE3D_PTR line,POINT3D_PTR pt){

// 計算直線方向與多邊形法線點積

double a = plane->n % (line->v);

if (a == 0)

return false;

// 計算相交點

*pt = line->p0 – (line->v) * ((plane->n % line->p0 + plane->D) / a);

return true;

}

 

計算頂點是否為於多邊形之上,

首先計算頂點與多邊形所有頂點之間角度總和.如果該頂點位於多邊形之上.那麼此頂點與多邊形所有頂點之間角度總和將等於或接近2PI

bool Intersect_Vector3D_Polygon3D(VECTOR3D_PTR polygon, int num,VECTOR3D_PTR v){

VECTOR3D segment1, segment2;// 頂點 到 多邊形頂點 矢量

double length1, length2;// 矢量長度

double sumAngle = 0;// 矢量之間角度總和

double cosAngle = 0;// 兩矢量余弦角

// 編曆多邊形所有頂點

for (int index = 0; index < num; ++index)     {

segment1 = polygon[index] – *v;

segment2 = polygon[(index+1) % num] – *v; // % num 確保數值環形加一

length1 = Length_VECTOR3D(&segment1);

length2 = Length_VECTOR3D(&segment2);// 矢量長度

//檢查頂點是否落在多邊形邊界上

if ( length1 * length2 <= 0.0000001f){

// 多邊形邊界被認為是多邊形內部

sumAngle = PI2; // pai * 2

break;

}

// 計算上述兩個矢量之間余弦角

cosAngle = (segment1 % segment2) / (length1 * length2);

// 將計算結果累加入角度總和

sumAngle = sumAngle + acosf(cosAngle);

}

if ((sumAngle <= PI2 + 0.0000001f) && (sumAngle >= PI2 – 0.0000001f))

return true;// 頂點與多邊形發生碰撞

else

return false;

return true;

}

 

使用三個頂點初始化(定義)3D平面!

void Init_PLANE3D(PLANE3D_PTR plane,VECTOR3D_PTR va,VECTOR3D_PTR vb,VECTOR3D_PTR vc){

VECTOR3D normalA = *vc – *va;// 計算頂點C->A向量

VECTOR3D normalB = *vc – *vb;// 計算頂點C->B向量

plane->n = Cross_VECTOR3D(&normalA, &normalB);// 計算兩個3D向量叉積

plane->D = Dot_VECTOR3D(&(-(*va)), &plane->n); //距離等於va求返後與n求點積

}

矢量(VECTOR)也稱『向量』其實是抽象『量』它在遊戲世界被頂義為『位置』『速度』『磨擦』『方向』『點』等等. 矢量通常有3種

矢量	分量	簡序
2D矢量	x,y	2D空間
3D矢量	x,y,z	3D空間
4D矢量	x,y,z,w	3D空間w總是為1.用於方陣運算

首先定義3D矢量結構:

typedef struct VECTOR3D_TYP{

float x,y,z;

}VECTOR3D,*VECTOR3D_PTR;

下面是3D矢量(VECTOR)運算函式庫.

 

計算3D矢量長度,矢量長度也稱為範數(norm).將其理解為原點(0,0,0)到矢量(x,y,z)之距離

float Length_VECTOR3D(VECTOR3D_PTR va){

return( (float)sqrtf(va->xva->x + va->yva->y + va->z*va->z) );

}

 

對3D矢量進行歸一化(normalize),也就使其長度縮放為1,但同時方向保持不變.它通常被用於無需理會長度之運算如『方向』

void Normalize_VECTOR3D(VECTOR3D_PTR va){

// 1.首先計算長度

float length = sqrtf(va->xva->x + va->yva->y + va->z*va->z);

//2.矢量除以長度得到歸一化矢量

va->x= va->x/length;

va->y= va->y/length;

va->z= va->z/length;

}

 

3D矢量點積運算可以理解為矢量乘法.先將各分量相乘後再相加得到一個標量

float operator%(VECTOR3D va, VECTOR3D vb){

return((va.x * vb.x) + (va.y * vb.y) + (va.z * vb.z));

}

float Dot_VECTOR3D(VECTOR3D_PTR va, VECTOR3D_PTR vb){

return( (va->x * vb->x) + (va->y * vb->y) + (va->z * vb->z) );

}

叉積是另一種矢量乘法,叉積運算最小要有3個分量才有效.

VECTOR3D operator^(VECTOR3D va, VECTOR3D vb){

VECTOR3D vn;

vn.x = ((va.y * vb.z) – (va.z * vb.y));

vn.y = -((va.x * vb.z) – (va.z * vb.x));

vn.z = ((va.x * vb.y) – (va.y * vb.x));

return(vn);

}

VECTOR3D Cross_VECTOR3D(VECTOR3D_PTR va, VECTOR3D_PTR vb){

VECTOR3D vn;

vn.x =  ( (va->y * vb->z) – (va->z * vb->y) );

vn.y = -( (va->x * vb->z) – (va->z * vb->x) );

vn.z =  ( (va->x * vb->y) – (va->y * vb->x) );

return(vn);

}

 

計算兩個3D矢量va和vb之間夾角余弦值

float CosTh_VECTOR3D(VECTOR3D_PTR va, VECTOR3D_PTR vb){

return(Dot_VECTOR3D(va,vb)/(Length_VECTOR3D(va)*Length_VECTOR3D(vb)));

}

 

 

計算三角形法線

void Normal_VECTOR3D(VECTOR3D_PTR normal,VECTOR3D_PTR va, VECTOR3D_PTR vb, VECTOR3D_PTR vc){

VECTOR3D u, v, n;

float length;

u = *vb – *va;

v = *vc – *va;

n = u^v;//Cross_VECTOR3D(&u, &v, &n);// 計算叉積

length = sqrtf(n.xn.x + n.yn.y + n.z*n.z);

normal->x = n.x/length;

normal->y = n.y/length;

normal->z = n.z/length;

}

 

將兩個3D矢量相加(va + vb),如用於位置移動

VECTOR3D operator+(VECTOR3D va, VECTOR3D vb){

VECTOR3D vsum;

vsum.x = va.x + vb.x;

vsum.y = va.y + vb.y;

vsum.z = va.z + vb.z;

return (vsum);//返回相加結果!

}

 

將兩個3D矢量相減(va – vb),如用於位置移動

VECTOR3D operator-(VECTOR3D va, VECTOR3D vb){

VECTOR3D vdiff;

vdiff.x = va.x – vb.x;

vdiff.y = va.y – vb.y;

vdiff.z = va.z – vb.z;

return(vdiff);     //返回相減向量!

}

 

3D矢量反數,如返轉方向

VECTOR3D operator-(VECTOR3D v){

VECTOR3D negation;

negation.x = -v.x ;

negation.y = -v.y ;

negation.z = -v.z ;

return(negation);     //返回反數向量!

}

 

使用縮放因子k對3D矢量進行縮放如:位置=位置+速度*時間

VECTOR3D operator*(VECTOR3D va, float k){

VECTOR3D vscaled;

vscaled.x = k * va.x;

vscaled.y = k * va.y;

vscaled.z = k * va.z;

return vscaled;// 返回縮放後向量

}

 

3D矢量賦值

void Init_VECTOR3D(VECTOR3D_PTR v, float x,float y,float z) {

v->x = x;  v->y = y; v->z = z;

}

 

3D矢量拷貝

Copy_VECTOR3D(VECTOR3D_PTR vdst, VECTOR3D_PTR vsrc){

vdst->x = vsrc->x;  vdst->y = vsrc->y; vdst->z = vsrc->z;

}

 

3D矢量比較

bool operator==(VECTOR3D vdst, VECTOR3D vsrc){

if (vdst.x == vsrc.x && vdst.y == vsrc.y && vdst.z == vsrc.z)

return true;

else

return false;

}

 

3D向量不等比較

bool operator!=(VECTOR3D vdst, VECTOR3D vsrc)

{

if (vdst.x != vsrc.x ||         vdst.y != vsrc.y ||vdst.z != vsrc.z)

return true;

else

return false;

}

 

向量歸零(3D向量)無方向,無距離,代表位於原點

void Zero_VECTOR3D(VECTOR3D_PTR v) {

v->x = v->y = v->z = 0.0f;

}

計算兩矢量之間夾角

float Angle_VECTOR3D(VECTOR3D_PTR va, VECTOR3D_PTR vb){

return acosf(*va % *vb);

}

角度轉弧度

#define DEG_TO_RAD(ang) ((ang)*PI/180.0)

弧度轉角度

#define RAD_TO_DEG(rads) ((rads)*180.0/PI)

隨機數 x:下限,  y:上限.

#define RAND_RANGE(x,y) ( (x) + (rand()%((y)-(x)+1)))

隨機數: -1.0 ~ 1.0

#define FRAND_RANGE1()   (((float)rand()-(float)rand())/RAND_MAX)

隨機數 0~1

#define FRAND_RANGE() ((float)rand() / (float)RAND_MAX)