shithub: asif

Download patch

ref: 8e0e384527daa1b1b4ef59b5413d074617a62dd4
parent: 71250575dc797b28a5e9a9e8fd612c1253be9bc1
author: qwx <qwx@sciops.net>
date: Wed Mar 23 18:31:17 EDT 2022 

add 4-directional pathfinding functions


--- a/path/a∗.c
+++ b/path/a∗.c
@@ -21,7 +21,7 @@
 }
 
 static Node **
-successors(Node *n)
+successors8(Node *n)
 {
 	static Node *suc[8+1];
 	static dtab[2*(nelem(suc)-1)]={
@@ -44,11 +44,40 @@
 		assert(s >= map && s < map + mapwidth * mapheight);
 		if(isblocked(s))
 			continue;
+		s->Δg = 1;
 		*np++ = s;
 	}
 	return suc;
 }
 
+static Node **
+successors4(Node *n)
+{
+	static Node *suc[4+1];
+	static dtab[2*(nelem(suc)-1)]={
+		0,-1, -1,0, 1,0, 0,1,
+	};
+	int i;
+	Node *s, **np;
+	Point p;
+	Rectangle r;
+
+	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 = 1;
+		*np++ = s;
+	}
+	return suc;
+}
+
 static Node *
 a∗(Node *a, Node *b)
 {
@@ -67,13 +96,13 @@
 		if(x == b)
 			break;
 		x->closed = 1;
-		if((sl = successors(x)) == nil)
+		if((sl = successors8(x)) == nil)
 			sysfatal("a∗: %r");
 		for(s=*sl++; s!=nil; s=*sl++){
 			if(s->closed)
 				continue;
 			assert(!isblocked(s));
-			g = x->g + 1;
+			g = x->g + s->Δg;
 			Δg = s->g - g;
 			if(!s->open){
 				s->from = x;
--- a/path/dijkstra.c
+++ b/path/dijkstra.c
@@ -21,7 +21,7 @@
 }
 
 static Node **
-successors(Node *n)
+successors8(Node *n)
 {
 	static Node *suc[8+1];
 	static dtab[2*(nelem(suc)-1)]={
@@ -50,6 +50,34 @@
 	return suc;
 }
 
+static Node **
+successors4(Node *n)
+{
+	static Node *suc[4+1];
+	static dtab[2*(nelem(suc)-1)]={
+		0,-1, -1,0, 1,0, 0,1,
+	};
+	int i;
+	Node *s, **np;
+	Point p;
+	Rectangle r;
+
+	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 = 1;
+		*np++ = s;
+	}
+	return suc;
+}
+
 static Node *
 dijkstra(Node *a, Node *b)
 {
@@ -68,7 +96,7 @@
 		if(x == b)
 			break;
 		x->closed = 1;
-		if((sl = successors(x)) == nil)
+		if((sl = successors8(x)) == nil)
 			sysfatal("a∗: %r");
 		for(s=*sl++; s!=nil; s=*sl++){
 			if(s->closed)
--- a/path/fns.h
+++ b/path/fns.h
@@ -8,6 +8,7 @@
 void	resetdrw(void);
 double	eucdist(Node*, Node*);
 double	octdist(Node*, Node*);
+double	manhdist(Node*, Node*);
 Vertex	n2p(Node*);
 Node*	p2n(Vertex);
 int	isblocked(Node*);
--- a/path/map.c
+++ b/path/map.c
@@ -45,6 +45,19 @@
 	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)
 {