shithub: asif

Info  •  Files  •  Log

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

diff: cannot open b/app/path//null: file does not exist: 'b/app/path//null' diff: cannot open b/app//null: file does not exist: 'b/app//null'

--- /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*);