pd.if.org Git - hexagon/blob - lib/hexagon.c

   1 #include "hexagon.h"
   2
   3 #include <math.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <limits.h>
   7
   8 /* constructor function */
   9 struct HL_hex HL_hex_xy(int x, int y) {
  10         struct HL_hex h;
  11         h.x = x;
  12         h.y = y;
  13         return h;
  14 }
  15
  16 int HL_hex_cmp(struct HL_hex const *a, struct HL_hex const *b) {
  17         if (a->x != b->x) {
  18                 return a->x > b->x ? 1 : -1;
  19         }
  20         if (a->y != b->y) {
  21                 return a->y > b->y ? 1 : -1;
  22         }
  23         return 0;
  24 }
  25
  26 int HL_hex_eq(struct HL_hex const *a, struct HL_hex const *b) {
  27         return a->x == b->x && a->y == b->y;
  28 }
  29
  30 /*
  31  * This file is written by Nathan Wagner and dedicated to the public
  32  * domain
  33  */
  34
  35 double HL_vertexv[12] = {
  36         .577350269189625764509148780502, 0.0,
  37         .288675134594812882254574390251, 0.5,
  38         -.288675134594812882254574390251, 0.5,
  39         -.577350269189625764509148780502, 0.0,
  40         -.288675134594812882254574390251, -0.5,
  41         .288675134594812882254574390251, -0.5};
  42
  43 double HL_fand[16] = {
  44         0.0, 0.0,
  45         .577350269189625764509148780502, 0.0,
  46         .288675134594812882254574390251, 0.5,
  47         -.288675134594812882254574390251, 0.5,
  48         -.577350269189625764509148780502, 0.0,
  49         -.288675134594812882254574390251, -0.5,
  50         .288675134594812882254574390251, -0.5,
  51         .577350269189625764509148780502, 0.0
  52 };
  53
  54 double HL_hfand[16] = {
  55         0.0, 0.0,
  56         0.0, .577350269189625764509148780502,
  57         0.5, .288675134594812882254574390251,
  58         0.5, -.288675134594812882254574390251,
  59         0.0, -.577350269189625764509148780502,
  60         -0.5, -.288675134594812882254574390251,
  61         -0.5, .288675134594812882254574390251,
  62         0.0, .577350269189625764509148780502
  63 };
  64
  65 float HL_fanf[16] = {
  66         0.0f, 0.0f,
  67         .577350269189625764509148780502f, 0.0f,
  68         .288675134594812882254574390251f, 0.5f,
  69         -.288675134594812882254574390251f, 0.5f,
  70         -.577350269189625764509148780502f, 0.0f,
  71         -.288675134594812882254574390251f, -0.5f,
  72         .288675134594812882254574390251f, -0.5f,
  73         .577350269189625764509148780502f, 0.0f
  74 };
  75
  76 float HL_hfanf[16] = {
  77         0.0f, 0.0f,
  78         0.0f, .577350269189625764509148780502f,
  79         0.5f, .288675134594812882254574390251f,
  80         0.5f, -.288675134594812882254574390251f,
  81         0.0f, -.577350269189625764509148780502f,
  82         -0.5f, -.288675134594812882254574390251f,
  83         -0.5f, .288675134594812882254574390251f,
  84         0.0f, .577350269189625764509148780502f
  85 };
  86
  87 /* size of a square that will exactly fit in a hexagon */
  88 /* 2.0/(1+sqrt(3.0)) */
  89 double HL_square = .73205080756887729352;
  90
  91 /* these all are for a hex one unit across */
  92 static double          hexptvd[6][2] = {
  93         {.577350269189625764509148780502, 0.0}, /* 1.0/sqrt3 */
  94         {.288675134594812882254574390251, 0.5}, /* 0.5/sqrt3 */
  95         {-.288675134594812882254574390251, 0.5},
  96         {-.577350269189625764509148780502, 0.0},
  97         {-.288675134594812882254574390251, -0.5},
  98         {.288675134594812882254574390251, -0.5}
  99 };
 100
 101 #if 0
 102
 103 /* TODO how is this related? to the above? */
 104 static double          texptvd[6][2] = {
 105         {1.154700538379251529018297561004, 0.5},        /* 2.0/sqrt3 */
 106         {.866025403784438646763723170753, 1.0}, /* 1.5/sqrt3 */
 107         {.288675134594812882254574390251, 1.0},
 108         {0.0, 0.5},
 109         {.288675134594812882254574390251, 0.0},
 110         {.866025403784438646763723170753, 0.0}
 111 };
 112
 113 static double          hexpthd[6][2] = {
 114         {0.0, .577350269189625764509148780502},
 115         {0.5, .288675134594812882254574390251},
 116         {0.5, -.288675134594812882254574390251},
 117         {0.0, -.577350269189625764509148780502},
 118         {-0.5, -.288675134594812882254574390251},
 119         {-0.5, .288675134594812882254574390251}
 120 };
 121
 122 #endif
 123
 124 #define RD (180.0 / M_PI)
 125 /* angle ranges from 0-6 */
 126 /* distance is 0 at origin, 1.0 at the hex side */
 127
 128 #if 0
 129         double sqrt3;
 130
 131         sqrt3 = sqrt(3.0);
 132
 133         1
 134       /---\
 135     2/     \0
 136     /       \
 137     \       /
 138     3\     /5
 139       \---/
 140         4
 141
 142       /\
 143     0/  \5
 144     /    \
 145     |    |
 146    1|    |4
 147     |    |
 148     \    /
 149     2\  /3
 150       \/
 151
 152 #endif
 153
 154 /* return the polar distance */
 155 struct HL_point HL_polar(double angle, double distance, double *d) {
 156         double A, B, C, b;
 157         struct HL_point pt;
 158
 159 #if 0
 160            C
 161           /\
 162        b /  \ a
 163         /    \
 164        /      \
 165      A -------- B
 166            c
 167
 168      c = 1 ; fixed, will scale later
 169      B = 60 ; exterior angle of hextant
 170      C = 180-B-A = 120-A ; sum of angles of a triangle
 171      A = function argument ; the polar coordinate we are calculating
 172      b = c * sin(B) / sin(C) ; law of sines
 173
 174 #endif
 175         /* convert angle to radians */
 176         angle = angle * M_PI / 3.0;
 177
 178         /* calculate the distance along the ray to the hex side */
 179
 180         A = fmod(angle, M_PI/3.0); /* constrain to within an equilateral */
 181         B = M_PI / 3.0;
 182         C = M_PI - B - A;
 183
 184         b = sin(B) / sin(C);
 185
 186         /* scale for hex one unit from side to side, rather than
 187          * one unit from center to vertex
 188          */
 189 /*      b = b * sqrt(3.0) / 2.0 / 2.0; */
 190         b = b / sqrt(3);
 191
 192         pt.x = distance * b * cos(angle);
 193         pt.y = distance * b * sin(angle);
 194
 195         if (d) {
 196                 *d = distance * b;
 197         }
 198
 199         return pt;
 200 }
 201
 202 void HL_vertices(struct HL_hex hex, double *vc) {
 203         int i;
 204         double xc, yc;
 205         struct HL_point center;
 206
 207         center = HL_hexcenter(hex);
 208         xc = center.x;
 209         yc = center.y;
 210
 211         for (i=0; i<6; i++) {
 212                 *vc++ = hexptvd[i][0] + xc;
 213                 *vc++ = hexptvd[i][1] + yc;
 214         }
 215         *vc++ = hexptvd[0][0] + xc;
 216         *vc++ = hexptvd[0][1] + yc;
 217 }
 218
 219 #if 0
 220 void HL_trianglefan(int cantor, double *vc) {
 221         HL_hexcenter(cantor, vc, vc+1);
 222         HL_vertices(cantor, vc+2);
 223 }
 224 #endif
 225
 226 struct HL_point HL_hexcenter(struct HL_hex hex) {
 227         int x, y;
 228         struct HL_point center;
 229         double yc;
 230
 231         double stride = 1.5/sqrt(3.0);
 232
 233         x = hex.x;
 234         y = hex.y;
 235
 236         center.x = x * stride;
 237
 238         if (x >= 0) yc = y + ((x + 1) % 2) / 2.0 - 0.5;
 239         if (x < 0) yc = y + ((-x + 1) % 2) / 2.0 - 0.5;
 240
 241         center.y = yc;
 242
 243         return center;
 244 }
 245
 246 /*
 247  * This function assumes that the hexes are one unit across, and vertically
 248  * oriented.  If that is not the case, you will need to transform
 249  * your input coordinates first.
 250  */
 251 struct HL_hex HL_bin(double x, double y) {
 252         return HL_hexbin(1.0, x, y);
 253 }
 254
 255 struct HL_isohex HL_xy2ijk(struct HL_hex hex) {
 256         int pi, pj, pk;
 257         int x, y;
 258         struct HL_isohex iso;
 259
 260         x = hex.x;
 261         y = hex.y;
 262
 263         pi = x;
 264         pj = -y;
 265
 266         if (x < 0) {
 267                 pj = pj + (-x + 1) / 2;
 268         } else {
 269                 pj = pj - x/2;
 270         }
 271         pk = -pi - pj;
 272
 273         iso.i = pi;
 274         iso.j = pj;
 275         iso.k = pk;
 276
 277         return iso;
 278 }
 279
 280 #if 0
 281
 282 static int xy2ijk(int x, int y, int *i, int *j, int *k) {
 283         int pi, pj, pk;
 284
 285         pi = x;
 286         pj = -y;
 287         if (x < 0) {
 288                 pj = pj + (-x + 1) / 2;
 289         } else {
 290                 pj = pj - x/2;
 291         }
 292         pk = -pi - pj;
 293
 294         if (i) *i = pi;
 295         if (j) *j = pj;
 296         if (k) *k = pk;
 297
 298         return HL_cantor_xy(x,y);
 299 }
 300 static int ijk2xy(int i, int j, int k, int *x, int *y) {
 301         int px, py;
 302
 303         px = i;
 304
 305         /* py = -j - i/2; */
 306         py = -j;
 307
 308         if (i < 0) {
 309                 py += (-i + 1)/2;
 310         } else {
 311                 py -= i/2;
 312         }
 313
 314         if (x) *x = px;
 315         if (y) *y = py;
 316
 317         return HL_cantor_xy(px,py);
 318 }
 319
 320 #endif
 321
 322 struct HL_hex HL_ijk2xy(struct HL_isohex iso) {
 323         int px, py;
 324         struct HL_hex xy;
 325         int i,j;
 326
 327         i = iso.i;
 328         j = iso.j;
 329
 330         px = i;
 331
 332         /* py = -j - i/2; */
 333         py = -j;
 334
 335         if (i < 0) {
 336                 py += (-i + 1)/2;
 337         } else {
 338                 py -= i/2;
 339         }
 340
 341         xy.x = px;
 342         xy.y = py;
 343
 344         return xy;
 345 }
 346
 347
 348 static void xy2ijkp(struct HL_hex h, int *ijk) {
 349         struct HL_isohex iso;
 350
 351         iso = HL_xy2ijk(h);
 352         ijk[0] = iso.i;
 353         ijk[1] = iso.j;
 354         ijk[2] = iso.k;
 355 }
 356
 357 int HL_distance(struct HL_hex from, struct HL_hex to) {
 358         int dist = 0, i;;
 359         int fc[3], tc[3];
 360
 361         xy2ijkp(from, fc);
 362         xy2ijkp(to, tc);
 363
 364         for (i=0;i<=2;i++) {
 365                 dist += abs(fc[i] - tc[i]);
 366         }
 367
 368         return dist / 2;
 369 }
 370
 371 int HL_hexes_within_range(struct HL_hex hex, int range, struct HL_hex *list, int size) {
 372         int count = 0;
 373         int i;
 374
 375         if (range == 0) {
 376                 return HL_hexes_at_range(hex, 0, list, size);
 377         }
 378
 379         for (i=1;i<=range;i++) {
 380                 count += HL_hexes_at_range(hex, i, count > size ? 0 : list+count, size-count);
 381         }
 382         return count;
 383 }
 384
 385 int HL_hexes_at_range(struct HL_hex hex, int range, struct HL_hex *list, int size) {
 386         int q; /* p and q are count/loop vars */
 387         struct HL_isohex iso;
 388
 389
 390         if (range == 0) {
 391                 if (list) {
 392                         list[0] = hex;
 393                 }
 394                 return 1;
 395         } else if (range < 0) {
 396                 return 0;
 397         }
 398
 399         /* TODO don't bother to collect if the list isn't big enough? */
 400         /* i.e. if (!list || size < range * 6) */
 401         if (!list || size < 1) return range * 6;
 402
 403         iso = HL_xy2ijk(hex);
 404
 405         iso.i += range;
 406         iso.k = -iso.i - iso.j;
 407
 408         hex = HL_ijk2xy(iso);
 409
 410         for(q=0; q<size && q < range * 6; q++) {
 411                 list[q] = hex;
 412                 hex = HL_adjhex(hex, q/range+2);
 413         }
 414
 415         return range * 6;
 416 }
 417
 418 /* direction 0 is positive X , counter clockwise from there */
 419 struct HL_hex HL_adjhex(struct HL_hex hex, int dir) {
 420         int c[3];
 421         struct HL_isohex iso;
 422
 423         iso = HL_xy2ijk(hex);
 424         c[0] = iso.i;
 425         c[1] = iso.j;
 426         c[2] = iso.k;
 427
 428         switch (dir%6) {
 429                 case 2:
 430                         c[0]--; c[1]++; break;
 431                 case 1:
 432                                 c[1]++; c[2]--; break;
 433                 case 0:
 434                         c[0]++;         c[2]--; break;
 435                 case 5:
 436                         c[0]++; c[1]--; break;
 437                 case 4:
 438                                 c[1]--; c[2]++; break;
 439                 case 3:
 440                         c[0]--;       ; c[2]++; break;
 441         }
 442
 443         iso.i = c[0];
 444         iso.j = c[1];
 445         iso.k = c[2];
 446
 447         return HL_ijk2xy(iso);
 448 }
 449
 450 int HL_adjhexp(struct HL_hex hex, int dir, struct HL_hex *adj) {
 451         if (adj) {
 452                 *adj = HL_adjhex(hex, dir);
 453         }
 454         return dir;
 455 }
 456
 457 /* Determine if a map with these dimensions will overflow */
 458 int HL_map_bounds_ok(int xdim, int ydim) {
 459
 460         /* return (x+y) * (x + y + 1) / 2 + y+1; */
 461
 462         if (INT_MAX - xdim - 1 < ydim) return 0;
 463         if (INT_MAX / (xdim+ydim) < (xdim+ydim+1)) return 0;
 464         if ( (xdim+ydim) * (xdim+ydim+1) / 2 > INT_MAX - ydim - 1)
 465                 return 0;
 466
 467         return 1;
 468 }
 469
 470 int HL_map_max_dimension(void) {
 471         int low, high, try;
 472
 473         low = 1; high = INT_MAX/2;
 474
 475         while (low != high - 1) {
 476                 try = (low + high) / 2;
 477                 if (HL_map_bounds_ok(try,try)) {
 478                         low = try;
 479                 } else {
 480                         high = try;
 481                 }
 482         }
 483
 484         return low;
 485 }
 486
 487 struct hex {
 488         int iso;
 489         int x, y, z;
 490 };
 491
 492 /* y *must* be positive down as the xy /iso conversion assumes this */
 493 static int hex_xy(struct hex *h) {
 494         if (!h->iso) return 1;
 495         if (h->x >= 0) {
 496                 h->y = -h->y - (h->x+1)/2;
 497         } else {
 498                 /* need to round toward -inf, not toward zero, so x-1 */
 499                 h->y = -h->y - h->x/2;
 500         }
 501         h->iso = 0;
 502
 503         return 1;
 504 }
 505
 506 #if 0
 507
 508 static int hex_iso(struct hex *h) {
 509         if (h->iso) return 1;
 510
 511         if (h->x >= 0) {
 512                 h->y = (-h->y - (h->x+1)/2);
 513         } else {
 514                 /* need to round toward -inf, not toward zero, so x-1 */
 515                 h->y = (-h->y - (h->x)/2);
 516         }
 517
 518         h->z = -h->x - h->y;
 519         h->iso = 1;
 520         return 1;
 521 }
 522
 523 #endif
 524
 525 #define COS30 (.866025403784438646763723170752)
 526
 527 struct HL_hex HL_hexbin(double width, double x, double y) {
 528         double z, rx, ry, rz;
 529         double abs_dx, abs_dy, abs_dz;
 530         int ix, iy, iz, s;
 531         struct hex h;
 532         struct HL_hex hex;
 533
 534         /*x = x / cos(30 * M_PI / 180.0); */ /* rotated X coord */
 535         x = x / COS30;
 536         y = y - x / 2.0; /* adjustment for rotated X */
 537
 538         /* adjust for actual hexwidth */
 539         x /= width;
 540         y /= width;
 541
 542         z = -x - y;
 543
 544         ix = rx = floor(x + 0.5);
 545         iy = ry = floor(y + 0.5);
 546         iz = rz = floor(z + 0.5);
 547
 548         s = ix + iy + iz;
 549
 550         if (s) {
 551                 abs_dx = fabs(rx - x);
 552                 abs_dy = fabs(ry - y);
 553                 abs_dz = fabs(rz - z);
 554
 555                 if (abs_dx >= abs_dy && abs_dx >= abs_dz) {
 556                         ix -= s;
 557                 } else if (abs_dy >= abs_dx && abs_dy >= abs_dz) {
 558                         iy -= s;
 559                 } else {
 560                         iz -= s;
 561                 }
 562         }
 563         h.x = ix;
 564         h.y = iy;
 565         h.z = iz;
 566         h.iso = 1;
 567
 568         hex_xy(&h);
 569
 570         hex.x = h.x;
 571         hex.y = h.y;
 572
 573         return hex;
 574 }