source: golgotha/src/golg/visible.cc

Last change on this file 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: 7.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
10
11#include "visible.hh"
12#include "map.hh"
13#include "map_cell.hh"
14
15/*
16Fast Line-Edge Intersections on a Uniform Grid
17by Andrew Shapira
18from "Graphics Gems", Academic Press, 1990
19*/
20
21
22
23#define G1_STOP(hx, hy) \
24{                 \
25  S("stopped"); x2=lx;          \
26  y2=ly;          \
27  hit_x=hx;       \
28  hit_y=hy;       \
29  return i4_F;    \
30}
31
32#define S(x) { i4_warning("%s : %d %d",x,cx,cy); }
33
34#define OCTANT(f1, f2, f3, f4, f5, i1, s1, r1, r2)              \
35{                                                               \
36for (f1, f2, f3, nr = 0; f4; f5)                                \
37{                                                               \
38  if (nr < liconst)                                             \
39  {                                                             \
40    if (i1)                                                     \
41    { S("test 1");                                                          \
42      if (map->cell(cx, cy)->is_blocking())                      \
43        { G1_STOP(cx,cy);  }                                    \
44    } else if  (map->cell(cx, cy)->is_blocking())                \
45    { G1_STOP(cx,cy); }                                         \
46    else if (map->cell(cx-1, cy-1)->is_blocking())               \
47    { G1_STOP(cx-1,cy-1); }                                     \
48    else if (map->cell(cx, cy-1)->is_blocking())                 \
49    { G1_STOP(cx,cy-1); }                                       \
50    else if (map->cell(cx-1, cy)->is_blocking())                 \
51    { G1_STOP(cx-1, cy);  }                                     \
52  }                                                             \
53  else                                                          \
54  {                                                             \
55    s1;                                                         \
56    if (nr -= liconst)                                          \
57    {                                                           \
58      S("test 2"); if (map->cell(cx, cy)->is_blocking())                      \
59        { G1_STOP(cx,cy);  }                                    \
60    } else if  (map->cell(cx, cy)->is_blocking())                \
61    { G1_STOP(cx,cy); }                                         \
62    else if (map->cell(cx-1, cy-1)->is_blocking())               \
63    { G1_STOP(cx-1,cy-1); }                                     \
64    else if (map->cell(cx, cy-1)->is_blocking())                 \
65    { G1_STOP(cx,cy-1); }                                       \
66    else if (map->cell(cx-1, cy)->is_blocking())                 \
67    { G1_STOP(cx-1, cy);  }                                     \
68  }                                                             \
69  lx=cx;                                                        \
70  ly=cy;                                                        \
71}                                                               \
72return i4_T;                                                    \
73}                                                               
74
75i4_bool g1_visibility_check_old(sw32 x1, sw32 y1,
76                            sw32 &x2, sw32 &y2,
77                            sw32 &hit_x, sw32 &hit_y,
78                            g1_map_class *map)
79
80{
81  sw32 cx, cy, lx=x1, ly=y1;
82
83  sw32         nr;             /* remainder */
84  sw32         deltax, deltay; /* Q.x - P.x, Q.y - P.y */
85  sw32         liconst;          /* loop-invariant constant */
86
87  deltax = x2 - x1;
88  deltay = y2 - y1;
89
90  if (x1==x2)
91  {
92    int add=y1>y2 ? -1 : 1;
93    while (y1!=y2)
94    {
95      if (map->cell(x1,y1)->is_blocking())
96      {
97        hit_x=x1;
98        hit_y=y1;
99        y2=y1-add;
100        return i4_F;
101      }
102      y1+=add;
103    }
104  }
105  else if (y1==y2)
106  {
107    int add=x1>x2 ? -1 : 1;
108    while (x1!=x2)
109    {
110      if (map->cell(x1,y1)->is_blocking())
111      {
112        hit_x=x1;
113        hit_y=y1;
114        x2=x1-add;
115        return i4_F;
116      }
117      x1+=add;
118    }
119  }
120
121
122  i4_warning("--------------");
123     
124
125  /* for reference purposes, let theta be the angle from P to Q */
126
127  if ((deltax >= 0) && (deltay >= 0) && (deltay < deltax))
128    /* 0 <= theta < 45 */
129    OCTANT(cx = x1 + 1, cy = y1, liconst = deltax - deltay,
130           cx < x2, cx++, nr += deltay, cy++, up, left)
131  else if ((deltax > 0) && (deltay >= 0) && (deltay >= deltax))
132    /* 45 <= theta < 90 */
133    OCTANT(cy = y1 + 1, cx = x1, liconst = deltay - deltax,
134           cy < y2, cy++, nr += deltax, cx++, right, down)
135  else if ((deltax <= 0) && (deltay >= 0) && (deltay > -deltax))
136    /* 90 <= theta < 135 */
137    OCTANT(cy = y1 + 1, cx = x1, liconst = deltay + deltax,
138           cy < y2, cy++, nr -= deltax, cx--, left, down)
139  else if ((deltax <= 0) && (deltay > 0) && (deltay <= -deltax))
140    /* 135 <= theta < 180 */
141    OCTANT(cx = x1 - 1, cy = y1, liconst = -deltax - deltay,
142           cx > x2, cx--, nr += deltay, cy++, up, right)
143  else if ((deltax <= 0) && (deltay <= 0) && (deltay > deltax))
144    /* 180 <= theta < 225 */
145    OCTANT(cx = x1 - 1, cy = y1, liconst = -deltax + deltay,
146           cx > x2, cx--, nr -= deltay, cy--, down, right)
147  else if ((deltax < 0) && (deltay <= 0) && (deltay <= deltax))
148    /* 225 <= theta < 270 */
149    OCTANT(cy = y1 - 1, cx = x1, liconst = -deltay + deltax,
150           cy > y2, cy--, nr -= deltax, cx--, left, up)
151  else if ((deltax >= 0) && (deltay <= 0) && (-deltay > deltax))
152    /* 270 <= theta < 315 */
153    OCTANT(cy = y1 - 1, cx = x1, liconst = -deltay - deltax,
154           cy > y2, cy--, nr += deltax, cx++, right, up)
155  else if ((deltax >= 0) && (deltay < 0) && (-deltay <= deltax))
156    /* 315 <= theta < 360 */
157    OCTANT(cx = x1 + 1, cy = y1, liconst = deltax + deltay,
158           cx < x2, cx++, nr -= deltay, cy--, down, left)
159  return i4_T;
160                                           
161}
162
163
164i4_bool g1_visibility_check(sw32 x1, sw32 y1,
165                            sw32 &x2, sw32 &y2,
166                            sw32 &hit_x, sw32 &hit_y,
167                            g1_map_class *map)
168{
169  // this does a fixed point step through the blocks the line passes through
170
171  enum { POINT_5=(0xffff/2) };
172
173  sw32 fx=(x1<<16)+POINT_5, fy=(y1<<16)+POINT_5, lx,ly,nx,ny;
174  lx=x1; ly=y1;
175 
176  sw32 sx=(x2-x1), sy=(y2-y1), t;
177  if (x1==x2 && y1==y2)
178    return i4_T;
179
180  if (abs(sx)>abs(sy))
181    t=abs(sx);
182  else
183    t=abs(sy);
184
185  sx=(sx<<16)/t;
186  sy=(sy<<16)/t;
187
188
189  while (t)
190  {
191   
192
193
194
195    fx+=sx;    fy+=sy;
196    nx=fx>>16; ny=fy>>16;
197
198    if (nx!=lx && map->cell(nx, ly)->is_blocking())
199    {
200      x2=lx;     y2=ly;      hit_x=nx;  hit_y=ly;      return i4_F;
201    }
202    else if (ny!=ly && map->cell(lx, ny)->is_blocking())
203    {
204      x2=lx;     y2=ly;      hit_x=lx;  hit_y=ny;      return i4_F;
205    }
206    else if ((nx!=lx && ny!=ly) && map->cell(nx, ny)->is_blocking())
207    {
208      x2=lx;     y2=ly;      hit_x=nx;  hit_y=ny;      return i4_F;
209    }
210
211    lx=fx>>16; ly=fy>>16;         
212
213    t--;
214  }
215  return i4_T;
216}
Note: See TracBrowser for help on using the repository browser.