shithub: riscv

Download patch

ref: 7ca11774a1a78dcfa520f35a60d6ce34c2dc724a
parent: b7d31909f6258a36d00cb2bc2ef08687d6817755
author: aiju <devnull@localhost>
date: Sat Mar 10 09:40:34 EST 2018 

games/mines: build a better ghost trap


--- a/sys/src/games/mines/fns.h
+++ b/sys/src/games/mines/fns.h
@@ -2,5 +2,7 @@
 void RightClick(Point);
 void DrawButton(int);
 void InitMineField(void);
+void GhostInit(void);
 void GhostMode(void);
-void GhostReset(void);
+void GhostReset(int);
+int GhostCheck(Point);
--- a/sys/src/games/mines/ghost.c
+++ b/sys/src/games/mines/ghost.c
@@ -2,9 +2,18 @@
 #include <libc.h>
 #include <draw.h>
 #include <event.h>
+#include <mp.h>
+#include <cursor.h>
 #include "dat.h"
 #include "fns.h"
 
+enum { TURBO = 0 };
+
+static Cursor bunny = {
+	.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},
+	.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}
+};
+
 enum {
 	MEmpty,
 	MMine,
@@ -12,39 +21,71 @@
 	NState,
 };
 
-int ghostactive;
-int ghostwait;
-Point ghosttarget;
+typedef struct Ghost Ghost;
+typedef struct CList CList;
+typedef struct CGroup CGroup;
 
+struct Ghost {
+	QLock;
+	Rendez;
+	int active, wait;
+	int pid;
+	
+	enum { NOTARG, LTARG, RTARG } targettype;
+	Point target;
+	int generation;
+	
+	int nmines;
+	uchar *f;
+	
+	int w, h;
+	
+	int cursor;
+	Point moves[3];
+	int nmoves;
+	Point cpos;
+};
+
+struct CList {
+	int mines, pts;
+	int pt[8];
+	int next;
+};
+
+struct CGroup {
+	CList *cl;
+	int ncl;
+	mpint **cnt;
+	int max;
+	int cur;
+};
+
+static Ghost ghost;
+
 static uchar ***
