shithub: asif

Info  •  Files  •  Log  •  Branches

path: gather common grid-based code

--- a/path/a∗.c

+++ b/path/a∗.c

@@ -8,79 +8,6 @@

 #include "dat.h"

 #include "fns.h"

-Node *start, *goal;

-

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

-static Node**	(*successorfn)(Node*);

-

-static void

-backtrack(void)

-{

-	Node *n;

-

-	assert(goal != start);

-	for(n=goal; n!=start; n=n->from)

-		n->from->to = n;

-}

-

-static Node **

-successors8(Node *n)

-{

-	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,

-	};

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

-		//s->Δg = dtab[i] != 0 && dtab[i+1] != 0 ? SQRT2 : 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)

 {

@@ -125,47 +52,10 @@

 	return x;

 }

-static int

-findpath(void)

-{

-	if(start == nil || goal == nil)

-		return -1;

-	resetmap();

-	if(a∗(start, goal) != goal)

-		return -1;

-	backtrack();

-	return 0;

-}

-

-int

-mouseinput(Node *n, Mouse m, Node *old)

-{

-	switch(m.buttons & 7){

-	case 1: if(goal != n && !n->blocked) start = n; break;

-	case 2: if(start != n && !n->blocked) goal = n; break;

-	case 4: if(old == nil || n->blocked ^ old->blocked) n->blocked ^= 1; return 0;

-	}

-	if(start != nil && goal != nil)

-		return findpath();

-	return 0;

-}

-

-int

-keyinput(Rune)

-{

-	return 0;

-}

-

 void

 threadmain(int argc, char **argv)

 {

 	init(argc, argv);

-	if(fourdir){

-		distfn = manhdist;

-		successorfn = successors4;

-	}else{

-		distfn = octdist;

-		successorfn = successors8;

-	}

+	initgrid(a∗);

 	evloop();

 }

--- a/path/bfs.c

+++ b/path/bfs.c

@@ -8,87 +8,6 @@

 #include "dat.h"

 #include "fns.h"

-Node *start, *goal;

-

-static Node**	(*successorfn)(Node*);

-

-static void

-backtrack(void)

-{

-	Node *n;

-

-	assert(goal != start);

-	for(n=goal; n!=start; n=n->from)

-		n->from->to = n;

-}

-

-static Node **

-successors8(Node *n)

-{

-	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,

-	};

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

-		*np++ = s;

-	}

-	return suc;

-}

-

-static Node **

-successors4(Node *n)

-{

-	static Node *suc[4+1];

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

-		1,0, -1,0, 0,-1, 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);

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

-		s = n + dtab[i+1] * mapwidth + dtab[i];

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

-		if(isblocked(s))

-			continue;

-		*np++ = s;

-	}

-	}

-	return suc;

-}

-

 static Node *

 bfs(Node *a, Node *b)

 {

@@ -119,48 +38,10 @@

 	return x;

 }

-static int

-findpath(void)

-{

-	if(start == nil || goal == nil){

-		werrstr("findpath: start and/or goal undefined");

-		return -1;

-	}

-	resetmap();

-	if(bfs(start, goal) != goal){

-		werrstr("findpath: failed");

-		return -1;

-	}

-	backtrack();

-	return 0;

-}

-

-int

-mouseinput(Node *n, Mouse m, Node *old)

-{

-	switch(m.buttons & 7){

-	case 1: if(goal != n && !n->blocked) start = n; break;

-	case 2: if(start != n && !n->blocked) goal = n; break;

-	case 4: if(old == nil || n->blocked ^ old->blocked) n->blocked ^= 1; return 0;

-	}

-	if(start != nil && goal != nil)

-		return findpath();

-	return 0;

-}

-

-int

-keyinput(Rune)

-{

-	return 0;

-}

-

 void

 threadmain(int argc, char **argv)

 {

 	init(argc, argv);

-	if(fourdir)

-		successorfn = successors4;

-	else

-		successorfn = successors8;

+	initgrid(bfs);

 	evloop();

 }

--- a/path/client.c

+++ b/path/client.c

@@ -10,11 +10,12 @@

 #include "fns.h"

 extern QLock drawlock;

-int	mouseinput(Node*, Mouse, Node*);

-int	keyinput(Rune);

 Node*	scrselect(Point);

 void	updatedrw(void);

+int	(*mousefn)(Node*, Mouse, Node*);

+int	(*keyfn)(Rune);

+

 static Keyboardctl *kc;

 static Mousectl *mc;

@@ -51,7 +52,7 @@

 				break;

 			}

 			if((n = scrselect(m.xy)) != nil && p != n){

-				if(mouseinput(n, mc->Mouse, p) < 0)

+				if(mousefn(n, mc->Mouse, p) < 0)

 					fprint(2, "%r\n");

 				p = n;

 			}

@@ -62,7 +63,7 @@

 			case Kdel: threadexitsall(nil);

 			case 'r': clearmap(); updatedrw(); break;

 			}

-			keyinput(r);

+			keyfn(r);

 			break;

 		}

 		m = mc->Mouse;

