source: golgotha/src/golg/solvemap_astar.cc @ 80

Last change on this file since 80 was 80, checked in by Sam Hocevar, 12 years ago
  • Adding the Golgotha source code. Not sure what's going to be interesting in there, but since it's all public domain, there's certainly stuff to pick up.
File size: 5.3 KB
Line 
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
17i4_profile_class pf_solve_astar("solve_astar");
18
19const i4_float sqrt2 = sqrt(2.0);
20
21enum { VISITED = g1_map_cell_class::SCRATCH1, OK = g1_map_cell_class::SCRATCH2 };
22
23inline void visit(w16 x, w16 y)
24{
25  g1_get_map()->cell(x,y)->flags |= VISITED;
26}
27
28inline void ok(w16 x, w16 y)
29{
30  g1_get_map()->cell(x,y)->flags |= OK;
31}
32
33inline i4_bool is_visited(w16 x, w16 y)
34{
35  return (g1_get_map()->cell(x,y)->flags & VISITED)!=0;
36}
37
38inline 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
46inline 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
54typedef g1_astar_map_solver_class::cell cell_type;
55int 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
66i4_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
100i4_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
119i4_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
135i4_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
152void 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
171i4_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,y-1, l+1);
201    add_step_link(x,y, x-1,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, x-1,y+1, l+sqrt2);
206    add_step_link(x,y, x+1,y-1, l+sqrt2);
207    add_step_link(x,y, x-1,y-1, 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 (nx-x==dx && ny-y==dy)
227      points--;
228    dx = nx-x;
229    dy = ny-y;
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// folded-file: t
245// End:
246//}}}
Note: See TracBrowser for help on using the repository browser.