实验二:聚集与避障

一、实验目的

掌握游戏中聚集与避障的人工智能算法,理解宽视野和有限视野的区别

二、实验仪器

Microsoft Visual Studio2019

三、实验原理及过程

//描述聚集与避障的算法原理

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

智能体只考虑哪些在检测盒内的障碍物。 

1.初始的时候,要将游戏世界中所有的障碍物都迭代到内存中,并标记哪些在检测盒内的障碍物以作进一步分析,然后把所有已经标记的障碍物都转换到智能体的局部空间。 

2.转换坐标后,那些x坐标为负值的物体将不被考虑,所以问题就变得简单多了,接下来必须要检测障碍物是否和检测盒重叠。使障碍物的包围半径扩大检测盒宽度的一半。然后测试该障碍物的y值是否小于这个值(即障碍物的包围半径加上检测盒宽度的一半)。

此时,只剩下那些与检测盒相交的障碍物了。

3.接下来我们找出离智能体最近的相交点。 

再一次在局部空间中计算,第三步中扩大了障碍物的包围半径。

用简单的线圆周相交测试方法可以得到被扩大的圈和x轴的相交点。

四、实验结果

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

//你认为目前的聚集与避障有什么不足之处,如何改进

程序的设计还有部分的不足,在避障方面还是有一部分小的瑕疵,在偶尔的时候没有进行到避障,但也是极少数的时候。

只有不断完善代码与算法进行合理与正确的计算。

六、主要代码

#include "main.h"

#include "time.h"

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

/*

Book:           AI for Game Developers

Authors:        David M. Bourg & Glenn Seemann

Example:        Flocking, Chapter 4

*/

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

#define          _TIMESTEP                                     0.0025

#define          _TOL                                               1e-10

#define          _FWDTIME                                     10

#define          _THRUSTFACTOR                                  1.0

#define     _CHASESETUP                                        true

#define          _SPAWN_AREA_R                                  100

#define          _MAX_NUM_UNITS                              20

#define          _UNIT_LENGTH                              4

#define          _OBSTACLE_RADIUS_FACTOR                    8

#define          _OBSTACLE_RADIUS                     _OBSTACLE_RADIUS_FACTOR
* _UNIT_LENGTH

#define          _COLLISION_VISIBILITY_FACTOR 25

#define          _WIDEVIEW_RADIUS_FACTOR                          200

#define          _NARROWVIEW_RADIUS_FACTOR                    50

#define          _LIMITEDVIEW_RADIUS_FACTOR              30

#define          _SEPARATION_FACTOR                        5

#define          _BACK_VIEW_ANGLE_FACTOR                  1

#define          _FRONT_VIEW_ANGLE_FACTOR         1

#define          _NUM_OBSTACLES                               8

// Global Variables:

int                        FrameCounter = 0;

RigidBody2D        Units[_MAX_NUM_UNITS];

Vector                   Target;

Vector                   Obstacles[_NUM_OBSTACLES];

bool Initialize(void)

{

       int i;

       GetRandomNumber(0, _WINWIDTH, true);

                    

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

       {    

              Units[i].fMass = 10;

              Units[i].fInertia = 10;

              Units[i].fInertiaInverse = 1/10;

              Units[i].vPosition.x =
GetRandomNumber(_WINWIDTH/2-_SPAWN_AREA_R, _WINWIDTH/2+_SPAWN_AREA_R, false);

              Units[i].vPosition.y =
GetRandomNumber(_WINHEIGHT/2-_SPAWN_AREA_R, _WINHEIGHT/2+_SPAWN_AREA_R, false);

              Units[i].fWidth = _UNIT_LENGTH/2;

              Units[i].fLength = _UNIT_LENGTH;

              Units[i].fHeight = _UNIT_LENGTH;

              Units[i].fOrientation = GetRandomNumber(0, 360, false); 

              Units[i].CD.y = -0.12*Units[i].fLength;       Units[i].CD.x =
0.0f;                   // coordinates of the body center of drag

              Units[i].CT.y = -0.50*Units[i].fLength;       Units[i].CT.x =
0.0f;                    // coordinates of the propeller thrust vector

              Units[i].CPT.y = 0.5*Units[i].fLength;        Units[i].CPT.x =
-0.5*Units[i].fWidth; // coordinates of the port bow thruster

              Units[i].CST.y = 0.5*Units[i].fLength;        Units[i].CST.x =
0.5*Units[i].fWidth;  // coordinates of the starboard bow thruster

              Units[i].ProjectedArea = (Units[i].fLength + Units[i].fWidth) *
Units[i].fHeight;

              Units[i].Leader = false;

             

              if(i>_MAX_NUM_UNITS/2)

              {

                     Units[i].Interceptor = true;

                     Units[i].ThrustForce = _THRUSTFORCE*1.5f;

              } else {

                     Units[i].Interceptor = false;

                     Units[i].ThrustForce = _THRUSTFORCE;

              }           

       }

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

       {

              Obstacles[i].x = GetRandomNumber(_OBSTACLE_RADIUS*4,
_WINWIDTH-_OBSTACLE_RADIUS*4, false);

              Obstacles[i].y =
/*_WINHEIGHT/2;*/GetRandomNumber(_OBSTACLE_RADIUS*4,
_WINHEIGHT-_OBSTACLE_RADIUS*4, false);

       }

       return true;

}

