/*
  XBubble - path_init.c
 
  Copyright (C) 2002  Ivan Djelic <ivan@savannah.gnu.org>
  Copyright (C) 2003  Martin Quinson <mquinson@savannah.gnu.org>
  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.
  
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
*/

#include <stdio.h>

#include <string.h>
#include <math.h>
#include <assert.h>

#include "utils.h"
#include "setting.h"
#include "bubble.h"
#include "cell.h"

static int debug=1; /* To control the verbosity of the cache creation stuff */

/* xbubble_path_cache is what this program builds. 
   Fake definition here to break dependency loop, to compile cell.c
   (which we need to load to get low level stuff, and which loads the result
    of this program by declaring 'extern int xbubble_path_cache') */
int xbubble_path_cache[2][ROWS][NB_ANGLES][2][TRAJ_MAX_LENGTH];


/* We use a cache to compute quickly were a launched ball will land */
typedef struct {
  Vector neighbor;
  Vector position;
} LaunchPath;


static int cellXY( CellArray ca, double x, double y ) {
  double rx, ry;
  int column, row, rest, a, b, c, e;
  e = ca->parity;
  rx = (x-(e+1.0)/4);
  ry = 2*ROW_HEIGHT*(y-0.5) + 1;
  a = (int) floor(rx+ry);
  b = (int) floor(ry-rx);
  c = (int) floor(2*x + (1-e)/2);
  row = (a+b)/3;
  rest = e*(row%2);
  column = (c+rest)>>1;
  return cellCL( ca, row, column );
}

/* Algorithm for the target cell finding:
   (applied for each possible angle in target_cell_init() to fill the cache in)

   While the bubble did not reach the top:
     Compute the next segment the ball will cover, ie the position on which it will either
       stick on the ceiling (and end of the algorithm) or bump against a wall (before 
       covering yet another segment

     Clip the searched area for colliding balls for efficiency

     For each ball in the covered area:
       if the trajectory of the ball touches the ball, 
          store where, and after which distance on the segment

     Sort the array of reached position by lenght of the covered area

     Put it in the cache of paths.
	
*/
typedef struct {
  int neighbor;  /* pos of the neighbor */
  int position;  /* where to go if neighbor is there */
  double dist;   /* Y distance covered on the segment to get there */
} possible_target_t;

/**
 * possible_target_cmp:
 * 
 * Helping function of cell_path_init() to qsort() between the different possible 
 * target and get the closer one (which will be kept)
 */
int possible_target_cmp(const void *a, const void *b) { /* used to qsort */
  return ((possible_target_t*)a)->dist < ((possible_target_t*)b)->dist ? -1 :
        (((possible_target_t*)a)->dist > ((possible_target_t*)b)->dist ? 1 : 0);
}




/**
 * compute_one_traj:
 *
 * FIXME: TODO
 * Compute one of the trajectories
 
void compute_one_traj(int parity, int ceiling, int angle) {
}
 */

/**
 * path_init:
 * 
 * Computes the caches of trajectories path
 */
