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 <math.h>


10  #include "solvemap_astar.hh"


11  #include "memory/malloc.hh"


12  #include "error/error.hh"


13  #include "map.hh"


14  #include "map_man.hh"


15  #include "time/profile.hh"


16 


17  i4_profile_class pf_solve_astar("solve_astar");


18 


19  const i4_float sqrt2 = sqrt(2.0);


20 


21  enum { VISITED = g1_map_cell_class::SCRATCH1, OK = g1_map_cell_class::SCRATCH2 };


22 


23  inline void visit(w16 x, w16 y)


24  {


25  g1_get_map()>cell(x,y)>flags = VISITED;


26  }


27 


28  inline void ok(w16 x, w16 y)


29  {


30  g1_get_map()>cell(x,y)>flags = OK;


31  }


32 


33  inline i4_bool is_visited(w16 x, w16 y)


34  {


35  return (g1_get_map()>cell(x,y)>flags & VISITED)!=0;


36  }


37 


38  inline void set_solve_link(w16 x, w16 y, w16 from_x, w16 from_y)


39  {


40  g1_map_cell_class *c = g1_get_map()>cell(x,y);


41 


42  c>scratch_x = from_x;


43  c>scratch_y = from_y;


44  }


45 


46  inline void solve_link(w16 x, w16 y, w16 &from_x, w16 &from_y)


47  {


48  g1_map_cell_class *c = g1_get_map()>cell(x,y);


49 


50  from_x = c>scratch_x;


51  from_y = c>scratch_y;


52  }


53 


54  typedef g1_astar_map_solver_class::cell cell_type;


55  int cell_compare(const i4_float *a, const cell_type *b)


56  {


57  i4_float ca = *a, cb = b>hint + b>length;


58  if (cb<ca)


59  return 1;


60  else if (cb>ca)


61  return 1;


62  else


63  return 0;


64  }


65 


66  i4_bool g1_astar_map_solver_class::add_link(w16 from_x,w16 from_y, w16 x,w16 y,


67  i4_float from_length)


68  //{{{


69  {


70  set_solve_link(x,y, from_x,from_y);


71  visit(x,y);


72 


73  i4_float


74  dx = dest_x  x,


75  dy = dest_y  y,


76  hint = dx*dx+dy*dy,


77  cost = hint + from_length;


78  w32 loc;


79  cell *p;


80 


81  if (heap.size()>0)


82  {


83  w32 hs = heap.size();


84  i4_bsearch(&cost, loc, &heap[0], hs, cell_compare);


85 


86  p = heap.add_at(loc);


87  }


88  else


89  p = heap.add();


90 


91  p>x = x;


92  p>y = y;


93  p>length = from_length;


94  p>hint = hint;


95 


96  return i4_T;


97  }


98  //}}}


99 


100  i4_bool g1_astar_map_solver_class::add_step_link(w16 from_x,w16 from_y, w16 x,w16 y,


101  i4_float from_length)


102  //{{{


103  {


104  g1_map_class *map = g1_get_map();


105 


106  if (x<=1  x>=map>width()1  y<=1  y>=map>height())


107  return i4_F;


108 


109  if (is_visited(x,y))


110  return i4_F;


111 


112  if (g1_get_map()>cell(x,y)>get_solid_list())


113  return i4_F;


114 


115  return add_link(from_x,from_y, x,y, from_length);


116  }


117  //}}}


118 


119  i4_bool g1_astar_map_solver_class::add_path_link(w16 from_x,w16 from_y, w16 x,w16 y,


120  i4_float from_length)


121  //{{{


122  {


123  g1_map_class *map = g1_get_map();


124 


125  if (x<=1  x>=map>width()1  y<=1  y>=map>height())


126  return i4_F;


127 


128  if (is_visited(x,y))


129  return i4_F;


130 


131  return add_link(from_x,from_y, x,y, from_length);


132  }


133  //}}}


134 


135  i4_bool g1_astar_map_solver_class::get_next_cell(w16 &x,w16 &y, i4_float &length)


136  //{{{


137  {


138  if (heap.size()==0)


139  return i4_F;


140 


141  cell *p = &heap[heap.size()1];


142  x = p>x;


143  y = p>y;


144  length = p>length;


145 


146  heap.remove(heap.size()1);


147 


148  return i4_T;


149  }


150  //}}}


151 


152  void g1_astar_map_solver_class::clear_solve()


153  //{{{


154  {


155  int x=0,y=0;


156  g1_map_class *map=g1_get_map();


157  g1_map_cell_class *c;


158 


159  for (y=0; y<map>height(); y++)


160  {


161  c = map>cell(0,y);


162  for (x=0; x<map>width(); x++)


163  {


164  c>flags &= ~VISITED;


165  c++;


166  }


167  }


168  }


169  //}}}


170 


171  i4_bool g1_astar_map_solver_class::path_solve(i4_float startx, i4_float starty,


172  i4_float destx, i4_float desty,


173  i4_float *point, w16 &points)


174  //{{{


175  {


176  pf_solve_astar.start();


177 


178  w16 x = (w16)startx,y = (w16)starty;


179  i4_float l;


180 


181  dest_x = (w16)destx;


182  dest_y = (w16)desty;


183 


184  clear_heap();


185  clear_solve();


186 


187  add_link(x, y, x, y, 0);


188 


189  i4_bool found=i4_F;


190 


191  while (!found && get_next_cell(x,y,l))


192  {


193  if (x==dest_x && y==dest_y)


194  {


195  found = i4_T;


196  break;


197  }


198 


199  add_step_link(x,y, x,y+1, l+1);


200  add_step_link(x,y, x,y1, l+1);


201  add_step_link(x,y, x1,y, l+1);


202  add_step_link(x,y, x+1,y, l+1);


203 


204  add_step_link(x,y, x+1,y+1, l+sqrt2);


205  add_step_link(x,y, x1,y+1, l+sqrt2);


206  add_step_link(x,y, x+1,y1, l+sqrt2);


207  add_step_link(x,y, x1,y1, l+sqrt2);


208 


209  g1_object_chain_class *c = g1_get_map()>cell(x,y)>get_obj_list();


210  }


211 


212  if (!found)


213  {


214  pf_solve_astar.stop();


215  return i4_F;


216  }


217 


218  w16 nx=dest_x,ny=dest_y;


219  sw16 dx=0,dy=0;


220  x = nx+1;


221 


222  points = 0;


223  while (x!=nx  y!=ny)


224  {


225  ok(nx,ny);


226  if (nxx==dx && nyy==dy)


227  points;


228  dx = nxx;


229  dy = nyy;


230  x = nx; y = ny;


231  point[points*2]= i4_float(x*2+1)/2.0;


232  point[points*2+1]= i4_float(y*2+1)/2.0;


233  points++;


234  solve_link(x,y, nx,ny);


235  }


236 


237  pf_solve_astar.stop();


238  return i4_T;


239  }


240  //}}}


241 


242  //{{{ Emacs Locals


243  // Local Variables:


244  // foldedfile: t


245  // End:


246  //}}}

