shithub: asif

Download patch

ref: 13a7d1ca0b2e2fe5fae116d92e475ff0bfad6a9a
parent: 8e0e384527daa1b1b4ef59b5413d074617a62dd4
author: qwx <qwx@sciops.net>
date: Wed Mar 23 18:40:53 EDT 2022 

option for 4-directional pathfinding


--- a/path/a∗.c
+++ b/path/a∗.c
@@ -10,6 +10,9 @@
 
 Node *start, *goal;
 
+static double	(*distfn)(Node*, Node*);
+static Node**	(*successorfn)(Node*);
+
 static void
 backtrack(void)
 {
@@ -89,7 +92,7 @@
 	assert(a != b);
 	queue = nil;
 	x = a;
-	a->pq = pushqueue(octdist(a, b), a, &queue);
+	a->pq = pushqueue(distfn(a, b), a, &queue);
 	while((pn = popqueue(&queue)) != nil){
 		x = pn->aux;
 		free(pn);
@@ -96,7 +99,7 @@
 		if(x == b)
 			break;
 		x->closed = 1;
-		if((sl = successors8(x)) == nil)
+		if((sl = successorfn(x)) == nil)
 			sysfatal("a∗: %r");
 		for(s=*sl++; s!=nil; s=*sl++){
 			if(s->closed)
@@ -107,7 +110,7 @@
 			if(!s->open){
 				s->from = x;
 				s->open = 1;
-				s->h = octdist(s, b);
+				s->h = distfn(s, b);
 				s->g = g;
 				s->pq = pushqueue(s->g + s->h, s, &queue);
 			}else if(Δg > 0){
@@ -155,5 +158,12 @@
 threadmain(int argc, char **argv)
 {
 	init(argc, argv);
+	if(fourdir){
+		distfn = manhdist;
+		successorfn = successors4;
+	}else{
+		distfn = octdist;
+		successorfn = successors8;
+	}
 	evloop();
 }
--- a/path/client.c
+++ b/path/client.c
@@ -68,7 +68,7 @@
 static void
 usage(void)
 {
-	fprint(2, "usage: %s [-s width[,height]]\n", argv0);
+	fprint(2, "usage: %s [-4] [-s width[,height]]\n", argv0);
 	threadexits("usage");
 }
 
@@ -80,6 +80,9 @@
 	mapwidth = 64;
 	mapheight = 64;
 	ARGBEGIN{
+	case '4':
+		fourdir = 1;
+		break;
 	case 's':
 		mapwidth = strtol(EARGF(usage()), &s, 0);
 		if(mapwidth <= 0)
--- a/path/dat.h
+++ b/path/dat.h
@@ -24,3 +24,4 @@
 extern int mapwidth, mapheight;
 extern Node *selected;
 extern Node *start, *goal;
+extern int fourdir;
--- a/path/dijkstra.c
+++ b/path/dijkstra.c
@@ -10,6 +10,8 @@
 
 Node *start, *goal;
 
+static Node**	(*successorfn)(Node*);
+
 static void
 backtrack(void)
 {
@@ -96,7 +98,7 @@
 		if(x == b)
 			break;
 		x->closed = 1;
-		if((sl = successors8(x)) == nil)
+		if((sl = successorfn(x)) == nil)
 			sysfatal("a∗: %r");
 		for(s=*sl++; s!=nil; s=*sl++){
 			if(s->closed)
@@ -154,5 +156,9 @@
 threadmain(int argc, char **argv)
 {
 	init(argc, argv);
+	if(fourdir)
+		successorfn = successors4;
+	else
+		successorfn = successors8;
 	evloop();
 }
--- a/path/map.c
+++ b/path/map.c
@@ -6,6 +6,7 @@
 
 Node *map;
 int mapwidth, mapheight;
+int fourdir;
 
 Vertex
 n2p(Node *n)