shithub: asif

Info  •  Files  •  Log  •  Branches

bfs: better paths

https://www.redblobgames.com/pathfinding/a-star/implementation.html#troubleshooting-ugly-path

the order of returned successors is significant and determines the overall shape of the final path; this is different for every type of movement and graph...

currently just an ugly hack until the rest is fixed

--- a/path/bfs.c

+++ b/path/bfs.c

@@ -27,8 +27,8 @@

 {

 	static Node *suc[8+1];

 	static dtab[2*(nelem(suc)-1)]={

-		0,-1, 1,0, 0,1, -1,0,

-		1,-1, 1,1, -1,1, -1,-1,

+		0,-1, -1,0, 0,1, 1,0,

+		-1,-1, -1,1, 1,1, 1,-1,

 	};

 	int i;

 	Node *s, **np;

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

 		assert(s >= map && s < map + mapwidth * mapheight);

 		if(isblocked(s))

 			continue;

-		s->Δg = dtab[i] != 0 && dtab[i+1] != 0 ? SQRT2 : 1;

 		*np++ = s;

 	}

 	return suc;

@@ -56,7 +55,7 @@

 {

 	static Node *suc[4+1];

 	static dtab[2*(nelem(suc)-1)]={

-		0,-1, -1,0, 1,0, 0,1,

+		1,0, -1,0, 0,-1, 0,1

 	};

 	int i;

 	Node *s, **np;

@@ -66,6 +65,17 @@

 	memset(suc, 0, sizeof suc);

 	p = n2p(n);

 	r = Rect(0, 0, mapwidth, mapheight);

+	if((p.x + p.y & 1) == 0){

+	for(i=2*(nelem(suc)-1)-2, np=suc; i>=0; 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;

+		*np++ = s;

+	}

+	}else{

 	for(i=0, np=suc; i<nelem(dtab); i+=2){

 		if(!ptinrect(addpt(p, Pt(dtab[i], dtab[i+1])), r))

 			continue;

@@ -73,8 +83,8 @@

 		assert(s >= map && s < map + mapwidth * mapheight);

 		if(isblocked(s))

 			continue;

-		s->Δg = 1;

 		*np++ = s;

+	}

 	}

 	return suc;

 }