shithub: asif

Info  •  Files  •  Log  •  Branches

disallow corner cutting, refactor grid to remove redundancies

also make the shared Node struct the first class citizen in pathing, not PNode
not happy about the vertex shit, but don't know of a better solution yet
direction encoded as bits, anticipating jps(b) et al

--- a/app/path/client.c

+++ b/app/path/client.c

@@ -6,6 +6,7 @@

 #include <keyboard.h>

 #include <pool.h>

 #include "asif.h"

+#include "graph.h"

 #include "path.h"

 #include "dat.h"

 #include "fns.h"

--- a/app/path/drw.c

+++ b/app/path/drw.c

@@ -2,6 +2,7 @@

 #include <libc.h>

 #include <draw.h>

 #include "asif.h"

+#include "graph.h"

 #include "path.h"

 #include "dat.h"

 #include "fns.h"

@@ -12,6 +13,7 @@

 int nodesz = 1;

 typedef Vertex Point;

+typedef Vectangle Rectangle;

 enum{

 	Cbg,

--- a/app/path/fns.h

+++ b/app/path/fns.h

@@ -6,7 +6,7 @@

 void	showscen(int);

 void	reloadscen(void);

 void	runscens(void);

-int	readscen(char*, char*, Vertex*, int*, int*, int*);

+int	readscen(char*, char*, Vertex*);

 void	initfs(void);

 int	Vfmt(Fmt*);

 int	Nfmt(Fmt*);

--- a/app/path/fs.c

+++ b/app/path/fs.c

@@ -2,6 +2,7 @@

 #include <libc.h>

 #include <bio.h>

 #include "asif.h"

+#include "graph.h"

 #include "path.h"

 #include "dat.h"

 #include "fns.h"

@@ -197,7 +198,7 @@

 }

 int

-readscen(char *path, char *respath, Vertex *v, int *m, int *a, int *d)

