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

Last change on this file since 80 was 80, checked in by Sam Hocevar, 11 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: 6.7 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 "path_api.hh"
10#include "solvemap_astar.hh" //(OLI) Debug hack
11#include <math.h>
12
13extern g1_astar_map_solver_class *g1_solvemap;
14
15int 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         x-k>=0 &&
22         !is_blocked(x-k,y,dir) &&
23         x+k<width() &&
24         !is_blocked(x+k,y,dir))
25    k++;
26  return k;
27}
28
29int 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         y-k>=0 &&
36         !is_blocked(x,y-k,dir) &&
37         y+k<height() &&
38         !is_blocked(x,y+k,dir))
39    k++;
40  return k;
41}
42
43#if 1
44int floor(i4_float val) { return i4_f_to_i(val); }
45int ceil(i4_float val) { return 2048-i4_f_to_i(2048.0-val); }
46
47i4_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 (y1-rad_y<0) rad_y = y1;
61  if (y1+rad_y>i4_float(height())) rad_y = i4_float(height()) - y1;
62  if (y2-rad_y<0) rad_y = y2;
63  if (y2+rad_y>i4_float(height())) rad_y = i4_float(height()) - y2;
64  if (x1-rad_x<0) rad_x = x1;
65  if (x1+rad_x>i4_float(width())) rad_x = i4_float(width()) - x1;
66  if (x2-rad_x<0) rad_x = x2;
67  if (x2+rad_x>i4_float(width())) rad_x = i4_float(width()) - x2;
68
69  dist_y = y2-y1;
70  dist_x = x2-x1;
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 = (x2-x1)/(y2-y1);                         // change in X over y
97  iy = floor(y1-rad_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(x1-rad_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(x2-rad_x);
112    rbx = ceil(x1+rad_x);
113    lx = floor(x1-rad_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 = (y1-y-1);
156          fit = (fity>fit)? fity : fit;
157        }
158        else if (y>y2)
159        {
160          i4_float fity = (y-y2);
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
178i4_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=x2-x1,
186    dy=y2-y1,
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(xdir|ydir),max_fit))>=i &&
203         (max_fit = max_fit_NS(x1,y1-i,g1_compass_direction(xdir|ydir),max_fit))>=i)
204    i++;
205  max_fit=i-1;
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 = dy-xf + 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 = dx-yf + 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 = dx-yf + 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 = dy-xf + 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
Note: See TracBrowser for help on using the repository browser.