游戏人工智能——追逐与拦截

我不是女神ヾ 2023-10-01 15:57 28阅读 0赞

## **实验一：追逐与拦截** ##

### **一、实验目的** ###

掌握游戏中追逐与拦截的人工智能算法

###  ###

### **二、实验仪器** ###

Microsoft Visual Studio2019

### **三、实验原理及过程** ###

//描述追逐与拦截的算法原理

//描述程序实现时的思路包括对每个调用的API进行详细说明

（1）描述追逐与拦截的算法原理：连续环境中的视线追逐是最简单的追逐算法，但是追逐者的移动不仅有线速度，而且还有角速度。算法思路就是：首先根据角速度把方向转到视线方向，然后向目标追过去。完整追逐/闪躲由三部分组成：首先，作出追或逃的决策判断。其次，开始追或逃（本章重点）最后，避开障碍物。拦截算法的基本原理是可以预测猎物未来的位置，然后直接到那个位置去，让追击者和猎物同时到达同一个位置。为了找出追击者和猎物能同时到达的点，不仅要考虑他们的移动方向，还要考虑他们的速度。

（2）Main和winmain进行函数的定义。RigidBody2D类：进行物体的质量，惯性，关系，坐标，长高宽即外形的定义，用向量表示他们移动的方向。UpdateSimulation函数对于物体1,2的移动进行反应和控制。DoCraft2Chase函数对于物体1,2追逐进行判断，DoCraft2Evade函数对于物体1,2躲避进行判断。DoCraft2InterceptAlt函数对于物体1,2拦截进行判断。DoAttractCraft2函数判断是否攻击。

### **四、实验结果** ###

![26de797c182f426899161f0a1b8771c7.png][]

![36f58b71a16c4a638d254a4dad49461b.png][]

![1fed5928dafd4169a48b33b98fd7d323.png][]

![9d90f52ca2ae43bebba12160513f5adb.png][]

### **五、实验心得****(****需包括有何不足如何改进****)** ###

//你认为目前的追逐与拦截有什么不足之处,如何改进

猎物和追逐者的速度向量和位移向量都是固定的，因为靠拢时间的计算,需要相对位移和相对速度。但是

如果这些都是固定的话，很容易得到两者很可能不会相遇的问题。更近合理的解释应该是猎物的速度向量和初始位置向量固定,追逐者的初始位置和速度大小固定，而速度方向不固定，这样通过调整方向来达到

拦截的作用。计算可以采用靠拢时间的方法，不过是一个方程。

**六、主要代码**

**//main.cpp**

\#include "main.h"

\#include "time.h"

//---------------------------------------------------------------------------

/\*

Book: AI for Game Developers

Authors: David M. Bourg & Glenn Seemann

Example: Chasing and evading in continuous environments, Chapter 2

\*/

//---------------------------------------------------------------------------

// Global Variables:

int FrameCounter = 0;

RigidBody2D Craft1, Craft2;

Vector Target;

\#define \_TIMESTEP 0.001

\#define \_TOL 1e-10

\#define \_FWDTIME 10

\#define \_THRUSTFACTOR 3

\#define \_CHASESETUP true

bool Initialize(void)

Craft1.fMass = 10;

Craft1.fInertia = 10;

Craft1.fInertiaInverse = 1/10;

Craft1.vPosition.x = \_WINWIDTH-60;

Craft1.vPosition.y = \_WINHEIGHT\*0.8;

Craft1.fWidth = 10;

Craft1.fLength = 20;

Craft1.fHeight = 5;

Craft1.fOrientation = 135;

Craft1.CD.y = -0.12\*Craft1.fLength; Craft1.CD.x = 0.0f; // coordinates of the body center of drag

Craft1.CT.y = -0.50\*Craft1.fLength; Craft1.CT.x = 0.0f; // coordinates of the propeller thrust vector

Craft1.CPT.y = 0.5\*Craft1.fLength; Craft1.CPT.x = -0.5\*Craft1.fWidth; // coordinates of the port bow thruster

