Re: [Xbubble-users] i18n patch

[xbubble]

Quoting Martin Quinson <address@hidden>:

> I quickly checked, and the code of this part didn't seem to change. 

Yes it did ! See below...

> So,
> here
> is the feeling I have:
> 
> In this situation:
> 
>  .   .   .   .   .   .
>    .   .   .   .   .
>  .   .   .   .   X   .
>    .   .   .       .
>  .   .   .       .   .
>    .   A       B   .
> 
>            |
> 
> it is possible in fb to shoot at X while in xbubble, it will stick on A
> or B. 
> 

OK here is a commented version of target_cell() (xbubble-0.2.4):

This function takes an initial bubble location (x,y) with an initial
speed (vx,vy), and computes the exact location where this bubble
will end after it is fired (unlike in fb where this computation is
done step by step with a collision test during the animation).

The path vector is used in player vs computer mode (see opponent.c).

int target_cell( CellArray ca,
                 double x,
                 double y,
                 double vx,
                 double vy,
                 double * target_y, /* predicted target y */
                 Vector path ) {
  int row, col, first_col, min_col, max_col, min_row, max_row, cell;
  int bouncing = 1;
  double v2, dp, vp, vp2, xt, yt, xc, xa, ya, half_range, dist, min_dist;
  v2 = vx*vx + vy*vy;
  
  /* sanity check */
  if ( vy >= 0 )
    return OUT_OF_BOUNDS;

  if ( path != NULL )
    empty_vector(path);

  while ( bouncing ) {
    /* intersect trajectory with ceiling */
    xc = x + ( ceiling_y(ca) - y )*vx/vy;
    if ( xc < 0.5 ) { /* bubble hits left wall */
      xt = 0.5;
      yt = y + ( xt - x )*vy/vx;
    }
    else {
      if ( xc > COLS - 0.5001 ) { /* bubble hits right wall */
        xt = COLS - 0.5001; /* always stay inside board cells */
        yt = y + ( xt - x )*vy/vx; 
      }
      else { /* bubble hits ceiling */
      bouncing = 0;
      xt = xc;
      yt = ceiling_y(ca);
      }
    }
    min_dist = ( yt - y )/vy;
    /* now scan cells and look for a colliding bubble */

    /* here we could scan ALL cells starting from the bottom, 
       but we can optimize and restrict the range of cells to check:
       hence max_row, min_row, half_range, min_col, max_col...


    /* row range */
    max_row = clip( (int) floor( y / ROW_HEIGHT ) + 1, 0, ROWS-1 );
    min_row = clip( (int) floor( yt / ROW_HEIGHT ) - 1, 0, ROWS-1 );

    /* scan from bottom to top */
    for ( row = max_row; row >= min_row; row-- ) {
      cell = COLS*row;
      /* column range */
      half_range = sqrt( 1 + vx*vx/vy/vy );
      first_col = row_start( ca, row);
      xc = x + ( row*ROW_HEIGHT + 0.5 - y )*vx/vy - ( 1.0 - first_col )/2;
      min_col = clip( (int) floor( xc - half_range + 1 ), first_col, COLS-1 );
      max_col = clip( (int) floor( xc + half_range ), first_col, COLS-1 );

      for ( col = min_col; col <= max_col; col++ ) {
        if ( ca->cell[ col + cell ] != EMPTY_CELL ) {
          /* compute collision location */

/* here I check if our bubble (let's call it 'M') 
   trajectory intersects or not with
   bubble at row,col (which we'll call 'A') */

          cell_center( ca, col + cell, &xa, &ya );
          /* now (xa,ya) = location of bubble A */

          /* dot product: used to check if bubble M is approaching
           or leaving bubble A (hence the ( dp > 0 ) test )*/

          dp = vx*( xa - x ) + vy*( ya - y );

          if ( dp > 0 ) {
            /* Let v be the velocity vector of bubble M.
               Let theta = angle(v,MA).
               Then, let H be the
               orthogonal projection of A on (M,v):

                     A
                     +
                    /|
                   / |
                  /  |
                 /   |      
                /    |       
               /     |_       
            M +->....|.|..........
               v     H

            There will be collision if AH <= 1. So we need to compute
            AH.
            vp = v /\ MA = v.MA.sin(theta)      (vector product)

            AH = |MA.sin(theta)| = |vp/v|

            But I don't want to compute a slow v = sqrt(v2), so I
            compute vp2 = vp.vp = v2.AH.AH
*/
            vp2 = vp*vp; /* square vector product */

            /*  
               Now the test AH <= 1 becomes vp2 <= v2 */
            /*
              Strictly speaking, if vp2 <= v2 then bubbles will intersect.
              But we relax this condition so that the game is a little bit 
              easier :-). 
            */
            if ( vp2 <= 0.9*v2 ) {
              /* We have a collision. But where will M be when it
                 touches A ? In point T = M + dist.v :
                (T is on (M,v), between M and H and such that
                 TA = 1)
              */
              dist = ( dp - sqrt( v2 - vp2 ))/v2;
              if (( dist >= 0 )&&( dist <= min_dist )) {
                /* store the closest of all 'T points' */
                min_dist = dist;
                /* store location of point T */
                xt = x + vx*dist;
                yt = y + vy*dist;

                bouncing = 0;
                /* check next row and finish */
                if ( min_row < row - 1 )
                  min_row = row - 1;
              }
            }
          }
        }
        else
          if ( path != NULL )
            add_element_to_vector( path, col + cell );
      }
    }
    /* prepare for next part of trajectory */
    vx *= -1;
    x = xt;
    y = yt;
  }
  *target_y = yt;
  /* Now we know that bubble M will end touching a bubble (or the 
   ceiling) at point T (xt,yt). So let's compute the closest adjacent
   cell (that's where M will end up) :
   */
  return cellXY( ca, xt, yt );
}

I hope these explanations are useful, I suggest you use a paper and
a pencil to figure it out more clearly :-)
Side note: I had a look at fb source, and I saw that their collision
detection is not 100% accurate (for instance it can miss a collision
if you increase the velocity - this is inherent to the fact that
they detect collision during animation).

Ivan