+readscen(char *path, char *respath, Vertex *v)

 {

 	int n;

 	char *s, *arg[32];

@@ -207,9 +208,6 @@

 	if(path == nil)

 		return 0;

 	doprof = 1;

-	/* only supported benchmarking configurations so far */

-	if(*a != Pa∗ && *a != Pdijkstra)

-		sysfatal("unimplemented profiling for parameter set");

 	if((s = strrchr(path, '.')) == nil){

 		werrstr("invalid path name");

 		return -1;

--- a/app/path/map.c

+++ b/app/path/map.c

@@ -1,6 +1,7 @@

 #include <u.h>

 #include <libc.h>

 #include "asif.h"

+#include "graph.h"

 #include "path.h"

 #include "dat.h"

 #include "fns.h"

@@ -58,7 +59,7 @@

 	setparm(m, a, d);

 	if(scen == nil)

 		initgrid(v.x, v.y);

-	else if(readscen(scen, res, &v, &m, &a, &d) < 0)

+	else if(readscen(scen, res, &v) < 0)

 		sysfatal("readscen: %r");

 	return 0;

 }

--- a/app/path/mkfile

+++ b/app/path/mkfile

@@ -1,8 +1,9 @@

 </$objtype/mkfile

 BIN=$home/bin/$objtype/asif

 TARG=path

-HFILES=../../asif.h ../../path/path.h dat.h fns.h

+HFILES=../../asif.h ../../path/path.h ../../graph/graph.h dat.h fns.h

 OFILES=\

+	../../graph/vertex.$O\

 	../../path/a∗.$O\

 	../../path/bfs.$O\

 	../../path/dijkstra.$O\

@@ -21,7 +22,7 @@

 </sys/src/cmd/mkone

-CFLAGS=$CFLAGS -I../.. -I../../path

+CFLAGS=$CFLAGS -I../.. -I../../path -I../../graph

 %.$O:	%.c

 	$CC -o $target $CFLAGS $stem.c

--- a/app/path/path.c

+++ b/app/path/path.c

@@ -6,6 +6,7 @@

 #include <keyboard.h>

 #include <pool.h>

 #include "asif.h"

+#include "graph.h"

 #include "path.h"

 #include "dat.h"

 #include "fns.h"

--- /dev/null

+++ b/graph/graph.h

@@ -1,0 +1,17 @@

+typedef struct Vertex Vertex;

+typedef struct Vectangle Vectangle;

+struct Vertex{

+	int x;

+	int y;

+};

+struct Vectangle{

+	Vertex min;

+	Vertex max;

+};

+

+Vertex	V(int, int);

+Vectangle	V²(int, int, int, int);

+Vectangle	toV²(Vertex, Vertex);

+Vertex	ΔV(Vertex, Vertex);

+Vertex	∑V(Vertex, Vertex);

+int	V∩V²(Vertex, Vectangle);

--- /dev/null

+++ b/graph/vertex.c

@@ -1,0 +1,44 @@

+#include <u.h>

+#include <libc.h>

+#include <draw.h>

+#include "asif.h"

+#include "graph.h"

+

+typedef Vertex Point;

+

+Vertex

+V(int x, int y)

+{

+	return (Vertex){x, y};

+}

+

+Vectangle

+V²(int ux, int uy, int vx, int vy)

+{

+	return (Vectangle){(Vertex){ux, uy}, (Vertex){vx, vy}};

+}

+

+Vectangle

+toV²(Vertex u, Vertex v)

+{

+	return (Vectangle){(Vertex){u.x, u.y}, (Vertex){v.x, v.y}};

+}

+

+Vertex

+ΔV(Vertex u, Vertex v)

+{

+	return (Vertex){v.x - u.x, v.y - u.y};

+}

+

+Vertex

+∑V(Vertex u, Vertex v)

+{

+	return (Vertex){u.x + v.x, u.y + v.y};

+}

+

+int

+V∩V²(Vertex u, Vectangle w)

+{

+	return u.x >= w.min.x && u.x < w.max.x

+		&& u.y >= w.min.y && u.y < w.max.y;

+}

--- a/path/a∗.c

+++ b/path/a∗.c

@@ -2,6 +2,7 @@

 #include <libc.h>

 #include <draw.h>

 #include "asif.h"

+#include "graph.h"

 #include "path.h"

 typedef Vertex Point;

@@ -15,7 +16,6 @@

 	Pairheap *pq;

 };

-static PNode**	(*successorfn)(Node*);

 static Zpool *zpool;

 static void

@@ -33,142 +33,76 @@

 	}

 }

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

- * resolve tie-breakers in favor of closer nodes, otherwise we will

- * explore all nodes in the rectangle between the two points */

-static double

-movecost(int Δx, int Δy)

+static Node **

+successors(Node *u)

 {

-	return Δx != 0 && Δy != 0 ? 1.001 : 1.0;

-}

+	Node **vl, **vp, *n;

+	PNode *pu;

-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;

-		if((v = nv->aux) == nil){

-			v = nv->aux = zalloc(zpool);

-			v->n = nv;

+	vl = expand(u);

+	for(vp=vl; (n=*vp)!=nil; vp++)

+		if(n->aux == nil){

+			pu = n->aux = zalloc(zpool);

+			pu->n = n;

 		}

-		v->Δg = movecost(dtab[i], dtab[i+1]);

-		*vp++ = v;

-	}

-	return suc;

+	return vl;

 }

-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;