void path_init( void ) {
  int angle, i, ceiling,parity;
  double cdist= COLLISION_DIST*COLLISION_DIST; /* square of the collision distance */
  CellArray ca;
  Vector neighbor, position;
   
  /* malloc the tables */

  neighbor = vector_new(25);
  position = vector_new(25);
  ca=cell_array_new(1);
    
  /* for each parity */
  for (parity=0;parity<2;parity++){
    ca->parity *= -1; /* parity=0 => ca->parity=-1; p=1 => ca->p=1 */
    printf("  /* parity=%d */ {\n", parity);

    for (ceiling=0; ceiling<ROWS ; ceiling++) {
      ca->first_row=ceiling;
      printf("    /* ceiling=%d */ {\n",ceiling);
      for (angle=0; angle<NB_ANGLES; angle++) {
	double vx,vy; /* speed (ie, direction) of the bubble */
	double v2;    /* square bubble velocity */
	double xt,yt; /* position of the target */
	double xb,yb; /* position of segment begin */
	double xe,ye; /* position of segment end */
	double xc;    /* temp for x position. */
	
	double half_range; /* horizontal cross-section of bubble sweeping area */
	int min_col, max_col, min_row, max_row; /* area searched for colision */
	int col,row; /* position of currently searched */
	int cell,first_col; /* position of the corner of the searched area */
	double xa,ya; /* pos of the ball with which we may collide */
	double dp; /* dot product: used to check if we approach or leave the considered ball */
	double seg_len; /* length of this segment */
	int ceiling_pos=OUT_OF_BOUNDS; /* position to get when sticked to the ceiling */
	
	int bouncing; /* set to 0 when stick to the top */

	if (debug) fprintf(stderr,"PARITY=%d(%c); CEILING=%d; ANGLE=%d:",parity,parity==0?'-':'+',ceiling,angle);
	printf("      /* angle=%d */ {\n",angle);

	vector_empty(neighbor);
	vector_empty(position);
      
	vx = LAUNCHING_SPEED *   sin( (angle-CANON_ANGLE_MAX)*ANGLE_STEP );
	vy = LAUNCHING_SPEED * - cos( (angle-CANON_ANGLE_MAX)*ANGLE_STEP );

	half_range = sqrt( 1 + vx*vx/vy/vy );
	bouncing=1;
	xb=CANON_X;
	yb=CANON_Y;
	v2 = vx*vx + vy*vy;
	
	while (bouncing) {
	  possible_target_t targets[NB_CELLS];
	  int target_count=0;
	  
	  /* Where would be the ball at the level of the ceiling when going that direction? */
	  xc = xb + ( ceiling_y(ca) - yb )*vx/vy;
	  if ( xc < 0.5 ) { /* Too left: hits the wall before */
	    xe = 0.5;
	    ye = yb + ( xe - xb )*vy/vx;
	  } else if ( xc > COLS - 0.5 ) { /* Too right: hits wall */
//	  xe = 2*COLS - 1.0 - xc; /* always stay inside board cells */
	    xe = COLS - 0.5; /* always stay inside board cells */
	    ye = yb + ( xe - xb )*vy/vx; 
	  } else { /* bubble hits ceiling: this segment is the last one */
	    bouncing = 0;
	    xe = xc;
	    ye = (0.5 + ceiling*ROW_HEIGHT);
	    ceiling_pos=cellXY( ca, xe, ye );
	  }
	  if (debug>1) fprintf(stderr,"[%.1f;%.1f -> %.1f;%.1f;vx=%f;vy=%f]\n",xb,yb,xe,ye,vx,vy);
	  seg_len = ( ye - yb )/vy; /* segment length */
	  
	  /* now scan cells and look for any colliding bubble */
	  
	  /* try to minimize row range */
	  max_row = clip( (int) floor( yb / ROW_HEIGHT ) + 1, 0, ROWS-1 );
	  min_row = clip( (int) floor( ye / ROW_HEIGHT ) - 1, 0, ROWS-1 );
	  if (debug>1) fprintf(stderr,"Rows=%d-%d\n",min_row,max_row);
	  /* scan from bottom to top */
	  for ( row = max_row; row >= min_row; row-- ) {
	    cell = COLS*row;
	    /* column range */
	    first_col = row_start( ca, row); /* 0 when parity=1; 1 when parity=-1 */
	    /* xc = intersection between row and bubble trajectory */
	    xc = xb + ( row*ROW_HEIGHT + 0.5 - yb )*vx/vy - ( 1.0 - first_col )/2;
	    /* restrict cell scan to a small horizontal range : */
	    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 );
	    if (debug>1) 
	      fprintf(stderr,"Row=%d; first_col=%d; half_range=%.1f;xc=%.1f Cols=%d-%d\n",
		      row, first_col, half_range,xc,min_col,max_col);
	  
	    for ( col = min_col; col <= max_col; col++ ) {
	      /* We have a potential collider in cell[col+cell], let's call it 'A'.
		 We now check if A will intersect our bubble (let's call it 'M').
	       
		 let's compute ( xa, ya ) = location of bubble A */
	      cell_center( ca, col + cell, &xa, &ya );
	      if (debug>1) fprintf(stderr,"%d (%.1f;%.1f)=>",col+cell,xa,ya);
	      
	      /* dot product: used to check if bubble M is approaching
		 or leaving bubble A (hence the ( dp > 0 ) test ) */
	      dp = vx*( xa - xb ) + vy*( ya - yb );
	    
	      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 a collision if AH <= 1.
		  Thus, we compute AH using a vector product :

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

		  Since v and MA are in the same plane we have:

		      vp = | vy*( xa - xb ) - vx*( ya - yb ) |
	    
		      AH = |MA.sin(theta)| = vp/v
	    
		  But instead of computing v = sqrt(v2), we compute 
		  vp2 = vp.vp = v2.AH.AH, such that :

		      AH = sqrt( vp2 / v2 )
	    
		  Now the test AH <= 1 becomes vp2 <= v2.
	      */
		double vp, vp2;
		
		vp = vy*( xa - xb ) - vx*( ya - yb );
		vp2 = vp*vp;
	      
		/*
		  Strictly speaking, if AH <= 1 then bubbles will intersect.
		  But we relax this condition for easier aiming:
                  AH <= COLLISION_DIST
		*/
		if ( vp2 <= cdist*v2 ) {
		  double dist;
		  /* 
		     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 = COLLISION_DIST )
		  */
		  dist = ( dp - sqrt( v2*cdist - vp2 ) )/v2;
		  if (debug>1) fprintf(stderr,"(d=%f) ",dist);
		  if (dist >= 0 && dist <= seg_len) {
		    xt = xb + vx*dist;
		    yt = yb + vy*dist;
		    
		  //		  if (xt < 0.5) xt=1-xt;
		  //		  if (xt >  COLS - 0.5001) xt = 2*COLS - 1.0002 - xt;
		    targets[target_count].neighbor=col+cell;
		    targets[target_count].position=cellXY( ca, xt, yt );
		    targets[target_count].dist=dist;
		    if (targets[target_count].position == -1) {
		      if (debug>1) {
			fprintf(stderr,"Pos (%.1f;%.1f) => -1 because of %d\n",xt,yt,col+cell);
		      }
		      if (debug>2) abort();
		    } else {
		      target_count++;
		    }
		    if (debug>1) fprintf(stderr,"%d\n",targets[target_count-1].position);
		  } else {if (debug>1) fprintf (stderr,"dist=%.1f<0;\n",dist); }
		} else {if (debug>1) fprintf (stderr,"too far;\n");}
	      } else { if (debug>1) fprintf (stderr,"dp=%.1f<0;{vx=%.1f,xa-xb=%.1f;vy=%.1f,ya-yb=%.1f}\n",dp,vx,xa-xb,vy,ya-yb);	}
	    }
	  }
	  /* sort out the targets found on this segment, and push them to the cache */
	  qsort(targets,target_count, sizeof(possible_target_t),&possible_target_cmp);
	  for (i=0; i<target_count; i++) {
	    vector_push(neighbor, targets[i].neighbor);
	    vector_push(position, targets[i].position);

//	   printf(" ,%d,%d",targets[i].neighbor,targets[i].position);
//	  printf("  vector_push(path[%d][%d][% 3d].neighbor, %d);\t",
//		 parity%2,ceiling,angle,   targets[i].neighbor);
//	  printf("vector_push(path[%d][%d][% 3d].position, %d);\n",
//		 parity%2,ceiling,angle,   targets[i].position);
	    if (debug) fprintf (stderr, " (%d,%d)", targets[i].neighbor, targets[i].position);
	  }
	
	  /* prepare for next segment */
	  if (bouncing) {
	    vx *= -1;
	    xb = xe;
	    yb = ye;
	  } else {
	   
//	   vector_push(neighbor, OUT_OF_BOUNDS);
//	  vector_push(position, ceiling_pos);
	   
//	  printf(" ,%d,%d);\n",OUT_OF_BOUNDS,ceiling_pos);

//	  printf("  vector_push(path[%d][%d][% 3d].neighbor, %d);\t",
//		 parity%2,ceiling,angle,   OUT_OF_BOUNDS);
//	  printf("vector_push(path[%d][%d][% 3d].position, %d);\n\n",
//		 parity%2,ceiling,angle,   ceiling_pos);

//	  vector_push(path[parity%2][ceiling][angle].neighbor, OUT_OF_BOUNDS);
//	  vector_push(path[parity%2][ceiling][angle].position, ceiling_pos);
	    if (debug) fprintf (stderr, " (###,%d)\n", ceiling_pos);
	  }
	}
	/* There is no new segment: Output the traj. */
	
	if (neighbor->size >= TRAJ_MAX_LENGTH)
	  fail("the constant TRAJ_MAX_LENGTH is too small (%d=<%d). Please edit setting.h",
	       TRAJ_MAX_LENGTH,neighbor->size);

	printf("        /* neighbor */ {");
	for (i=0;i<TRAJ_MAX_LENGTH; i++){
	  printf(" %-2d%c",
		 (i<neighbor->size   ? neighbor->element[i] :
		  (i==neighbor->size ? OUT_OF_BOUNDS : 0 )),
		 (i<TRAJ_MAX_LENGTH-1?',':' '));
	}
	printf("},\n");

	printf("        /* position */ {");
	for (i=0;i<TRAJ_MAX_LENGTH; i++){
	  printf(" %-2d%c",
		 (i<position->size   ? position->element[i] :
		  (i==position->size ? ceiling_pos : 0 )),
		 (i<TRAJ_MAX_LENGTH-1?',':' '));
	}
	printf("}\n");
	
	printf("      }%c /* angle=%d */%c\n", 
	       angle < NB_ANGLES-1 ? ',' : ' ',
	       angle,
	       angle < NB_ANGLES-1 ? '\n' : ' ');
      }
      printf("    }%c /* ceiling=%d */%c\n",
	     ceiling < ROWS-1 ? ',' : ' ',
	     ceiling,
	     ceiling < ROWS-1 ? '\n' : ' ');
    }
    printf("  }%c /* parity=%d */\n", (parity == 0 ? ',' : ' '), parity);
  }


  cell_array_free(ca);
  vector_free(neighbor);
  vector_free(position);
}

int main() {
  printf("/* This file is generated. Do not edit */\n");
  printf("/* Here are the trajectories as computed at compilation time */\n\n");

  printf("/* parity x ceiling x angle x { neighbor; position } x { several positions } */\n\n");
  printf("int xbubble_path_cache[2][%d][%d][2][%d] = {\n",ROWS,NB_ANGLES,TRAJ_MAX_LENGTH);
  path_init();
  printf("}; /* path */\n");
  return 0;
}