shithub: asif

Download patch

ref: 8e2a344a89b52e664f8cd8abf9dfa3848514129d
parent: d82bab87ecc28965c91621f1193efa8badc909df
author: qwx <qwx@sciops.net>
date: Sun Jun 5 07:13:36 EDT 2022 

make path algos more amenable to drop in usage; move path(1) to its own dir


--- /dev/null
+++ b/app/path/client.c
@@ -1,0 +1,66 @@
+#include <u.h>
+#include <libc.h>
+#include <thread.h>
+#include <draw.h>
+#include <mouse.h>
+#include <keyboard.h>
+#include <pool.h>
+#include "asif.h"
+#include "path.h"
+#include "dat.h"
+#include "fns.h"
+
+int	(*mousefn)(Mouse);
+int	(*keyfn)(Rune);
+
+static Keyboardctl *kc;
+static Mousectl *mc;
+
+void
+evloop(void)
+{
+	Rune r;
+
+	enum{
+		Aresize,
+		Amouse,
+		Akbd,
+		Aend,
+	};
+	Alt a[] = {
+		[Aresize] {mc->resizec, nil, CHANRCV},
+		[Amouse] {mc->c, &mc->Mouse, CHANRCV},
+		[Akbd] {kc->c, &r, CHANRCV},
+		[Aend] {nil, nil, CHANEND},
+	};
+	for(;;){
+		switch(alt(a)){
+		case Aresize:
+			if(getwindow(display, Refnone) < 0)
+				sysfatal("resize failed: %r");
+			resetdrw();
+			break;
+		case Amouse:
+			if(mousefn(mc->Mouse))
+				updatedrw();
+			break;
+		case Akbd:
+			keyfn(r);
+			break;
+		}
+	}
+}
+
+void
+init(int w, int h)
+{
+	fmtinstall('P', Pfmt);
+	fmtinstall('R', Rfmt);
+	initfs();
+	initmap(w, h);
+	initdrw();
+	if((kc = initkeyboard(nil)) == nil)
+		sysfatal("initkeyboard: %r");
+	if((mc = initmouse(nil, screen)) == nil)
+		sysfatal("initmouse: %r");
+}
--- /dev/null
+++ b/app/path/dat.h
@@ -1,0 +1,7 @@
+enum{
+	Nodesz = 8,
+};
+extern Node *selected;
+extern Node *start, *goal;
+
+extern int	(*pathfn)(Node*, Node*);
--- /dev/null
+++ b/app/path/drw.c
@@ -1,0 +1,190 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.h>
+#include "asif.h"
+#include "path.h"
+#include "dat.h"
+#include "fns.h"
+
+QLock drawlock;
+Node *selected;
+
+typedef Vertex Point;
+
+enum{
+	Cbg,
+	Cgrid,
+	Cfree,
+	Cblocked,
+	Copen,
+	Cclosed,
+	Cpath,
+	Cstart,
+	Cgoal,
+	Cend,
+};
+static Image *col[Cend];
+static Point viewΔ;
+static Rectangle viewr, hudr;
+static Image *view;
+
+static Image *
+eallocimage(Rectangle r, int repl, ulong col)
+{
+	Image *i;
+
+	if((i = allocimage(display, r, screen->chan, repl, col)) == nil)
+		sysfatal("allocimage: %r");
+	return i;
+}
+
+Node *
+scrselect(Point p)
+{
+	p = subpt(addpt(subpt(p, screen->r.min), viewΔ), Pt(1,1));
+	if(!ptinrect(p, viewr)){
+		selected = nil;
+		return nil;
+	}
+	p = divpt(p, Nodesz);
+	p.x = MIN(p.x, gridwidth-1);
+	p.y = MIN(p.y, gridheight-1);
+	selected = grid + p.y * gridwidth + p.x;
+	return selected;
+}
+
+static void
+flushdrw(void)
+{
+	draw(screen, screen->r, view, nil, viewΔ);
+	flushimage(display, 1);
+}
+
+static void
+drawhud(void)
+{
+	char s[64], *sp;
+	Node *n;
+
+	draw(screen, hudr, col[Cbg], nil, ZP);
+	sp = seprint(s, s+sizeof s, "grid size: %d,%d", viewr.max.x-1, viewr.max.y-1);
+	if((n = selected) != nil){
+		assert(n >= grid && n < grid + gridwidth * gridheight);
+		sp = seprint(sp, s+sizeof s, " selected: %P%s",
+			Pt((n-grid) % gridwidth, (n-grid) / gridwidth),
+			isblocked(n) ? ": blocked" : "");
+	}
+	USED(sp);
+	string(screen, addpt(screen->r.min, subpt(Pt(2, viewr.max.y+2), viewΔ)), col[Cfree], ZP, font, s);
+}
+
+static void
+drawnodes(void)
+{
+	Node *n;
+	Rectangle r;
+	Image *c;
+
+	for(n=grid; n<grid+gridwidth*gridheight; n++){
+		if(isblocked(n))
+			c = col[Cblocked];
+		else if(n == start)
+			c = col[Cstart];
+		else if(n == goal)
+			c = col[Cgoal];
+		else if(n->to != nil)
+			c = col[Cpath];
+		else if(n->closed)
+			c = col[Cclosed];
+		else if(n->open)
+			c = col[Copen];
+		else
+			continue;
+		r.min = n2s(n);
+		r.max = addpt(r.min, Pt(Nodesz-1, Nodesz-1));
+		draw(view, r, c, nil, ZP);
+	}
+}
+
+static void
+drawfrom(void)
+{
+	Node *n;
+	Point p0, p1;
+
+	for(n=grid; n<grid+gridwidth*gridheight; n++){
+		if(!n->open)
+			continue;
+		p1 = addpt(n2s(n), Pt(Nodesz / 2, Nodesz / 2));
+		p0 = addpt(n2s(n->from), Pt(Nodesz / 2, Nodesz / 2));
+		line(view, p0, p1, Endarrow, 0, 0, col[Cgrid], ZP);
+	}
+}
+
+static void
+drawgrid(void)
+{
+	Rectangle r;
+
+	draw(view, view->r, col[Cfree], nil, ZP);
+	r = viewr;
+	while(r.min.x < viewr.max.x){
+		r.max.x = r.min.x;
+		line(view, r.min, r.max, 0, 0, 0, col[Cgrid], ZP);
+		r.min.x += Nodesz;
+	}
+	r = viewr;
+	while(r.min.y < viewr.max.y){
+		r.max.y = r.min.y;
+		line(view, r.min, r.max, 0, 0, 0, col[Cgrid], ZP);
+		r.min.y += Nodesz;
+	}
+	drawnodes();
+	drawfrom();
+}
+
+static void
+redraw(void)
+{
+	drawgrid();
+}
+
+void
+updatedrw(void)
+{
+	qlock(&drawlock);
+	redraw();
+	qunlock(&drawlock);
+	drawhud();
+	flushdrw();
+}
+
+void
+resetdrw(void)
+{
+	viewr = Rpt(ZP, Pt(gridwidth*Nodesz+1, gridheight*Nodesz+1));
+	viewΔ = divpt(addpt(subpt(ZP, subpt(screen->r.max, screen->r.min)), viewr.max), 2);
+	hudr.min = addpt(screen->r.min, subpt(Pt(2, viewr.max.y+2), viewΔ));
+	hudr.max = addpt(hudr.min, Pt(viewr.max.x-2, font->height*3));
+	freeimage(view);
+	view = eallocimage(viewr, 0, DNofill);
+	draw(screen, screen->r, col[Cbg], nil, ZP);
+	updatedrw();
+}
+
+void
+initdrw(void)
+{
+	if(initdraw(nil, nil, "path") < 0)
+		sysfatal("initdraw: %r");
+	col[Cbg] = display->black;
+	col[Cgrid] = eallocimage(Rect(0,0,1,1), 1, 0x222222ff);
+	col[Cblocked] = display->black;
+	col[Cfree] = eallocimage(Rect(0,0,1,1), 1, 0x777777ff);
+	col[Copen] = eallocimage(Rect(0,0,1,1), 1, 0x00ccccff);
+	col[Cclosed] = eallocimage(Rect(0,0,1,1), 1, 0x0000ccff);
+	col[Cpath] = eallocimage(Rect(0,0,1,1), 1, 0xcccc00ff);
+	col[Cstart] = eallocimage(Rect(0,0,1,1), 1, 0x00cc00ff);
+	col[Cgoal] = eallocimage(Rect(0,0,1,1), 1, 0xcc0000ff);
+	resetdrw();
+}
--- /dev/null
+++ b/app/path/fns.h
@@ -1,0 +1,11 @@
+void	init(int, int);
+Node*	scrselect(Point);
+void	updatedrw(void);
+void	evloop(void);
+void	initfs(void);
+void	initmap(int, int);
+void	initdrw(void);
+void	resetdrw(void);
+Vertex	n2s(Node*);
+void	clearmap(void);
+int	setparm(int, int, int);
--- /dev/null
+++ b/app/path/fs.c
@@ -1,0 +1,11 @@
+#include <u.h>
+#include <libc.h>
+#include "asif.h"
+#include "path.h"
+#include "dat.h"
+#include "fns.h"
+
+void
+initfs(void)
+{
+}
--- /dev/null
+++ b/app/path/map.c
@@ -1,0 +1,57 @@
+#include <u.h>
+#include <libc.h>
+#include "asif.h"
+#include "path.h"
+#include "dat.h"
+#include "fns.h"
+
+int movemode;
+int	(*pathfn)(Node*, Node*);
+
+Vertex
+n2s(Node *n)
+{
+	Vertex v;
+
+	v = n2p(n);
+	v.x = v.x * Nodesz + 1;
+	v.y = v.y * Nodesz + 1;
+	return v;
+}
+
+int
+setparm(int mmode, int alg, int dist)
+{
+	switch(mmode){
+	case Move8: /* wet floor */
+	case Move4: movemode = mmode; break;
+	default: sysfatal("setparm: unknown move mode %d", mmode);
+	}
+	switch(alg){
+	case 0: pathfn = a∗findpath; break;
+	default: sysfatal("setparm: unknown algo type %d", alg);
+	}
+	switch(dist){
+	case Deuclid: distfn = eucdist; break;
+	case Dmanhattan: distfn = manhdist; break;
+	case Doctile: distfn = octdist; break;
+	default: sysfatal("setparm: unknown distance function %d", dist);
+	}
+	clearmap();
+	return 0;
+}
+
+void
+clearmap(void)
+{
+	if(grid == nil)
+		return;
+	cleargrid();
+	start = goal = nil;
+}
+
+void
+initmap(int w, int h)
+{
+	initgrid(w, h);
+}
--- /dev/null
+++ b/app/path/mkfile
@@ -1,0 +1,28 @@
+</$objtype/mkfile
+BIN=$home/bin/$objtype/asif
+TARG=path
+HFILES=../../asif.h ../../path/path.h dat.h fns.h
+OFILES=\
+	../../path/a∗.$O\
+	../../path/grid.$O\
+	../../dprint.$O\
+	../../emalloc.$O\
+	../../pheap.$O\
+	../../vec.$O\
+	../../zalloc.$O\
+	client.$O\
+	drw.$O\
+	fs.$O\
+	map.$O\
+	path.$O\
+
+</sys/src/cmd/mkone
+
+CFLAGS=$CFLAGS -I../.. -I../../path
+%.$O:	%.c
+	$CC -o $target $CFLAGS $stem.c
+
+dicks:V:
+	mkdir -p $BIN
+install:V:	dicks
+CLEANFILES=$CLEANFILES $OFILES
--- /dev/null
+++ b/app/path/path.c
@@ -1,0 +1,114 @@
+#include <u.h>
+#include <libc.h>
+#include <thread.h>
+#include <draw.h>
+#include <mouse.h>
+#include <keyboard.h>
+#include <pool.h>
+#include "asif.h"
+#include "path.h"
+#include "dat.h"
+#include "fns.h"
+
+extern int	(*mousefn)(Mouse);
+extern int	(*keyfn)(Rune);
+
+mainstacksize = 512*1024;
+
+Node *start, *goal;
+
+static int
+grmouse(Mouse m)
+{
+	static Node *old;
+	Node *n;
+
+	if(m.buttons == 0){
+		old = nil;
+		return 0;
+	}
+	if((n = scrselect(m.xy)) == nil || old == n)
+		return 0;
+	switch(m.buttons & 7){
+	case 1:
+		if(goal != n && !isblocked(n))
+			start = n;
+		break;
+	case 2:
+		if(start != n && !isblocked(n))
+			goal = n;
+		break;
+	case 4:
+		if(old == nil || isblocked(n) ^ isblocked(old))
+			toggleblocked(n);
+		break;
+	}
+	old = n;
+	if(start != nil && goal != nil)
+		if(pathfn(start, goal) < 0){
+			dprint(Logdebug, "grid::findpath: findpath from [%#p,%P] to [%#p,%P]: %r\n",
+				start, n2p(start), goal, n2p(goal));
+		}
+	return 1;
+}
+
+static int
+grkey(Rune r)
+{
+	switch(r){
+	case Kdel:
+	case 'q': threadexitsall(nil);
+	case 'r': cleargrid(); updatedrw(); break;
+	}
+	return 0;
+}
+
+static void
+usage(void)
+{
+	fprint(2, "usage: %s [-D4] [-s width[,height]]\n", argv0);
+	threadexits("usage");
+}
+
+void
+threadmain(int argc, char **argv)
+{
+	int w, h, d, m;
+	char *s;
+
+	w = 64;
+	h = 64;
+	d = Move8;
+	m = Doctile;
+	ARGBEGIN{
+	case 'D':
+		if(++debuglevel >= Logparanoid)
+			mainmem->flags |= POOL_NOREUSE | POOL_PARANOIA | POOL_LOGGING;
+		break;
+	case '4':
+		d = Move4;
+		m = Dmanhattan;
+		break;
+	case 's':
+		w = strtol(EARGF(usage()), &s, 0);
+		if(w <= 0)
+			usage();
+		if(*s != ','){
+			h = w;
+			break;
+		}
+		h = strtol(s+1, nil, 0);
+		if(h <= 0)
+			usage();
+		break;
+	default: usage();
+	}ARGEND
+	if(w <= 0 || w > 512
+	|| h <= 0 || h > 512)
+		sysfatal("invalid map size, must be in ]0,512]");
+	keyfn = grkey;
+	mousefn = grmouse;
+	setparm(d, 0, m);
+	init(w, h);
+	evloop();
+}
--- a/path/a∗.c
+++ b/path/a∗.c
@@ -1,16 +1,45 @@
 #include <u.h>
 #include <libc.h>