-		if((v = nv->aux) == nil){

-			v = nv->aux = 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;

-	PNode *u, *v, **vl;

-	Node *nu, *nv;

-	Pairheap *queue, *pn;

+	Node *u, *v, **vl;

+	PNode *pu, *pv;

+	Pairheap *queue, *pq;

 	queue = nil;

-	u = a->aux = zalloc(zpool);

-	nu = u->n = a;

-	u->pq = pushqueue(distfn(a, b), u, &queue);

-	while((pn = popqueue(&queue)) != nil){

-		u = pn->aux;

-		nu = u->n;

-		free(pn);

-		if(nu == b)

+	u = a;

+	pu = zalloc(zpool);

+	pu->n = u;

+	u->aux = pu;

+	pu->pq = pushqueue(distfn(a, b), pu, &queue);

+	while((pq = popqueue(&queue)) != nil){

+		pu = pq->aux;

+		u = pu->n;

+		free(pq);

+		if(u == b)

 			break;

-		nu->closed = 1;

+		u->closed = 1;

 		stats.closed++;

 		dprint(Logtrace, "a∗: closed [%#p,%P] h %.4f g %.4f\n",

-			u, n2p(nu), u->h, u->g);

-		if((vl = successorfn(nu)) == nil)

+			u, n2p(u), pu->h, pu->g);

+		if((vl = successors(u)) == nil)

 			sysfatal("a∗: %r");

 		for(v=*vl++; v!=nil; v=*vl++){

-			nv = v->n;

+			pv = v->aux;

 			stats.touched++;

-			if(nv->closed)

+			if(v->closed)

 				continue;

-			g = u->g + v->Δg;

-			Δg = v->g - g;

-			if(!nv->open){

-				nv->from = nu;

-				nv->open = 1;

+			g = pu->g + unitmovecost(u, v);

+			Δg = pv->g - g;

+			if(!v->open){

+				v->from = u;

+				v->open = 1;

 				stats.opened++;

-				v->h = distfn(nv, b);

-				v->g = g;

+				pv->h = distfn(v, b);

+				pv->g = g;

 				dprint(Logtrace, "a∗: opened [%#p,%P] h %.4f g %.4f f %.4f\n",

-					v, n2p(nv), v->h, v->g, v->h + v->g);

-				v->pq = pushqueue(v->g + v->h, v, &queue);

+					v, n2p(v), pv->h, pv->g, pv->h + pv->g);

+				pv->pq = pushqueue(pv->g + pv->h, pv, &queue);

 			}else if(Δg > 0){

 				stats.updated++;

 				dprint(Logtrace, "a∗: decrease [%#p,%P] h %.4f g %.4f Δg %.4f → f %.4f\n",

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

+					v, n2p(v), pv->h, pv->g, Δg, pv->h + pv->g - Δg);

+				v->from = u;

+				pv->g -= Δg;

+				decreasekey(pv->pq, Δg, &queue);

+				assert(pv->g >= 0);

 			}

 		}

 	}

 	nukequeue(&queue);

-	if(nu != b)

+	if(u != b)

 		return -1;

 	return 0;

 }

@@ -182,7 +116,6 @@

 	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((r = a∗(a, b)) < 0)

@@ -190,5 +123,7 @@

 	else

 		backtrack(a, b);

 	znuke(zpool);

+	if(r >= 0)

+		dprintpath(a, b);

 	return r;

 }

--- a/path/bfs.c

+++ b/path/bfs.c

@@ -5,88 +5,23 @@

 #include <mouse.h>

 #include <keyboard.h>

 #include "asif.h"

+#include "graph.h"

 #include "path.h"

 typedef Vertex Point;

-typedef Node PNode;

-static PNode**	(*successorfn)(Node*);

-

 static void

 backtrack(Node *a, Node *b)

 {

 	Node *n;

-	for(n=b; n!=a; n=n->from)

+	for(n=b; n!=a; n=n->from){

+		stats.cost++;

+		stats.steps++;

 		n->from->to = n;

-}

-

-static double

-movecost(int Δx, int Δy)

-{

-	return Δx != 0 && Δy != 0 ? 1.001 : 1.0;

-}

-

-static PNode **

-successors8(Node *u)

-{

-	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 *v, **vp;

-	Point p;

-	Rectangle r;

-

-	memset(suc, 0, sizeof suc);

-	p = n2p(u);

-	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;

-		v = u + dtab[i+1] * gridwidth + dtab[i];

-		assert(v >= grid && v < grid + gridwidth * gridheight);

-		if(isblocked(v))

-			continue;

-		*vp++ = v;

 	}

-	return suc;

 }