Craft1.CST.y = 0.5\*Craft1.fLength; Craft1.CST.x = 0.5\*Craft1.fWidth; // coordinates of the starboard bow thruster

Craft1.ProjectedArea = (Craft1.fLength + Craft1.fWidth) \* Craft1.fHeight;

Craft1.ThrustForce = \_THRUSTFORCE\*1;

Craft2.fMass = 10;

Craft2.fInertia = 10;

Craft2.fInertiaInverse = 1/10;

if(\_CHASESETUP)

Craft2.vPosition.x = 40;

Craft2.vPosition.y = \_WINHEIGHT\*0.8;

\} else \{

Craft2.vPosition.x = Craft1.vPosition.x - Craft1.fLength\*8;

Craft2.vPosition.y = Craft1.vPosition.y - Craft1.fLength\*4;

Craft2.fWidth = 10;

Craft2.fLength = 20;

Craft2.fHeight = 5;

if(\_CHASESETUP)

Craft2.fOrientation = -135;

else

Craft2.fOrientation = 135;

Craft2.CD.y = -0.12\*Craft2.fLength; Craft2.CD.x = 0.0f; // coordinates of the body center of drag

Craft2.CT.y = -0.50\*Craft2.fLength; Craft2.CT.x = 0.0f; // coordinates of the propeller thrust vector

Craft2.CPT.y = 0.5\*Craft2.fLength; Craft2.CPT.x = 0.5\*Craft2.fWidth; // coordinates of the port bow thruster

Craft2.CST.y = 0.5\*Craft2.fLength; Craft2.CST.x = -0.5\*Craft2.fWidth; // coordinates of the starboard bow thruster

Craft2.ProjectedArea = (Craft2.fLength + Craft2.fWidth) \* Craft2.fHeight;

Craft2.ThrustForce = \_THRUSTFORCE\*\_THRUSTFACTOR;

return true;

void UpdateSimulation(void)

double dt = \_TIMESTEP;

RECT r;

Craft1.SetThrusters(false, false);

if (IsKeyDown(VK\_UP))

Craft1.ModulateThrust(true);

if (IsKeyDown(VK\_DOWN))

Craft1.ModulateThrust(false);

if (IsKeyDown(VK\_RIGHT))

Craft1.SetThrusters(true, false);

if (IsKeyDown(VK\_LEFT))

Craft1.SetThrusters(false, true);

// Do craft 2 AI

Craft2.Fa.x = 0;

Craft2.Fa.y = 0;

Craft2.Pa.x = 0;

Craft2.Pa.y = 0;

if(BasicChase)

DoCraft2Chase();

DoCraft2ModulateThrust();

if(BasicEvade)

DoCraft2Evade();

if(InterceptChase)

//DoCraft2Intercept();

//DoCraft2ModulateThrust();

DoCraft2InterceptAlt();

if(PotentialChase)

DoAttractCraft2();

// update the simulation

Craft1.UpdateBodyEuler(dt);

Craft2.UpdateBodyEuler(dt);

if(FrameCounter >= \_RENDER\_FRAME\_COUNT)

// update the display

if(!ShowTrails)

ClearBackBuffer();

DrawCraft(Craft1, RGB(0,0,255));

DrawCraft(Craft2, RGB(255,0,0));

RECT r;

r.left = (int) (Target.x-3);

r.top = (int) (Target.y-3);

r.right = (int) (Target.x+3);

r.bottom = (int) (Target.y+3);

DrawEllipse(&r, 1, RGB(0,255,0));

CopyBackBufferToWindow();

FrameCounter = 0;

\} else

FrameCounter++;

if(Craft1.vPosition.x > \_WINWIDTH) Craft1.vPosition.x = 0;

if(Craft1.vPosition.x < 0) Craft1.vPosition.x = \_WINWIDTH;

if(Craft1.vPosition.y > \_WINHEIGHT) Craft1.vPosition.y = 0;

if(Craft1.vPosition.y < 0) Craft1.vPosition.y = \_WINHEIGHT;