-#include <thread.h>
 #include <draw.h>
-#include <mouse.h>
-#include <keyboard.h>
-#include "../asif.h"
-#include "dat.h"
-#include "fns.h"
+#include "asif.h"
+#include "path.h"
 
-/* FIXME: nope, non-optimal paths + too many nodes opened, again
- * (dijsktra works fine) */
+/* FIXME: assumes grid */
 
+typedef Vertex Point;
+
+typedef struct PNode PNode;
+struct PNode{
+	Node *n;
+	double g;
+	double h;
+	double Δg;
+	Pairheap *pq;
+};
+
+static PNode**	(*successorfn)(Node*);
+static Zpool *zpool;
+
+static void
+cleanup(Pairheap **queue)
+{
+	Pairheap *p;
+
+	while((p = popqueue(queue)) != nil){
+		zfree(p->aux);
+		free(p);
+	}
+}
+
+static void
+backtrack(Node *a, Node *b)
+{
+	Node *n;
+
+	for(n=b; n!=a; n=n->from)
+		n->from->to = n;
+}
+
 /* slightly penalize diagonal movement for nicer-looking paths; cf.:
  * https://www.redbloblgames.com/pathfinding/a-star/implementation.html
  * one addition: make cost function to increase at a slower rate to
@@ -17,6 +46,7 @@
  * resolve tie-breakers in favor of closer nodes, otherwise we will
  * explore all nodes in the rectangle between the two points; does
  * NOT work with 4-way movement and manhattan distance for some reason */