-static PNode **

-successors4(Node *u)

-{

-	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 *v, **vp;

-	Point p;

-	Rectangle r;

-

-	memset(suc, 0, sizeof suc);

-	p = n2p(u);

-	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;

-		v = u + t[i+1] * gridwidth + t[i];

-		assert(v >= grid && v < grid + gridwidth * gridheight);

-		if(isblocked(v))

-			continue;

-		*vp++ = v;

-	}

-	return suc;

-}

-

 static int

 bfs(Node *a, Node *b)

 {

@@ -99,15 +34,18 @@

 	u = a;

 	vecpush(front, &u);

 	while(front->len > 0){

-		u = *((PNode **)vechpop(front));

+		u = *((Node **)vechpop(front));

 		if(u == b)

 			break;

+		stats.closed++;

 		u->closed = 1;

-		if((vl = successorfn(u)) == nil)

+		if((vl = expand(u)) == nil)

 			sysfatal("bfs: %r");

 		for(v=*vl++; v!=nil; v=*vl++){

+			stats.touched++;

 			if(v->open)

 				continue;

+			stats.opened++;

 			v->from = u;

 			vecpush(front, &v);

 			v->open = 1;

@@ -125,7 +63,6 @@

 {

 	assert(a != nil && b != nil && a != b);

 	clearpath();

-	successorfn = movemode == Move8 ? successors8 : successors4;

 	dprint(Logdebug, "grid::bfsfindpath: bfs from [%#p,%P] to [%#p,%P]\n",

 		a, n2p(a), b, n2p(b));

 	if(bfs(a, b) < 0){

@@ -132,5 +69,6 @@

 		dprint(Logdebug, "grid::bfsfindpath: failed to find a path\n");

 		return -1;

 	}

+	dprintpath(a, b);

 	return 0;

 }

--- a/path/dijkstra.c

+++ b/path/dijkstra.c

@@ -5,6 +5,7 @@

 #include <mouse.h>

 #include <keyboard.h>

 #include "asif.h"

+#include "graph.h"

 #include "path.h"

 /* currently uniform cost search and no reprioritizing (decrease-key operation) */

@@ -19,7 +20,6 @@

 	Pairheap *pq;

 };

-static PNode**	(*successorfn)(Node*);

 static Zpool *zpool;

 static void

@@ -48,135 +48,68 @@

 	}

 }

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

- * resolve tie-breakers in favor of closer nodes, otherwise we will

- * explore all nodes in the rectangle between the two points */

-static double

-movecost(int Δx, int Δy)

+static Node **

+successors(Node *u)

 {

-	return Δx != 0 && Δy != 0 ? 1.001 : 1.0;

-}

+	Node **vl, **vp, *n;

+	PNode *pu;

-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;

-		if((v = nv->aux) == nil){

-			v = nv->aux = zalloc(zpool);

-			v->n = nv;

+	vl = expand(u);

+	for(vp=vl; (n=*vp)!=nil; vp++)

+		if(n->aux == nil){

+			pu = n->aux = zalloc(zpool);

+			pu->n = n;

 		}

-		v->Δg = movecost(dtab[i], dtab[i+1]);

-		*vp++ = v;

-	}

-	return suc;

+	return vl;

 }

-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;

-		if((v = nv->aux) == nil){

-			v = nv->aux = zalloc(zpool);

-			v->n = nv;

-		}

-		v->Δg = movecost(t[i], t[i+1]);

-		*vp++ = v;

-	}

-	return suc;

-}