--- a/path/dat.h

+++ b/path/dat.h

@@ -28,3 +28,7 @@

 extern Node *selected;

 extern Node *start, *goal;

 extern int fourdir;

+

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

+extern Node**	(*successorfn)(Node*);

+extern Node*	(*pathfn)(Node*, Node*);

--- a/path/dijkstra.c

+++ b/path/dijkstra.c

@@ -8,77 +8,6 @@

 #include "dat.h"

 #include "fns.h"

-Node *start, *goal;

-

-static Node**	(*successorfn)(Node*);

-

-static void

-backtrack(void)

-{

-	Node *n;

-

-	assert(goal != start);

-	for(n=goal; n!=start; n=n->from)

-		n->from->to = n;

-}

-

-static Node **

-successors8(Node *n)

-{

-	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,

-	};

-	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 = dtab[i] != 0 && dtab[i+1] != 0 ? SQRT2 : 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 *

 dijkstra(Node *a, Node *b)

 {

@@ -122,44 +51,10 @@

 	return x;

 }

-static int

-findpath(void)

-{

-	if(start == nil || goal == nil)

-		return -1;

-	resetmap();

-	if(dijkstra(start, goal) != goal)

-		return -1;

-	backtrack();

-	return 0;

-}

-

-int

-mouseinput(Node *n, Mouse m, Node *old)

-{

-	switch(m.buttons & 7){

-	case 1: if(goal != n && !n->blocked) start = n; break;

-	case 2: if(start != n && !n->blocked) goal = n; break;

-	case 4: if(old == nil || n->blocked ^ old->blocked) n->blocked ^= 1; return 0;

-	}

-	if(start != nil && goal != nil)

-		return findpath();

-	return 0;

-}

-

-int

-keyinput(Rune)

-{

-	return 0;

-}

-

 void

 threadmain(int argc, char **argv)

 {

 	init(argc, argv);

-	if(fourdir)

-		successorfn = successors4;

-	else

-		successorfn = successors8;

+	initgrid(dijkstra);

 	evloop();

 }

--- a/path/fns.h

+++ b/path/fns.h

@@ -1,6 +1,7 @@

 void	init(int, char**);

 void	evloop(void);

 void	initfs(void);

+void	initgrid(Node* (*)(Node*, Node*));

 void	resetmap(void);

 void	clearmap(void);

 void	initmap(void);

--- /dev/null

+++ b/path/grid.c

@@ -1,0 +1,136 @@

+#include <u.h>

+#include <libc.h>

+#include <thread.h>

+#include <draw.h>

+#include <mouse.h>

+#include <keyboard.h>

+#include "../asif.h"

+#include "dat.h"

+#include "fns.h"

+

+extern int	(*mousefn)(Node*, Mouse, Node*);

+extern int	(*keyfn)(Rune);

+

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

+Node**	(*successorfn)(Node*);

+Node*	(*pathfn)(Node*, Node*);

+

+Node *start, *goal;

+

+static void

+backtrack(void)

+{

+	Node *n;

+

+	assert(goal != start);

+	for(n=goal; n!=start; n=n->from)

+		n->from->to = n;

+}

+

+static Node **

+successors8(Node *n)

+{

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

+	};

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

+		//s->Δg = dtab[i] != 0 && dtab[i+1] != 0 ? SQRT2 : 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 int

+findpath(void)

+{

+	if(start == nil || goal == nil){

+		werrstr("findpath: start and goal not undefined");

+		return -1;

+	}

+	resetmap();

+	if(pathfn(start, goal) != goal){

+		werrstr("findpath: failed");

+		return -1;

+	}

+	backtrack();

+	return 0;

+}

+

+static int

+grmouse(Node *n, Mouse m, Node *old)

+{

+	switch(m.buttons & 7){

+	case 1: if(goal != n && !n->blocked) start = n; break;

+	case 2: if(start != n && !n->blocked) goal = n; break;

+	case 4: if(old == nil || n->blocked ^ old->blocked) n->blocked ^= 1; return 0;

+	}

+	if(start != nil && goal != nil)

+		return findpath();

+	return 0;

+}

+

+static int

+grkey(Rune)

+{

+	return 0;

+}

+

+void

+initgrid(Node* (*f)(Node*, Node*))

+{

+	if(fourdir){

+		distfn = manhdist;

+		successorfn = successors4;

+	}else{

+		distfn = octdist;

+		successorfn = successors8;

+	}

+	mousefn = grmouse;

+	keyfn = grkey;

+	pathfn = f;

+}

--- a/path/map.c

+++ b/path/map.c

@@ -4,6 +4,8 @@

 #include "dat.h"

 #include "fns.h"

+Node *start, *goal;

+

 Node *map;

 int mapwidth, mapheight;

 int fourdir;

--- a/path/mkfile

+++ b/path/mkfile

@@ -11,6 +11,7 @@

 	client.$O\

 	drw.$O\

 	fs.$O\

+	grid.$O\

 	map.$O\

 </sys/src/cmd/mkmany