+ 	// FIXME: ^- reverify that it does not work
 static double
 movecost(int Δx, int Δy)
 {
@@ -23,60 +53,142 @@
 	return Δx != 0 && Δy != 0 ? 1.001 : 1.0;
 }
 
-static Node *
+static PNode **
+successors8(Node *nu)
+{
+	static PNode *suc[8+1];
+	static dtab[2*(nelem(suc)-1)]={
+		1,0, 0,-1, -1,0, 0,1,
+		-1,-1, -1,1, 1,-1, 1,1,
+	};
+	int i;
+	Node *nv;
+	PNode *v, **vp;
+	Point p;
+	Rectangle r;
+
+	memset(suc, 0, sizeof suc);
+	p = n2p(nu);
+	r = Rect(0, 0, gridwidth, gridheight);
+	for(i=0, vp=suc; i<nelem(dtab); i+=2){
+		if(!ptinrect(addpt(p, Pt(dtab[i], dtab[i+1])), r))
+			continue;
+		nv = nu + dtab[i+1] * gridwidth + dtab[i];
+		assert(nv >= grid && nv < grid + gridwidth * gridheight);
+		if(isblocked(nv))
+			continue;
+		v = zalloc(zpool);
+		v->n = nv;
+		v->Δg = movecost(dtab[i], dtab[i+1]);
+		*vp++ = v;
+	}
+	return suc;
+}
+
+static PNode **
+successors4(Node *nu)
+{
+	static PNode *suc[4+1];
+	static int dtab[2*(nelem(suc)-1)]={
+		1,0, -1,0, 0,-1, 0,1,
+	}, rdtab[nelem(dtab)]={
+		0,1, 0,-1, -1,0, 1,0,
+	};
+	int i, *t;
+	Node *nv;
+	PNode *v, **vp;
+	Point p;
+	Rectangle r;
+
+	memset(suc, 0, sizeof suc);
+	p = n2p(nu);
+	r = Rect(0, 0, gridwidth, gridheight);
+	/* path straightening; cf.:
+	 * https://www.redbloblgames.com/pathfinding/a-star/implementation.html */
+	t = (p.x + p.y) % 2 == 0 ? rdtab : dtab;
+	for(i=0, vp=suc; i<nelem(dtab); i+=2){
+		if(!ptinrect(addpt(p, Pt(t[i], t[i+1])), r))
+			continue;
+		nv = nu + t[i+1] * gridwidth + t[i];
+		assert(nv >= grid && nv < grid + gridwidth * gridheight);
+		if(isblocked(nv))
+			continue;
+		v = zalloc(zpool);
+		v->n = nv;
+		v->Δg = movecost(t[i], t[i+1]);
+		*vp++ = v;
+	}
+	return suc;
+}
+
+static int
 a∗(Node *a, Node *b)
 {
 	double g, Δg;
-	Node *x, *s, **sl;
+	PNode *u, *v, **vl;
+	Node *nu, *nv;
 	Pairheap *queue, *pn;
 
-	assert(a != nil && b != nil);
-	assert(a != b);
 	queue = nil;
-	a->pq = pushqueue(distfn(a, b), a, &queue);
-	x = a;
+	nu = a;
+	u = zalloc(zpool);
+	u->n = a;
+	u->pq = pushqueue(distfn(a, b), u, &queue);
 	while((pn = popqueue(&queue)) != nil){
-		x = pn->aux;
+		u = pn->aux;
+		nu = u->n;
 		free(pn);
-		if(x == b)
+		if(nu == b)
 			break;
-		x->closed = 1;
+		nu->closed = 1;
 		dprint(Logtrace, "a∗: closed [%#p,%P] h %.4f g %.4f\n",
-			x, n2p(x), x->h, x->g);
-		if((sl = successorfn(x)) == nil)
+			u, n2p(nu), u->h, u->g);
+		if((vl = successorfn(nu)) == nil)
 			sysfatal("a∗: %r");
-		for(s=*sl++; s!=nil; s=*sl++){
-			if(s->closed)
+		for(v=*vl++; v!=nil; v=*vl++){
+			nv = v->n;
+			if(nv->closed)
 				continue;
-			assert(!isblocked(s));
-			g = x->g + s->Δg;
-			Δg = s->g - g;
-			if(!s->open){
-				s->from = x;
-				s->open = 1;
-				s->h = distfn(s, b);
-				s->g = g;
+			g = u->g + v->Δg;
+			Δg = v->g - g;
+			if(!nv->open){
+				nv->from = nu;
+				nv->open = 1;
+				v->h = distfn(nv, b);
+				v->g = g;
 				dprint(Logtrace, "a∗: opened [%#p,%P] h %.4f g %.4f f %.4f\n",
-					s, n2p(s), s->h, s->g, s->h + s->g);
-				s->pq = pushqueue(s->g + s->h, s, &queue);
+					v, n2p(nv), v->h, v->g, v->h + v->g);
+				v->pq = pushqueue(v->g + v->h, v, &queue);
 			}else if(Δg > 0){
 				dprint(Logtrace, "a∗: decrease [%#p,%P] h %.4f g %.4f Δg %.4f → f %.4f\n",
-					s, n2p(s), s->h, s->g, Δg, s->h + s->g - Δg);
-				s->from = x;
-				s->g -= Δg;
-				decreasekey(s->pq, Δg, &queue);
-				assert(s->g >= 0);
+					v, n2p(nv), v->h, v->g, Δg, v->h + v->g - Δg);
+				nv->from = u->n;
+				v->g -= Δg;
+				decreasekey(v->pq, Δg, &queue);
+				assert(v->g >= 0);
 			}
 		}
 	}
