1  /********************************************************************** <BR>


2  This file is part of Crack dot Com's free source code release of


3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for


4  information about compiling & licensing issues visit this URL</a>


5  <PRE> If that doesn't help, contact Jonathan Clark at


6  golgotha_source@usa.net (Subject should have "GOLG" in it)


7  ***********************************************************************/


8 


9  #include "path_api.hh"


10  #include "solvemap_astar.hh" //(OLI) Debug hack


11  #include <math.h>


12 


13  extern g1_astar_map_solver_class *g1_solvemap;


14 


15  int g1_block_map_class::max_fit_NS(int x, int y, g1_compass_direction dir, int max) const


16  {


17  int k;


18 


19  k=0;


20  while (k<max &&


21  xk>=0 &&


22  !is_blocked(xk,y,dir) &&


23  x+k<width() &&


24  !is_blocked(x+k,y,dir))


25  k++;


26  return k;


27  }


28 


29  int g1_block_map_class::max_fit_WE(int x, int y, g1_compass_direction dir, int max) const


30  {


31  int k;


32 


33  k=0;


34  while (k<max &&


35  yk>=0 &&


36  !is_blocked(x,yk,dir) &&


37  y+k<height() &&


38  !is_blocked(x,y+k,dir))


39  k++;


40  return k;


41  }


42 


43  #if 1


44  int floor(i4_float val) { return i4_f_to_i(val); }


45  int ceil(i4_float val) { return 2048i4_f_to_i(2048.0val); }


46 


47  i4_float g1_block_map_class::line_of_sight(i4_float x1, i4_float y1, i4_float x2, i4_float y2,


48  i4_float rad_x, i4_float rad_y) const


49  {


50  i4_float x, y, dx, fit, max_fit;


51  i4_float tmp, dist_y, dist_x;


52  int ix, iix, iy, lx, rx, nlx, nrx, min_lx, max_rx, lbx, rbx;


53  int ey;


54  int flip;


55  w8 dir;


56 


57  //{{{ setup


58 


59  // limit rad values


60  if (y1rad_y<0) rad_y = y1;


61  if (y1+rad_y>i4_float(height())) rad_y = i4_float(height())  y1;


62  if (y2rad_y<0) rad_y = y2;


63  if (y2+rad_y>i4_float(height())) rad_y = i4_float(height())  y2;


64  if (x1rad_x<0) rad_x = x1;


65  if (x1+rad_x>i4_float(width())) rad_x = i4_float(width())  x1;


66  if (x2rad_x<0) rad_x = x2;


67  if (x2+rad_x>i4_float(width())) rad_x = i4_float(width())  x2;


68 


69  dist_y = y2y1;


70  dist_x = x2x1;


71 


72  // direction of blocking that would stop movement


73  dir = ((dist_y<0)? G1_NORTH : G1_SOUTH)  ((dist_x<0)? G1_EAST : G1_WEST);


74 


75  // absolute values of distances


76  dist_y = (dist_y<0) ? dist_y: dist_y;


77  dist_x = (dist_x<0) ? dist_x: dist_x;


78 


79  if (dist_x>dist_y)


80  {


81  // flip axes for easier processing


82  flip=1;


83  tmp = x1; x1 = y1; y1 = tmp;


84  tmp = x2; x2 = y2; y2 = tmp;


85  tmp = rad_x; rad_x = rad_y; rad_y = tmp;


86  }


87  else


88  flip=0;


89 


90  if (y1>y2)


91  {


92  tmp = x1; x1 = x2; x2 = tmp;


93  tmp = y1; y1 = y2; y2 = tmp;


94  }


95 


96  dx = (x2x1)/(y2y1); // change in X over y


97  iy = floor(y1rad_y); // integer 'pixel' location


98  y = iy;


99  ey = ceil(y2+rad_y); // ending row


100  x = x1 + (i4_float(iy+1)y1)*dx; // center of edge


101  if (dx>0)


102  {


103  lbx = floor(x1rad_x); // bounding edges


104  rbx = ceil(x2+rad_x);


105  lx = lbx; // initial left edge


106  rx = ceil(x1+rad_x); // initial right edge


107  max_fit = rad_x + rad_y*dx; // initial corridor width


108  }


109  else


110  {


111  lbx = floor(x2rad_x);


112  rbx = ceil(x1+rad_x);


113  lx = floor(x1rad_x);


114  rx = rbx;


115  max_fit = rad_x  rad_y*dx;


116  }


117  //}}}


118 


119  // Edge Stepping


120  while (iy<ey && max_fit>0)


121  {


122  // calculate locations of next edges


123  nlx = floor(x  max_fit);


124  nlx = (lbx>nlx)? lbx : nlx;


125  nrx = ceil(x + max_fit);


126  nrx = (rbx<nrx)? rbx : nrx;


127 


128  // scan row


129  ix = floor(x),


130  min_lx = (dx>0)? lx : nlx,


131  max_rx = (dx>0)? nrx : rx ;


132 


133  for (iix=min_lx; iix<max_rx; iix++)


134  {


135  //{{{ (OLI) Debug hack


136  #if 0


137  if (g1_solvemap)


138  if (flip)


139  g1_solvemap>ok(iy,iix);


140  else


141  g1_solvemap>ok(iix,iy);


142  #endif


143  //}}}


144  if ((!flip && is_blocked(iix,iy,dir)) 


145  (flip && is_blocked(iy,iix,dir)))


146  {


147  if (iix==ix)


148  fit = 0.0;


149  else if (iix<ix)


150  fit = x  i4_float(iix+1);


151  else


152  fit = i4_float(iix)  x;


153  if (y<y1)


154  {


155  i4_float fity = (y1y1);


156  fit = (fity>fit)? fity : fit;


157  }


158  else if (y>y2)


159  {


160  i4_float fity = (yy2);


161  fit = (fity>fit)? fity : fit;


162  }


163  max_fit = (fit<max_fit)? fit : max_fit;


164  }


165  }


166 


167  // update values to next row


168  iy++;


169  x += dx;


170  y += 1.0;


171  lx = nlx; rx = nrx;


172  }


173 


174  i4_float d = sqrt(1.0+dx*dx);


175  return max_fit/d;


176  }


