GKアルゴリズム

河原林研究室 >> EcoBe!世界一への道 >> GKアルゴリズム

GKアルゴリズム †

• GKの行動は以下のアルゴリズムで開発を行った。
  • ボールが近いときは蹴りに行く(味方に)
  • それ以外の時はポジションに移動する

GKポジション †

• ここではGKポジションについて説明していく。

GKポジションのアルゴリズム †

• GKポジションは以下の図のように相手のシュートコースをなくすようにポジションを取ることにした。

ポジション座標計算 †

• GKのポジション座標は以下のように円と直線の交点を計算することにより求めた。

• main関数内

  a = sqrt((goal_xl - ball_x) * (goal_xl - ball_x) + ball_y * ball_y);
  b = goal_xl - goal_xr;
  c = sqrt((goal_xr - ball_x) * (goal_xr - ball_x) + ball_y * ball_y);
  fai[1] = acos((a*a + c+c -b*b) / (2*a*c));
  fai[2] = acos((a*a + b+b -c*c) / (2*a*b));
  fai[0] = 2*M_PI - (M_PI + fai[1]/2 + fai[2])
  tilt = atan(fai[0]);
  cons = ball_y - tilt * ball_x;

pt1[0] = ball_x;	//pt1:ball座標
pt1[1] = ball_y;
pt2[0] = (ball_y - cons) / titl;	//pt2:x軸との交点
pt2[1] = 0;
xyr[0] = x / 2.0;	//xyr:円の中心と半径
xyr[1] = 0;
xyr[2] = 300;
pnear[0] = x / 2.0;
pnear[1] = 200;
if(gPlayer.lncl( pt1 , pt2 , xyr , pnear , xy ) < 0){
	printf("Error,交点が存在しない。\n");
	exit(1);
}
posi[0] = xy[0];
posi[1] = xy[1];

• 直線の方程式の計算用関数

  int
  BasicPlayer :: lnprm( double *pt1, double *pt2, double *a, double *b, double *c )
  {
  	double  xlk, ylk, rsq, rinv;
  	double  accy = 1.0E-15;
  	xlk = pt2[0] - pt1[0];
  	ylk = pt2[1] - pt1[1];
  	rsq = pow(xlk, 2.0) + pow(ylk, 2.0);
  	if(rsq < accy){
  		return (-1);
  	}else{
  		rinv = 1.0 / sqrt(rsq);
  		*a = -ylk * rinv;
  		*b = xlk * rinv;
  		*c = (pt1[0] * pt2[1] - pt2[0] * pt1[1]) * rinv;
  	} 
  	return (0);
  }

• 円と直線の交点の計算

  int
  BasicPlayer :: lncl( double *pt1, double *pt2, double *xyr, double *pnear, double *xy)
  {
     double  root, factor, xo, yo, f, g, fsq, gsq, fgsq, xjo, yjo, a, b, c;
     double  fygx, fxgy, t, fginv, t1, t2, x1, y1, x2, y2, sqdst1, sqdst2;
     double  accy = 1.0E-15;
     if(lnprm(pt1, pt2, &a, &b, &c)) return (-1);
     root = 1.0 / (a*a + b*b);
     factor = -c * root;
     xo = a * factor;
     yo = b * factor;
     root = sqrt(root);
     f = b * root;
     g = -a * root;
     fsq = f*f;
     gsq = g*g;
     fgsq = fsq+gsq;
     if(fgsq < accy){
         return (3);
     }else{
         xjo = xyr[0] - xo;
         yjo = xyr[1] - yo;
         fygx = f*yjo - g*xjo;
         root = xyr[2]*xyr[2]*fgsq - fygx*fygx;
         if (root < -accy){  /* 交点なし */
             return (-1);
         }else{
             fxgy = f*xjo + g*yjo;
             if (root < accy){  /* 直線と円は接する。*/
                 t = fxgy / fgsq;
                 xy[0] = xo + f*t;
                 xy[1] = yo + g*t;
                 return (1);
             }else{
                 root = sqrt(root);
                 fginv = 1.0 / fgsq;
                 t1 = (fxgy - root)*fginv;
                 t2 = (fxgy + root)*fginv;
                 x1 = xo + f*t1;
                 y1 = yo + g*t1;
                 x2 = xo + f*t2;
                 y2 = yo + g*t2;
             }
         }
     }
     sqdst1 = pow((pnear[0] - x1), 2.0) + pow((pnear[1] - y1), 2.0);
     sqdst2 = pow((pnear[0] - x2), 2.0) + pow((pnear[1] - y2), 2.0);
     if (sqdst1 < sqdst2){  /* pnearに近い方の交点を返す。*/
         xy[0] = x1;
         xy[1] = y1;
     }else{
         xy[0] = x2;
         xy[1] = y2;
     }
     return (2);
  } 

• 上で挙げた関数は以下を参照した。
  • 円と直線の交点の計算：h ttp://www.shibata.nu/kenji/author/soft.html

ポジションまでのベクトル計算 †

• ポジションとプレイヤーの向きとの角度は以下の図のようにまず座標系のX座標に垂直となる角度を出し、その後それぞれの角度の差を取った。

• これを実装したのが以下のプログラムソースである。

  my_c = sqrt(my_x * my_x + my_y * my_y);
  my_angle = acos( my_y / my_c );
  my_angle = my_angle * 180.0 / M_PI;
  my_c1angle = mycorner2.angle;
  my_angle = my_angle + my_c1angle;
  my_angle = (int(my_angle) +360) % 360;	//-180〜180→0〜360
  ps_angle = atan( (my_x - posi[0]) / (posi[1] - my_y) );
  ps_angle = ps_angle * 180.0 /M_PI;			
  if(my_x - posi[0] < 0)
  	ps_angle = ps_angle + 180.0;
  ps_angle = (int(ps_angle) + 90 + 360) % 360;
  position.angle = my_angle - ps_angle;	//positionと自分の向きの角度
  if(position.angle < -180.0)
  	position.angle = position.angle +360.0;
  if(position.angle > 180.0)
  	position.angle = 180 - position.angle;
  position.length = sqrt((my_x - posi[0]) * (my_x - posi[0]) + (posi[1] - my_y) * (posi[1] - my_y));
  
  position.angle = position.angle * M_PI / 180.0;