-	nukequeue(&queue);
-	return x;
+	cleanup(&queue);
+	if(nu != b)
+		return -1;
+	backtrack(a, b);
+	return 0;
 }
 
-void
-threadmain(int argc, char **argv)
+int
+a∗findpath(Node *a, Node *b)
 {
-	init(argc, argv);
-	initgrid(a∗, movecost);
-	evloop();
+	assert(a != nil && b != nil && a != b);
+	clearpath();
+	if(zpool == nil)
+		zpool = znew(sizeof(PNode));
+	successorfn = movemode == Move8 ? successors8 : successors4;
+	dprint(Logdebug, "grid::a∗findpath: a∗ from [%#p,%P] to [%#p,%P]\n",
+		a, n2p(a), b, n2p(b));
+	if(a∗(a, b) < 0){
+		dprint(Logdebug, "grid::a∗findpath: failed to find a path\n");
+		return -1;
+	}
+	return 0;
 }
--- a/path/client.c
+++ /dev/null
@@ -1,123 +1,0 @@
-#include <u.h>
-#include <libc.h>
-#include <thread.h>
-#include <draw.h>
-#include <mouse.h>
-#include <keyboard.h>
-#include <pool.h>
-#include "../asif.h"
-#include "dat.h"
-#include "fns.h"
-
-mainstacksize = 512*1024;
-
-extern QLock drawlock;
-Node*	scrselect(Point);
-void	updatedrw(void);
-
-int	(*mousefn)(Node*, Mouse, Node*);
-int	(*keyfn)(Rune);
-
-static Keyboardctl *kc;
-static Mousectl *mc;
-
-void
-evloop(void)
-{
-	Rune r;
-	Mouse m;
-	Node *n, *p;
-
-	enum{
-		Aresize,
-		Amouse,
-		Akbd,
-		Aend,
-	};
-	Alt a[] = {
-		[Aresize] {mc->resizec, nil, CHANRCV},
-		[Amouse] {mc->c, &mc->Mouse, CHANRCV},
-		[Akbd] {kc->c, &r, CHANRCV},
-		[Aend] {nil, nil, CHANEND},
-	};
-	p = nil;
-	for(;;){
-		switch(alt(a)){
-		case Aresize:
-			if(getwindow(display, Refnone) < 0)
-				sysfatal("resize failed: %r");
-			resetdrw();
-			break;
-		case Amouse:
-			if(mc->buttons == 0){
-				p = nil;
-				break;
-			}
-			if((n = scrselect(m.xy)) != nil && p != n){
-				if(mousefn(n, mc->Mouse, p) < 0)
-					fprint(2, "%r\n");
-				p = n;
-			}
-			updatedrw();
-			break;
-		case Akbd:
-			switch(r){
-			case Kdel: threadexitsall(nil);
-			case 'r': clearmap(); updatedrw(); break;
-			}
-			keyfn(r);
-			break;
-		}
-		m = mc->Mouse;
-	}
-}
-
-static void
-usage(void)
-{
-	fprint(2, "usage: %s [-D4] [-s width[,height]]\n", argv0);
-	threadexits("usage");
-}
-
-void
-init(int argc, char **argv)
-{
-	char *s;
-
-	mapwidth = 64;
-	mapheight = 64;
-	ARGBEGIN{
-	case 'D':
-		if(++debuglevel >= Logparanoid)
-			mainmem->flags |= POOL_NOREUSE | POOL_PARANOIA | POOL_LOGGING;
-		break;
-	case '4':
-		fourdir = 1;
-		break;
-	case 's':
-		mapwidth = strtol(EARGF(usage()), &s, 0);
-		if(mapwidth <= 0)
-			usage();
-		if(*s != ','){
-			mapheight = mapwidth;
-			break;
-		}
-		mapheight = strtol(s+1, nil, 0);
-		if(mapheight <= 0)
-			usage();
-		break;
-	default: usage();
-	}ARGEND
-	if(mapwidth <= 0 || mapwidth > 512
-	|| mapheight <= 0 || mapheight > 512)
-		sysfatal("invalid map size, must be in ]0,512]");
-	fmtinstall('P', Pfmt);
-	fmtinstall('R', Rfmt);
-	initfs();
-	initmap();
-	initdrw();
-	if((kc = initkeyboard(nil)) == nil)
-		sysfatal("initkeyboard: %r");
-	if((mc = initmouse(nil, screen)) == nil)
-		sysfatal("initmouse: %r");
-}
--- a/path/dat.h
+++ /dev/null
@@ -1,33 +1,0 @@
-typedef struct Vertex Vertex;
-typedef struct Node Node;
-typedef struct PNode PNode;
-
-struct Vertex{
-	int x;
-	int y;
-};
-struct PNode{
-	int open;
-	int closed;
-	double g;
-	double h;
-	double Δg;
-	Node *to;
-	Node *from;
-	Pairheap *pq;
-};
-enum{
-	Nodesz = 8,
-};
-struct Node{
-	int blocked;
-	PNode;
-};
-extern Node *map;
-extern int mapwidth, mapheight;
-extern Node *selected;
-extern Node *start, *goal;
-extern int fourdir;
-
-extern double	(*distfn)(Node*, Node*);
-extern Node**	(*successorfn)(Node*);
--- a/path/drw.c
+++ /dev/null
@@ -1,188 +1,0 @@
-#include <u.h>
-#include <libc.h>
-#include <draw.h>
-#include "../asif.h"
-#include "dat.h"
-#include "fns.h"
-
-QLock drawlock;
-Node *selected;
-
-typedef Vertex Point;
-
-enum{
-	Cbg,
-	Cgrid,
-	Cfree,
-	Cblocked,
-	Copen,
-	Cclosed,
-	Cpath,
-	Cstart,
-	Cgoal,
-	Cend,
-};
-static Image *col[Cend];
-static Point viewΔ;
-static Rectangle viewr, hudr;
-static Image *view;
-
-static Image *
-eallocimage(Rectangle r, int repl, ulong col)
-{
-	Image *i;
-
-	if((i = allocimage(display, r, screen->chan, repl, col)) == nil)
-		sysfatal("allocimage: %r");
-	return i;
-}
-
-Node *
-scrselect(Point p)
-{
-	p = subpt(addpt(subpt(p, screen->r.min), viewΔ), Pt(1,1));
-	if(!ptinrect(p, viewr)){
-		selected = nil;
-		return nil;
-	}
-	p = divpt(p, Nodesz);
-	p.x = MIN(p.x, mapwidth-1);
-	p.y = MIN(p.y, mapheight-1);
-	selected = map + p.y * mapwidth + p.x;
-	return selected;
-}
-
-static void
-flushdrw(void)
-{
-	draw(screen, screen->r, view, nil, viewΔ);
-	flushimage(display, 1);
-}
-
-static void
-drawhud(void)
-{
-	char s[64], *sp;
-	Node *n;
-
-	draw(screen, hudr, col[Cbg], nil, ZP);
-	sp = seprint(s, s+sizeof s, "map size: %d,%d", viewr.max.x-1, viewr.max.y-1);
-	if((n = selected) != nil){
-		assert(n >= map && n < map + mapwidth * mapheight);
-		sp = seprint(sp, s+sizeof s, " selected: %P%s",
-			Pt((n-map) % mapwidth, (n-map) / mapwidth),
-			n->blocked ? ": blocked" : "");
-	}
-	USED(sp);
-	string(screen, addpt(screen->r.min, subpt(Pt(2, viewr.max.y+2), viewΔ)), col[Cfree], ZP, font, s);
-}
-
-static void
-drawnodes(void)
-{
-	Node *n;
-	Rectangle r;
-	Image *c;
-
-	for(n=map; n<map+mapwidth*mapheight; n++){
-		if(n->blocked)
-			c = col[Cblocked];
-		else if(n == start)
-			c = col[Cstart];
-		else if(n == goal)
-			c = col[Cgoal];
-		else if(n->to != nil)
-			c = col[Cpath];
-		else if(n->closed)
-			c = col[Cclosed];
-		else if(n->open)
-			c = col[Copen];
-		else
-			continue;
-		r.min = n2s(n);
-		r.max = addpt(r.min, Pt(Nodesz-1, Nodesz-1));
-		draw(view, r, c, nil, ZP);
-	}
-}
-
-static void
-drawfrom(void)
-{
-	Node *n;
-	Point p0, p1;
-
-	for(n=map; n<map+mapwidth*mapheight; n++){
-		if(!n->open)
-			continue;
-		p1 = addpt(n2s(n), Pt(Nodesz / 2, Nodesz / 2));
-		p0 = addpt(n2s(n->from), Pt(Nodesz / 2, Nodesz / 2));
-		line(view, p0, p1, Endarrow, 0, 0, col[Cgrid], ZP);
-	}
-}
-static void
-drawmap(void)
-{
-	Rectangle r;
-
-	draw(view, view->r, col[Cfree], nil, ZP);
-	r = viewr;
-	while(r.min.x < viewr.max.x){
-		r.max.x = r.min.x;
-		line(view, r.min, r.max, 0, 0, 0, col[Cgrid], ZP);
-		r.min.x += Nodesz;
-	}
-	r = viewr;
-	while(r.min.y < viewr.max.y){
-		r.max.y = r.min.y;
-		line(view, r.min, r.max, 0, 0, 0, col[Cgrid], ZP);
-		r.min.y += Nodesz;
-	}
-	drawnodes();
-	drawfrom();
-}
-
-static void
-redraw(void)
-{
-	drawmap();
-}
-
-void
-updatedrw(void)
-{
-	qlock(&drawlock);
-	redraw();
-	qunlock(&drawlock);
-	drawhud();
-	flushdrw();
-}
-
-void
-resetdrw(void)
-{
-	viewr = Rpt(ZP, Pt(mapwidth*Nodesz+1, mapheight*Nodesz+1));
-	viewΔ = divpt(addpt(subpt(ZP, subpt(screen->r.max, screen->r.min)), viewr.max), 2);
-	hudr.min = addpt(screen->r.min, subpt(Pt(2, viewr.max.y+2), viewΔ));
-	hudr.max = addpt(hudr.min, Pt(viewr.max.x-2, font->height*3));
-	freeimage(view);
-	view = eallocimage(viewr, 0, DNofill);
-	draw(screen, screen->r, col[Cbg], nil, ZP);
-	updatedrw();
-}
-
-void
-initdrw(void)
-{
-	if(initdraw(nil, nil, "path") < 0)
-		sysfatal("initdraw: %r");
-	col[Cbg] = display->black;
-	col[Cgrid] = eallocimage(Rect(0,0,1,1), 1, 0x222222ff);
-	col[Cblocked] = display->black;
-	col[Cfree] = eallocimage(Rect(0,0,1,1), 1, 0x777777ff);
-	col[Copen] = eallocimage(Rect(0,0,1,1), 1, 0x00ccccff);
-	col[Cclosed] = eallocimage(Rect(0,0,1,1), 1, 0x0000ccff);
-	col[Cpath] = eallocimage(Rect(0,0,1,1), 1, 0xcccc00ff);
-	col[Cstart] = eallocimage(Rect(0,0,1,1), 1, 0x00cc00ff);
-	col[Cgoal] = eallocimage(Rect(0,0,1,1), 1, 0xcc0000ff);
-	resetdrw();
-}
--- a/path/fns.h
+++ /dev/null
@@ -1,16 +1,0 @@
-void	init(int, char**);
-void	evloop(void);
-void	initfs(void);
-void	initgrid(Node* (*)(Node*, Node*), double (*)(int, int));
-void	resetmap(void);
-void	clearmap(void);
-void	initmap(void);
-void	initdrw(void);
-void	resetdrw(void);
-double	eucdist(Node*, Node*);
-double	octdist(Node*, Node*);
-double	manhdist(Node*, Node*);
-Vertex	n2p(Node*);
-Node*	p2n(Vertex);
-Vertex	n2s(Node*);
-int	isblocked(Node*);
--- a/path/fs.c
+++ /dev/null
@@ -1,10 +1,0 @@
-#include <u.h>
-#include <libc.h>
-#include "../asif.h"
-#include "dat.h"
-#include "fns.h"
-
-void
-initfs(void)
-{
-}
--- a/path/grid.c
+++ b/path/grid.c
@@ -1,145 +1,104 @@
 #include <u.h>
 #include <libc.h>