if(Craft2.vPosition.x > \_WINWIDTH) Craft2.vPosition.x = 0;

if(Craft2.vPosition.x < 0) Craft2.vPosition.x = \_WINWIDTH;

if(Craft2.vPosition.y > \_WINHEIGHT) Craft2.vPosition.y = 0;

if(Craft2.vPosition.y < 0) Craft2.vPosition.y = \_WINHEIGHT;

void DrawCraft(RigidBody2D craft, COLORREF clr)

Vector vList\[5\];

double wd, lg;

int i;

Vector v1;

wd = craft.fWidth;

lg = craft.fLength;

vList\[0\].y = lg/2; vList\[0\].x = wd/2;

vList\[1\].y = -lg/2; vList\[1\].x = wd/2;

vList\[2\].y = -lg/2; vList\[2\].x = -wd/2;

vList\[3\].y = lg/2; vList\[3\].x = -wd/2;

vList\[4\].y = lg/2\*1.5; vList\[4\].x = 0;

for(i=0; i<5; i++)

v1 = VRotate2D(craft.fOrientation, vList\[i\]);

vList\[i\] = v1 + craft.vPosition;

DrawLine(vList\[0\].x, vList\[0\].y, vList\[1\].x, vList\[1\].y, 2, clr);

DrawLine(vList\[1\].x, vList\[1\].y, vList\[2\].x, vList\[2\].y, 2, clr);

DrawLine(vList\[2\].x, vList\[2\].y, vList\[3\].x, vList\[3\].y, 2, clr);

DrawLine(vList\[3\].x, vList\[3\].y, vList\[4\].x, vList\[4\].y, 2, clr);

DrawLine(vList\[4\].x, vList\[4\].y, vList\[0\].x, vList\[0\].y, 2, clr);

if(ShowVectors)

Vector v, u;

double f = 5;

// Show velocity vectors in green

DrawLine(craft.vPosition.x, craft.vPosition.y, craft.vPosition.x+craft.vVelocity.x, craft.vPosition.y+craft.vVelocity.y, 3, RGB(0,255,0));

// Show force vectors in black

// thrust vector

v.x = 0;

v.y = craft.ThrustForce\*f;

v = VRotate2D(craft.fOrientation, v);

u.x = craft.CT.x;

u.y = craft.CT.y;

u = VRotate2D(craft.fOrientation, u);

DrawLine(craft.vPosition.x+u.x, craft.vPosition.y+u.y, craft.vPosition.x + u.x + v.x, craft.vPosition.y + u.y + v.y, 1, RGB(0,0,0));

// port steering force

v.x = craft.PThrust.x\*f;

v.y = craft.PThrust.y\*f;

v = VRotate2D(craft.fOrientation, v);

u.x = craft.CPT.x;

u.y = craft.CPT.y;

u = VRotate2D(craft.fOrientation, u);

DrawLine(craft.vPosition.x+u.x, craft.vPosition.y+u.y, craft.vPosition.x + u.x + v.x, craft.vPosition.y + u.y + v.y, 1, RGB(0,0,0));

// stbd steering force

v.x = craft.SThrust.x\*f;

v.y = craft.SThrust.y\*f;

v = VRotate2D(craft.fOrientation, v);

u.x = craft.CST.x;

u.y = craft.CST.y;

u = VRotate2D(craft.fOrientation, u);

DrawLine(craft.vPosition.x+u.x, craft.vPosition.y+u.y, craft.vPosition.x + u.x + v.x, craft.vPosition.y + u.y + v.y, 1, RGB(0,0,0));

// applied force

v.x = craft.Fa.x\*f;

v.y = craft.Fa.y\*f;

v = VRotate2D(craft.fOrientation, v);

u.x = craft.Pa.x;

u.y = craft.Pa.y;

u = VRotate2D(craft.fOrientation, u);

DrawLine(craft.vPosition.x+u.x, craft.vPosition.y+u.y, craft.vPosition.x + u.x + v.x, craft.vPosition.y + u.y + v.y, 1, RGB(0,0,0));

