shithub: asif

Info  •  Files  •  Log

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)