-#include <thread.h>
-#include <draw.h>
-#include <mouse.h>
-#include <keyboard.h>
-#include "../asif.h"
-#include "dat.h"
-#include "fns.h"
+#include "asif.h"
+#include "path.h"
 
-extern int	(*mousefn)(Node*, Mouse, Node*);
-extern int	(*keyfn)(Rune);
-
+Node *grid;
+int gridwidth, gridheight;
 double	(*distfn)(Node*, Node*);
-Node**	(*successorfn)(Node*);
 
-Node *start, *goal;
+double
+eucdist(Node *a, Node *b)
+{
+	int dx, dy;
 
-static Node*	(*pathfn)(Node*, Node*);
-static double	(*costfn)(int, int);
+	dx = a->x - b->x;
+	dy = a->y - b->y;
+	return sqrt(dx *dx + dy *dy);
+}
 
-static void
-backtrack(void)
+double
+octdist(Node *a, Node *b)
 {
-	Node *n;
+	int dx, dy;
 
-	assert(goal != start);
-	for(n=goal; n!=start; n=n->from)
-		n->from->to = n;
+	dx = abs(a->x - b->x);
+	dy = abs(a->y - b->y);
+	return 1 * (dx + dy) + MIN(dx, dy) * (SQRT2 - 2 * 1);
 }
 
