sys/src/games/mines/ghost.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <draw.h>
   4 #include <event.h>
   5 #include <mp.h>
   6 #include <cursor.h>
   7 #include "dat.h"
   8 #include "fns.h"
   9
  10 enum { TURBO = 0 };
  11
  12 static Cursor bunny = {
  13         .set = {0x0,0x32,0x60,0x76,0x40,0x6e,0x3,0xec,0xf,0xfc,0x1f,0xf8,0x27,0x9c,0x3,0xc,0x33,0xcc,0x73,0xce,0x67,0x9e,0x7f,0xfe,0x7f,0xfe,0x7f,0xfe,0x6e,0x76},
  14         .clr = {0xf8,0xcd,0x90,0x89,0xa3,0x91,0xcc,0x12,0x90,0x2,0x20,0x6,0x58,0x62,0x7c,0xf2,0x4c,0x33,0x8c,0x31,0x98,0x61,0x80,0x1,0x80,0x1,0x80,0x1,0x91,0x89}
  15 };
  16
  17 enum {
  18         MEmpty,
  19         MMine,
  20         MUnknown,
  21         NState,
  22 };
  23
  24 typedef struct Ghost Ghost;
  25 typedef struct CList CList;
  26 typedef struct CGroup CGroup;
  27
  28 struct Ghost {
  29         QLock;
  30         Rendez;
  31         int active, wait;
  32         int pid;
  33
  34         enum { NOTARG, LTARG, RTARG } targettype;
  35         Point target;
  36         int generation;
  37
  38         int nmines;
  39         uchar *f;
  40
  41         int w, h;
  42
  43         int cursor;
  44         Point moves[3];
  45         int nmoves;
  46         Point cpos;
  47 };
  48
  49 struct CList {
  50         int mines, pts;
  51         int pt[8];
  52         int next;
  53 };
  54
  55 struct CGroup {
  56         CList *cl;
  57         int ncl;
  58         mpint **cnt;
  59         int max;
  60         int cur;
  61 };
  62
  63 static Ghost ghost;
  64
  65 static uchar ***
  66 neighbours(void)
  67 {
  68         int x, y, p;
  69         uchar ***n;
  70
  71         n = calloc(sizeof(void*), ghost.w);
  72         for(x = 0; x < ghost.w; x++){
  73                 n[x] = calloc(sizeof(void*), ghost.h);
  74                 for(y = 0; y < ghost.h; y++)
  75                         n[x][y] = calloc(sizeof(uchar), NState);
  76         }
  77
  78         for(y = 0; y < ghost.h; y++)
  79                 for(x = 0; x < ghost.w; x++){
  80                         p = ghost.f[x + y * ghost.w];
  81                         if(x > 0 && y > 0) n[x-1][y-1][p]++;
  82                         if(y > 0) n[x][y-1][p]++;
  83                         if(x < ghost.w-1 && y > 0) n[x+1][y-1][p]++;
  84                         if(x > 0) n[x-1][y][p]++;
  85                         if(x < ghost.w-1) n[x+1][y][p]++;
  86                         if(x > 0 && y < ghost.h-1) n[x-1][y+1][p]++;
  87                         if(y < ghost.h-1) n[x][y+1][p]++;
  88                         if(x < ghost.w-1 && y < ghost.h-1) n[x+1][y+1][p]++;
  89                 }
  90         return n;
  91 }
  92
  93 static void
  94 freeneighbours(uchar ***n)
  95 {
  96         int x, y;
  97
  98         for(x = 0; x < ghost.w; x++){
  99                 for(y = 0; y < ghost.h; y++)
 100                         free(n[x][y]);
 101                 free(n[x]);
 102         }
 103         free(n);
 104 }
 105
 106 static void
 107 printcl(CList *cl, int ncl)
 108 {
 109         int i, j;
 110
 111         for(i = 0; i < ncl; i++){
 112                 print("%d: ", cl[i].mines);
 113                 for(j = 0; j < cl[i].pts; j++)
 114                         print("%d ", cl[i].pt[j]);
 115                 print("\n");
 116         }
 117         print("--\n");
 118 }
 119
 120 static void
 121 mklists(CList **clp, int *nclp)
 122 {
 123         CList *c, *cl;
 124         int ncl, x, y;
 125         uchar ***nei;
 126
 127         cl = nil;
 128         ncl = 0;
 129         nei = neighbours();
 130         for(y = 0; y < ghost.h; y++)
 131                 for(x = 0; x < ghost.w; x++)
 132                         if(MineField[x][y].Picture <= Empty8 && nei[x][y][MUnknown] > 0){
 133                                 cl = realloc(cl, (ncl + 1) * sizeof(CList));
 134                                 c = &cl[ncl++];
 135                                 memset(c, 0, sizeof(CList));
 136                                 c->mines = MineField[x][y].Picture - nei[x][y][MMine];
 137                                 if(x > 0 && y > 0 && ghost.f[(x-1)+(y-1)*ghost.w] == MUnknown)
 138                                         c->pt[c->pts++] = (x-1)+(y-1)*ghost.w;
 139                                 if(y > 0 && ghost.f[(x)+(y-1)*ghost.w] == MUnknown)
 140                                         c->pt[c->pts++] = (x)+(y-1)*ghost.w;
 141                                 if(x < ghost.w-1 && y > 0 && ghost.f[(x+1)+(y-1)*ghost.w] == MUnknown)
 142                                         c->pt[c->pts++] = (x+1)+(y-1)*ghost.w;
 143                                 if(x > 0 && ghost.f[(x-1)+(y)*ghost.w] == MUnknown)
 144                                         c->pt[c->pts++] = (x-1)+(y)*ghost.w;
 145                                 if(x < ghost.w-1 && ghost.f[(x+1)+(y)*ghost.w] == MUnknown)
 146                                         c->pt[c->pts++] = (x+1)+(y)*ghost.w;
 147                                 if(x > 0 && y < ghost.h-1 && ghost.f[(x-1)+(y+1)*ghost.w] == MUnknown)
 148                                         c->pt[c->pts++] = (x-1)+(y+1)*ghost.w;
 149                                 if(y < ghost.h-1 && ghost.f[(x)+(y+1)*ghost.w] == MUnknown)
 150                                         c->pt[c->pts++] = (x)+(y+1)*ghost.w;
 151                                 if(x < ghost.w-1 && y < ghost.h-1 && ghost.f[(x+1)+(y+1)*ghost.w] == MUnknown)
 152                                         c->pt[c->pts++] = (x+1)+(y+1)*ghost.w;
 153                         }
 154         freeneighbours(nei);
 155         *clp = cl;
 156         *nclp = ncl;
 157 }
 158
 159 static int
 160 ismember(CList *c, int p)
 161 {
 162         int i;
 163
 164         for(i = 0; i < c->pts; i++)
 165                 if(c->pt[i] == p)
 166                         return 1;
 167         return 0;
 168 }
 169
 170 static void
 171 splitknown(CList **clp, int *nclp, int i, int *lastq)
 172 {
 173         int j;
 174         CList *cl;
 175         int ncl;
 176
 177         cl = *clp;
 178         ncl = *nclp;
 179         cl = realloc(cl, sizeof(CList) * (ncl + cl[i].pts - 1));
 180         memset(cl + ncl, 0, sizeof(CList) * (cl[i].pts - 1));
 181         for(j = 1; j < cl[i].pts; j++){
 182                 cl[ncl - 1 + j].mines = cl[i].pts == cl[i].mines;
 183                 cl[ncl - 1 + j].pts = 1;
 184                 cl[ncl - 1 + j].pt[0] = cl[i].pt[j];
 185                 cl[*lastq].next = ncl - 1 + j;
 186                 *lastq = ncl - 1 + j;
 187         }
 188         cl[i].mines = cl[i].pts == cl[i].mines;
 189         *nclp += cl[i].pts - 1;
 190         cl[i].pts = 1;
 191         *clp = cl;
 192 }
 193
 194 static int
 195 merge(CList **clp, int *nclp, int start, int split)
 196 {
 197         int i, j, k, l, p;
 198         CList *cl, *q, *r;
 199         int qi, lastq;
 200         int zero;
 201
 202         cl = *clp;
 203         qi = -1;
 204         lastq = -1;
 205         zero = 0;
 206         for(i = 0; i < *nclp; i++)
 207                 if(cl[i].pts == 0 || start >= 0 && start != i)
 208                         cl[i].next = -2;
 209                 else{
 210                         cl[i].next = -1;
 211                         if(lastq >= 0)
 212                                 cl[lastq].next = i;
 213                         else
 214                                 qi = i;
 215                         lastq = i;
 216                 }
 217         while(qi >= 0){
 218                 q = &cl[qi];
 219                 for(i = 0; i < *nclp; i++){
 220                         r = &cl[i];
 221                         if(r == q || r->pts < q->pts) continue;
 222                         for(j = k = 0; j < q->pts; j++, k++){
 223                                 p = q->pt[j];
 224                                 if(r->pt[r->pts - 1] < p)
 225                                         goto next;
 226                                 while(r->pt[k] < p)
 227                                         k++;
 228                                 if(r->pt[k] > p)
 229                                         goto next;
 230                         }
 231                         for(j = k = l = 0; j < q->pts; j++, k++){
 232                                 p = q->pt[j];
 233                                 while(r->pt[k] < p)
 234                                         r->pt[l++] = r->pt[k++];
 235                         }
 236                         while(k < r->pts)
 237                                 r->pt[l++] = r->pt[k++];
 238                         r->pts = l;
 239                         r->mines -= q->mines;
 240                         if(r->mines < 0 || r->mines > r->pts){
 241                                 *clp = cl;
 242                                 return -1;
 243                         }
 244                         if(r->pts == 0 && r->mines == 0)
 245                                 zero++;
 246                         if(r->next == -2 && r->pts > 0){
 247                                 r->next = -1;
 248                                 cl[lastq].next = i;
 249                                 lastq = i;
 250                         }
 251                         if(split && r->pts > 1 && (r->pts == r->mines || r->mines == 0)){
 252                                 splitknown(&cl, nclp, i, &lastq);
 253                                 q = &cl[qi];
 254                         }
 255                 next: ;
 256                 }
 257                 qi = q->next;
 258                 q->next = -2;
 259         }
 260         if(zero != 0){
 261                 for(i = 0, j = 0; i < *nclp; i++)
 262                         if(cl[i].mines != 0 || cl[i].pts != 0)
 263                                 cl[j++] = cl[i];
 264                 *nclp = j;
 265         }
 266         *clp = cl;
 267         return 0;
 268 }
 269
 270 static void
 271 countref(CList *cl, int ncl, uchar *ref)
 272 {
 273         int i, j;
 274
 275         memset(ref, 0, ghost.w * ghost.h);
 276         for(i = 0; i < ncl; i++)
 277                 for(j = 0; j < cl[i].pts; j++)
 278                         ref[cl[i].pt[j]]++;
 279 }
 280
 281 static int *
 282 clgroup(CList *cl, int ncl, uchar *ref)
 283 {
 284         int i, j, k, og, ng;
 285         int *g;
 286
 287         g = calloc(ncl, sizeof(int));
 288         for(i = 0; i < ncl; i++)
 289                 g[i] = i;
 290 start:
 291         for(i = 0; i < ncl; i++)
 292                 for(j = 0; j < cl[i].pts; j++){
 293                         if(ref[cl[i].pt[j]] == 1) continue;
 294                         for(k = 0; k < ncl; k++)
 295                                 if(g[i] != g[k] && ismember(&cl[k], cl[i].pt[j]))
 296                                         break;
 297                         if(k == ncl) continue;
 298                         if(g[i] < g[k]){
 299                                 og = g[i];
 300                                 ng = g[k];
 301                         }else{
 302                                 og = g[k];
 303                                 ng = g[i];
 304                         }
 305                         for(k = 0; k < ncl; k++)
 306                                 if(g[k] == og)
 307                                         g[k] = ng;
 308                         goto start;
 309                 }
 310         return g;
 311 }
 312
 313 static int
 314 groupmin(int *g, int ncl)
 315 {
 316         int i, j, og, ng;
 317         u32int *bs;
 318
 319         bs = calloc(sizeof(u32int), ncl + 31 >> 5);
 320         for(i = 0; i < ncl; i++)
 321                 bs[g[i]>>5] |= 1<<(g[i] & 31);
 322         for(i = 0; i < ncl; i++){
 323                 for(j = 0; j < g[i]; j++)
 324                         if((bs[j>>5] & 1<<(j & 31)) == 0)
 325                                 break;
 326                 if(j == g[i]) continue;
 327                 og = g[i];
 328                 ng = j;
 329                 for(j = 0; j < ncl; j++)
 330                         if(g[j] == og)
 331                                 g[j] = ng;
 332                 bs[og>>5] &= ~(1<<(og & 31));
 333                 bs[ng>>5] |= 1<<(ng & 31);
 334         }
 335         og = 0;
 336         for(i = 0; i < ncl; i++)
 337                 if(g[i] + 1 > og)
 338                         og = g[i] + 1;
 339         free(bs);
 340         return og;
 341 }
 342
 343 static int
 344 mkgroups(CList *cl, int ncl, uchar *ref, CGroup **gp)
 345 {
 346         CGroup *g, *p;
 347         int i, j, k, ng;
 348         int *gr;
 349
 350         gr = clgroup(cl, ncl, ref);
 351         ng = groupmin(gr, ncl);
 352         g = calloc(sizeof(CGroup), ng);
 353         for(i = 0; i < ng; i++){
 354                 p = &g[i];
 355                 for(j = 0; j < ncl; j++)
 356                         if(gr[j] == i)
 357                                 p->ncl++;
 358                 p->cl = calloc(sizeof(CList), p->ncl);
 359                 for(j = 0, k = 0; j < ncl; j++)
 360                         if(gr[j] == i)
 361                                 p->cl[k++] = cl[j];
 362         }
 363         free(gr);
 364         *gp = g;
 365         return ng;
 366 }
 367
 368 static void
 369 freegroups(CGroup *g, int ng)
 370 {
 371         int i, j;
 372
 373         for(i = 0; i < ng; i++){
 374                 for(j = 0; j <= g[i].max; j++)
 375                         mpfree(g[i].cnt[j]);
 376                 free(g[i].cl);
 377                 free(g[i].cnt);
 378         }
 379         free(g);
 380 }
 381
 382 static void
 383 binom(mpint *acc, mpint *temp, int n, int k)
 384 {
 385         int i;
 386
 387         for(i = 0; i < k; i++){
 388                 itomp(n - i, temp);
 389                 mpmul(acc, temp, acc);
 390         }
 391         for(i = 2; i <= k; i++){
 392                 itomp(i, temp);
 393                 mpdiv(acc, temp, acc, nil);
 394         }
 395 }
 396
 397 static void countcomb(CList *cl, int ncl, mpint **);
 398
 399 static void
 400 cltry(CList *cl, int ncl, int p, int v, mpint **cnt)
 401 {
 402         CList *cm;
 403         int ncm;
 404
 405         cm = calloc(ncl + 1, sizeof(CList));
 406         memcpy(cm, cl, ncl * sizeof(CList));
 407         memset(&cm[ncl], 0, sizeof(CList));
 408         cm[ncl].mines = v;
 409         cm[ncl].pts = 1;
 410         cm[ncl].pt[0] = p;
 411         ncm = ncl + 1;
 412         if(merge(&cm, &ncm, ncl, 1) < 0){
 413                 free(cm);
 414                 return;
 415         }
 416         countcomb(cm, ncm, cnt);
 417         free(cm);
 418 }
 419
 420 static void
 421 countcomb(CList *cl, int ncl, mpint **cnt)
 422 {
 423         uchar *ref;
 424         int p, i, j, nm;
 425         mpint *rc, *c0;
 426
 427         ref = calloc(ghost.w, ghost.h);
 428         countref(cl, ncl, ref);
 429         for(i = 0; i < ncl; i++)
 430                 for(j = 0; j < cl[i].pts; j++){
 431                         p = cl[i].pt[j];
 432                         if(ref[p] > 1){
 433                                 cltry(cl, ncl, p, 0, cnt);
 434                                 cltry(cl, ncl, p, 1, cnt);
 435                                 free(ref);
 436                                 return;
 437                         }
 438                 }
 439         rc = itomp(1, nil);
 440         c0 = mpnew(0);
 441         nm = 0;
 442         for(i = 0; i < ncl; i++){
 443                 nm += cl[i].mines;
 444                 binom(rc, c0, cl[i].pts, cl[i].mines);
 445         }
 446         if(mpcmp(rc, mpzero) != 0)
 447                 if(cnt[nm] == nil)
 448                         cnt[nm] = rc;
 449                 else{
 450                         mpadd(cnt[nm], rc, cnt[nm]);
 451                         mpfree(rc);
 452                 }
 453         else
 454                 mpfree(rc);
 455         mpfree(c0);
 456         free(ref);
 457 }
 458
 459 static mpint *
 460 totcomb(int tot, int nf, CGroup *g, int ng)
 461 {
 462         int i, j, s, carry;
 463         mpint *r, *v, *t, *m;
 464
 465         s = 0;
 466         for(i = 0; i < ng; i++){
 467                 for(j = 0; j <= g[i].max; j++)
 468                         if(g[i].cnt[j] != nil)
 469                                 break;
 470                 if(j > g[i].max)
 471                         return mpnew(0);
 472                 g[i].cur = j;
 473                 s += j;
 474         }
 475         if(s > tot)
 476                 return mpnew(0);
 477         r = mpnew(0);
 478         v = mpnew(0);
 479         t = mpnew(0);
 480         do{
 481                 itomp(1, v);
 482                 s = 0;
 483                 for(i = 0; i < ng; i++){
 484                         m = g[i].cnt[g[i].cur];
 485                         mpmul(v, m, v);
 486                         s += g[i].cur;
 487                 }
 488                 if(s <= tot){
 489                         binom(v, t, nf, tot - s);
 490                         mpadd(r, v, r);
 491                 }
 492                 for(i = 0; i < ng; i++){
 493                         carry = 0;
 494                         do
 495                                 if(++g[i].cur > g[i].max){
 496                                         g[i].cur = 0;
 497                                         carry = 1;
 498                                 }
 499                         while(g[i].cnt[g[i].cur] == nil);
 500                         if(!carry) break;
 501                 }
 502         }while(i < ng);
 503         mpfree(v);
 504         mpfree(t);
 505         return r;
 506 }
 507
 508 static int
 509 freefields(uchar *ref)
 510 {
 511         int nf, p;
 512
 513         nf = 0;
 514         for(p = 0; p < ghost.w * ghost.h; p++)
 515                 if(ref[p] == 0 && ghost.f[p] == MUnknown)
 516                         nf++;
 517         return nf;
 518 }
 519
 520 static int
 521 basecounts(CGroup *g, int ng)
 522 {
 523         int i, j;
 524         int allmax;
 525         CGroup *p;
 526
 527         allmax = 0;
 528         for(i = 0; i < ng; i++){
 529                 p = &g[i];
 530                 p->max = 0;
 531                 for(j = 0; j < p->ncl; j++)
 532                         p->max += p->cl[j].mines;
 533                 p->cnt = calloc(p->max + 1, sizeof(mpint *));
 534                 countcomb(p->cl, p->ncl, p->cnt);
 535                 if(p->max > allmax) allmax = p->max;
 536         }
 537         return allmax;
 538 }
 539
 540 static void
 541 fieldcombs(CList *cl, int ncl, int *xp, int *yp)
 542 {
 543         uchar *ref;
 544         int i, k, p;
 545         int nf, ng;
 546         int allmax;
 547         int ref1;
 548         mpint *min, *v, **alt, **backup;
 549         CList *l;
 550         CGroup *g, *gp;
 551
 552         ref = calloc(ghost.w, ghost.h);
 553         countref(cl, ncl, ref);
 554         nf = freefields(ref);
 555         ng = mkgroups(cl, ncl, ref, &g);
 556         allmax = basecounts(g, ng);
 557         alt = calloc(allmax + 1, sizeof(mpint *));
 558
 559         *xp = -1;
 560         *yp = -1;
 561         min = mpnew(0);
 562
 563         for(gp = g; gp < g + ng; gp++)
 564                 for(l = gp->cl; l < gp->cl + gp->ncl; l++){
 565                         ref1 = 0;
 566                         for(i = 0; i < l->pts; i++){
 567                                 p = l->pt[i];
 568                                 if(ref[p] == 0xff)
 569                                         continue;
 570                                 if(ref[p] == 1 && ref1++ != 0)
 571                                         continue;
 572                                 ref[p] = 0xff;
 573
 574                                 cltry(gp->cl, gp->ncl, p, 1, alt);
 575                                 backup = gp->cnt;
 576                                 gp->cnt = alt;
 577                                 v = totcomb(ghost.nmines, nf, g, ng);
 578                                 if(*xp < 0 || mpcmp(v, min) < 0){
 579                                         mpassign(v, min);
 580                                         *xp = p % ghost.w;
 581                                         *yp = p / ghost.w;
 582                                 }
 583
 584                                 gp->cnt = backup;
 585                                 for(k = 0; k <= gp->max; k++)
 586                                         mpfree(alt[k]);
 587                                 memset(alt, 0, (gp->max + 1) * sizeof(mpint *));
 588                                 mpfree(v);
 589                         }
 590                 }
 591         if(nf > 0){
 592                 v = totcomb(ghost.nmines - 1, nf - 1, g, ng);
 593                 if(*xp < 0 || mpcmp(v, min) < 0){
 594                         i = nrand(nf);
 595                         for(p = 0; p < ghost.w * ghost.h; p++)
 596                                 if(ref[p] == 0 && ghost.f[p] == MUnknown && i-- == 0)
 597                                         break;
 598                         mpassign(v, min);
 599                         *xp = p % ghost.w;
 600                         *yp = p / ghost.w;
 601                 }
 602                 mpfree(v);
 603         }
 604         mpfree(min);
 605         free(alt);
 606         free(ref);
 607         freegroups(g, ng);
 608 }
 609
 610 static void
 611 ghostprep(CList **clp, int *nclp)
 612 {
 613         int x, y;
 614
 615         ghost.w = MaxX;
 616         ghost.h = MaxY;
 617         ghost.nmines = MinesRemain;
 618         ghost.f = calloc(ghost.w, ghost.h);
 619         for(x = 0; x < ghost.w; x++){
 620                 for(y = 0; y < ghost.h; y++)
 621                         switch(MineField[x][y].Picture){
 622                         case Empty0:
 623                         case Empty1:
 624                         case Empty2:
 625                         case Empty3:
 626                         case Empty4:
 627                         case Empty5:
 628                         case Empty6:
 629                         case Empty7:
 630                         case Empty8:
 631                                 ghost.f[x + y * ghost.w] = MEmpty;
 632                                 break;
 633                         case Mark:
 634                                 ghost.f[x + y * ghost.w] = MMine;
 635                                 break;
 636                         default:
 637                                 ghost.f[x + y * ghost.w] = MUnknown;
 638                         }
 639         }
 640         mklists(clp, nclp);
 641 }
 642
 643 static int
 644 ghostfind(CList *cl, int ncl, Point *targp)
 645 {
 646         int i, j, x, y;
 647         Point p, pd;
 648         int d, min;
 649         Point targ;
 650         int rt;
 651
 652         merge(&cl, &ncl, -1, 0);
 653         min = 0;
 654         rt = NOTARG;
 655         targ = ghost.cpos;
 656         for(i = 0; i < ncl; i++)
 657                 if(cl[i].mines == 0 || cl[i].mines == cl[i].pts)
 658                         for(j = 0; j < cl[i].pts; j++){
 659                                 p = Pt(cl[i].pt[j]%ghost.w, cl[i].pt[j]/ghost.w);
 660                                 pd = subpt(addpt(addpt(mulpt(p, 16), Pt(12+8, 57+8)), Origin), targ);
 661                                 d = pd.x * pd.x + pd.y * pd.y;
 662                                 if(rt == NOTARG || d < min){
 663                                         rt = cl[i].mines == cl[i].pts ? RTARG : LTARG;
 664                                         *targp = p;
 665                                         min = d;
 666                                 }
 667                                 ghost.f[cl[i].pt[j]] = cl[i].mines == cl[i].pts ? MMine : MEmpty;
 668                         }
 669         if(rt == NOTARG){
 670                 fieldcombs(cl, ncl, &x, &y);
 671                 if(x >= 0){
 672                         rt = LTARG;
 673                         *targp = Pt(x, y);
 674                 }
 675         }
 676         free(ghost.f);
 677         free(cl);
 678         return rt;
 679 }
 680
 681 static void
 682 killchild(void)
 683 {
 684         postnote(PNPROC, ghost.pid, "kill");
 685 }
 686
 687 void
 688 GhostInit(void)
 689 {
 690         CList *cl;
 691         int ncl;
 692         int rt;
 693         Point p;
 694         int rc;
 695         int g;
 696
 697         ghost.Rendez.l = &ghost;
 698         if(rc = rfork(RFPROC|RFMEM), rc == 0){
 699                 qlock(&ghost);
 700                 for(;;){
 701                         while(!ghost.active || ghost.targettype != NOTARG)
 702                                 rsleep(&ghost);
 703                         g = ghost.generation;
 704                         ghostprep(&cl, &ncl);
 705                         qunlock(&ghost);
 706                         rt = ghostfind(cl, ncl, &p);
 707                         qlock(&ghost);
 708                         if(ghost.generation == g){
 709                                 ghost.targettype = rt;
 710                                 ghost.target = p;
 711                         }
 712                 }
 713         }else{
 714                 ghost.pid = rc;
 715                 atexit(killchild);
 716         }
 717 }
 718
 719 int
 720 GhostCheck(Point p)
 721 {
 722         int i;
 723
 724         for(i = 0; i < ghost.nmoves; i++)
 725                 if(eqpt(ghost.moves[i], p))
 726                         return 1;
 727         return 0;
 728 }
 729
 730 static void
 731 move(Point p)
 732 {
 733         if(ghost.nmoves == nelem(ghost.moves))
 734                 memmove(ghost.moves + 1, ghost.moves, sizeof(ghost.moves) - sizeof(Point));
 735         else
 736                 memmove(ghost.moves + 1, ghost.moves, ghost.nmoves++ * sizeof(Point));
 737         ghost.moves[0] = p;
 738         ghost.cpos = p;
 739         emoveto(p);
 740 }
 741
 742 static void
 743 approach(Point p)
 744 {
 745         Point q;
 746         double d;
 747
 748         q = subpt(p, ghost.cpos);
 749         d = hypot(q.x, q.y);
 750         if(d == 0)
 751                 return;
 752         d = 2 / d * 2 * (1 + d / (400 + d));
 753         move(addpt(ghost.cpos, Pt(ceil(q.x * d), ceil(q.y * d))));
 754 }
 755
 756 void
 757 GhostMode(void)
 758 {
 759         Point p;
 760
 761         if(!ghost.cursor){
 762                 esetcursor(&bunny);
 763                 ghost.cursor = 1;
 764         }
 765         if(ghost.wait > 0){
 766                 if(Status == Oops)
 767                         move(addpt(ghost.cpos, Pt(nrand(20) - 10, nrand(20) - 10)));
 768                 ghost.wait--;
 769                 return;
 770         }
 771         if(Status != Game){
 772                 ghost.active = 0;
 773                 p = Pt(Origin.x + MaxX * 8 + 12, Origin.y + 28);
 774                 if(TURBO || ptinrect(ghost.cpos, insetrect(Rpt(p, p), -4))){
 775                         InitMineField();
 776                         qlock(&ghost);
 777                         ghost.active = 0;
 778                         ghost.targettype = NOTARG;
 779                         ghost.generation++;
 780                         qunlock(&ghost);
 781                         eresized(0);
 782                 }else
 783                         approach(p);
 784                 return;
 785         }
 786         qlock(&ghost);
 787         if(!ghost.active){
 788                 ghost.active = 1;
 789                 rwakeup(&ghost);
 790         }
 791         if(ghost.targettype != NOTARG){
 792                 p = addpt(addpt(mulpt(ghost.target, 16), Pt(12+8, 57+8)), Origin);
 793                 if(TURBO || ptinrect(ghost.cpos, insetrect(Rpt(p, p), -4))){
 794                         switch(ghost.targettype){
 795                         case LTARG: LeftClick(ghost.target); break;
 796                         case RTARG: RightClick(ghost.target); break;
 797                         }
 798                         ghost.targettype = NOTARG;
 799                         rwakeup(&ghost);
 800                         qunlock(&ghost);
 801                         if(Status != Game && !TURBO) ghost.wait = 100;
 802                         DrawButton(Status);
 803                         flushimage(display, 1);
 804                         return;
 805                 }else{
 806                         qunlock(&ghost);
 807                         approach(p);
 808                 }
 809         }else
 810                 qunlock(&ghost);
 811 }
 812
 813 void
 814 GhostReset(int deltarg)
 815 {
 816         if(ghost.cursor){
 817                 esetcursor(nil);
 818                 ghost.cursor = 0;
 819         }
 820         ghost.cpos = LastMouse.xy;
 821         qlock(&ghost);
 822         ghost.active = 0;
 823         ghost.wait = 0;
 824         ghost.targettype = NOTARG;
 825         if(deltarg)
 826                 ghost.generation++;
 827         qunlock(&ghost);
 828 }