shithub: asif

Info  •  Files  •  Log

path, a∗: add profiling code, fixes

- nodes now keep track of pnodes to reuse them (bespoke hash table?)
- proper clean up in a∗, avoid leaks

--- a/path/a∗.c

+++ b/path/a∗.c

@@ -19,25 +19,20 @@

 static Zpool *zpool;

 static void

-cleanup(Pairheap **queue)

+backtrack(Node *a, Node *b)

 {

-	Pairheap *p;

+	Node *u, *v;

+	PNode *p;

-	while((p = popqueue(queue)) != nil){

-		zfree(p->aux);

-		free(p);

+	for(u=b; u!=a; u=v){

+		p = u->aux;

+		stats.cost += p->g;

+		stats.steps++;

+		v = u->from;

+		v->to = u;

 	}

 }

-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

@@ -73,8 +68,10 @@

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

 		if(isblocked(nv))

 			continue;

-		v = zalloc(zpool);

-		v->n = nv;

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

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

+			v->n = nv;

+		}

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

 		*vp++ = v;

 	}

@@ -109,8 +106,10 @@

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

 		if(isblocked(nv))

 			continue;

-		v = zalloc(zpool);

-		v->n = nv;

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

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

+			v->n = nv;

+		}

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

 		*vp++ = v;

 	}

@@ -126,9 +125,8 @@

 	Pairheap *queue, *pn;

 	queue = nil;

-	nu = a;

-	u = zalloc(zpool);

-	u->n = a;

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

@@ -137,6 +135,7 @@

 		if(nu == b)

 			break;

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

@@ -143,6 +142,7 @@

 			sysfatal("a∗: %r");

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

 			nv = v->n;

+			stats.touched++;

 			if(nv->closed)

 				continue;

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

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

 			if(!nv->open){

 				nv->from = nu;

 				nv->open = 1;

+				stats.opened++;

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

 				v->g = g;

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

@@ -156,6 +157,7 @@

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

 				v->pq = pushqueue(v->g + v->h, v, &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;

@@ -165,10 +167,9 @@

 			}

 		}

 	}

-	cleanup(&queue);

+	nukequeue(&queue);

 	if(nu != b)

 		return -1;

-	backtrack(a, b);

 	return 0;

 }

@@ -175,6 +176,8 @@

 int

 a∗findpath(Node *a, Node *b)

 {

+	int r;

+

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

 	clearpath();

 	if(zpool == nil)

@@ -182,9 +185,10 @@

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

+	if((r = a∗(a, b)) < 0)

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

-		return -1;

-	}

-	return 0;

+	else

+		backtrack(a, b);

+	znuke(zpool);

+	return r;

 }

--- a/path/grid.c

+++ b/path/grid.c

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

 int gridwidth, gridheight;

 double	(*distfn)(Node*, Node*);

+int doprof;

+Prof stats;

+

 double

 eucdist(Node *a, Node *b)

 {

@@ -58,6 +61,7 @@

 		return;

 	for(n=grid; n<grid+gridwidth*gridheight; n++)

 		memset(&n->PState, 0, sizeof n->PState);

+	memset(&stats, 0, sizeof stats);

 }

 void

@@ -81,6 +85,26 @@

 n2p(Node *n)

 {

 	return (Vertex){(n - grid) % gridwidth, (n - grid) / gridheight};

+}

+

+int

+Vfmt(Fmt *f)

+{

+	Vertex v;

+

+	v = va_arg(f->args, Vertex);

+	return fmtprint(f, "[%d %d]", v.x, v.y);

+}

+

+int

+Nfmt(Fmt *f)

+{

+	Node *n;

+	Vertex v;

+

+	n = va_arg(f->args, Node*);

+	v = n2p(n);

+	return fmtprint(f, "[%#p %V]", n, v);

 }

 Node *

--- a/path/path.h

+++ b/path/path.h

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

 typedef struct PState PState;

 typedef struct Node Node;

 typedef struct Vertex Vertex;

+typedef struct Prof Prof;

 struct Vertex{

 	int x;

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

 	int closed;

 	Node *from;

 	Node *to;

+	void *aux;

 };

 struct State{

 	int blocked;

@@ -53,3 +55,18 @@

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

 int	bfsfindpath(Node*, Node*);

 int	dijkstrafindpath(Node*, Node*);

+

+struct Prof{

+	double dist;

+	double cost;

+	int steps;

+	int touched;

+	int opened;

+	int updated;

+	int closed;

+};

+extern Prof stats;

+extern int doprof;

+

+#pragma	varargck	type	"N"	Node*

+#pragma	varargck	type	"V"	Vertex