void DoCraft2Chase(void)

Vector u, v;

bool p = false;

bool s = false;

u = VRotate2D(-Craft2.fOrientation, (Craft1.vPosition - Craft2.vPosition));

u.Normalize();

Target = Craft1.vPosition;

if(u.x < -\_TOL)

p = true;

else if(u.x > \_TOL)

s = true;

Craft2.SetThrusters(p,s);

void DoCraft2Evade(void)

Vector u, v;

bool p = false;

bool s = false;

u = VRotate2D(-Craft2.fOrientation, (Craft1.vPosition - Craft2.vPosition));

u.Normalize();

if(u.x > 0)

p = true;

else if(u.x < 0)

s = true;

Craft2.SetThrusters(p,s);

Target = Craft2.vPosition;

void DoCraft2Intercept(void)

Vector u1, u2, u;

Vector s1, s2;

Vector Vr;

double t1, t2;

Vector s1unit, s2unit;

bool p = false;

bool s = false;

Vr = Craft1.vVelocity - Craft2.vVelocity;

s2 = GetVelocityIntersection() - Craft2.vPosition;

s2unit = s2;

s2unit.Normalize();

u2 = VRotate2D(-Craft2.fOrientation, s2);

t2 = s2.Magnitude()/(Vr \* s2unit);

s1 = Craft1.vPosition - Craft2.vPosition;

s1unit = s1;

s1unit.Normalize();

u1 = VRotate2D(-Craft2.fOrientation, s1);

t1 = s1.Magnitude()/(Vr \* s1unit);

if(t1 < 0.0)

u = u2;

Target = s2 + Craft2.vPosition;

\} else if(t2 < 0.0) \{

u = u1;

Target = s1 + Craft2.vPosition;

\} else if(t2 < t1)

u = u2;

Target = s2 + Craft2.vPosition;