-

 static int

 dijkstra(Node *a, Node *b)

 {

 	double g, Δg;

-	PNode *u, *v, **vl;

-	Node *nu, *nv;

-	Pairheap *queue, *pn;

+	PNode *pu, *pv;

+	Node *u, *v, **vl;

+	Pairheap *queue, *pq;

 	queue = nil;

-	nu = a;

-	u = zalloc(zpool);

-	u->n = a;

-	u->pq = pushqueue(distfn(a, b), u, &queue);

-	while((pn = popqueue(&queue)) != nil){

-		u = pn->aux;

-		nu = u->n;

-		free(pn);

-		if(nu == b)

+	u = a;

+	pu = zalloc(zpool);

+	pu->n = u;

+	u->aux = pu;

+	pu->pq = pushqueue(distfn(a, b), pu, &queue);

+	while((pq = popqueue(&queue)) != nil){

+		pu = pq->aux;

+		u = pu->n;

+		free(pq);

+		if(u == b)

 			break;

-		nu->closed = 1;

+		u->closed = 1;

 		stats.closed++;

 		dprint(Logtrace, "dijkstra: closed [%#p,%P] g %.4f\n",

-			u, n2p(nu), u->g);

-		if((vl = successorfn(nu)) == nil)

+			u, n2p(u), pu->g);

+		if((vl = successors(u)) == nil)

 			sysfatal("a∗: %r");

 		for(v=*vl++; v!=nil; v=*vl++){

-			nv = v->n;

+			pv = v->aux;

 			stats.touched++;

-			if(nv->closed)

+			if(v->closed)

 				continue;

-			g = u->g + v->Δg;

-			Δg = v->g - g;

+			g = pu->g + unitmovecost(u, v);

+			Δg = pv->g - g;

 			assert(floor(Δg) <= 0.0);

-			if(!nv->open){

-				nv->from = nu;

-				nv->open = 1;

+			if(!v->open){

+				v->from = u;

+				v->open = 1;

 				stats.opened++;

-				v->g = g;

+				pv->g = g;

 				dprint(Logtrace, "dijkstra: opened [%#p,%P] g %.4f\n",

-					v, n2p(nv), v->g);

-				v->pq = pushqueue(v->g, v, &queue);

+					v, n2p(v), pv->g);

+				pv->pq = pushqueue(pv->g, pv, &queue);

 			}

 		}

 	}

-	cleanup(&queue);

-	if(nu != b)

+	nukequeue(&queue);

+	if(u != b)

 		return -1;

 	backtrack(a, b);

 	return 0;

@@ -189,7 +122,6 @@

 	clearpath();

 	if(zpool == nil)

 		zpool = znew(sizeof(PNode));

-	successorfn = movemode == Move8 ? successors8 : successors4;

 	dprint(Logdebug, "grid::dijkstrafindpath: dijkstra from [%#p,%P] to [%#p,%P]\n",

 		a, n2p(a), b, n2p(b));

 	if(dijkstra(a, b) < 0){

@@ -196,5 +128,6 @@

 		dprint(Logdebug, "grid::dijkstrafindpath: failed to find a path\n");

 		return -1;

 	}

+	dprintpath(a, b);

 	return 0;

 }

--- a/path/grid.c

+++ b/path/grid.c

@@ -1,6 +1,7 @@

 #include <u.h>

 #include <libc.h>

 #include "asif.h"

+#include "graph.h"

 #include "path.h"

 Node *grid;

@@ -46,10 +47,117 @@

 	n->blocked ^= 1;

 }

+/* 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

+ * resolve tie-breakers in favor of closer nodes, otherwise we will

+ * explore all nodes in the rectangle between the two points */

+double

+unitmovecost(Node *a, Node *b)

+{

+	Vertex Δ;

+

+	Δ = ΔV(*b, *a);

+	return Δ.x != 0 && Δ.y != 0 ? 1.001 : 1.0;

+}

+

 int

 isblocked(Node *n)

 {

+	if(n < grid || n >= grid + gridwidth * gridheight){

+		fprint(2, "isblocked: access beyond borders at %N\n", n);

+		return 1;

+	}

 	return n->blocked;

+}

+

+Node **

+expand4(Node *u)

