00001 00002 /* 00003 * 00004 * Original author: unknown 00005 * 00006 * Copyright (c) 1996-2002 Markus Stenberg 00007 * Copyright (c) 1998-2002 Thomas Wouters 00008 * Copyright (c) 2000-2002 Cord Awtry 00009 * 00010 */ 00011 00012 /************************************************************* 00013 **** LOS code ********************************************** 00014 ************************************************************** 00015 00016 What happens in the code now: 00017 (pretty close, anyway -- I haven't spent THAT much time studying it. 00018 00019 Right now, the code just finds a line between the hexes and steps 00020 along it in units of 1 hex, checking each hex it enters. This is, 00021 well, wrong. It makes no allowance whatsoever that the LOS line might 00022 "clip" the edge of a hex, and will occasionally skip hexes: 00023 __ __ __ 00024 /# \__/ \__/# \ 00025 \__/ \__/ \__/ is possible, when it SHOULD be: 00026 __ __ __ 00027 /# \__/ \__/# \ A 1 hex wide wall in the first case would be 00028 \__/ \__/ \__/ skipped entirely. 00029 \__/ \__/ 00030 00031 Now my, (correct, but tougher) algorithm: 00032 00033 OK, first FASA rules: "The LOS is checked by laying a straightedge 00034 ... from the center of the attackers's hex to the center of the 00035 target's hex. Any hex that the straightedge crosses is in the LOS. 00036 If the straightedge passes directly between two hexes, the defender 00037 chooses which hex ist passes through." -- Compendium, p21 00038 00039 It is fairly easy to convince yourself that the case of the line lying 00040 directly between two hexes is a well-defined special case: it happens 00041 only when the hexes lie exactly on a 30, 90, 150, 210, 270, or 330 00042 line. This is easy to check for, so we'll put that check in as the 00043 first stage of the routine. We'll assume from then on that the line 00044 is not a special case (which is good -- the numbers explode to 00045 infinity for 90 degree lines). 00046 00047 Now we iterate as the current muse code does. We start at the hex at 00048 one end of the line, find the next one, and repeat until we get to the 00049 end. Here is the algorithm for finding the "next" hex: 00050 00051 First, we need only check the 6 adjacent hexes (obviously -- but the 00052 current code ignores this and sometimes returns "next" hexes that are 00053 not adjacent). 00054 00055 In addition, an eligible hex muse be "on the line." That is, the 00056 imaginary line drawn between the endpoints must pass through the hex. 00057 Figuring this out is the "meat" of this algorithm. The best way to 00058 determine this (that I have discovered, anyway) is to find the 00059 (absolute, cartesian, floating point) distance between the center 00060 point of the hex in question and the line (i.e. the length of a line 00061 drawn from the center of hex, perpendicular to the LOS line). If this 00062 distance is less than the "effective radius" of the hex, then the line 00063 lies inside the hex. By "effective radius" I mean the width of the 00064 hex along a line perpendicular to the LOS line. This will vary 00065 (depending on the angle of the line) between 0.5 (if the hex is lying 00066 flat along the line -- i.e. a line pointing at 30, 90, 150, 210, 270, 00067 or 330 degrees) and (1/sqrt(3)) (if the line passes only through the 00068 point of the hex -- i.e. a line pointing at 0, 60, 120, 180, 240, or 00069 300) 00070 00071 _Effective_Radius_ 00072 _____ _____ 00073 / \ | / \ / (Hope this diagram makes sense! 00074 / \| / *_ \ / the *'s are the line representing 00075 \ /| \ * // the effective radius) 00076 \_____/ | \_____// 00077 *****| / 00078 00079 (1/sqrt(3)) 0.5 00080 00081 For other angles, the effective radius varies as a cosine. Since the 00082 whole thing is periodic with intervals of 60 deg, we can "modulo" it 00083 by subtracting 60 deg until we get the angle to within a -30 < angle < 00084 30 degrees region and then taking the cosine. 00085 00086 Hoof! That's the worst of it. Now, from among the adjacent, eligible 00087 hexes, the "next" one is the one that is closest "along the line" to 00088 the one we are in. (But is still closer to the endpoint than the 00089 current hex. We have to check here to make sure we don't hop back 00090 into the hex we came from!) 00091 00092 Now performance issues: 00093 00094 The main calculations here are the distance-to-line determination, and 00095 the effective radius calculation. Each of these must be performed 5 00096 times (6 adjacent hexes, but we don't have to check the one we came 00097 from). Distance-to-line is best found by using a matrix to rotate the 00098 coordinates to a frame where the line is horizontal and taking the 00099 difference in y coords between the hex and any point on the line (one 00100 of the endpoints will do). The angle to rotate is -(slope of the LOS 00101 line), which is -atan(y1-y2/x1-x2). The atan function need only be 00102 called once, since the slope of the line is unchanging. That leaves 00103 us with the matrix: |cos(u) -sin(u)| 00104 |sin(u) cos(u)| where u=-atan(y1-y2/x1-x2) 00105 00106 This contains four more trigonometric functions, but again each need 00107 only be called once (and there are really only two anyway, sin(u) and 00108 cos(u)). 00109 00110 The effective radius involves a cos() function. Again, though, since 00111 the slope of the line is unchanging, the effective radius of the hex 00112 is a constant throughout the iterations, and need only be calculated 00113 once. 00114 00115 So now we have one time costs: 00116 00117 *Calculate matrix coefficients: 1 atan(), 1 cos(), 1 sin() 00118 2 fp subtractions, 1 fp divide. 00119 00120 *Find effective radius: 1 cos(), 00121 <6 fp subtractions (to get -30<u<30) 00122 00123 And per-hex-travelled costs: 00124 00125 *Test 5 hexes if on line: 10 fp mults, 5 fp additions 00126 5 fp compares 00127 00128 *Test for closest forward hex: <5 fp compares 00129 00130 This is actually, I would think, not much more than the current LOS 00131 code, which makes many calls to RealCoordToMapCoord() (a costly 00132 function) and is generally messy, with lots of repeated mults by 00133 constants such as ZSCALE (which would optimize out, if we did, but we 00134 don't :) 00135 00136 ********************************************************************** 00137 00138 OK, enough of this. Let's get on to the code. 00139 */ 00140 00141 #include <stdio.h> 00142 #include <stdlib.h> 00143 #include <math.h> 00144 #include "mech.h" 00145 #include "btmacros.h" 00146 00147 #define DEG60 1.0471976 /* In radians, of course ;) */ 00148 #define DEG30 0.5235988 00149 #define ROOT3 1.7320508 00150 #define TRACESCALEMAP 1 00151 00152 typedef enum { N, NE, SE, S, SW, NW } hexdir; 00153 00154 #define Store_Hex(store_x,store_y) \ 00155 do { found_coords[found_count].x = store_x; \ 00156 found_coords[found_count++].y = store_y; } \ 00157 while (0) 00158 00159 #define Store_BestOf(x1,y1,x2,y2) \ 00160 if ( ((x1) < 0) || ((x1) >= map->map_width) || \ 00161 ((y1) < 0) || ((y1) >= map->map_height) ) \ 00162 { Store_Hex((x2), (y2)); } \ 00163 else if ( ((x2) < 0) || ((x2) >= map->map_width) || \ 00164 ((y2) < 0) || ((y2) >= map->map_height) ) \ 00165 { Store_Hex((x1), (y1)); }\ 00166 else if ((Elevation(map,(x1),(y1))) > (Elevation(map, (x2), (y2)))) \ 00167 { Store_Hex((x1),(y1)); } \ 00168 else { Store_Hex((x2),(y2)); } 00169 00170 #define LOS_MapCoordToRealCoord(x,y,cx,cy) \ 00171 do { cx = (float)x * ROOT3 / 2 * TRACESCALEMAP; \ 00172 cy = ((float)y - 0.5*(x%2))*TRACESCALEMAP;} while (0) 00173 00174 static void GetAdjHex(int currx, int curry, int nexthex, int *x, int *y) 00175 { 00176 switch (nexthex) { 00177 case N: 00178 *x = currx; 00179 *y = curry - 1; 00180 break; 00181 case NE: 00182 *x = currx + 1; 00183 *y = curry - (currx % 2); 00184 break; 00185 case SE: 00186 *x = currx + 1; 00187 *y = curry - (currx % 2) + 1; 00188 break; 00189 case S: 00190 *x = currx; 00191 *y = curry + 1; 00192 break; 00193 case SW: 00194 *x = currx - 1; 00195 *y = curry - (currx % 2) + 1; 00196 break; 00197 case NW: 00198 *x = currx - 1; 00199 *y = curry - (currx % 2); 00200 break; 00201 default: /* Mostly there to satisfy gcc */ 00202 fprintf(stderr, "XXX ARGH: TraceLos doesn't know where to go!\n"); 00203 *x = currx + 1; /* Just grab some values that aren't x/y */ 00204 *y = curry + 1; /* so we can break out of the loop */ 00205 } 00206 } 00207 00208 int TraceLOS(MAP * map, int ax, int ay, int bx, int by, 00209 lostrace_info ** result) 00210 { 00211 00212 int i; /* Generic counter */ 00213 float acx, acy, bcx, bcy; /* endpoints CARTESIAN coords */ 00214 float currcx, currcy; /* current hex CARTESIAN coords */ 00215 int currx, curry; /* current hex being worked from */ 00216 int nextx, nexty; /* x & y coords of next hex */ 00217 int bestx = 0, besty = 0; /* best found so far */ 00218 int lastx, lasty; /* Holding place for final intervening hex */ 00219 int xmul, ymul; /* Used in 30/150/210/330 special case */ 00220 hexdir nexthex; /* potential next hex being examined */ 00221 float nextcx, nextcy; /* Next hex's CARTESIAN coords */ 00222 float slope; /* slope of line */ 00223 float uangle; /* angle of line (in STD CARTESIAN FORM!) */ 00224 float sinu; /* sin of -uangle */ 00225 float cosu; /* cos of same */ 00226 float liney; /* TRANSFORMED y coord of the line */ 00227 float tempangle; /* temporary uangle used for effrad calc */ 00228 float effrad; /* effective radius of hex */ 00229 float currdist; /* distance along line of current hex */ 00230 float nextdist; /* distance along the line of potential hex */ 00231 float bestdist; /* "best" (not furthest) distance tried */ 00232 float enddist; /* distance along at end of line */ 00233 static lostrace_info found_coords[4000]; 00234 int found_count = 0; 00235 00236 /* Before doing anything, let's check for special circumstances, this */ 00237 /* means vertical lines (which work using the current code, but depend */ 00238 /* on atan returning proper vaules for atan(-Inf) -- which is probably */ 00239 /* slow and may break on non-ANSI systems; and also lines at 30, 90 */ 00240 /* etc.. degrees which contain 'ties' between hexes. FASA rules here */ 00241 /* say that the 'best' hex for the defender (the one that breaks LOS, */ 00242 /* or gives a greater BTH penalty) should be used. */ 00243 00244 /* THE base case */ 00245 if((ax == bx) && (ay == by)) { 00246 Store_Hex(bx, by); 00247 *result = found_coords; 00248 return found_count; 00249 } 00250 /* Is it vertical? */ 00251 if(ax == bx) { 00252 if(ay > by) 00253 for(i = ay - 1; i > by; i--) 00254 Store_Hex(ax, i); 00255 else 00256 for(i = ay + 1; i < by; i++) 00257 Store_Hex(ax, i); 00258 Store_Hex(bx, by); 00259 *result = found_coords; 00260 return found_count; 00261 } 00262 00263 /* Does it lie along a 90 degree 'tie' direction? */ 00264 /* IF(even-number-of-cols apart AND same-y-coord) */ 00265 if(!((bx - ax) % 2) && ay == by) { 00266 currx = ax; 00267 i = bx > ax ? 1 : -1; 00268 while (currx != bx) { 00269 /* Do best of (currx+1,by-currx%2) */ 00270 /* or (currx+1,by-currx%2+1) */ 00271 Store_BestOf(currx + 1 * i, by - currx % 2, currx + 1 * i, 00272 by - currx % 2 + 1); 00273 00274 if(currx != bx) 00275 Store_Hex(currx + 2 * i, by); 00276 00277 currx += 2 * i; 00278 } 00279 00280 /* Store_Hex(bx,by); */ 00281 *result = found_coords; 00282 return found_count; 00283 } 00284 00285 /* Does it lie along a 30, 150, 210, 330 degree 'tie' direction? */ 00286 /* This expression is messy, but it just means that a hex is along */ 00287 /* 30 degrees if the y distance is (the integer part of) 3/2 */ 00288 /* times the x distance, plus 1 if the x difference is odd, AND */ 00289 /* the original hex was in an even column and heads in the +y */ 00290 /* direction, or odd and goes -y. It works, try it :) */ 00291 if(abs(by - ay) == 00292 (3 * abs(bx - ax) / 2) + abs((bx - ax) % 2) * abs((by < 00293 ay) ? (ax % 00294 2) : (1 - 00295 ax % 00296 2))) { 00297 00298 /* First get the x and y 'multipliers' -- either 1 or -1 */ 00299 /* they determine the direction of the movement */ 00300 if(bx > ax) 00301 if(by > ay) { 00302 xmul = 1; 00303 ymul = 1; 00304 } else { 00305 xmul = 1; 00306 ymul = -1; 00307 } else if(by > ay) { 00308 xmul = -1; 00309 ymul = 1; 00310 } else { 00311 xmul = -1; 00312 ymul = -1; 00313 } 00314 00315 currx = ax; 00316 curry = ay; 00317 while ((currx != bx) && (curry != by)) { 00318 00319 Store_BestOf(currx, curry + ymul, currx + xmul, 00320 ymul == 00321 1 ? curry + 1 - currx % 2 : curry - currx % 2); 00322 00323 curry += (ymul == 1) ? (2 - currx % 2) : (-1 - currx % 2); 00324 currx += xmul; 00325 00326 if(currx == bx && curry == by) 00327 continue; 00328 00329 Store_Hex(currx, curry); 00330 } 00331 Store_Hex(currx, curry); 00332 *result = found_coords; 00333 return found_count; 00334 } 00335 00336 /****************************************************************************/ 00337 00338 /**** OK, now we know it's not a special case ******************************/ 00339 00340 /****************************************************************************/ 00341 00342 /* First get the necessary constants set up */ 00343 00344 LOS_MapCoordToRealCoord(ax, ay, acx, acy); 00345 LOS_MapCoordToRealCoord(bx, by, bcx, bcy); 00346 00347 slope = (float) (acy - bcy) / (float) (acx - bcx); 00348 00349 uangle = -atan(slope); 00350 00351 sinu = sin(uangle); 00352 cosu = cos(uangle); 00353 00354 liney = acx * sinu + acy * cosu; /* we could just as */ 00355 /* correctly use bx, by */ 00356 00357 enddist = bcx * cosu - bcy * sinu; 00358 00359 tempangle = fabs(uangle); 00360 while (tempangle > DEG60) 00361 tempangle -= DEG60; 00362 effrad = cos(tempangle - DEG30) * TRACESCALEMAP / ROOT3; 00363 00364 /*****************************************************************/ 00365 00368 /*****************************************************************/ 00369 00370 currx = ax; 00371 curry = ay; 00372 LOS_MapCoordToRealCoord(currx, curry, currcx, currcy); 00373 currdist = currcx * cosu - currcy * sinu; 00374 bestdist = enddist; /* set this to the endpoint, the worst */ 00375 /* possible point to go to */ 00376 00377 while (!(currx == bx && curry == by)) { 00378 00379 for(nexthex = N; nexthex <= NW; nexthex++) { 00380 00381 GetAdjHex(currx, curry, nexthex, &nextx, &nexty); 00382 LOS_MapCoordToRealCoord(nextx, nexty, nextcx, nextcy); 00383 00384 /* Is it on the line? */ 00385 if(fabs((nextcx * sinu + nextcy * cosu) - liney) > effrad) 00386 continue; 00387 00388 /* Where is it? Find the transformed x coord */ 00389 nextdist = nextcx * cosu - nextcy * sinu; 00390 00391 /* is it forward of the current hex? */ 00392 if(fabs(enddist - nextdist) > fabs(enddist - currdist)) 00393 continue; 00394 00395 /* Is it better than what we have? */ 00396 if(fabs(enddist - nextdist) >= fabs(enddist - bestdist)) { 00397 bestdist = nextdist; 00398 bestx = nextx; 00399 besty = nexty; 00400 } 00401 } 00402 00403 if(bestx == bx && besty == by) { /* If we've found the last hex, record */ 00404 lastx = currx; /* the current hex as the last */ 00405 lasty = curry; /* intervening hex, save currx/y, */ 00406 currx = bestx; /* and jump to the end of the loop */ 00407 curry = besty; 00408 continue; 00409 } 00410 00411 /* ********************************************************* */ 00412 /* HERE is where you put the test code for intervening hexes */ 00413 /* ********************************************************* */ 00414 Store_Hex(bestx, besty); 00415 /* ********************************************************* */ 00416 00417 currx = bestx; /* Reset the curr hex for the next iteration */ 00418 curry = besty; 00419 currdist = bestdist; 00420 bestdist = enddist; /* reset to worst possible value */ 00421 00422 } 00423 00424 /* **************************************************** */ 00425 /* HERE is where you put the test code for the LAST hex */ 00426 /* **************************************************** */ 00427 Store_Hex(currx, curry); 00428 /* ********************************************************* */ 00429 *result = found_coords; 00430 return found_count; 00431 }
1.4.7