\} else \{

u = u1;

Target = s1 + Craft2.vPosition;

u.Normalize();

if(u.x < -\_TOL)

p = true;

else if(u.x > \_TOL)

s = true;

Craft2.SetThrusters(p,s);

void DoCraft2InterceptAlt(void)

Vector u;

Vector s1, s2, s12;

bool p = false;

bool s = false;

double tClose;

Vector Vr12;

double vr;

// turn around if we get ahead of the prey...

s12 = Craft1.vPosition - Craft2.vPosition;

u = VRotate2D(-Craft2.fOrientation, s12);

if(u.y < -\_TOL)

//if(GetRandomNumber(0, 10, true) < 5)

p = true;

//else

// s = true;

Craft2.SetThrusters(p,s);

Target = Craft2.vPosition;

return;

Vr12 = Craft1.vVelocity-Craft2.vVelocity; // closing velocity

s12 = Craft1.vPosition - Craft2.vPosition; // range to close

tClose = s12.Magnitude() / Vr12.Magnitude(); // time to close

s1 = Craft1.vPosition + (Craft1.vVelocity \* tClose);

Target = s1;

s2 = s1 - Craft2.vPosition;

u = VRotate2D(-Craft2.fOrientation, s2);

u.Normalize();

if(u.x < -\_TOL)

p = true;

else if(u.x > \_TOL)

s = true;

Craft2.SetThrusters(p,s);

void DoAttractCraft2(void)

// Apply Lenard-Jones potential force to Craft2

Vector r = Craft2.vPosition - Craft1.vPosition;

Vector u = r;

u.Normalize();

double U, A, B, n, m, d;

A = 2000;

B = 4000;

n = 2;

m = 3;

d = r.Magnitude()/Craft2.fLength;

U = -A/pow(d, n) + B/pow(d, m);

Craft2.Fa = VRotate2D( -Craft2.fOrientation, U \* u);

Craft2.Pa.x = 0;

Craft2.Pa.y = Craft2.fLength / 2;

Target = Craft1.vPosition;

Vector GetVelocityIntersection(void)

double s, t, num, denom;

Vector a,b,c,d;

a = Craft1.vPosition;

b = a+Craft1.vVelocity;

c = Craft2.vPosition;

d = c+Craft2.vVelocity;

denom = a.x \* (d.y-c.y) +

b.x \* (c.y-d.y) +

d.x \* (b.y-a.y) +

c.x \* (a.y-b.y);

if(denom == 0)

return Vector(a.x, a.y, 0);

num = a.x \* (d.y-c.y) +

c.x \* (a.y-d.y) +

d.x \* (c.y-a.y);

s = num/denom;

num = -( a.x \* (c.y-b.y) +

b.x \* (a.y-c.y) +

c.x \* (b.y-a.y) );

t = num/denom;

if( (s >= 0) && (t >= 0) )

return Vector(a.x+s\*(b.x-a.x), a.y+s\*(b.y-a.y),0);

else

return Vector(a.x, a.y, 0);

int GetRandomNumber(int min, int max, bool seed)

int number;

if(seed)

srand( (unsigned)time( NULL ) );

number = (((abs(rand())%(max-min+1))+min));

if(number>max)

number = max;

if(number<min)

number = min;

return number;

void DoCraft2ModulateThrust(void)

Vector r = Craft1.vPosition - Craft2.vPosition;

double dmax = Craft2.fLength \* 10;

if((Craft2.PThrust.Magnitude() > 0) || (Craft2.SThrust.Magnitude() > 0)) // turning

if(r.Magnitude() > dmax)

Craft2.ThrustForce = \_MAXTHRUST;

else

Craft2.ThrustForce = r.Magnitude() / dmax \* \_MAXTHRUST;

\} else \{

// todo: check how close we are to target and adjust speed to stay with it

Craft2.ThrustForce = \_MAXTHRUST;

**//** **RigidBody2D.cpp**

\#include "RigidBody2D.h"

RigidBody2D::RigidBody2D(void)

void RigidBody2D::CalcLoads(void)

Vector Fb; // stores the sum of forces

Vector Mb; // stores the sum of moments

Vector Thrust; // thrust vector

// reset forces and moments:

vForces.x = 0.0f;

vForces.y = 0.0f;

vForces.z = 0.0f; // always zero in 2D

vMoment.x = 0.0f; // always zero in 2D

vMoment.y = 0.0f; // always zero in 2D

vMoment.z = 0.0f;

Fb.x = 0.0f;

Fb.y = 0.0f;

Fb.z = 0.0f;

Mb.x = 0.0f;

Mb.y = 0.0f;

Mb.z = 0.0f;

// Define the thrust vector, which acts through the craft's CG

Thrust.x = 0.0f;

Thrust.y = 1.0f;

Thrust.z = 0.0f; // zero in 2D

Thrust \*= ThrustForce;

// Calculate forces and moments in body space:

Vector vLocalVelocity;

float fLocalSpeed;

Vector vDragVector;

float tmp;

Vector vResultant;

Vector vtmp;

// Calculate the aerodynamic drag force:

// Calculate local velocity:

// The local velocity includes the velocity due to linear motion of the craft,

// plus the velocity at each element due to the rotation of the craft.

vtmp = vAngularVelocity^CD; // rotational part

vLocalVelocity = vVelocityBody + vtmp;

// Calculate local air speed

fLocalSpeed = vLocalVelocity.Magnitude();

// Find the direction in which drag will act.

// Drag always acts inline with the relative velocity but in the opposing direction

if(fLocalSpeed > tol)

vLocalVelocity.Normalize();

vDragVector = -vLocalVelocity;

// Determine the resultant force on the element.

double f;

if((Thrust \* vLocalVelocity)/(Thrust.Magnitude() \* vLocalVelocity.Magnitude()) > 0)

f = 2;

else

f = 1;

tmp = 0.5f \* rho \* fLocalSpeed\*fLocalSpeed \* ProjectedArea \* f;

vResultant = vDragVector \* \_LINEARDRAGCOEFFICIENT \* tmp; // simulate fuselage drag

// Keep a running total of these resultant forces (total force)

Fb += vResultant;

// Calculate the moment about the CG of this element's force

// and keep a running total of these moments (total moment)

vtmp = CD^vResultant;

Mb += vtmp;

// Calculate the Port & Starboard bow thruster forces:

// Keep a running total of these resultant forces (total force)

Fb += 3\*PThrust;

// Calculate the moment about the CG of this element's force

// and keep a running total of these moments (total moment)

vtmp = CPT^PThrust;

Mb += vtmp;

// Keep a running total of these resultant forces (total force)

Fb += 3\*SThrust;

// Calculate the moment about the CG of this element's force

// and keep a running total of these moments (total moment)

vtmp = CST^SThrust;

Mb += vtmp;

// do other applied forces here

Fb += Fa;

vtmp = Pa ^ Fa;

Mb += vtmp;

// Calculate rotational drag

if(vAngularVelocity.Magnitude() > tol)

vtmp.x = 0;

vtmp.y = 0;

tmp = 0.5f \* rho \* vAngularVelocity.z\*vAngularVelocity.z \* ProjectedArea;

if(vAngularVelocity.z > 0.0)

vtmp.z = -\_ANGULARDRAGCOEFFICIENT \* tmp;

else

vtmp.z = \_ANGULARDRAGCOEFFICIENT \* tmp;

Mb += vtmp;

// Now add the propulsion thrust

Fb += Thrust; // no moment since line of action is through CG

// Convert forces from model space to earth space

vForces = VRotate2D(fOrientation, Fb);

vMoment += Mb;

void RigidBody2D::UpdateBodyEuler(double dt)

Vector a;

Vector dv;

Vector ds;

float aa;

float dav;

float dr;

// Calculate forces and moments:

CalcLoads();

// Integrate linear equation of motion:

a = vForces / fMass;

dv = a \* dt;

vVelocity += dv;

ds = vVelocity \* dt;

vPosition += ds;

// Integrate angular equation of motion:

aa = vMoment.z / fInertia;

dav = aa \* dt;

vAngularVelocity.z += dav;

dr = RadiansToDegrees(vAngularVelocity.z \* dt);

fOrientation += dr;

// Misc. calculations:

fSpeed = vVelocity.Magnitude();

vVelocityBody = VRotate2D(-fOrientation, vVelocity);

void RigidBody2D::SetThrusters(bool p, bool s)

PThrust.x = 0;

PThrust.y = 0;

SThrust.x = 0;

SThrust.y = 0;

if(p)

PThrust.x = -\_STEERINGFORCE;

if(s)

SThrust.x = \_STEERINGFORCE;

Vector VRotate2D( float angle, Vector u)

float x,y;

x = u.x \* cos(DegreesToRadians(-angle)) + u.y \* sin(DegreesToRadians(-angle));

y = -u.x \* sin(DegreesToRadians(-angle)) + u.y \* cos(DegreesToRadians(-angle));

return Vector( x, y, 0);

void RigidBody2D::ModulateThrust(bool up)

double dT = up ? \_DTHRUST:-\_DTHRUST;

ThrustForce += dT;

if(ThrustForce > \_MAXTHRUST) ThrustForce = \_MAXTHRUST;

if(ThrustForce < \_MINTHRUST) ThrustForce = \_MINTHRUST;

[26de797c182f426899161f0a1b8771c7.png]: https://img-blog.csdnimg.cn/26de797c182f426899161f0a1b8771c7.png
[36f58b71a16c4a638d254a4dad49461b.png]: https://img-blog.csdnimg.cn/36f58b71a16c4a638d254a4dad49461b.png
[1fed5928dafd4169a48b33b98fd7d323.png]: https://img-blog.csdnimg.cn/1fed5928dafd4169a48b33b98fd7d323.png
[9d90f52ca2ae43bebba12160513f5adb.png]: https://img-blog.csdnimg.cn/9d90f52ca2ae43bebba12160513f5adb.png