+{

+	static Node *neigh[4+1];

+	static Vertex dtab[]={

+		{1,0}, {-1,0}, {0,-1}, {0,1},

+	}, rdtab[nelem(dtab)]={

+		{0,1}, {0,-1}, {-1,0}, {1,0},

+	};

+	int i;

+	Node *v, **vl;

+	Vertex p, p´, *dir;

+	Vectangle r;

+

+	memset(neigh, 0, sizeof neigh);

+	p = n2p(u);

+	r = V²(0, 0, gridwidth, gridheight);

+	/* simple path straightening, cf.:

+	 * https://www.redblobgames.com/pathfinding/a-star/implementation.html */

+	dir = (p.x + p.y) % 2 == 0 ? rdtab : dtab;

+	for(i=0, vl=neigh; i<nelem(dtab); i++){

+		p´ = ∑V(p, dir[i]);

+		if(!V∩V²(p´, r))

+			continue;

+		v = u + p´.y * gridwidth + p´.x;

+		assert(v >= grid && v < grid + gridwidth * gridheight);

+		if(!isblocked(v))

+			*vl++ = v;

+	}

+	return neigh;

+}

+

+Node **

+expand8(Node *u)

+{

+	static Node *neigh[8+1];

+	/* same as for expand4, order tweaked for nicer paths */

+	static Vertex dir[] = {

+		{1,0}, {0,-1}, {-1,0}, {0,1},

+		{-1,-1}, {-1,1}, {1,-1}, {1,1},

+	};

+	static dmask[] = {

+		θ→, θ↑, θ←, θ↓,

+		θ← | θ↑, θ← | θ↓, θ→ | θ↑, θ→ | θ↓

+	};

+	int i, open;

+	Node *v, **vl;

+	Vertex p, p´;

+	Vectangle r;

+

+	assert(u >= grid && u < grid + gridwidth * gridheight);

+	memset(neigh, 0, sizeof neigh);

+	p = n2p(u);

+	r = V²(0, 0, gridwidth, gridheight);

+	for(i=0, vl=neigh, open=0; i<nelem(dir); i++){

+		p´ = ∑V(p, dir[i]);

+		if(!V∩V²(p´, r)){

+			open |= dmask[i];

+			continue;

+		}

+		v = grid + p´.y * gridwidth + p´.x;

+		/* forbid corner cutting */

+		if(isblocked(v) || (open & dmask[i]) != 0){

+			open |= dmask[i];

+			continue;

+		}

+		*vl++ = v;

+	}

+	return neigh;

+}

+

+Node **

+expand(Node *n)

+{

+	return movemode == Move8 ? expand8(n) : expand4(n);

+}

+

+void

+dprintpath(Node *n, Node *goal)

+{

+	if(debuglevel < Logtrace)

+		return;

+	dprint(Logtrace, "path: ");

+	while(n != goal){

+		dprint(Logtrace, "%N ", n);

+		n = n->to;

+	}

 }

 void

--- a/path/path.h

+++ b/path/path.h

@@ -1,13 +1,8 @@

 typedef struct State State;

 typedef struct PState PState;

 typedef struct Node Node;

-typedef struct Vertex Vertex;

 typedef struct Prof Prof;

-struct Vertex{

-	int x;

-	int y;

-};

 struct PState{

 	int open;

 	int closed;

@@ -45,12 +40,27 @@

 };

 extern int movemode;

+enum{

+	θ∅ = 0,

+	θ→ = 1<<0,

+	θ↘ = 1<<1,

+	θ↓ = 1<<2,

+	θ↙ = 1<<3,

+	θ← = 1<<4,

+	θ↖ = 1<<5,

+	θ↑ = 1<<6,

+	θ↗ = 1<<7,

+};

+

 extern Node *grid;

 extern int gridwidth, gridheight;

+void	dprintpath(Node*, Node*);

 void	clearpath(void);

 void	cleargrid(void);

 Node*	initgrid(int, int);

+double	unitmovecost(Node*, Node*);

+Node**	expand(Node*);

 int	a∗findpath(Node*, Node*);

 int	bfsfindpath(Node*, Node*);