-static Node **
-successors8(Node *n)
+double
+manhdist(Node *a, Node *b)
 {
-	static Node *suc[8+1];
-	static dtab[2*(nelem(suc)-1)]={
-		1,0, 0,-1, -1,0, 0,1,
-		-1,-1, -1,1, 1,-1, 1,1,
-	};
-	int i;
-	Node *s, **np;
-	Point p;
-	Rectangle r;
+	int dx, dy;
 
-	memset(suc, 0, sizeof suc);
-	p = n2p(n);
-	r = Rect(0, 0, mapwidth, mapheight);
-	for(i=0, np=suc; i<nelem(dtab); i+=2){
-		if(!ptinrect(addpt(p, Pt(dtab[i], dtab[i+1])), r))
-			continue;
-		s = n + dtab[i+1] * mapwidth + dtab[i];
-		assert(s >= map && s < map + mapwidth * mapheight);
-		if(isblocked(s))
-			continue;
-		s->Δg = costfn != nil ? costfn(dtab[i], dtab[i+1]) : 0;
-		*np++ = s;
-	}
-	return suc;
+	dx = abs(a->x - b->x);
+	dy = abs(a->y - b->y);
+	return dx + dy;
 }
 
-static Node **
-successors4(Node *n)
+void
+toggleblocked(Node *n)
 {
-	static Node *suc[4+1];
-	static int dtab[2*(nelem(suc)-1)]={
-		1,0, -1,0, 0,-1, 0,1,
-	}, rdtab[nelem(dtab)]={
-		0,1, 0,-1, -1,0, 1,0,
-	};
-	int i, *t;
-	Node *s, **np;
-	Point p;
-	Rectangle r;
+	n->blocked ^= 1;
+}
 