void DoUnitAI(int i)

{

             

              int          j;

              int          N;

              Vector     Pave;

              Vector     Vave;

              Vector     Fs;

              Vector     Pfs;

              Vector     d, u, v, w;

              double    m;

              int          Nf;

              bool InView;

              bool DoFlock = WideView || LimitedView || NarrowView;

              int          RadiusFactor;

              // begin Flock AI

              Fs.x = Fs.y = Fs.z = 0;

              Pave.x = Pave.y = Pave.z = 0;

              Vave.x = Vave.y = Vave.z = 0;

              N = 0;

              Pfs.x = 0;

              Pfs.y = Units[i].fLength / 2.0f;

              Nf = 0;

             

              for(j=1; j<_MAX_NUM_UNITS; j++)

              {

                     if(i!=j)

                     {

                            InView = false;

                            d = Units[j].vPosition - Units[i].vPosition;

                            w = VRotate2D(-Units[i].fOrientation, d);

                           

                            if(((w.y > 0) && (fabs(w.x) <
fabs(w.y)*_FRONT_VIEW_ANGLE_FACTOR)))

                                   if(d.Magnitude() <= (Units[i].fLength *
_NARROWVIEW_RADIUS_FACTOR))

                                          Nf++;

                            if(WideView)

                            {

                                   InView = ((w.y > 0) || ((w.y < 0) &&
(fabs(w.x) > fabs(w.y)*_BACK_VIEW_ANGLE_FACTOR)));

                                   RadiusFactor = _WIDEVIEW_RADIUS_FACTOR;

                            }

                            if(LimitedView)

                            {

                                   InView = (w.y > 0);

                                   RadiusFactor = _LIMITEDVIEW_RADIUS_FACTOR;

                            }

                            if(NarrowView)

                            {

                                   InView = (((w.y > 0) && (fabs(w.x) <
fabs(w.y)*_FRONT_VIEW_ANGLE_FACTOR)));

                                   RadiusFactor = _NARROWVIEW_RADIUS_FACTOR;

                            }

                           

                            if(InView && (Units[i].Interceptor ==
Units[j].Interceptor))                   

                            {

                                   if(d.Magnitude() <= (Units[i].fLength *
RadiusFactor))

                                   {

                                          Pave += Units[j].vPosition;

                                          Vave += Units[j].vVelocity;

                                          N++;

                                   }

                            }

                            // Separation Rule:

                            if(InView)//(w.y > 0) || ((w.y < 0) && (fabs(w.x)
> fabs(w.y)*_BACK_VIEW_ANGLE_FACTOR)))

                            {                                

                                   if(d.Magnitude() <= (Units[i].fLength *
_SEPARATION_FACTOR))

                                   {

                                          if(w.x < 0) m = 1;

                                          if(w.x > 0) m =
-1;                                    

                                         

                                          Fs.x += m*_STEERINGFORCE *
(Units[i].fLength * _SEPARATION_FACTOR) / d.Magnitude();

                                   }

                            }

                           

                     }

              }

             

              // Cohesion Rule:

              if(DoFlock && (N > 0))

              {

                     Pave = Pave / N;

                     v = Units[i].vVelocity;

                     v.Normalize();

                     u = Pave - Units[i].vPosition;

                     u.Normalize();

                     w = VRotate2D(-Units[i].fOrientation, u);

                     if(w.x < 0) m = -1;

                     if(w.x > 0) m = 1;

                     if(fabs(v*u) < 1.0f)

                            Fs.x += m * _STEERINGFORCE * acos(v * u) / pi;

              }

              // Alignment Rule:

              if(DoFlock && (N > 0))

              {

                     Vave = Vave / N;

                     u = Vave;

                     u.Normalize();

                     v = Units[i].vVelocity;

                     v.Normalize();             

                     w = VRotate2D(-Units[i].fOrientation, u);

                     if(w.x < 0) m = -1;

                     if(w.x > 0) m = 1;

                     if(fabs(v*u) < 1)

                            Fs.x += m * _STEERINGFORCE * acos(v * u) / pi;

              }

              // Chase the target if the unit is a leader

              if(Chase)

              {

                     if(Nf == 0)

                            Units[i].Leader = true;

                     else

                            Units[i].Leader = false;

                     if((Units[i].Leader || !DoFlock))

                     {                         

                            if(!Units[i].Interceptor)

                            {

                                   //
Chase                                           

                                   u = Units[0].vPosition;

                                   d = u - Units[i].vPosition;

                                   w = VRotate2D(-Units[i].fOrientation, d);

                                   if(w.x < 0) m = -1;

                                   if(w.x > 0) m = 1;

                                   Fs.x += m*_STEERINGFORCE;

                            } else {

                                   // Intercept           

                                   Vector     s1, s2, s12;

                                   double    tClose;   

                                   Vector     Vr12;

                                   Vr12 =
Units[0].vVelocity-Units[i].vVelocity; // closing velocity

                                   s12 = Units[0].vPosition -
Units[i].vPosition; // range to close

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

                                   s1 = Units[0].vPosition +
(Units[0].vVelocity * tClose);

                                   Target = s1;

                                   s2 = s1 - Units[i].vPosition;  

                                   w = VRotate2D(-Units[i].fOrientation, s2); 

                                   if(w.x < 0) m = -1;

                                   if(w.x > 0) m = 1;

                                   Fs.x += m*_STEERINGFORCE;

                            }

                     }

              }

             

              // Collision avoidance (with static obstacles)

              Vector     a, p, b;          

             

              for(j=0; j<_NUM_OBSTACLES; j++)

              {

                     u = Units[i].vVelocity;

                     u.Normalize();

                     v = u * _COLLISION_VISIBILITY_FACTOR * Units[i].fLength;

                    

                     a = Obstacles[j] - Units[i].vPosition;

                     p = (a * u) * u;

                     b = p - a;

                     if((b.Magnitude() < _OBSTACLE_RADIUS) && (p.Magnitude() <
v.Magnitude()))

                     {

                            // impending collision...steer away

                            w = VRotate2D(-Units[i].fOrientation, a);

                            w.Normalize();

                            if(w.x < 0) m = 1;

                            if(w.x > 0) m = -1;

                            Fs.x += m * _STEERINGFORCE *
(_COLLISION_VISIBILITY_FACTOR * Units[i].fLength)/a.Magnitude();

                     }

              }

             

             

              // apply accumulated steering force

              Units[i].Fa = Fs;

              Units[i].Pa = Pfs;

              // end Flock AI

}

