ref: 5256da0634295bcdb48c1da4ece5bddd4f75166d
parent: 20e31bc8a9ae12ad832ea079ffb9f2c7121966ad
author: qwx <qwx@sciops.net>
date: Wed Jul 6 01:53:36 EDT 2022
bfs: make amenable to drop in i hate this, it's tons of duplication and obscures the algo
--- a/path/bfs.c
+++ b/path/bfs.c
@@ -4,44 +4,126 @@
#include <draw.h>
#include <mouse.h>
#include <keyboard.h>
-#include "../asif.h"
-#include "dat.h"
-#include "fns.h"
+#include "asif.h"
+#include "path.h"
-static Node *
+typedef Vertex Point;
+
+typedef Node PNode;
+static PNode** (*successorfn)(Node*);
+
+static void
+cleanup(void)
+{+}
+
+static double
+movecost(int Δx, int Δy)
+{+ return Δx != 0 && Δy != 0 ? 1.001 : 1.0;
+}
+
+static PNode **
+successors8(Node *u)
+{+ static PNode *suc[8+1];
+ static dtab[2*(nelem(suc)-1)]={+ 1,0, 0,-1, -1,0, 0,1,
+ -1,-1, -1,1, 1,-1, 1,1,
+ };
+ int i;
+ Node *v, **vp;
+ Point p;
+ Rectangle r;
+
+ memset(suc, 0, sizeof suc);
+ p = n2p(u);
+ r = Rect(0, 0, gridwidth, gridheight);
+ for(i=0, vp=suc; i<nelem(dtab); i+=2){+ if(!ptinrect(addpt(p, Pt(dtab[i], dtab[i+1])), r))
+ continue;
+ v = u + dtab[i+1] * gridwidth + dtab[i];
+ assert(v >= grid && v < grid + gridwidth * gridheight);
+ if(isblocked(v))
+ continue;
+ *vp++ = v;
+ }
+ return suc;
+}
+
+static PNode **
+successors4(Node *u)
+{+ static Node *suc[4+1];
+ static int dtab[2*(nelem(suc)-1)]={+ 1,0, -1,0, 0,-1, 0,1,
+ }, rdtab[nelem(dtab)]={+ 0,1, 0,-1, -1,0, 1,0,
+ };
+ int i, *t;
+ Node *v, **vp;
+ Point p;
+ Rectangle r;
+
+ memset(suc, 0, sizeof suc);
+ p = n2p(u);
+ r = Rect(0, 0, gridwidth, gridheight);
+ /* path straightening; cf.:
+ * https://www.redbloblgames.com/pathfinding/a-star/implementation.html */
+ t = (p.x + p.y) % 2 == 0 ? rdtab : dtab;
+ for(i=0, vp=suc; i<nelem(dtab); i+=2){+ if(!ptinrect(addpt(p, Pt(t[i], t[i+1])), r))
+ continue;
+ v = u + t[i+1] * gridwidth + t[i];
+ assert(v >= grid && v < grid + gridwidth * gridheight);
+ if(isblocked(v))
+ continue;
+ *vp++ = v;
+ }
+ return suc;
+}
+
+static int
bfs(Node *a, Node *b)
{- Vector *v;
- Node *x, *s, **sl;
+ Vector *front;
+ Node *u, *v, **vl;
assert(a != nil && b != nil);
assert(a != b);
- v = vec(sizeof a);
- x = a;
- vecpush(v, &x);
- while(v->len > 0){- x = *((Node **)vechpop(v));
- if(x == b)
+ front = vec(sizeof u);
+ u = a;
+ vecpush(front, &u);
+ while(front->len > 0){+ u = *((PNode **)vechpop(front));
+ if(u == b)
break;
- x->closed = 1;
- if((sl = successorfn(x)) == nil)
+ u->closed = 1;
+ if((vl = successorfn(u)) == nil)
sysfatal("bfs: %r");- for(s=*sl++; s!=nil; s=*sl++){- if(s->open)
+ for(v=*vl++; v!=nil; v=*vl++){+ if(v->open)
continue;
- s->from = x;
- vecpush(v, &s);
- s->open = 1;
+ v->from = u;
+ vecpush(front, &v);
+ v->open = 1;
}
}
- vecfree(v);
- return x;
+ vecfree(front);
+ return 0;
}
-void
-threadmain(int argc, char **argv)
+int
+bfsfindpath(Node *a, Node *b)
{- init(argc, argv);
- initgrid(bfs, nil);
- evloop();
+ assert(a != nil && b != nil && a != b);
+ clearpath();
+ successorfn = movemode == Move8 ? successors8 : successors4;
+ dprint(Logdebug, "grid::bfsfindpath: bfs from [%#p,%P] to [%#p,%P]\n",
+ a, n2p(a), b, n2p(b));
+ if(bfs(a, b) < 0){+ dprint(Logdebug, "grid::bfsfindpath: failed to find a path\n");
+ return -1;
+ }
+ return 0;
}