-	memset(suc, 0, sizeof suc);
-	p = n2p(n);
-	r = Rect(0, 0, mapwidth, mapheight);
-	/* path straightening; cf.:
-	 * https://www.redbloblgames.com/pathfinding/a-star/implementation.html */
-	t = (p.x + p.y) % 2 == 0 ? rdtab : dtab;
-	for(i=0, np=suc; i<nelem(dtab); i+=2){
-		if(!ptinrect(addpt(p, Pt(t[i], t[i+1])), r))
-			continue;
-		s = n + t[i+1] * mapwidth + t[i];
-		assert(s >= map && s < map + mapwidth * mapheight);
-		if(isblocked(s))
-			continue;
-		s->Δg = costfn != nil ? costfn(t[i], t[i+1]) : 0;
-		*np++ = s;
-	}
-	return suc;
+int
+isblocked(Node *n)
+{
+	return n->blocked;
 }
 
-static int
-findpath(void)
+void
+clearpath(void)
 {
-	if(start == nil || goal == nil){
-		werrstr("findpath: start and goal not undefined");
-		return -1;
-	}
-	resetmap();
-	dprint(Logdebug, "grid::findpath: findpath from [%#p,%P] to [%#p,%P]\n",
-		start, n2p(start), goal, n2p(goal));
-	if(pathfn(start, goal) != goal){
-		werrstr("findpath: failed");
-		return -1;
-	}
-	backtrack();
-	return 0;
+	Node *n;
+
+	if(grid == nil)
+		return;
+	for(n=grid; n<grid+gridwidth*gridheight; n++)
+		memset(&n->PState, 0, sizeof n->PState);
 }
 
-static int
-grmouse(Node *n, Mouse m, Node *old)
+void
+cleargrid(void)
 {
-	switch(m.buttons & 7){
-	case 1: if(goal != n && !n->blocked) start = n; break;
-	case 2: if(start != n && !n->blocked) goal = n; break;
-	case 4: if(old == nil || n->blocked ^ old->blocked) n->blocked ^= 1; return 0;
-	}
-	if(start != nil && goal != nil)
-		return findpath();
-	return 0;
+	Node *n;
+
+	if(grid == nil)
+		return;
+	for(n=grid; n<grid+gridwidth*gridheight; n++)
+		memset(&n->State, 0, sizeof n->State);
 }
 