177  #else


178  i4_float g1_block_map_class::line_of_sight(i4_float _x1, i4_float _y1, i4_float _x2, i4_float _y2,


179  i4_float rad_x, i4_float rad_y) const


180  {


181  int x1=int(_x1),y1=int(_y1),x2=int(_x2),y2=int(_y2);


182 


183  int max_fit = 20;


184  int


185  dx=x2x1,


186  dy=y2y1,


187  sx,sy,


188  x,y,


189  xf,yf,


190  nx,ny;


191 


192  g1_compass_direction xdir,ydir;


193 


194  // determine step directions


195  if (dx>=0) { sx=1; xdir = G1_WEST; }


196  else { sx=1; xdir = G1_EAST; dx=dx; }


197  if (dy>=0) { sy=1; ydir = G1_SOUTH; }


198  else { sy=1; ydir = G1_NORTH; dy=dy; }


199 


200  // find maximum size convoy that can fit at start point


201  int i=0;


202  while ((max_fit = max_fit_NS(x1,y1+i,g1_compass_direction(xdirydir),max_fit))>=i &&


203  (max_fit = max_fit_NS(x1,y1i,g1_compass_direction(xdirydir),max_fit))>=i)


204  i++;


205  max_fit=i1;


206 


207  // initial positions & fractions


208  x = x1; y =y1;


209  xf = dy/2; yf = dx/2;


210 


211  if (dx>dy)


212  {


213  while (x!=x2  y!=y2)


214  {


215  ny = dyxf + yf;


216  if (ny>dx)


217  {


218  while (max_fit_NS(x,y+sy*max_fit,ydir,max_fit)<max_fit)


219  max_fit;


220  if (max_fit==0)


221  return 0;


222  y += sy;


223  xf = dxyf + xf;


224  yf = 0;


225  }


226  else


227  {


228  while (max_fit_WE(x+sx*max_fit,y,xdir,max_fit)<max_fit)


229  max_fit;


230  if (max_fit==0)


231  return 0;


232  x += sx;


233  yf = ny;


234  xf = 0;


235  }


236  }


237  }


238  else


239  {


240  while (x!=x2  y!=y2)


241  {


242  nx = dxyf + xf;


243  if (nx>dy)


244  {


245  while(max_fit_WE(x+sx*max_fit,y,xdir,max_fit)<max_fit)


246  max_fit;


247  if (max_fit==0)


248  return 0;


249  x += sx;


250  yf = dyxf + yf;


251  xf = 0;


252  }


253  else


254  {


255  while(max_fit_NS(x,y+sy*max_fit,ydir,max_fit)<max_fit)


256  max_fit;


257  if (max_fit==0)


258  return 0;


259  y += sy;


260  xf = nx;


261  yf = 0;


262  }


263  }


264  }


265  return max_fit;


266  }


267  #endif

