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

   1 #include "hexmap.h"
   2
   3 #include <math.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <limits.h>
   7
   8 static int inversecantor(int cantor, int *x, int *y);
   9
  10 /*
  11  * This file is written by Nathan Wagner and dedicated to the public
  12  * domain
  13  */
  14
  15 double HL_vertexv[] = {
  16         .577350269189625764509148780502, 0.0,
  17         .288675134594812882254574390251, 0.5,
  18         -.288675134594812882254574390251, 0.5,
  19         -.577350269189625764509148780502, 0.0,
  20         -.288675134594812882254574390251, -0.5,
  21         .288675134594812882254574390251, -0.5};
  22
  23 /* these all are for a hex one unit across */
  24 double          hexptvd[6][2] = {
  25         {.577350269189625764509148780502, 0.0}, /* 1.0/sqrt3 */
  26         {.288675134594812882254574390251, 0.5}, /* 0.5/sqrt3 */
  27         {-.288675134594812882254574390251, 0.5},
  28         {-.577350269189625764509148780502, 0.0},
  29         {-.288675134594812882254574390251, -0.5},
  30         {.288675134594812882254574390251, -0.5}
  31 };
  32
  33 /* TODO how is this related? to the above? */
  34 double          texptvd[6][2] = {
  35         {1.154700538379251529018297561004, 0.5},        /* 2.0/sqrt3 */
  36         {.866025403784438646763723170753, 1.0}, /* 1.5/sqrt3 */
  37         {.288675134594812882254574390251, 1.0},
  38         {0.0, 0.5},
  39         {.288675134594812882254574390251, 0.0},
  40         {.866025403784438646763723170753, 0.0}
  41 };
  42
  43 double          hexpthd[6][2] = {
  44         {0.0, .577350269189625764509148780502},
  45         {0.5, .288675134594812882254574390251},
  46         {0.5, -.288675134594812882254574390251},
  47         {0.0, -.577350269189625764509148780502},
  48         {-0.5, -.288675134594812882254574390251},
  49         {-0.5, .288675134594812882254574390251}
  50 };
  51
  52 void HL_vertices(int cantor, double *vc) {
  53         int i;
  54         double xc, yc;
  55
  56         HL_hexcenter(cantor, &xc, &yc);
  57
  58         for (i=0; i<6; i++) {
  59                 *vc++ = hexptvd[i][0] + xc;
  60                 *vc++ = hexptvd[i][1] + yc;
  61         }
  62         *vc++ = hexptvd[0][0] + xc;
  63         *vc++ = hexptvd[0][1] + yc;
  64 }
  65
  66 void HL_trianglefan(int cantor, double *vc) {
  67         HL_hexcenter(cantor, vc, vc+1);
  68         HL_vertices(cantor, vc+2);
  69 }
  70
  71 double HL_center_x(int cantor) {
  72         double x;
  73
  74         HL_hexcenter(cantor, &x, 0);
  75         return x;
  76 }
  77
  78 double HL_center_y(int cantor) {
  79         double y;
  80
  81         HL_hexcenter(cantor, 0, &y);
  82         return y;
  83 }
  84
  85 int HL_hexcenter(int cantor, double *xc, double *yc) {
  86         int x, y;
  87         double stride = 1.5/sqrt(3.0);
  88
  89         inversecantor(cantor, &x, &y);
  90
  91         if (xc) *xc = x * stride;
  92         if (yc && x >= 0) *yc = y + ((x + 1) % 2) / 2.0 - 0.5;
  93         if (yc && x < 0) *yc = y + ((-x + 1) % 2) / 2.0 - 0.5;
  94
  95         return cantor;
  96 }
  97
  98 /*
  99  * This function assumes that the hexes are one unit across, and vertically
 100  * oriented.  If that is not the case, you will need to transform
 101  * your input coordinates first.
 102  */
 103 int HL_cantor_bin(double x, double y) {
 104         int i, j;
 105
 106         HL_hexbin(1.0, x, y, &i, &j);
 107         return HL_cantor_xy(i, j);
 108 }
 109
 110 static int xy2ijk(int x, int y, int *i, int *j, int *k) {
 111         int pi, pj, pk;
 112
 113         pi = x;
 114         pj = -y;
 115         if (x < 0) {
 116                 pj = pj + (-x + 1) / 2;
 117         } else {
 118                 pj = pj - x/2;
 119         }
 120         pk = -pi - pj;
 121
 122         if (i) *i = pi;
 123         if (j) *j = pj;
 124         if (k) *k = pk;
 125
 126         return HL_cantor_xy(x,y);
 127 }
 128
 129 static int ijk2xy(int i, int j, int k, int *x, int *y) {
 130         int px, py;
 131
 132         px = i;
 133
 134         /* py = -j - i/2; */
 135         py = -j;
 136
 137         if (i < 0) {
 138                 py += (-i + 1)/2;
 139         } else {
 140                 py -= i/2;
 141         }
 142
 143         if (x) *x = px;
 144         if (y) *y = py;
 145
 146         return HL_cantor_xy(px,py);
 147 }
 148
 149 int HL_cantor_ijk(int i, int j, int k) {
 150         return ijk2xy(i,j,k,0,0);
 151 }
 152
 153 int HL_distance(int from, int to) {
 154         int dist = 0, i;;
 155         int fc[3], tc[3];
 156
 157         HL_cantor_arrays(from, 0, fc);
 158         HL_cantor_arrays(to, 0, tc);
 159
 160         for (i=0;i<=2;i++) {
 161                 dist += abs(fc[i] - tc[i]);
 162         }
 163
 164         return dist / 2;
 165 }
 166
 167 int HL_hexes_within_range(int hex, int range, int *list, int size) {
 168         int count = 0;
 169         int i;
 170
 171         if (range == 0) {
 172                 return HL_hexes_at_range(hex, 0, list, size);
 173         }
 174
 175         for (i=1;i<=range;i++) {
 176                 count += HL_hexes_at_range(hex, i, count > size ? 0 : list+count, size-count);
 177         }
 178         return count;
 179 }
 180
 181 int HL_hexes_at_range(int hex, int range, int *list, int size) {
 182         int q; /* p and q are count/loop vars */
 183         int c[3]; /* ijk coord array */
 184
 185         if (range == 0) {
 186                 if (list) {
 187                         list[0] = hex;
 188                 }
 189                 return 1;
 190         } else if (range < 0) {
 191                 return 0;
 192         }
 193
 194         /* TODO don't bother to collect if the list isn't big enough? */
 195         /* i.e. if (!list || size < range * 6) */
 196         if (!list || size < 1) return range * 6;
 197
 198         HL_cantor_arrays(hex, 0, c);
 199         c[0] += range;
 200         c[2] = -c[0] - c[1];
 201         hex = HL_cantor_ijkp(c);
 202
 203         for(q=0; q<size && q < range * 6; q++) {
 204                 list[q] = hex;
 205                 hex = HL_adjhex(hex, q/range+2);
 206         }
 207
 208         return range * 6;
 209 }
 210
 211 /* direction 0 is positive X , counter clockwise from there */
 212 int HL_adjhex(int start, int dir) {
 213         int c[3];
 214
 215         HL_cantor_arrays(start, 0, c);
 216
 217         switch (dir%6) {
 218                 case 2:
 219                         c[0]--; c[1]++; break;
 220                 case 1:
 221                                 c[1]++; c[2]--; break;
 222                 case 0:
 223                         c[0]++;         c[2]--; break;
 224                 case 5:
 225                         c[0]++; c[1]--; break;
 226                 case 4:
 227                                 c[1]--; c[2]++; break;
 228                 case 3:
 229                         c[0]--;       ; c[2]++; break;
 230         }
 231
 232         return HL_cantor_ijkp(c);
 233 }
 234
 235 /* returns last hex in found path */
 236 int HL_findpath(int start, int end, int *path, int size) {
 237         return 0;
 238 }
 239
 240 int HL_cantor_xyp(int *xy) {
 241         return HL_cantor_xy(xy[0], xy[1]);
 242 }
 243
 244 int HL_cantor_ijkp(int *ijk) {
 245         return HL_cantor_ijk(ijk[0], ijk[1], ijk[2]);
 246 }
 247
 248 int HL_cantor_arrays(int can, int *xy, int *ijk) {
 249         return HL_cantor_decode(can, xy, xy ? xy+1 : 0,
 250                         ijk, ijk ? ijk+1 : 0, ijk ? ijk+2 : 0);
 251 }
 252
 253 int HL_cantor_decode(int can, int *x, int *y, int *i, int *j, int *k) {
 254         int px, py;
 255
 256         inversecantor(can, &px, &py);
 257         if (x) *x = px;
 258         if (y) *y = py;
 259
 260         xy2ijk(px, py, i, j, k);
 261
 262         return can;
 263 }
 264
 265 int HL_cantor_i(int cantor) {
 266         int i;
 267
 268         HL_cantor_decode(cantor, 0,0, &i,0,0);
 269         return i;
 270 }
 271
 272 int HL_cantor_j(int cantor) {
 273         int j;
 274
 275         HL_cantor_decode(cantor, 0,0, 0,&j,0);
 276         return j;
 277 }
 278
 279 int HL_cantor_k(int cantor) {
 280         int k;
 281
 282         HL_cantor_decode(cantor, 0,0, 0,0,&k);
 283         return k;
 284 }
 285
 286 int HL_cantor_x(int cantor) {
 287         int x;
 288         inversecantor(cantor, &x, 0);
 289         return x;
 290 }
 291
 292 int HL_cantor_y(int cantor) {
 293         int y;
 294         inversecantor(cantor, 0, &y);
 295         return y;
 296 }
 297
 298 /* Determine if a map with these dimensions will overflow */
 299 int HL_map_bounds_ok(int xdim, int ydim) {
 300
 301         /* return (x+y) * (x + y + 1) / 2 + y+1; */
 302
 303         if (INT_MAX - xdim - 1 < ydim) return 0;
 304         if (INT_MAX / (xdim+ydim) < (xdim+ydim+1)) return 0;
 305         if ( (xdim+ydim) * (xdim+ydim+1) / 2 > INT_MAX - ydim - 1)
 306                 return 0;
 307
 308         return 1;
 309 }
 310
 311 int HL_map_max_dimension(void) {
 312         int low, high, try;
 313
 314         low = 1; high = INT_MAX/2;
 315
 316         while (low != high - 1) {
 317                 try = (low + high) / 2;
 318                 if (HL_map_bounds_ok(try,try)) {
 319                         low = try;
 320                 } else {
 321                         high = try;
 322                 }
 323         }
 324
 325         return low;
 326 }
 327
 328 #ifdef ASTAR
 329
 330 struct astar_hex {
 331         int hex;
 332         int f, g, h;
 333         int parent;
 334 };
 335
 336 struct astar {
 337         int open, closed; /* how many in open or closed */
 338         int closedroom, openroom; /* how much is malloced */
 339         struct astar_hex *openlist;
 340         struct astar_hex *closedlist;
 341         int known, index;
 342         int error;
 343 };
 344
 345 static void astar_init(struct astar *state) {
 346         state->open = 0;
 347         state->closed = 0;
 348         state->closedroom = 0;
 349         state->openroom = 0;
 350         state->openlist = 0;
 351         state->closedlist = 0;
 352         state->error = 0;
 353         state->known = 0;
 354         state->index = 0;
 355
 356         return;
 357 }
 358
 359 static void removeopen(struct astar *s, int hex) {
 360         int index;
 361
 362         if (s->error) return;
 363         if (s->open == 0) return;
 364
 365         if (s->known != hex) {
 366                 for (index = 0; index < s->open; index++) {
 367                         if (s->openlist[index].hex == hex) break;
 368                 }
 369         } else {
 370                 index = s->index;
 371                 s->known = 0; s->index = 0;
 372         }
 373         s->openlist[index] = s->openlist[open];
 374         s->open--;
 375 }
 376
 377 static void addopen(struct astar *s, int hex) {
 378         struct astar_hex *mem;
 379         if (s->error) return;
 380
 381         if (s->open + 1 > s->openroom) {
 382                 mem = realloc(s->openlist, s->openroom * 2 * sizeof *mem);
 383                 if (mem == NULL) {
 384                         s->error = errno;
 385                         return;
 386                 }
 387                 state->openlist = mem;
 388                 s->openroom = s->openroom * 2;
 389         }
 390
 391         s->openlist[s->open].hex = hex;
 392         s->openlist[s->open].f = 0;
 393         s->openlist[s->open].g = 0;
 394         s->openlist[s->open].h = 0;
 395         s->known = hex;
 396         s->index = s->open;
 397         s->open = s->open + 1;
 398 }
 399
 400 int lowrank(struct astar *s) {
 401         int f;
 402         int hex;
 403         int i;
 404
 405         if (!s || s->open = 0) return 0;
 406
 407         hex = s->openlist[0].hex;
 408         f = s->openlist[0].f;
 409
 410         for(i=1; i < s->open; i++) {
 411                 if (s->openlist[i].f < f) {
 412                         hex = s->openlist[i].hex;
 413                         f = s->openlist[i].f;
 414                 }
 415                 /* TODO check s->openlist[i].tiebreak */
 416         }
 417
 418         return hex;
 419 }
 420
 421 static int default_metric(int a, int b) {
 422         return 1;
 423 }
 424
 425 /*
 426  * find a path from start to end.  we use A*
 427  */
 428 int HL_findpath(int start, int end, int psize, int *path,
 429                 double (*metric)(int,int)) {
 430         int neighbors[6];
 431         int count;
 432         int cur = 0;
 433         struct astar state;
 434         int neighbor;
 435
 436         if (start == end) return 0;
 437         if (!metric) metric = default_metric;
 438
 439         astar_init(&state);
 440         addopen(&state, start);
 441
 442         while (1) {
 443                 cur = lowrank(&state);
 444                 if (cur == end) {
 445                         break;
 446                 }
 447                 addclosed(&state, cur);
 448                 count = HL_hexes_at_range(cur->hex, 1, neighbors, 6);
 449                 for (i=0;i<count;i++) {
 450                         neighbor = neighbors[i];
 451                         cost = g(&state, current) + metric(current, neighbor);
 452                         if (inopen(&state, neighbor) && cost < g(&state, neighbor)) {
 453                                 removeopen(&state, neighbor);
 454                         } else
 455                         if (inclosed(&state, neighbor) && cost < g(&state, neighbor)) {
 456                                 /* should never happen with
 457                                  * admissible heuristic
 458                                  */
 459                                 removeclosed(&state, neighbor);
 460                         } else
 461                         if (!inopen(&state, neighbor) && !inclosed(&state, neighbor)) {
 462                                 addopen(&state, neighbor);
 463                                 setg(&state, neighbor, cost);
 464                                 setrank(&state, neighbor, cost + h(neighbor,end));
 465                                 setparent(&state, neighbor, current);
 466                         } else {
 467                                 abort();
 468                         }
 469                 }
 470         }
 471
 472         count = 0;
 473         while (parent(&state, cur) != start) {
 474                 count++;
 475                 cur = parent(&state, cur);
 476         }
 477         cur = end;
 478         while (parent(&state, cur) != start) {
 479                 path[count--] = cur;
 480                 cur = parent(&state, cur);
 481         }
 482
 483 }
 484
 485 #endif
 486
 487 static int inversenatcantor(int cantor, int *x, int *y) {
 488         int w, t, py;
 489
 490         cantor -= 1;
 491
 492         w = (int)floor((sqrt(8.0 * cantor + 1.0) - 1.0)/2.0);
 493         t = (w * w + w)/2;
 494
 495         py = cantor - t;
 496
 497         if (y) *y = py;
 498         if (x) *x = w - py;
 499
 500         return cantor;
 501 }
 502
 503 /*
 504  * map non negative integer pairs to their cantor pairing function
 505  * number, plus one.  We add one so that the result is never zero,
 506  * leaving zero to be "invalid" or "none" or what have you.
 507  */
 508
 509 static int natcantor(int x, int y) {
 510         return (x+y) * (x + y + 1) / 2 + y+1;
 511 }
 512
 513 /* See http://en.wikipedia.org/wiki/Cantor_pairing_function */
 514 /* see also http://szudzik.com/ElegantPairing.pdf */
 515 /*
 516  * if either coordinate is negative, map the integers onto the
 517  * whole numbers, and then return the negative of the adjusted
 518  * cantor number.  As for most grids negative coordinates will
 519  * be invalid, this will allow for a <= 0 test for invalid
 520  * or out of bounds (on the negative side anyway, you'll
 521  * still have to test for out of range on the positive side).
 522  *
 523  * TODO figure out what the maximum supported coordinates are
 524  * for given integer sizes.
 525  */
 526 int HL_cantor_xy(int x, int y) {
 527         if (x < 0 || y < 0) {
 528                 x = abs(2 * x) - (x < 0);
 529                 y = abs(2 * y) - (y < 0);
 530                 return -natcantor(x, y);
 531         }
 532         return natcantor(x,y);
 533 }
 534
 535 static int inversecantor(int cantor, int *x, int *y) {
 536         if (cantor < 0) {
 537                 inversenatcantor(-cantor, x, y);
 538                 if (x) {
 539                         if (*x % 2) {
 540                                 *x = -(*x+1)/2;
 541                         } else {
 542                                 *x = *x / 2;
 543                         }
 544                 }
 545                 if (y) {
 546                         if (*y % 2) {
 547                                 *y =  -(*y+1)/2;
 548                         } else {
 549                                 *y = *y/2;
 550                         }
 551                 }
 552         } else {
 553                 inversenatcantor(cantor, x, y);
 554         }
 555
 556         return cantor;
 557 }
 558
 559 struct hex {
 560         int iso;
 561         int x, y, z;
 562 };
 563
 564 /* y *must* be positive down as the xy /iso conversion assumes this */
 565 static int hex_xy(struct hex *h) {
 566         if (!h->iso) return 1;
 567         if (h->x >= 0) {
 568                 h->y = -h->y - (h->x+1)/2;
 569         } else {
 570                 /* need to round toward -inf, not toward zero, so x-1 */
 571                 h->y = -h->y - h->x/2;
 572         }
 573         h->iso = 0;
 574
 575         return 1;
 576 }
 577
 578 static int hex_iso(struct hex *h) {
 579         if (h->iso) return 1;
 580
 581         if (h->x >= 0) {
 582                 h->y = (-h->y - (h->x+1)/2);
 583         } else {
 584                 /* need to round toward -inf, not toward zero, so x-1 */
 585                 h->y = (-h->y - (h->x)/2);
 586         }
 587
 588         h->z = -h->x - h->y;
 589         h->iso = 1;
 590         return 1;
 591 }
 592
 593 int HL_hexbin(double width, double x, double y, int *i, int *j) {
 594         double z, rx, ry, rz;
 595         double abs_dx, abs_dy, abs_dz;
 596         int ix, iy, iz, s;
 597         struct hex h;
 598
 599         /* TODO just hard-code this cosine */
 600         x = x / cos(30 * M_PI / 180.0); /* rotated X coord */
 601         y = y - x / 2.0; /* adjustment for rotated X */
 602
 603         /* adjust for actual hexwidth */
 604         x /= width;
 605         y /= width;
 606
 607         z = -x - y;
 608
 609         ix = rx = floor(x + 0.5);
 610         iy = ry = floor(y + 0.5);
 611         iz = rz = floor(z + 0.5);
 612
 613         s = ix + iy + iz;
 614
 615         if (s) {
 616                 abs_dx = fabs(rx - x);
 617                 abs_dy = fabs(ry - y);
 618                 abs_dz = fabs(rz - z);
 619
 620                 if (abs_dx >= abs_dy && abs_dx >= abs_dz) {
 621                         ix -= s;
 622                 } else if (abs_dy >= abs_dx && abs_dy >= abs_dz) {
 623                         iy -= s;
 624                 } else {
 625                         iz -= s;
 626                 }
 627         }
 628         h.x = ix;
 629         h.y = iy;
 630         h.z = iz;
 631         h.iso = 1;
 632
 633         hex_xy(&h);
 634         if (i) *i = h.x;
 635         if (j) *j = h.y;
 636         return HL_cantor_xy(h.x, h.y);
 637 }