-static int
-grkey(Rune)
+Node *
+p2n(Vertex p)
 {
-	return 0;
+	return grid + p.y * gridwidth + p.x;
 }
 
-void
-initgrid(Node* (*f)(Node*, Node*), double (*cost)(int, int))
+Vertex
+n2p(Node *n)
 {
-	if(fourdir){
-		distfn = manhdist;
-		successorfn = successors4;
-	}else{
-		distfn = octdist;
-		successorfn = successors8;
+	return (Vertex){(n - grid) % gridwidth, (n - grid) / gridheight};
+}
+
+Node *
+initgrid(int w, int h)
+{
+	int x, y;
+	Node *n;
+
+	grid = emalloc(w * h * sizeof *grid);
+	for(n=grid, x=0, y=0; n<grid+w*h; n++){
+		n->x = x;
+		n->y = y;
+		if(++x == w){
+			x = 0;
+			y++;
+		}
 	}
-	mousefn = grmouse;
-	keyfn = grkey;
-	pathfn = f;
-	costfn = cost;
+	gridwidth = w;
+	gridheight = h;
+	return grid;
 }
--- a/path/map.c
+++ /dev/null
@@ -1,103 +1,0 @@
-#include <u.h>
-#include <libc.h>
-#include "../asif.h"
-#include "dat.h"
-#include "fns.h"
-
-Node *start, *goal;
-
-Node *map;
-int mapwidth, mapheight;
-int fourdir;
-
-Vertex
-n2p(Node *n)
-{
-	return (Vertex){(n - map) % mapwidth, (n - map) / mapwidth};
-}
-
-Node *
-p2n(Vertex p)
-{
-	return map + p.y * mapwidth + p.x;
-}
-
-Vertex
-n2s(Node *n)
-{
-	Vertex v;
-
-	v = n2p(n);
-	v.x = v.x * Nodesz + 1;
-	v.y = v.y * Nodesz + 1;
-	return v;
-}
-
-double
-eucdist(Node *a, Node *b)
-{
-	int dx, dy;
-	Vertex p, q;
-
-	p = n2p(a);
-	q = n2p(b);
-	dx = p.x - q.x;
-	dy = p.y - q.y;
-	return sqrt(dx *dx + dy *dy);
-}
-
-double
-octdist(Node *a, Node *b)
-{
-	int dx, dy;
-	Vertex p, q;
-
-	p = n2p(a);
-	q = n2p(b);
-	dx = abs(p.x - q.x);
-	dy = abs(p.y - q.y);
-	return 1 * (dx + dy) + MIN(dx, dy) * (SQRT2 - 2 * 1);
-}
-
-double
-manhdist(Node *a, Node *b)
-{
-	int dx, dy;
-	Vertex p, q;
-
-	p = n2p(a);
-	q = n2p(b);
-	dx = abs(p.x - q.x);
-	dy = abs(p.y - q.y);
-	return dx + dy;
-}
-
-int
-isblocked(Node *n)
-{
-	return n->blocked;
-}
-
-void
-resetmap(void)
-{
-	Node *n;
-
-	for(n=map; n<map+mapwidth*mapheight; n++)
-		memset(&n->PNode, 0, sizeof n->PNode);
-}
-
-void
-clearmap(void)
-{
-	Node *n;
-
-	for(n=map; n<map+mapwidth*mapheight; n++)
-		memset(n, 0, sizeof *n);
-}
-
-void
-initmap(void)
-{
-	map = emalloc(mapwidth * mapheight * sizeof *map);
-}
--- a/path/mkfile
+++ /dev/null
@@ -1,29 +1,0 @@
-</$objtype/mkfile
-BIN=$home/bin/$objtype/path
-TARG=\
-	a∗\
-	bfs\
-	dijkstra\
-
-HFILES=../asif.h dat.h fns.h
-OFILES=\
-	../emalloc.$O\
-	../dprint.$O\
-	client.$O\
-	drw.$O\
-	fs.$O\
-	grid.$O\
-	map.$O\
-
-</sys/src/cmd/mkmany
-
-$O.dijkstra: $OFILES dijkstra.$O ../pheap.$O
-$O.a∗: $OFILES a∗.$O ../pheap.$O
-$O.bfs: $OFILES bfs.$O ../vec.$O
-
-dicks:V:
-	mkdir -p $BIN
-install:V:	dicks
-%.$O:	%.c
-	$CC -o $target $CFLAGS $stem.c
-CLEANFILES=`{echo ../*.[$OS]}
--- /dev/null
+++ b/path/path.h
@@ -1,0 +1,53 @@
+typedef struct Vertex Vertex;
+typedef struct State State;
+typedef struct PState PState;
+typedef struct Node Node;
+
+struct Vertex{
+	int x;
+	int y;
+};
+struct PState{
+	int open;
+	int closed;
+	Node *from;
+	Node *to;
+};
+struct State{
+	int blocked;
+	PState;
+};
+struct Node{
+	Vertex;
+	State;
+};
+int	isblocked(Node*);
+void	toggleblocked(Node*);
+
+enum{
+	Deuclid,
+	Dmanhattan,
+	Doctile,
+};
+double	eucdist(Node*, Node*);
+double	octdist(Node*, Node*);
+double	manhdist(Node*, Node*);
+extern double	(*distfn)(Node*, Node*);
+
+Node*	p2n(Vertex);
+Vertex	n2p(Node*);
+
+enum{
+	Move8,
+	Move4,
+};
+extern int movemode;
+
+extern Node *grid;
+extern int gridwidth, gridheight;
+
+void	clearpath(void);
+void	cleargrid(void);
+Node*	initgrid(int, int);
+
+int	a∗findpath(Node*, Node*);