void UpdateSimulation(void)

{

       double    dt = _TIMESTEP;

       int          i;

      

       // initialize the back buffer

       if(FrameCounter >= _RENDER_FRAME_COUNT)

       {

              ClearBackBuffer();

              DrawObstacles();

       }

      

       // Update player controlled unit:   

       Units[0].SetThrusters(false, false, 1);

       Units[0].SetThrusters(false, false, 1);

       if (IsKeyDown(VK_RIGHT))

              Units[0].SetThrusters(true, false, 0.5);

       if (IsKeyDown(VK_LEFT))

              Units[0].SetThrusters(false, true, 0.5);

       Units[0].UpdateBodyEuler(dt);

       if(FrameCounter >= _RENDER_FRAME_COUNT)

              DrawCraft(Units[0], RGB(0, 255, 0));

       if(Units[0].vPosition.x > _WINWIDTH) Units[0].vPosition.x = 0;

       if(Units[0].vPosition.x < 0) Units[0].vPosition.x = _WINWIDTH;

       if(Units[0].vPosition.y > _WINHEIGHT) Units[0].vPosition.y = 0;

       if(Units[0].vPosition.y < 0) Units[0].vPosition.y = _WINHEIGHT;

      

       // update computer controlled units:     

       for(i=1; i<_MAX_NUM_UNITS; i++)

       {           

              DoUnitAI(i);

             

              Units[i].UpdateBodyEuler(dt);

              if(FrameCounter >= _RENDER_FRAME_COUNT)

              {

                     if(Units[i].Leader)

                            DrawCraft(Units[i], RGB(255,0,0));

                     else {

                            if(Units[i].Interceptor)

                                   DrawCraft(Units[i], RGB(255,0,255));       

                            else

                                   DrawCraft(Units[i], RGB(0,0,255));

                     }

              }

              if(Units[i].vPosition.x > _WINWIDTH) Units[i].vPosition.x = 0;

              if(Units[i].vPosition.x < 0) Units[i].vPosition.x = _WINWIDTH;

              if(Units[i].vPosition.y > _WINHEIGHT) Units[i].vPosition.y = 0;

              if(Units[i].vPosition.y < 0) Units[i].vPosition.y =
_WINHEIGHT;           

       } // end i-loop

       if(FrameCounter >= _RENDER_FRAME_COUNT) {

              CopyBackBufferToWindow();

              FrameCounter = 0;

       }  else

              FrameCounter++;

}

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 = 0.025;

              // 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 DrawObstacles(void)

{

       int          i;

       RECT     r;

       int          radius = _OBSTACLE_RADIUS/2;

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

       {

              SetRect(&r, Obstacles[i].x - radius, Obstacles[i].y - radius,
Obstacles[i].x + radius, Obstacles[i].y + radius);

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

       }

}

/*

void DoAttractCraft2(void)

{

       // Apply Leonard-Jones potential force to Craft2

       // todo: make sure rigidbody calcloads function handles it

       Vector     r = Craft2.vPosition - Craft1.vPosition;

       Vector  u = r;

       u.Normalize();

       double    k1 = 0.5e2; // repel

       double    k2 = 1.0e2; // attract

       Craft2.Fa = VRotate2D( -Craft2.fOrientation,
((k1*pow(Craft2.fLength*5/r.Magnitude(), 4) -
k2*pow(Craft2.fLength*3/r.Magnitude(), 2)) ) * u);

       Craft2.Pa.x = 0;

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

       Target = Craft1.vPosition;

      

}

*/

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;

}

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信