-neighbours(uchar **f, uchar ***n)
+neighbours(void)
 {
 	int x, y, p;
+	uchar ***n;
 
-	if(n != nil){
-		for(x = 0; x < MaxX; x++)
-			for(y = 0; y < MaxY; y++)
-				memset(n[x][y], 0, NState);
-	}else{
-		n = calloc(sizeof(void*), MaxX);
-		for(x = 0; x < MaxX; x++){
-			n[x] = calloc(sizeof(void*), MaxY);
-			for(y = 0; y < MaxY; y++)
-				n[x][y] = calloc(sizeof(uchar), NState);
-		}
+	n = calloc(sizeof(void*), ghost.w);
+	for(x = 0; x < ghost.w; x++){
+		n[x] = calloc(sizeof(void*), ghost.h);
+		for(y = 0; y < ghost.h; y++)
+			n[x][y] = calloc(sizeof(uchar), NState);
 	}
 	
-	for(y = 0; y < MaxY; y++)
-		for(x = 0; x < MaxX; x++){
-			p = f[x][y];
+	for(y = 0; y < ghost.h; y++)
+		for(x = 0; x < ghost.w; x++){
+			p = ghost.f[x + y * ghost.w];
 			if(x > 0 && y > 0) n[x-1][y-1][p]++;
 			if(y > 0) n[x][y-1][p]++;
-			if(x < MaxX-1 && y > 0) n[x+1][y-1][p]++;
+			if(x < ghost.w-1 && y > 0) n[x+1][y-1][p]++;
 			if(x > 0) n[x-1][y][p]++;
-			if(x < MaxX-1) n[x+1][y][p]++;
-			if(x > 0 && y < MaxY-1) n[x-1][y+1][p]++;
-			if(y < MaxY-1) n[x][y+1][p]++;
-			if(x < MaxX-1 && y < MaxY-1) n[x+1][y+1][p]++;
+			if(x < ghost.w-1) n[x+1][y][p]++;
+			if(x > 0 && y < ghost.h-1) n[x-1][y+1][p]++;
+			if(y < ghost.h-1) n[x][y+1][p]++;
+			if(x < ghost.w-1 && y < ghost.h-1) n[x+1][y+1][p]++;
 		}
 	return n;
 }
@@ -53,11 +94,9 @@
 freeneighbours(uchar ***n)
 {
 	int x, y;
-	
-	if(n == nil)
-		return;
-	for(x = 0; x < MaxX; x++){
-		for(y = 0; y < MaxY; y++)
+
+	for(x = 0; x < ghost.w; x++){
+		for(y = 0; y < ghost.h; y++)
 			free(n[x][y]);
 		free(n[x]);
 	}
@@ -64,57 +103,53 @@
 	free(n);
 }
 
-static int
-allneighbours(uchar **f, int x, int y, int (*fun)(uchar **, int, int, void *), void *aux)
+static void
+printcl(CList *cl, int ncl)
 {
-	int rc;
-
-	rc = 0;
-	if(x > 0 && y > 0) rc += fun(f, x-1, y-1, aux);
-	if(y > 0) rc += fun(f, x, y-1, aux);
-	if(x < MaxX-1 && y > 0) rc += fun(f, x+1, y-1, aux);
-	if(x > 0) rc += fun(f, x-1, y, aux);
-	if(x < MaxX-1) rc += fun(f, x+1, y, aux);
-	if(x > 0 && y < MaxY-1) rc += fun(f, x-1, y+1, aux);
-	if(y < MaxY-1) rc += fun(f, x, y+1, aux);
-	if(x < MaxX-1 && y < MaxY-1) rc += fun(f, x+1, y+1, aux);
-	return rc;
-}
-
-typedef struct {
-	int mines, pts;
-	Point pt[8];
-} CList;
-
-static int
-addlist(uchar **f, int x, int y, void *aux)
-{
-	CList *c;
+	int i, j;
 	
-	c = aux;
-	if(f[x][y] == MUnknown)
-		c->pt[c->pts++] = (Point){x,y};
-	return 0;
+	for(i = 0; i < ncl; i++){
+		print("%d: ", cl[i].mines);
+		for(j = 0; j < cl[i].pts; j++)
+			print("%d ", cl[i].pt[j]);
+		print("\n");
+	}
+	print("--\n");
 }
 
 static void
-mklists(uchar **f, CList **clp, int *nclp)
+mklists(CList **clp, int *nclp)
 {
-	CList *cl;
+	CList *c, *cl;
 	int ncl, x, y;
 	uchar ***nei;
 	
 	cl = nil;
 	ncl = 0;
-	nei = neighbours(f, nil);
-	for(y = 0; y < MaxY; y++)
-		for(x = 0; x < MaxX; x++)
+	nei = neighbours();
+	for(y = 0; y < ghost.h; y++)
+		for(x = 0; x < ghost.w; x++)
 			if(MineField[x][y].Picture <= Empty8 && nei[x][y][MUnknown] > 0){
 				cl = realloc(cl, (ncl + 1) * sizeof(CList));
-				memset(&cl[ncl], 0, sizeof(CList));
-				cl[ncl].mines = MineField[x][y].Picture - nei[x][y][MMine];
-				allneighbours(f, x, y, addlist, &cl[ncl]);
-				ncl++;
+				c = &cl[ncl++];
+				memset(c, 0, sizeof(CList));
+				c->mines = MineField[x][y].Picture - nei[x][y][MMine];
+				if(x > 0 && y > 0 && ghost.f[(x-1)+(y-1)*ghost.w] == MUnknown)
+					c->pt[c->pts++] = (x-1)+(y-1)*ghost.w;
+				if(y > 0 && ghost.f[(x)+(y-1)*ghost.w] == MUnknown)
+					c->pt[c->pts++] = (x)+(y-1)*ghost.w;
+				if(x < ghost.w-1 && y > 0 && ghost.f[(x+1)+(y-1)*ghost.w] == MUnknown)
+					c->pt[c->pts++] = (x+1)+(y-1)*ghost.w;
+				if(x > 0 && ghost.f[(x-1)+(y)*ghost.w] == MUnknown)
+					c->pt[c->pts++] = (x-1)+(y)*ghost.w;
+				if(x < ghost.w-1 && ghost.f[(x+1)+(y)*ghost.w] == MUnknown)
+					c->pt[c->pts++] = (x+1)+(y)*ghost.w;
+				if(x > 0 && y < ghost.h-1 && ghost.f[(x-1)+(y+1)*ghost.w] == MUnknown)
+					c->pt[c->pts++] = (x-1)+(y+1)*ghost.w;
+				if(y < ghost.h-1 && ghost.f[(x)+(y+1)*ghost.w] == MUnknown)
+					c->pt[c->pts++] = (x)+(y+1)*ghost.w;
+				if(x < ghost.w-1 && y < ghost.h-1 && ghost.f[(x+1)+(y+1)*ghost.w] == MUnknown)
+					c->pt[c->pts++] = (x+1)+(y+1)*ghost.w;
 			}
 	freeneighbours(nei);
 	*clp = cl;
@@ -122,56 +157,467 @@
 }
 
 static int
-ismember(CList *c, Point p)
+ismember(CList *c, int p)
 {
 	int i;
 	
 	for(i = 0; i < c->pts; i++)
-		if(c->pt[i].x == p.x && c->pt[i].y == p.y)
+		if(c->pt[i] == p)
 			return 1;
 	return 0;
 }
 
 static void
-merge(CList *cl, int *nclp)
+splitknown(CList **clp, int *nclp, int i, int *lastq)
 {
-	int i, j, k, l;
+	int j;
+	CList *cl;
+	int ncl;
+	
+	cl = *clp;
+	ncl = *nclp;
+	cl = realloc(cl, sizeof(CList) * (ncl + cl[i].pts - 1));
+	memset(cl + ncl, 0, sizeof(CList) * (cl[i].pts - 1));
+	for(j = 1; j < cl[i].pts; j++){
+		cl[ncl - 1 + j].mines = cl[i].pts == cl[i].mines;
+		cl[ncl - 1 + j].pts = 1;
+		cl[ncl - 1 + j].pt[0] = cl[i].pt[j];
+		cl[*lastq].next = i;
+		*lastq = i;
+	}
+	cl[i].mines = cl[i].pts == cl[i].mines;
+	*nclp += cl[i].pts - 1;
+	cl[i].pts = 1;
+	*clp = cl;
+}
 
-start:
+static int
+merge(CList **clp, int *nclp, int start, int split)
+{
+	int i, j, k, l, p;
+	CList *cl, *q, *r;
+	int qi, lastq;
+	int zero;
+
+	cl = *clp;
+	qi = -1;
+	lastq = -1;
+	zero = 0;
 	for(i = 0; i < *nclp; i++)
-		for(j = 0; j < *nclp; j++){
-			if(i == j) continue;
-			for(k = 0; k < cl[i].pts; k++)
-				if(!ismember(&cl[j], cl[i].pt[k]))
-					goto next;		
-			for(k = l = 0; k < cl[j].pts; k++)
-				if(!ismember(&cl[i], cl[j].pt[k]))
-					cl[j].pt[l++] = cl[j].pt[k];
-			cl[j].pts = l;
-			cl[j].mines -= cl[i].mines;
-			if(l == 0){
-				memcpy(&cl[j], &cl[j+1], (*nclp - j - 1) * sizeof(CList));
-				(*nclp)--;
+		if(cl[i].pts == 0 || start >= 0 && start != i)
+			cl[i].next = -2;
+		else{
+			cl[i].next = -1;
+			if(lastq >= 0)
+				cl[lastq].next = i;
+			else
+				qi = i;
+			lastq = i;
+		}
+	while(qi >= 0){
+		q = &cl[qi];
+		for(i = 0; i < *nclp; i++){
+			r = &cl[i];
+			if(r == q || r->pts < q->pts) continue;
+			for(j = k = 0; j < q->pts; j++, k++){
+				p = q->pt[j];
+				if(r->pt[r->pts - 1] < p)
+					goto next;
+				while(r->pt[k] < p)
+					k++;
+				if(r->pt[k] > p)
+					goto next;
 			}
-			goto start;
+			for(j = k = l = 0; j < q->pts; j++, k++){
+				p = q->pt[j];
+				while(r->pt[k] < p)
+					r->pt[l++] = r->pt[k++];
+			}
+			while(k < r->pts)
+				r->pt[l++] = r->pt[k++];
+			r->pts = l;
+			r->mines -= q->mines;
+			if(r->mines < 0 || r->mines > r->pts){
+				*clp = cl;
+				return -1;
+			}
+			if(r->pts == 0 && r->mines == 0)
+				zero++;
+			if(r->next == -2 && r->pts > 0){
+				r->next = -1;
+				cl[lastq].next = i;
+				lastq = i;
+			}
+			if(split && r->pts > 1 && (r->pts == r->mines || r->mines == 0)){
+				splitknown(&cl, nclp, i, &lastq);
+				q = &cl[qi];
+			}
 		next: ;
-		}	
+		}
+		qi = q->next;
+		q->next = -1;
+	}
+	if(zero != 0){
+		for(i = 0, j = 0; i < *nclp; i++)
+			if(cl[i].mines != 0 || cl[i].pts != 0)
+				cl[j++] = cl[i];
+		*nclp = j;
+	}
+	*clp = cl;
+	return 0;
 }
 
 static void
-ghostfind(void)
+countref(CList *cl, int ncl, uchar *ref)
 {
-	int x, y, i, j, n;
-	uchar **field;
-	CList *cl;
-	int ncl;
-	Point pd;
-	int d, min;
+	int i, j;
+	
+	memset(ref, 0, ghost.w * ghost.h);
+	for(i = 0; i < ncl; i++)
+		for(j = 0; j < cl[i].pts; j++)
+			ref[cl[i].pt[j]]++;
+}
 
-	field = calloc(sizeof(uchar*), MaxX);
-	for(x = 0; x < MaxX; x++){
-		field[x] = calloc(sizeof(uchar), MaxY);
-		for(y = 0; y < MaxY; y++)
+static int *
+clgroup(CList *cl, int ncl, uchar *ref)
+{
+	int i, j, k, og, ng;
+	int *g;
+	
+	g = calloc(ncl, sizeof(int));
+	for(i = 0; i < ncl; i++)
+		g[i] = i;
+start:
+	for(i = 0; i < ncl; i++)
+		for(j = 0; j < cl[i].pts; j++){
+			if(ref[cl[i].pt[j]] == 1) continue;
+			for(k = 0; k < ncl; k++)
+				if(g[i] != g[k] && ismember(&cl[k], cl[i].pt[j]))
+					break;
+			if(k == ncl) continue;
+			if(g[i] < g[k]){
+				og = g[i];
+				ng = g[k];
+			}else{
+				og = g[k];
+				ng = g[i];
+			}
+			for(k = 0; k < ncl; k++)
+				if(g[k] == og)
+					g[k] = ng;
+			goto start;
+		}
+	return g;
+}
+
+static int
+groupmin(int *g, int ncl)
+{
+	int i, j, og, ng;
+	u32int *bs;
+
+	bs = calloc(sizeof(u32int), ncl + 31 >> 5);
+	for(i = 0; i < ncl; i++)
+		bs[g[i]>>5] |= 1<<(g[i] & 31);
+	for(i = 0; i < ncl; i++){
+		for(j = 0; j < g[i]; j++)
+			if((bs[j>>5] & 1<<(j & 31)) == 0)
+				break;
+		if(j == g[i]) continue;
+		og = g[i];
+		ng = j;
+		for(j = 0; j < ncl; j++)
+			if(g[j] == og)
+				g[j] = ng;
+		bs[og>>5] &= ~(1<<(og & 31));
+		bs[ng>>5] |= 1<<(ng & 31);
+	}
+	og = 0;
+	for(i = 0; i < ncl; i++)
+		if(g[i] + 1 > og)
+			og = g[i] + 1;
+	free(bs);
+	return og;
+}
+
+static int
+mkgroups(CList *cl, int ncl, uchar *ref, CGroup **gp)
+{
+	CGroup *g, *p;
+	int i, j, k, ng;
+	int *gr;
+	
+	gr = clgroup(cl, ncl, ref);
+	ng = groupmin(gr, ncl);
+	g = calloc(sizeof(CGroup), ng);
+	for(i = 0; i < ng; i++){
+		p = &g[i];
+		for(j = 0; j < ncl; j++)
+			if(gr[j] == i)
+				p->ncl++;
+		p->cl = calloc(sizeof(CList), p->ncl);
+		for(j = 0, k = 0; j < ncl; j++)
+			if(gr[j] == i)
+				p->cl[k++] = cl[j];
+	}
+	free(gr);
+	*gp = g;
+	return ng;
+}
+
+static void
+freegroups(CGroup *g, int ng)
+{
+	int i, j;
+	
+	for(i = 0; i < ng; i++){
+		for(j = 0; j <= g[i].max; j++)
+			mpfree(g[i].cnt[j]);
+		free(g[i].cl);
+		free(g[i].cnt);
+	}
+	free(g);
+}
+
+static void
+binom(mpint *acc, mpint *temp, int n, int k)
+{
+	int i;
+	
+	for(i = 0; i < k; i++){
+		itomp(n - i, temp);
+		mpmul(acc, temp, acc);
+	}
+	for(i = 2; i <= k; i++){
+		itomp(i, temp);
+		mpdiv(acc, temp, acc, nil);
+	}
+}
+
+static void countcomb(CList *cl, int ncl, mpint **);
+
+static void
+cltry(CList *cl, int ncl, int p, int v, mpint **cnt)
+{
+	CList *cm;
+	int ncm;
+	
+	cm = calloc(ncl + 1, sizeof(CList));
+	memcpy(cm, cl, ncl * sizeof(CList));
+	memset(&cm[ncl], 0, sizeof(CList));
+	cm[ncl].mines = v;
+	cm[ncl].pts = 1;
+	cm[ncl].pt[0] = p;
+	ncm = ncl + 1;
+	if(merge(&cm, &ncm, ncl, 1) < 0){
+		free(cm);
+		return;
+	}
+	countcomb(cm, ncm, cnt);
+	free(cm);
+}
+
+static void
+countcomb(CList *cl, int ncl, mpint **cnt)
+{
+	uchar *ref;
+	int p, i, j, nm;
+	mpint *rc, *c0;
+	
+	ref = calloc(ghost.w, ghost.h);
+	countref(cl, ncl, ref);
+	for(i = 0; i < ncl; i++)
+		for(j = 0; j < cl[i].pts; j++){
+			p = cl[i].pt[j];
+			if(ref[p] > 1){
+				cltry(cl, ncl, p, 0, cnt);
+				cltry(cl, ncl, p, 1, cnt);
+				free(ref);
+				return;
+			}
+		}
+	rc = itomp(1, nil);
+	c0 = mpnew(0);
+	nm = 0;
+	for(i = 0; i < ncl; i++){
+		nm += cl[i].mines;
+		binom(rc, c0, cl[i].pts, cl[i].mines);
+	}
+	if(mpcmp(rc, mpzero) != 0)
+		if(cnt[nm] == nil)
+			cnt[nm] = rc;
+		else{
+			mpadd(cnt[nm], rc, cnt[nm]);
+			mpfree(rc);
+		}
+	else
+		mpfree(rc);
+	mpfree(c0);
+	free(ref);
+}
+
+static mpint *
+totcomb(int tot, int nf, CGroup *g, int ng)
+{
+	int i, j, s, carry;
+	mpint *r, *v, *t, *m;
+	
+	s = 0;
+	for(i = 0; i < ng; i++){
+		for(j = 0; j <= g[i].max; j++)
+			if(g[i].cnt[j] != nil)
+				break;
+		if(j > g[i].max)
+			return mpnew(0);
+		g[i].cur = j;
+		s += j;
+	}
+	if(s > tot)
+		return mpnew(0);
+	r = mpnew(0);
+	v = mpnew(0);
+	t = mpnew(0);
+	do{
+		itomp(1, v);
+		s = 0;
+		for(i = 0; i < ng; i++){
+			m = g[i].cnt[g[i].cur];
+			mpmul(v, m, v);
+			s += g[i].cur;
+		}
+		if(s <= tot){
+			binom(v, t, nf, tot - s);
+			mpadd(r, v, r);
+		}
+		for(i = 0; i < ng; i++){
+			carry = 0;
+			do
+				if(++g[i].cur > g[i].max){
+					g[i].cur = 0;
+					carry = 1;
+				}
+			while(g[i].cnt[g[i].cur] == nil);
+			if(!carry) break;
+		}
+	}while(i < ng);
+	mpfree(v);
+	mpfree(t);
+	return r;
+}
+
+static int
+freefields(uchar *ref)
+{
+	int nf, p;
+
+	nf = 0;
+	for(p = 0; p < ghost.w * ghost.h; p++)
+		if(ref[p] == 0 && ghost.f[p] == MUnknown)
+			nf++;
+	return nf;
+}
+
+static int
+basecounts(CGroup *g, int ng)
+{
+	int i, j;
+	int allmax;
+	CGroup *p;
+
+	allmax = 0;
+	for(i = 0; i < ng; i++){
+		p = &g[i];
+		p->max = 0;
+		for(j = 0; j < p->ncl; j++)
+			p->max += p->cl[j].mines;
+		p->cnt = calloc(p->max + 1, sizeof(mpint *));
+		countcomb(p->cl, p->ncl, p->cnt);
+		if(p->max > allmax) allmax = p->max;
+	}
+	return allmax;
+}
+
+static void
+fieldcombs(CList *cl, int ncl, int *xp, int *yp)
+{
+	uchar *ref;
+	int i, k, p;
+	int nf, ng;
+	int allmax;
+	int ref1;
+	mpint *min, *v, **alt, **backup;
+	CList *l;
+	CGroup *g, *gp;
+
+	ref = calloc(ghost.w, ghost.h);
+	countref(cl, ncl, ref);
+	nf = freefields(ref);
+	ng = mkgroups(cl, ncl, ref, &g);
+	allmax = basecounts(g, ng);
+	alt = calloc(allmax + 1, sizeof(mpint *));
+	
+	*xp = -1;
+	*yp = -1;
+	min = mpnew(0);
+	
+	for(gp = g; gp < g + ng; gp++)
+		for(l = gp->cl; l < gp->cl + gp->ncl; l++){
+			ref1 = 0;
+			for(i = 0; i < l->pts; i++){
+				p = l->pt[i];
+				if(ref[p] == 0xff)
+					continue;
+				if(ref[p] == 1 && ref1++ != 0)
+					continue;
+				ref[p] = 0xff;
+				
+				cltry(gp->cl, gp->ncl, p, 1, alt);
+				backup = gp->cnt;
+				gp->cnt = alt;
+				v = totcomb(ghost.nmines, nf, g, ng);
+				if(*xp < 0 || mpcmp(v, min) < 0){
+					mpassign(v, min);
+					*xp = p % ghost.w;
+					*yp = p / ghost.w;
+				}
+				
+				gp->cnt = backup;
+				for(k = 0; k <= gp->max; k++)
+					mpfree(alt[k]);
+				memset(alt, 0, (gp->max + 1) * sizeof(mpint *));
+				mpfree(v);
+			}
+		}
+	if(nf > 0){
+		v = totcomb(ghost.nmines - 1, nf - 1, g, ng);
+		if(*xp < 0 || mpcmp(v, min) < 0){
+			i = nrand(nf);
+			for(p = 0; p < ghost.w * ghost.h; p++)
+				if(ref[p] == 0 && ghost.f[p] == MUnknown && i-- == 0)
+					break;
+			mpassign(v, min);
+			*xp = p % ghost.w;
+			*yp = p / ghost.w;
+		}
+		mpfree(v);
+	}
+	mpfree(min);
+	free(alt);
+	free(ref);
+	freegroups(g, ng);
+}
+
+static void
+ghostprep(CList **clp, int *nclp)
+{
+	int x, y;
+
+	ghost.w = MaxX;
+	ghost.h = MaxY;
+	ghost.nmines = MinesRemain;
+	ghost.f = calloc(ghost.w, ghost.h);
+	for(x = 0; x < ghost.w; x++){
+		for(y = 0; y < ghost.h; y++)
 			switch(MineField[x][y].Picture){
 			case Empty0:
 			case Empty1:
@@ -182,102 +628,201 @@
 			case Empty6:
 			case Empty7:
 			case Empty8:
-				field[x][y] = MEmpty;
+				ghost.f[x + y * ghost.w] = MEmpty;
 				break;
 			case Mark:
-				field[x][y] = MMine;
+				ghost.f[x + y * ghost.w] = MMine;
 				break;
 			default:
-				field[x][y] = MUnknown;
+				ghost.f[x + y * ghost.w] = MUnknown;
 			}
 	}
+	mklists(clp, nclp);
+}
+
+static int
+ghostfind(CList *cl, int ncl, Point *targp)
+{
+	int i, j, x, y;
+	Point p, pd;
+	int d, min;
+	Point targ;
+	int rt;
 	
-	mklists(field, &cl, &ncl);
-	merge(cl, &ncl);
-	ghostactive = -1;
+	merge(&cl, &ncl, -1, 0);
 	min = 0;
+	rt = NOTARG;
+	targ = ghost.cpos;
 	for(i = 0; i < ncl; i++)
 		if(cl[i].mines == 0 || cl[i].mines == cl[i].pts)
 			for(j = 0; j < cl[i].pts; j++){
-				pd = subpt(addpt(addpt(mulpt(cl[i].pt[j], 16), Pt(12+8, 57+8)), Origin), LastMouse.xy);
+				p = Pt(cl[i].pt[j]%ghost.w, cl[i].pt[j]/ghost.w);
+				pd = subpt(addpt(addpt(mulpt(p, 16), Pt(12+8, 57+8)), Origin), targ);
 				d = pd.x * pd.x + pd.y * pd.y;
-				if(ghostactive < 0 || d < min){
-					ghostactive = 1 + (cl[i].mines == cl[i].pts);
-					ghosttarget = cl[i].pt[j];
+				if(rt == NOTARG || d < min){
+					rt = cl[i].mines == cl[i].pts ? RTARG : LTARG;
+					*targp = p;
 					min = d;
 				}
-				field[cl[i].pt[j].x][cl[i].pt[j].y] = cl[i].mines == cl[i].pts ? MMine : MEmpty;
+				ghost.f[cl[i].pt[j]] = cl[i].mines == cl[i].pts ? MMine : MEmpty;
 			}
-	if(ghostactive < 0){
-		n = 0;
-		for(x = 0; x < MaxX; x++)
-			for(y = 0; y < MaxY; y++)
-				if(field[x][y] == MUnknown)
-					n++;
-		if(n == 0) goto done;
-		n = lrand() % n;
-		for(x = 0; x < MaxX; x++)
-			for(y = 0; y < MaxY; y++)
-				if(field[x][y] == MUnknown && n-- == 0){
-					ghostactive = 1;
-					ghosttarget = Pt(x, y);
-					goto done;
-				}
-	done:;
+	if(rt == NOTARG){
+		fieldcombs(cl, ncl, &x, &y);
+		if(x >= 0){
+			rt = LTARG;
+			*targp = Pt(x, y);
+		}
 	}
-	for(x = 0; x < MaxX; x++)
-		free(field[x]);
-	free(field);
+	free(ghost.f);
 	free(cl);
+	return rt;
 }
 
+static void
+killchild(void)
+{
+	postnote(PNPROC, ghost.pid, "kill");
+}
+
 void
-GhostMode(void)
+GhostInit(void)
 {
-	Point p, q;
+	CList *cl;
+	int ncl;
+	int rt;
+	Point p;
+	int rc;
+	int g;
+
+	ghost.Rendez.l = &ghost;
+	if(rc = rfork(RFPROC|RFMEM), rc == 0){
+		qlock(&ghost);
+		for(;;){
+			while(!ghost.active || ghost.targettype != NOTARG)
+				rsleep(&ghost);
+			g = ghost.generation;
+			ghostprep(&cl, &ncl);
+			qunlock(&ghost);
+			rt = ghostfind(cl, ncl, &p);
+			qlock(&ghost);
+			if(ghost.generation == g){
+				ghost.targettype = rt;
+				ghost.target = p;
+			}
+		}
+	}else{
+		ghost.pid = rc;
+		atexit(killchild);
+	}
+}
+
+int
+GhostCheck(Point p)
+{
+	int i;
+	
+	for(i = 0; i < ghost.nmoves; i++)
+		if(eqpt(ghost.moves[i], p))
+			return 1;
+	return 0;
+}
+
+static void
+move(Point p)
+{
+	if(ghost.nmoves == nelem(ghost.moves))
+		memmove(ghost.moves + 1, ghost.moves, sizeof(ghost.moves) - sizeof(Point));
+	else
+		memmove(ghost.moves + 1, ghost.moves, ghost.nmoves++ * sizeof(Point));
+	ghost.moves[0] = p;
+	ghost.cpos = p;
+	emoveto(p);
+}
+
+static void
+approach(Point p)
+{
+	Point q;
 	double d;
 
-	if(ghostwait > 0){
-		ghostwait--;
+	q = subpt(p, ghost.cpos);
+	d = hypot(q.x, q.y);
+	if(d == 0)
 		return;
+	d = 2 / d * 2 * (1 + d / (400 + d));
+	move(addpt(ghost.cpos, Pt(ceil(q.x * d), ceil(q.y * d))));
+}
+
+void
+GhostMode(void)
+{
+	Point p;
+
+	if(!ghost.cursor){
+		esetcursor(&bunny);
+		ghost.cursor = 1;
 	}
+	if(ghost.wait > 0){
+		if(Status == Oops)
+			move(addpt(ghost.cpos, Pt(nrand(20) - 10, nrand(20) - 10)));
+		ghost.wait--;
+		return;
+	}
 	if(Status != Game){
-		ghostactive = 0;
-		p = Pt(Origin.x +  MaxX * 8 + 12, Origin.y + 28);
-		if(ptinrect(LastMouse.xy, insetrect(Rpt(p, p), -4))){
+		ghost.active = 0;
+		p = Pt(Origin.x + MaxX * 8 + 12, Origin.y + 28);
+		if(TURBO || ptinrect(ghost.cpos, insetrect(Rpt(p, p), -4))){
 			InitMineField();
+			qlock(&ghost);
+			ghost.active = 0;
+			ghost.targettype = NOTARG;
+			ghost.generation++;
+			qunlock(&ghost);
 			eresized(0);
-		}
-		goto move;
+		}else
+			approach(p);
+		return;
 	}
-	if(!ghostactive)
-		ghostfind();
-	if(ghostactive > 0){
-		p = addpt(addpt(mulpt(ghosttarget, 16), Pt(12+8, 57+8)), Origin);
-		if(ptinrect(LastMouse.xy, insetrect(Rpt(p, p), -4))){
-			switch(ghostactive){
-			case 1: LeftClick(ghosttarget); break;
-			case 2: RightClick(ghosttarget); break;
+	qlock(&ghost);
+	if(!ghost.active){
+		ghost.active = 1;
+		rwakeup(&ghost);
+	}
+	if(ghost.targettype != NOTARG){
+		p = addpt(addpt(mulpt(ghost.target, 16), Pt(12+8, 57+8)), Origin);
+		if(TURBO || ptinrect(ghost.cpos, insetrect(Rpt(p, p), -4))){
+			switch(ghost.targettype){
+			case LTARG: LeftClick(ghost.target); break;
+			case RTARG: RightClick(ghost.target); break;
 			}
-			if(Status != Game) ghostwait = 100;
+			ghost.targettype = NOTARG;
+			rwakeup(&ghost);
+			qunlock(&ghost);
+			if(Status != Game && !TURBO) ghost.wait = 100;
 			DrawButton(Status);
 			flushimage(display, 1);
-			ghostactive = 0;
 			return;
+		}else{
+			qunlock(&ghost);
+			approach(p);
 		}
-	move:
-		q = subpt(p, LastMouse.xy);
-		d = hypot(q.x, q.y);
-		d = 2 / d * (1 + d / (400 + d));
-		LastMouse.xy.x += ceil(q.x * d);
-		LastMouse.xy.y += ceil(q.y * d);
-		emoveto(LastMouse.xy);
-	}
+	}else
+		qunlock(&ghost);
 }
 
 void
-GhostReset(void)
+GhostReset(int deltarg)
 {
-	ghostactive = 0;
-	ghostwait = 0;
+	if(ghost.cursor){
+		esetcursor(nil);
+		ghost.cursor = 0;
+	}
+	ghost.cpos = LastMouse.xy;
+	qlock(&ghost);
+	ghost.active = 0;
+	ghost.wait = 0;
+	ghost.targettype = NOTARG;
+	if(deltarg)
+		ghost.generation++;
+	qunlock(&ghost);
 }
--- a/sys/src/games/mines/mines.c
+++ b/sys/src/games/mines/mines.c
@@ -2,6 +2,7 @@
 #include <libc.h>
 #include <draw.h>
 #include <event.h>
+#include <mp.h>
 #include "dat.h"
 #include "fns.h"
 
@@ -533,6 +534,7 @@
 		Event Event;
 		Point CurrentCell, Cell = Pt(-1, -1);
 
+		GhostInit();
 		Etimer = etimer(0, UseGhost ? 10 : 1000);
 		LastAction = nsec();
 
@@ -541,7 +543,7 @@
 
 			if(Key == Etimer) {
 			
-				if(nsec() - LastAction > 5000000000ULL && LastMouse.buttons == 0)
+				if(nsec() - LastAction > 1000000000ULL && LastMouse.buttons == 0)
 					GhostMode();
 			
 				if(++Counter == (UseGhost ? 100 : 1)){
@@ -556,11 +558,11 @@
 
 			if(Key == Emouse) {
 			
-				if(!eqpt(LastMouse.xy, Event.mouse.xy) || LastMouse.buttons != Event.mouse.buttons){
+				if(!GhostCheck(Event.mouse.xy) || LastMouse.buttons != Event.mouse.buttons){
 					LastAction = nsec();
-					GhostReset();
+					LastMouse = Event.mouse;
+					GhostReset(Event.mouse.buttons != 0);
 				}
-				LastMouse = Event.mouse;
 
 				/* mouse over button? */
 				CurrentButton = FALSE;
@@ -666,7 +668,7 @@
 			if(Key == Ekeyboard) {
 			
 				LastAction = nsec();
-				GhostReset();
+				GhostReset(1);
 
 				switch(Event.kbdc) {
 					case 'n':