shithub: sce

Download patch

ref: abe39da4407afac58b57173b8322936051c7bfa5
parent: 94e08d831823da42d1700faf4145dd795e0daff5
author: qwx <qwx@sciops.net>
date: Mon Aug 10 18:16:17 EDT 2020 

reimplement pathfinding and movement

- sce.db: count unit size in path nodes (8px)
- fs: bind() can now return negative non-error values
- fs: separate terrain and map into separate grids for drawing
- drw: path visualization (debugmap)
- drw: add visible unit bitmap for selection the size of the screen
- drw: bound drawing to visible area, separate layers
- drw: draw fixes, some legibility improvements
- map: spawn units on top of spawner object, finding free spawning spot
- path: add jps(B) on top of a∗ with pairing heaps for priority queues and bitmap for map
- path: disallow moving unit on top of itself
- path: attempt movement towards target if inaccessible, given jps limitations
- path: move pathfinding goal if target is within a block
- sim: redo tracking units on the map
- sim: redo movement increments, disallow corner coasting
- sim: rework pathfinding error conditions, restarting, aborting

pathfinding now performs very well even on largest 256x256 map,
but has several unresolved issues, listed in path.c.
the code is horrible and unreadable; many improvements can be made.
movement also needs refinement.
the worst: unit sizes are not multiples of 8px at all; the
benefits of compressing the map to 8x8 blocks now gone; other
approaches to be considered?
obviously, no multi-agent pathfinding yet.
drawing order still not right, probably have to build an ordered
list of things to draw in order.
loading all the sprites takes forever.
there's a non reproducible bug in the shitty net code which can
cause a hang on exit (or even start up?).


--- a/ai.c
+++ /dev/null
@@ -1,271 +1,0 @@
-#include <u.h>
-#include <libc.h>
-#include <draw.h>
-#include "dat.h"
-#include "fns.h"
-
-Path *path;
-int pathwidth, pathheight;
-
-typedef struct Queue Queue;
-struct Queue{
-	Path *pp;
-	Queue *q;
-	Queue *p;
-};
-static Queue q1 = {.q = &q1, .p = &q1}, *popen = &q1;
-
-int
-isblocked(Point *p, Mobj *mo)
-{
-	int x, y;
-	Path *pp, *e;
-
-	if(mo->o->f & Fair)
-		return 0;
-	pp = path + p->y * pathwidth + p->x;
-	x = mo->o->w * (Tlwidth / Tlsubwidth);
-	y = mo->o->h * (Tlheight / Tlsubheight);
-	while(y-- > 0){
-		for(e=pp+x; pp<e; pp++)
-			if(pp->blk != nil && pp->blk != mo)
-				return 1;
-		pp += pathwidth - x;
-	}
-	return 0;
-}
-
-void
-setblk(Mobj *mo, int clr)
-{
-	int x, y;
-	Path *pp, *e;
-	Lobj *lo;
-
-	pp = path + mo->y * pathwidth + mo->x;
-	x = mo->o->w * (Tlwidth / Tlsubwidth);
-	y = mo->o->h * (Tlheight / Tlsubheight);
-	lo = mo->blk;
-	if(mo->x + x > pathwidth)
-		x = pathwidth - mo->x;
-	if(mo->y + y > pathheight)
-		y = pathheight - mo->y;
-	while(y-- > 0){
-		for(e=pp+x; pp<e; pp++)
-			if(clr){
-				if(pp->blk == mo)
-					pp->blk = nil;
-				lunlink(lo++);
-			}else{
-				if((mo->o->f & Fair) == 0)
-					pp->blk = mo;
-				llink(lo++, &pp->lo);
-			}
-		pp += pathwidth - x;
-	}
-}
-
-static Path *
-poppath(Queue *r)
-{
-	Path *p;
-	Queue *q;
-
-	q = r->q;
-	if(q == r)
-		return nil;
-	p = q->pp;
-	r->q = q->q;
-	free(q);
-	return p;
-}
-
-static void
-pushpath(Queue *r, Path *pp)
-{
-	Queue *q, *qp, *p;
-
-	for(qp=r, q=qp->q; q!=r && pp->g+pp->h > q->pp->g+q->pp->h; qp=q, q=q->q)
-		;
-	p = emalloc(sizeof *p);
-	p->pp = pp;
-	p->q = q;
-	qp->q = p;
-}
-
-static void
-clearpath(void)
-{
-	Queue *p, *q;
-	Path *pp;
-
-	/* FIXME: separate table(s)? */
-	for(pp=path; pp<path+pathwidth*pathheight; pp++){
-		pp->g = 0x7fffffff;
-		pp->h = 0x7fffffff;
-		pp->from = nil;
-		pp->closed = 0;
-		pp->open = 0;
-	}
-	for(p=popen->q; p!=popen; p=q){
-		q = p->q;
-		free(p);
-	}
-	popen->p = popen->q = popen;
-}
-
-static void
-setpath(Path *e, Mobj *mo)
-{
-	int n;
-	Point *p, *pe, x, p0, p1;
-
-	/* FIXME: probably better to just replace it with a static buffer;
-	 * except for static buildings and air units, units are going to move
-	 * and use pathfinding almost always */
-	pe = emalloc(Npath * sizeof *pe);
-	mo->path = pe;
-	p = pe + Npath - 1;
-	n = 0;
-	/* FIXME: drawing: spawn needs to center unit on path node, and
-	 * drawing needs to offset sprite from path center */
-	for(; e!=nil; e=e->from){
-		x.x = ((e - path) % pathwidth) * Tlsubwidth + (Tlsubwidth >> 1);
-		x.y = ((e - path) / pathwidth) * Tlsubheight + (Tlsubheight >> 1);
-		if(n == 0){
-			x.x -= Tlsubwidth >> 1;
-			x.y -= Tlsubheight >> 1;
-			*p-- = x;
-			p0 = x;
-			n++;
-		}else if(n == 1){
-			p1 = x;
-			n++;
-		}else{
-			if(atan2(x.y - p0.y, x.x - p0.x)
-			!= atan2(p1.y - p0.y, p1.x - p0.x)){
-				if(p < pe){
-					memmove(pe+1, pe, (Npath - 1) * sizeof *pe);
-					*pe = p1;
-				}else
-					*p-- = p1;
-				p0 = p1;
-				n = 2;
-			}
-			p1 = x;
-		}
-	}
-	mo->pathp = p + 1;
-	mo->pathe = pe + Npath;
-}
-
-static double
-dist(Path *p, Path *q)
-{
-	int dx, dy;
-
-	dx = abs(p->x - q->x);
-	dy = abs(p->y - q->y);
-	return dx + dy;
-	//return 1 * (dx + dy) + (1 - 2 * 1) * (dx < dy ? dx : dy);
-	//return sqrt(dx * dx + dy * dy);
-}
-
-/* FIXME: air: ignore pathfinding? */
-static Path **
-trywalk(Path *pp, Mobj *mo)
-{
-	int x, y;
-	Point p, *d, diff[] = {
-		{1,0}, {0,-1}, {-1,0}, {0,1},
-		{1,1}, {-1,1}, {-1,-1}, {1,-1},
-	};
-	Path **lp;
-	static Path *l[nelem(diff) + 1];
-
-	x = (pp - path) % pathwidth;
-	y = (pp - path) / pathwidth;
-	for(d=diff, lp=l; d<diff+nelem(diff); d++){
-		p.x = x + d->x;
-		p.y = y + d->y;
-		if(p.x < 0 || p.x > pathwidth
-		|| p.y < 0 || p.y > pathheight)
-			continue;
-		if(!isblocked(&p, mo))
-			*lp++ = path + p.y * pathwidth + p.x;
-	}
-	*lp = nil;
-	return l;
-}
-
-static int
-a∗(Mobj *mo, Point *p2)
-{
-	double g;
-	Path *s, *pp, *e, *q, **l;
-
-	clearpath();
-	s = path + pathwidth * mo->y + mo->x;
-	e = path + pathwidth * (p2->y / Tlsubheight) + p2->x / Tlsubwidth;
-	/* FIXME: don't return an error, just an empty path, or the same
-	 * block as the source */
-	if(s == e){
-		werrstr("no.");
-		return -1;
-	}
-	s->g = 0;
-	s->h = dist(s, e);
-	pushpath(popen, s);
-	while((pp = poppath(popen)) != nil){
-		if(pp == e)
-			break;
-		pp->closed = 1;
-		pp->open = 0;
-		l = trywalk(pp, mo);
-		for(q=*l; q!=nil; q=*l++)
-			if(!q->closed){
-				g = pp->g + dist(pp, q);
-				if(!q->open){
-					q->from = pp;
-					q->g = g;
-					q->h = dist(q, e);
-					q->open = 1;
-					pushpath(popen, q);
-				}else if(g < q->g){
-					q->from = pp;
-					q->g = g;
-				}
-			}
-	}
-	/* FIXME: move towards target anyway */
-	if(e->from == nil && pp != e){
-		werrstr("NOPE");
-		return -1;
-	}
-	setpath(e, mo);
-	return 0;
-}
-
-int
-findpath(Mobj *mo, Point *p2)
-{
-	return a∗(mo, p2);
-}
-
-void
-initpath(void)
-{
-	int n, x, y;
-	Path *pp;
-
-	pathwidth = mapwidth * (Tlwidth / Tlsubwidth);
-	pathheight = mapheight * (Tlheight / Tlsubheight);
-	n = pathwidth * pathheight;
-	path = emalloc(n * sizeof *path);
-	for(y=0, pp=path; y<pathheight; y++)
-		for(x=0; x<pathwidth; x++, pp++){
-			pp->x = x;
-			pp->y = y;
-			pp->lo.lo = pp->lo.lp = &pp->lo;
-		}
-}
--- /dev/null
+++ b/bmap.c
@@ -1,0 +1,216 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.h>
+#include "dat.h"
+#include "fns.h"
+
+enum{
+	Nmaxsize = 4,
+	Npad = 1,
+};
+
+static u64int *bmap, *rbmap;
+static int bmapwidth, bmapheight, rbmapwidth, rbmapheight;
+
+static uchar ffstab[256];
+
+int
+lsb(uvlong v)
+{
+	int c;
+
+	c = 0;
+	if((v & 0xffffffff) == 0){
+		v >>= 32;
+		c += 32;
+	}
+	if((v & 0xffff) == 0){
+		v >>= 16;
+		c += 16;
+	}
+	if((v & 0xff) == 0){
+		v >>= 8;
+		c += 8;
+	}
+	if((v & 0xf) == 0){
+		v >>= 4;
+		c += 4;
+	}
+	if((v & 3) == 0){
+		v >>= 2;
+		c += 2;
+	}
+	if((v & 1) == 0)
+		c++;
+	return c;
+}
+
+int
+msb(uvlong v)
+{
+	int n;
+
+	if(n = v >> 56)
+		return 56 + ffstab[n];
+	else if(n = v >> 48)
+		return 48 + ffstab[n];
+	else if(n = v >> 40)
+		return 40 + ffstab[n];
+	else if(n = v >> 32)
+		return 32 + ffstab[n];
+	else if(n = v >> 24)
+		return 24 + ffstab[n];
+	else if(n = v >> 16)
+		return 16 + ffstab[n];
+	else if(n = v >> 8)
+		return 8 + ffstab[n];
+	else
+		return ffstab[v];
+}
+
+u64int *
+baddr(int x, int y)
+{
+	x >>= Bshift;
+	x += Npad;
+	y += Npad;
+	return bmap + y * bmapwidth + x;
+}
+
+u64int *
+rbaddr(int y, int x)
+{
+	x >>= Bshift;
+	x += Npad;
+	y += Npad;
+	return rbmap + y * rbmapwidth + x;
+}
+
+static u64int *
+breduce(u64int *p, int Δp, int ofs, int w, int h, int Δw, int Δh, int left)
+{
+	static u64int row[Nmaxsize+2];
+	int i, j;
+	u64int u, m;
+
+	m = (1 << w - 1) - 1;
+	if(left){
+		ofs = 64 - w - Δw - ofs;
+		m <<= 63 - w + 1;
+	}
+	m = ~m;
+	for(i=0; i<h+Δh; i++, p+=Δp){
+		u = p[0];
+		if(ofs > 0){
+			if(left){
+				u >>= ofs;
+				u |= p[-1] << 64 - ofs;
+			}else{
+				u <<= ofs;
+				u |= p[1] >> 64 - ofs;
+			}
+		}
+		if(left)
+			switch(w){
+			case 4: u |= u >> 1 | u >> 2 | u >> 3; break;
+			case 2: u |= u >> 1; break;
+			}
+		else
+			switch(w){
+			case 4: u |= u << 1 | u << 2 | u << 3; break;
+			case 2: u |= u << 1; break;
+			}
+		u &= m;
+		row[i] = u;
+		for(j=max(i-h+1, 0); j<i; j++)
+			row[j] |= u;
+	}
+	return row;
+}
+
+u64int *
+bload(int x, int y, int w, int h, int Δw, int Δh, int left, int rot)
+{
+	int ofs, Δp;
+	u64int *p;
+
+	if(rot){
+		p = rbaddr(x, y);
+		Δp = rbmapwidth;
+		ofs = y & Bmask;
+	}else{
+		p = baddr(x, y);
+		Δp = bmapwidth;
+		ofs = x & Bmask;
+	}
+	return breduce(p, Δp, ofs, w, h, Δw, Δh, left);
+}
+
+void
+bset(int x, int y, int w, int h, int set)
+{
+	int i, Δ, n;
+	u64int *p, m, m´;
+
+	p = baddr(x, y);
+	n = x & Bmask;
+	m = (1ULL << w) - 1 << 64 - w;
+	m >>= n;
+	Δ = n + w - 64;
+	m´ = (1ULL << Δ) - 1 << 64 - Δ;
+	for(i=0; i<h; i++, p+=bmapwidth){
+		p[0] = set ? p[0] | m : p[0] & ~m;
+		if(Δ > 0)
+			p[1] = set ? p[1] | m´ : p[1] & ~m´;
+	}
+	p = rbaddr(x, y);
+	n = y & Bmask;
+	m = (1ULL << h) - 1 << 64 - h;
+	m >>= n;
+	Δ = n + h - 64;
+	m´ = (1ULL << Δ) - 1 << 64 - Δ;
+	for(i=0; i<w; i++, p+=rbmapwidth){
+		p[0] = set ? p[0] | m : p[0] & ~m;
+		if(Δ > 0)
+			p[1] = set ? p[1] | m´ : p[1] & ~m´;
+	}
+}
+
+static void
+initffs(void)
+{
+	int i;
+
+	ffstab[0] = 0;
+	ffstab[1] = 0;
+	for(i=2; i<nelem(ffstab); i++)
+		ffstab[i] = 1 + ffstab[i/2];
+}
+
+void
+initbmap(void)
+{
+	int i;
+
+	bmapwidth = (mapwidth >> Bshift) + 2 * Npad;
+	bmapheight = mapheight + 2 * Npad;
+	rbmapwidth = (mapheight >> Bshift) + 2 * Npad;
+	rbmapheight = mapwidth + 2 * Npad;
+	bmap = emalloc(bmapwidth * bmapheight * sizeof *bmap);
+	rbmap = emalloc(rbmapwidth * rbmapheight * sizeof *rbmap);
+	for(i=0; i<Npad; i++){
+		memset(bmap + i * mapwidth, 0xff, bmapwidth * sizeof *bmap);
+		memset(bmap + (bmapheight - i - 1) * bmapwidth, 0xff,
+			bmapwidth * sizeof *bmap);
+		memset(rbmap + i * rbmapwidth, 0xff, rbmapwidth * sizeof *rbmap);
+		memset(rbmap + (rbmapheight - i - 1) * rbmapwidth, 0xff,
+			rbmapwidth * sizeof *rbmap);
+	}
+	for(i=Npad; i<bmapheight-Npad; i++){
+		memset(bmap + i * bmapwidth, 0xff, Npad * sizeof *bmap);
+		memset(bmap + (i+1) * bmapwidth - Npad, 0xff, Npad * sizeof *bmap);
+		memset(rbmap + i * rbmapwidth, 0xff, Npad * sizeof *rbmap);
+		memset(rbmap + (i+1) * rbmapwidth - Npad, 0xff, Npad * sizeof *rbmap);
+	}
+	initffs();
+}
--- a/dat.h
+++ b/dat.h
@@ -1,14 +1,16 @@
+typedef struct Node Node;
+typedef struct Pairheap Pairheap;
 typedef struct Attack Attack;
 typedef struct Pic Pic;
 typedef struct Pics Pics;
 typedef struct Obj Obj;
+typedef struct Path Path;
 typedef struct Mobj Mobj;
-typedef struct Lobj Lobj;
+typedef struct Mobjl Mobjl;
 typedef struct Terrain Terrain;
 typedef struct Map Map;
 typedef struct Resource Resource;
 typedef struct Team Team;
-typedef struct Path Path;
 
 enum{
 	Nresource = 3,
@@ -15,17 +17,44 @@
 	Nteam = 8,
 	Nselect = 12,
 	Nrot = 32,
-	Npath = 64,
 	Tlwidth = 32,
 	Tlheight = Tlwidth,
-	Tlshift = 16,
-	Tlmask = ((1 << Tlshift) - 1) << Tlshift,
 	Tlsubshift = 2,
 	Tlsubwidth = Tlwidth >> Tlsubshift,
 	Tlsubheight = Tlheight >> Tlsubshift,
-	Tlsubmask = Tlsubwidth - 1,
+	Tlnsub = Tlwidth / Tlsubwidth,
+	Subpxshift = 16,
+	Subpxmask = (1 << Subpxshift) - 1,
 };
 
+enum{
+	Bshift = 6,
+	Bmask = (1 << Bshift) - 1,
+};
+
+struct Pairheap{
+	double sum;
+	Node *n;
+	Pairheap *parent;
+	Pairheap *left;
+	Pairheap *right;
+};
+
+struct Node{
+	int x;
+	int y;
+	int closed;
+	int open;
+	double g;
+	double Δg;
+	double h;
+	int step;
+	int dir;
+	Node *from;
+	Pairheap *p;
+};
+extern Node *node;
+
 struct Attack{
 	char *name;
 	int dmg;
@@ -63,10 +92,10 @@
 	Pics pidle;
 	Pics pmove;
 	int nr;
-	Attack *atk[2];
-	int f;
 	int w;
 	int h;
+	int f;
+	Attack *atk[2];
 	int hp;
 	int def;
 	int speed;
@@ -76,47 +105,50 @@
 	Obj **spawn;
 	int nspawn;
 };
-
+struct Path{
+	Point target;
+	int goalblocked;
+	int npatherr;
+	int npathbuf;
+	Point *paths;
+	Point *pathp;
+	Point *pathe;
+};
 struct Mobj{
 	Obj *o;
 	Pics *pics;
-	Point;
-	Point p;
-	Point subp;
 	int θ;
-	double vx;
-	double vy;
-	double vv;
+	Point;
+	int px;
+	int py;
+	int subpx;
+	int subpy;
+	Path;
 	int Δθ;
-	Point *path;
-	Point *pathp;
-	Point *pathe;
+	double u;
+	double v;
+	double speed;
+	Mobjl *movingp;
+	Mobjl *mapp;
 	int f;
 	int team;
 	int hp;
 	int xp;
-	Lobj *blk;
-	Lobj *zl;
-	Lobj *vl;
 };
-
-struct Lobj{
+struct Mobjl{
 	Mobj *mo;
-	Lobj *lo;
-	Lobj *lp;
+	Mobjl *l;
+	Mobjl *lp;
 };
-extern Lobj zlist;
 
 struct Terrain{
 	Pic *p;
 };
+extern Terrain **terrain;
+extern terwidth, terheight;
 
 struct Map{
-	Point;
-	int tx;
-	int ty;
-	Terrain *t;
-	Lobj lo;
+	Mobjl ml;
 };
 extern Map *map;
 extern int mapwidth, mapheight;
@@ -135,19 +167,6 @@
 extern Team team[Nteam], *curteam;
 extern int nteam;
 
-struct Path{
-	Point;
-	Lobj lo;
-	Mobj *blk;
-	int closed;
-	int open;
-	Path *from;
-	double g;
-	double h;
-};
-extern Path *path;
-extern int pathwidth, pathheight;
-
 extern int lport;
 extern char *netmtpt;
 
@@ -160,3 +179,5 @@
 extern char *progname, *prefix, *dbname, *mapname;
 extern int clon;
 extern vlong tc;
+extern int pause, debugmap;
+extern int debug;
--- a/drw.c
+++ b/drw.c
@@ -7,25 +7,15 @@
 int scale = 1;
 Point p0, pan;
 
-static int fbsz, fbh, fbw;
-static u32int *fb, *fbe;
+static int fbsz, fbh, fbw, fbws;
+static u32int *fb, *fbvis;
 static Image *fbi;
 static Rectangle selr;
 static Point panmax;
 static Mobj *selected[Nselect];
+static Mobj **visbuf;
+static int nvisbuf, nvis;
 
-static int
-max(int a, int b)
-{
-	return a > b ? a : b;
-}
-
-static int
-min(int a, int b)
-{
-	return a < b ? a : b;
-}
-
 void
 dopan(int dx, int dy)
 {
@@ -41,38 +31,73 @@
 		pan.y = panmax.y;
 }
 
-static Mobj *
-mapselect(Point *pp)
-{
-	Path *p;
-
-	p = path + pathwidth * (pp->y / Tlsubheight) + pp->x / Tlsubwidth;
-	return p->lo.lo->mo;
-}
-
 void
 select(Point p, int b)
 {
+	int i;
+	Point vp;
+	Mobj *mo;
+
 	if(!ptinrect(p, selr))
 		return;
-	p = divpt(addpt(subpt(p, selr.min), pan), scale);
-	/* FIXME: multiple selections */
-	/* FIXME: selection map based on sprite dimensions and offset */
-	if(b & 1)
-		selected[0] = mapselect(&p);
-	else if(b & 4){
+	if(b & 1){
+		p = divpt(subpt(p, selr.min), scale);
+		i = fbvis[p.y * fbw + p.x];
+		selected[0] = i == -1 ? nil : visbuf[i];
+	}else if(b & 4){
 		if(selected[0] == nil)
 			return;
-		/* FIXME: this implements move for any unit of any team,
-		 * including buildings, but not attack or anything else */
-		/* FIXME: attack, attackobj, moveobj (follow obj), etc. */
-		/* FIXME: offset sprite size */
-		//move(p.x & ~Tlsubmask, p.y & ~Tlsubmask, selected);
-		move(p.x, p.y, selected);
+		vp = divpt(subpt(p, selr.min), scale);
+		i = fbvis[vp.y * fbw + vp.x];
+		mo = i == -1 ? nil : visbuf[i];
+		if(mo == selected[0]){
+			dprint("select: %#p not moving to itself\n", visbuf[i]);
+			return;
+		}
+		p = divpt(addpt(subpt(p, selr.min), pan), scale);
+		p.x /= Tlsubwidth;
+		p.y /= Tlsubheight;
+		moveone(p, selected[0], mo);
 	}
 }
 
+static void
+drawhud(void)
+{
+	char s[256];
+	Mobj *mo;
+
+	draw(screen, Rpt(p0, screen->r.max), display->black, nil, ZP);
+	mo = selected[0];
+	if(mo == nil)
+		return;
+	snprint(s, sizeof s, "%s %d/%d", mo->o->name, mo->hp, mo->o->hp);
+	string(screen, p0, display->white, ZP, font, s);
+}
+
 static int
+addvis(Mobj *mo)
+{
+	int i;
+
+	if((i = nvis++) >= nvisbuf){
+		visbuf = erealloc(visbuf, (nvisbuf + 16) * sizeof *visbuf,
+			nvisbuf * sizeof *visbuf);
+		nvisbuf += 16;
+	}
+	visbuf[i] = mo;
+	return i;
+}
+
+static void
+clearvis(void)
+{
+	if(visbuf != nil)
+		memset(visbuf, 0, nvisbuf * sizeof *visbuf);
+	nvis = 0;
+}
+
+static int
 boundpic(Rectangle *r, u32int **q)
 {
 	int w;
@@ -79,7 +104,7 @@
 
 	r->min.x -= pan.x / scale;
 	r->min.y -= pan.y / scale;
-	if(r->min.x + r->max.x < 0 || r->min.x >= fbw / scale
+	if(r->min.x + r->max.x < 0 || r->min.x >= fbw
 	|| r->min.y + r->max.y < 0 || r->min.y >= fbh)
 		return -1;
 	w = r->max.x;
@@ -89,8 +114,8 @@
 		r->max.x += r->min.x;
 		r->min.x = 0;
 	}
-	if(r->min.x + r->max.x > fbw / scale)
-		r->max.x -= r->min.x + r->max.x - fbw / scale;
+	if(r->min.x + r->max.x > fbw)
+		r->max.x -= r->min.x + r->max.x - fbw;
 	if(r->min.y < 0){
 		if(q != nil)
 			*q -= w * r->min.y;
@@ -100,14 +125,15 @@
 	if(r->min.y + r->max.y > fbh)
 		r->max.y -= r->min.y + r->max.y - fbh;
 	r->min.x *= scale;
+	r->max.x *= scale;
 	return 0;
 }
 
 static void
-drawpic(int x, int y, Pic *pic)
+drawpic(int x, int y, Pic *pic, int ivis)
 {
-	int n, w, Δp, Δq;
-	u32int v, *p, *q;
+	int n, Δp, Δsp, Δq;
+	u32int v, *p, *e, *sp, *q;
 	Rectangle r;
 
 	if(pic->p == nil)
@@ -116,12 +142,14 @@
 	r = Rect(x + pic->dx, y + pic->dy, pic->w, pic->h);
 	if(boundpic(&r, &q) < 0)
 		return;
-	Δq = pic->w - r.max.x;
-	p = fb + r.min.y * fbw + r.min.x;
-	Δp = fbw - r.max.x * scale;
+	Δq = pic->w - r.max.x / scale;
+	p = fb + r.min.y * fbws + r.min.x;
+	Δp = fbws - r.max.x;
+	sp = fbvis + r.min.y * fbw + r.min.x / scale;
+	Δsp = fbw - r.max.x / scale;
 	while(r.max.y-- > 0){
-		w = r.max.x;
-		while(w-- > 0){
+		e = p + r.max.x;
+		while(p < e){
 			v = *q++;
 			if(v & 0xff << 24){
 				for(n=0; n<scale; n++)
@@ -128,9 +156,11 @@
 					*p++ = v;
 			}else
 				p += scale;
+			*sp++ = ivis;
 		}
 		q += Δq;
 		p += Δp;
+		sp += Δsp;
 	}
 }
 
@@ -137,8 +167,8 @@
 static void
 drawshadow(int x, int y, Pic *pic)
 {
-	int n, w, Δp, Δq;
-	u32int v, *p, *q;
+	int n, Δp, Δq;
+	u32int v, *p, *e, *q;
 	Rectangle r;
 
 	q = pic->p;
@@ -145,12 +175,12 @@
 	r = Rect(x + pic->dx, y + pic->dy, pic->w, pic->h);
 	if(boundpic(&r, &q) < 0)
 		return;
-	Δq = pic->w - r.max.x;
-	p = fb + r.min.y * fbw + r.min.x;
-	Δp = fbw - r.max.x * scale;
+	Δq = pic->w - r.max.x / scale;
+	p = fb + r.min.y * fbws + r.min.x;
+	Δp = fbws - r.max.x;
 	while(r.max.y-- > 0){
-		w = r.max.x;
-		while(w-- > 0){
+		e = p + r.max.x;
+		while(p < e){
 			v = *q++;
 			if(v & 0xff << 24){
 				v = p[0];
@@ -167,21 +197,21 @@
 	}
 }
 
-static void
-compose(Path *pp, u32int c)
+void
+compose(int x, int y, u32int c)
 {
-	int n, w, Δp;
-	u32int v, *p;
+	int n, Δp;
+	u32int v, *p, *e;
 	Rectangle r;
 
-	r = Rect(pp->x * Tlsubwidth, pp->y * Tlsubheight, Tlsubwidth, Tlsubheight);
+	r = Rect(x * Tlsubwidth, y * Tlsubheight, Tlsubwidth, Tlsubheight);
 	if(boundpic(&r, nil) < 0)
 		return;
-	p = fb + r.min.y * fbw + r.min.x;
-	Δp = fbw - r.max.x * scale;
+	p = fb + r.min.y * fbws + r.min.x;
+	Δp = fbws - r.max.x;
 	while(r.max.y-- > 0){
-		w = r.max.x;
-		while(w-- > 0){
+		e = p + r.max.x;
+		while(p < e){
 			v = *p;
 			v = (v & 0xff0000) + (c & 0xff0000) >> 1 & 0xff0000
 				| (v & 0xff00) + (c & 0xff00) >> 1 & 0xff00
@@ -193,6 +223,41 @@
 	}
 }
 
+static void
+drawmap(Rectangle *r)
+{
+	int x, y;
+	u64int *row, v, m;
+	Node *n;
+	Mobj *mo;
+	Point *p;
+
+	for(y=r->min.y, n=node+y*mapwidth+r->min.x; y<r->max.y; y++){
+		x = r->min.x;
+		row = baddr(x, y);
+		v = *row++;
+		m = 1ULL << 63 - (x & Bmask);
+		for(; x<r->max.x; x++, n++, m>>=1){
+			if(m == 0){
+				v = *row++;
+				m = 1ULL << 63;
+			}
+			if(v & m)
+				compose(x, y, 0xff0000);
+			if(n->closed)
+				compose(x, y, 0x0000ff);
+			else if(n->open)
+				compose(x, y, 0xffff00);
+		}
+		n += mapwidth - (r->max.x - r->min.x);
+	}
+	if((mo = selected[0]) != nil && mo->pathp != nil){
+		for(p=mo->paths; p<mo->pathe; p++)
+			compose(p->x, p->y, 0x00ff00);
+		compose(mo->target.x, mo->target.y, 0x00ffff);
+	}
+}
+
 static Pic *
 frm(Mobj *mo, int notshadow)
 {
@@ -212,64 +277,90 @@
 void
 redraw(void)
 {
-	char s[256];
-	Point p;
+	int x, y;
+	Rectangle mr, tr;
+	Terrain **t;
 	Map *m;
 	Mobj *mo;
-	Lobj *lo;
-	//Path *pp;
+	Mobjl *ml;
 
-	/* FIXME: only process visible parts of the screen and adjacent tiles */
-	for(m=map; m<map+mapwidth*mapheight; m++)
-		drawpic(m->x, m->y, m->t->p);
-	/* FIXME: draw overlay (creep) */
-	/* FIXME: draw corpses */
-	for(m=map; m<map+mapwidth*mapheight; m++){
-		for(lo=m->lo.lo; lo!=&m->lo; lo=lo->lo){
-			mo = lo->mo;
-			drawshadow(mo->p.x, mo->p.y, frm(mo, 0));
+	clearvis();
+	tr.min.x = pan.x / scale / Tlwidth;
+	tr.min.y = pan.y / scale / Tlheight;
+	tr.max.x = min(tr.min.x + fbw / Tlwidth + scale, terwidth);
+	tr.max.y = min(tr.min.y + fbh / Tlheight + scale, terheight);
+	mr.min.x = max(tr.min.x - 3, 0) * Tlnsub;
+	mr.min.y = max(tr.min.y - 3, 0) * Tlnsub;
+	mr.max.x = tr.max.x * Tlnsub;
+	mr.max.y = tr.max.y * Tlnsub;
+	for(y=tr.min.y, t=terrain+y*terwidth+tr.min.x; y<tr.max.y; y++){
+		for(x=tr.min.x; x<tr.max.x; x++, t++)
+			drawpic(x*Tlwidth, y*Tlheight, (*t)->p, -1);
+		t += terwidth - (tr.max.x - tr.min.x);
+	}
+	for(y=mr.min.y, m=map+y*mapwidth+mr.min.x; y<mr.max.y; y++){
+		for(x=mr.min.x; x<mr.max.x; x++, m++){
+			for(ml=m->ml.l; ml!=&m->ml; ml=ml->l){
+				mo = ml->mo;
+				if(mo->o->f & Fair)
+					break;
+				drawshadow(mo->px, mo->py, frm(mo, 0));
+			}
+			for(ml=m->ml.l; ml!=&m->ml; ml=ml->l){
+				mo = ml->mo;
+				if(mo->o->f & Fair)
+					break;
+				drawpic(mo->px, mo->py, frm(mo, 1), addvis(mo));
+			}
 		}
-		for(lo=m->lo.lo; lo!=&m->lo; lo=lo->lo){
-			mo = lo->mo;
-			drawpic(mo->p.x, mo->p.y, frm(mo, 1));
+		m += mapwidth - (mr.max.x - mr.min.x);
+	}
+	for(y=mr.min.y, m=map+y*mapwidth+mr.min.x; y<mr.max.y; y++){
+		for(x=mr.min.x; x<mr.max.x; x++, m++){
+			for(ml=m->ml.l; ml!=&m->ml; ml=ml->l){
+				mo = ml->mo;
+				if((mo->o->f & Fair) == 0)
+					continue;
+				drawshadow(mo->px, mo->py, frm(mo, 0));
+			}
+			for(ml=m->ml.l; ml!=&m->ml; ml=ml->l){
+				mo = ml->mo;
+				if((mo->o->f & Fair) == 0)
+					continue;
+				drawpic(mo->px, mo->py, frm(mo, 1), addvis(mo));
+			}
 		}
+		m += mapwidth - (mr.max.x - mr.min.x);
 	}
-	//for(pp=path; pp<path+pathwidth*pathheight; pp++)
-	//	if(pp->blk != nil)
-	//		compose(pp, 0xff00ff);
-	/* FIXME: draw hud */
-	draw(screen, Rpt(p0, screen->r.max), display->black, nil, ZP);
-	mo = selected[0];
-	if(mo == nil)
-		return;
-	/* FIXME: selected should be its own layer, not mapped to Map,
-	 * since the coordinates won't match */
-	p = p0;
-	snprint(s, sizeof s, "%s %d/%d", mo->o->name, mo->hp, mo->o->hp);
-	string(screen, p, display->white, ZP, font, s);
+	if(debugmap)
+		drawmap(&mr);
+	drawhud();
 }
 
 void
 resetfb(void)
 {
-	fbw = min(mapwidth * Tlwidth * scale, Dx(screen->r));
-	fbh = min(mapheight * Tlheight * scale, Dy(screen->r));
-	selr = Rpt(screen->r.min, addpt(screen->r.min, Pt(fbw, fbh)));
+	fbws = min(mapwidth * Tlsubwidth * scale, Dx(screen->r));
+	fbh = min(mapheight * Tlsubheight * scale, Dy(screen->r));
+	selr = Rpt(screen->r.min, addpt(screen->r.min, Pt(fbws, fbh)));
 	p0 = Pt(screen->r.min.x + 8, screen->r.max.y - 3 * font->height);
-	panmax.x = max(Tlwidth * mapwidth * scale - Dx(screen->r), 0);
-	panmax.y = max(Tlheight * mapheight * scale - Dy(screen->r), 0);
+	panmax.x = max(Tlsubwidth * mapwidth * scale - Dx(screen->r), 0);
+	panmax.y = max(Tlsubheight * mapheight * scale - Dy(screen->r), 0);
 	if(p0.y < selr.max.y){
 		panmax.y += selr.max.y - p0.y;
+		fbh -= selr.max.y - p0.y;
 		selr.max.y = p0.y;
 	}
+	fbw = fbws / scale;
 	fbh /= scale;
-	fbsz = fbw * fbh * sizeof *fb;
+	fbsz = fbws * fbh * sizeof *fb;
 	free(fb);
+	free(fbvis);
 	freeimage(fbi);
 	fb = emalloc(fbsz);
-	fbe = fb + fbsz / sizeof *fb;
+	fbvis = emalloc(fbw * fbh * sizeof *fb);
 	if((fbi = allocimage(display,
-		Rect(0,0,fbw,scale==1 ? fbh : 1),
+		Rect(0,0,fbws,scale==1 ? fbh : 1),
 		XRGB32, scale>1, 0)) == nil)
 		sysfatal("allocimage: %r");
 	draw(screen, screen->r, display->black, nil, ZP);
@@ -282,8 +373,6 @@
 	Rectangle r, r2;
 
 	r = selr;
-	if(r.max.y > p0.y)
-		r.max.y = p0.y;
 	p = (uchar *)fb;
 	if(scale == 1){
 		loadimage(fbi, fbi->r, p, fbsz);
--- a/fns.h
+++ b/fns.h
@@ -1,7 +1,7 @@
 void	stepsnd(void);
 void	initsnd(void);
-void	llink(Lobj*, Lobj*);
-void	lunlink(Lobj*);
+void	linktomap(Mobj*);
+int	moveone(Point, Mobj*, Mobj*);
 void	stepsim(void);
 void	initsv(void);
 void	flushcl(void);
@@ -10,18 +10,36 @@
 void	joinnet(char*);
 void	listennet(void);
 void	dopan(int, int);
+void	compose(int, int, u32int);
 void	redraw(void);
 void	resetfb(void);
 void	drawfb(void);
 void	initimg(void);
 void	init(void);
-int	isblocked(Point*, Mobj*);
-void	setblk(Mobj*, int);
-int	findpath(Mobj*, Point*);
-void	initpath(void);
-int	move(int, int, Mobj**);
-int	spawn(Map*, Obj*, int);
-void	inittab(void);
+void	setgoal(Point*, Mobj*, Mobj*);
+int	isblocked(int, int, Obj*);
+void	markmobj(Mobj*, int);
+int	findpath(Point, Mobj*);
+Mobj*	mapspawn(int, int, Obj*);
+void	initmap(void);
+int	spawn(int, int, Obj*, int);
+void	nukequeue(Pairheap**);
+Pairheap*	popqueue(Pairheap**);
+void	decreasekey(Pairheap*, double, Pairheap**);
+void	pushqueue(Node*, Pairheap**);
+int	lsb(uvlong);
+int	msb(uvlong);
+u64int*	baddr(int, int);
+u64int*	rbaddr(int, int);
+u64int*	bload(int, int, int, int, int, int, int, int);
+void	bset(int, int, int, int, int);
+void	initbmap(void);
+void	dprint(char *, ...);
+int	max(int, int);
+int	min(int, int);
 char*	estrdup(char*);
+void*	erealloc(void*, ulong, ulong);
 void*	emalloc(ulong);
 vlong	flen(int);
+
+#pragma	varargck	argpos	dprint	1
--- a/fs.c
+++ b/fs.c
@@ -6,11 +6,7 @@
 #include "dat.h"
 #include "fns.h"
 
-/* FIXME: building sight range, set to 1 for now */
-
 Resource resource[Nresource];
-Map *map;
-int mapwidth, mapheight;
 
 typedef struct Table Table;
 typedef struct Objp Objp;
@@ -43,7 +39,7 @@
 	Terrain *t;
 	Terrainl *l;
 };
-static Terrainl terrain0 = {.l = &terrain0}, *terrain = &terrain0;
+static Terrainl terrainl0 = {.l = &terrainl0}, *terrainl = &terrainl0;
 static Picl pic0 = {.l = &pic0}, *pic = &pic0;
 static Objp *objp;
 static Attack *attack;
@@ -158,16 +154,16 @@
 {
 	Terrainl *tl;
 
-	for(tl=terrain->l; tl!=terrain; tl=tl->l)
+	for(tl=terrainl->l; tl!=terrainl; tl=tl->l)
 		if(tl->id == id)
 			break;
-	if(tl == terrain){
+	if(tl == terrainl){
 		tl = emalloc(sizeof *tl);
 		tl->id = id;
 		tl->t = emalloc(sizeof *tl->t);
 		tl->t->p = pushpic(",", id, PFterrain, 1);
-		tl->l = terrain->l;
-		terrain->l = tl;
+		tl->l = terrainl->l;
+		terrainl->l = tl;
 	}
 	return tl->t;
 }
@@ -275,23 +271,16 @@
 readmap(char **fld, int n, Table *tab)
 {
 	int x;
-	Map *m;
+	Terrain **t;
 
 	if(tab->row == 0){
 		tab->ncol = n;
-		mapwidth = n;
-		map = emalloc(mapheight * mapwidth * sizeof *map);
+		terwidth = n;
+		terrain = emalloc(terheight * terwidth * sizeof *terrain);
 	}
-	m = map + tab->row * mapwidth;
-	for(x=0; x<n; x++, m++){
-		unpack(fld++, "t", &m->t);
-		/* FIXME: get rid of these */
-		m->tx = x;
-		m->ty = tab->row;
-		m->x = m->tx * Tlwidth;
-		m->y = m->ty * Tlheight;
-		m->lo.lo = m->lo.lp = &m->lo;
-	}
+	t = terrain + tab->row * terwidth;
+	for(x=0; x<n; x++, t++)
+		unpack(fld++, "t", t);
 }
 
 static void
@@ -346,6 +335,8 @@
 		&o->hp, &o->def, &o->speed, &o->vis,
 		o->cost, o->cost+1, o->cost+2, &o->time,
 		o->atk, o->atk+1);
+	if(o->w < 1 || o->h < 1)
+		sysfatal("readobj: %s invalid dimensions %d,%d", o->name, o->w, o->h);
 }
 
 static void
@@ -386,7 +377,7 @@
 	{"resource", readresource, 2, &nresource},
 	{"spawn", readspawn, -1, nil},
 	{"tileset", readtileset, 1, nil},
-	{"map", readmap, -1, &mapheight},
+	{"map", readmap, -1, &terheight},
 	{"spr", readspr, -1, nil},
 };
 
@@ -467,13 +458,10 @@
 initmapobj(void)
 {
 	Objp *op;
-	Map *m;
 
-	for(op=objp; op<objp+nobjp; op++){
-		m = map + mapwidth * op->y + op->x;
-		if(spawn(m, op->o, op->team) < 0)
+	for(op=objp; op<objp+nobjp; op++)
+		if(spawn(op->x * Tlnsub, op->y * Tlnsub, op->o, op->team) < 0)
 			sysfatal("initmapobj: %s team %d: %r", op->o->name, op->team);
-	}
 	free(objp);
 }
 
@@ -482,8 +470,8 @@
 {
 	Terrainl *tl;
 
-	for(tl=terrain->l; tl!=terrain; tl=terrain->l){
-		terrain->l = tl->l;
+	for(tl=terrainl->l; tl!=terrainl; tl=terrainl->l){
+		terrainl->l = tl->l;
 		free(tl);
 	}
 }
@@ -495,8 +483,9 @@
 		sysfatal("checkdb: no tileset defined");
 	if(nresource != Nresource)
 		sysfatal("checkdb: incomplete resource specification");
-	if(mapwidth < 8 || mapheight < 8)
-		sysfatal("checkdb: map too small %d,%d", mapwidth, mapheight);
+	if(terwidth % 16 != 0 || terheight % 16 != 0 || terwidth * terheight == 0)
+		sysfatal("checkdb: map size %d,%d not in multiples of 16",
+			terwidth, terheight);
 	if(nteam < 2)
 		sysfatal("checkdb: not enough teams");
 }
@@ -504,9 +493,9 @@
 static void
 initdb(void)
 {
-	initpath();
-	initmapobj();
 	checkdb();
+	initmap();
+	initmapobj();
 	cleanup();
 }
 
@@ -513,7 +502,7 @@
 void
 init(void)
 {
-	if(bind(".", prefix, MBEFORE|MCREATE) < 0 || chdir(prefix) < 0)
+	if(bind(".", prefix, MBEFORE|MCREATE) == -1 || chdir(prefix) < 0)
 		fprint(2, "init: %r\n");
 	loaddb(dbname);
 	loaddb(mapname);
--- /dev/null
+++ b/map.c
@@ -1,0 +1,124 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.h>
+#include "dat.h"
+#include "fns.h"
+
+Terrain **terrain;
+int terwidth, terheight;
+Map *map;
+int mapwidth, mapheight;
+Node *node;
+
+static void
+updatemap(Mobj *mo)
+{
+	linktomap(mo);
+	markmobj(mo, 1);
+}
+
+static int
+findspawn(int *nx, int *ny, int ofs, Obj *o, Obj *spawn)
+{
+	int sz, x, y, minx, miny, maxx, maxy;
+
+	sz = ofs * o->w;
+	minx = *nx - sz;
+	miny = *ny - sz;
+	maxx = *nx + spawn->w + sz;
+	maxy = *ny + spawn->h + sz;
+	for(x=minx+sz, y=maxy; x<maxx; x++)
+		if(!isblocked(x, y, o))
+			goto found;
+	for(x=maxx, y=maxy; y>miny; y--)
+		if(!isblocked(x, y, o))
+			goto found;
+	for(x=maxx, y=miny; x>minx; x--)
+		if(!isblocked(x, y, o))
+			goto found;
+	for(x=minx, y=miny; y<=maxy; y++)
+		if(!isblocked(x, y, o))
+			goto found;
+	return -1;
+found:
+	*nx = x;
+	*ny = y;
+	return 0;
+}
+
+static int
+getspawn(int *nx, int *ny, Obj *o)
+{
+	int n, x, y;
+	Mobj *mo;
+	Map *m;
+
+	x = *nx;
+	y = *ny;
+	if(o->f & Fbuild){
+		if(isblocked(x, y, o)){
+			werrstr("getspawn: building placement at %d,%d blocked", x, y);
+			return -1;
+		}
+	}else if((o->f & Fair) == 0){
+		m = map + y * mapwidth + x;
+		if(m->ml.l == &m->ml || m->ml.l->mo == nil){
+			werrstr("getspawn: no spawn object at %d,%d", x, y);
+			return -1;
+		}
+		mo = m->ml.l->mo;
+		for(n=0; n<3; n+=o->w)
+			if(findspawn(&x, &y, n / o->w, o, mo->o) >= 0)
+				break;
+		if(n == 3){
+			werrstr("getspawn: no free spot for %s at %d,%d\n",
+				o->name, x, y);
+			return -1;
+		}
+	}
+	*nx = x;
+	*ny = y;
+	return 0;
+}
+
+Mobj *
+mapspawn(int x, int y, Obj *o)
+{
+	Mobj *mo;
+
+	if(o->f & Fbuild && (x & Tlnsub-1 || y & Tlnsub-1)){
+		werrstr("mapspawn: building spawn %d,%d not aligned to terrain map", x, y);
+		return nil;
+	}
+	if(getspawn(&x, &y, o) < 0)
+		return nil;
+	mo = emalloc(sizeof *mo);
+	mo->x = x;
+	mo->y = y;
+	mo->px = x * Tlsubwidth;
+	mo->py = y * Tlsubheight;
+	mo->subpx = mo->px << Subpxshift;
+	mo->subpy = mo->py << Subpxshift;
+	mo->o = o;
+	mo->f = o->f;
+	mo->hp = o->hp;
+	mo->θ = nrand(Nrot);
+	updatemap(mo);
+	return mo;
+}
+
+void
+initmap(void)
+{
+	int n;
+	Map *m;
+
+	mapwidth = terwidth * Tlnsub;
+	mapheight = terheight * Tlnsub;
+	n = mapwidth * mapheight;
+	map = emalloc(n * sizeof *map);
+	node = emalloc(n * sizeof *node);
+	for(m=map; m<map+n; m++)
+		m->ml.l = m->ml.lp = &m->ml;
+	initbmap();
+}
--- a/mkfile
+++ b/mkfile
@@ -2,13 +2,17 @@
 BIN=$home/bin/$objtype
 TARG=sce
 OFILES=\
-	ai.$O\
+	bmap.$O\
 	drw.$O\
 	fs.$O\
+	map.$O\
 	net.$O\
+	path.$O\
+	pheap.$O\
 	sce.$O\
 	sim.$O\
 	snd.$O\
+	util.$O\
 
 HFILES=dat.h fns.h
 </sys/src/cmd/mkone
--- /dev/null
+++ b/path.c
@@ -1,0 +1,525 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.h>
+#include "dat.h"
+#include "fns.h"
+
+/* jump point search with block-based symmetry breaking (JPS(B): 2014, harabor and
+ * grastien), using pairing heaps for priority queues and a bitmap representing the
+ * entire map.
+ * no preprocessing since we'd have to repair the database each time anything moves,
+ * which is a pain.
+ * no pruning of intermediate nodes (JPS(B+P)) as of yet, until other options are
+ * assessed.
+ * the pruning rules adhere to (2012, harabor and grastien) to disallow corner cutting
+ * in diagonal movement, and movement code elsewhere reflects that.
+ * if there is no path to the target, the unit still has to move to the nearest
+ * accessible node.  if there is such a node, we first attempt to find a nearer
+ * non-jump point in a cardinal direction, and if successful, the point is added at
+ * the end of the path.  unlike plain a∗, we cannot rely on the path backtracked from
+ * the nearest node, since it is no longer guaranteed to be optimal, and will in fact
+ * go all over the place.  unless jump points can be connected to all other visible
+ * jump points so as to perform a search on this reduced graph without rediscovering
+ * the map, we're forced to re-do pathfinding to this nearest node.  the search should
+ * be much quicker since this new node is accessible.
+ * pathfinding is not limited to an area, so entire map may be scanned, which is too
+ * slow.  simple approaches don't seem to work well, it would perhaps be better to
+ * only consider a sub-grid of the map, but the data structures currently used do not
+ * allow it.  since the pathfinding algorithm will probably change, the current
+ * implementation disregards the issue.
+ * pathfinding is limited by number of moves (the cost function).  this prevents the
+ * search to look at the entire map, but also means potentially non-optimal paths and
+ * more pathfinding when crossing the boundaries.
+ * since units are bigger than the pathfinding grid, the grid is "compressed" when
+ * scanned by using a sliding window the size of the unit, so the rest of the algorithm
+ * still operates on 3x3 neighbor grids, with each bit checking as many nodes as needed
+ * for impassibility.  such an approach has apparently not been discussed in regards
+ * to JPS(B), possibly since JPS(B) is a particular optimization of the original
+ * algorithm and this snag may rarely be hit in practice.
+ * map dimensions are assumed to be multiples of 16 tiles.
+ * the code is currently horrendously ugly, though short, and ultimately wrong.
+ * movement should occur at any angle (rather than in 8 directions) and unit sizes
+ * do not have a common denominator higher than 1 pixel. */
+
+enum{
+	θ∅ = 0,
+	θN,
+	θE,
+	θS,
+	θW,
+	θNE,
+	θSE,
+	θSW,
+	θNW,
+};
+
+#define SQRT2 1.4142135623730951
+
+static Pairheap *queue;
+static Node *nearest;
+
+static void
+clearpath(void)
+{
+	nukequeue(&queue);
+	memset(node, 0, mapwidth * mapheight * sizeof *node);
+	nearest = nil;
+}
+
+int
+isblocked(int x, int y, Obj *o)
+{
+	u64int *row;
+
+	row = bload(x, y, o->w, o->h, 0, 0, 0, 0);
+	return (*row & 1ULL << 63) != 0;
+}
+
+void
+markmobj(Mobj *mo, int set)
+{
+	int w, h;
+
+	w = mo->o->w;
+	if((mo->subpx & Subpxmask) != 0 && mo->x != (mo->px + 1) / Tlsubwidth)
+		w++;
+	h = mo->o->h;
+	if((mo->subpy & Subpxmask) != 0 && mo->y != (mo->py + 1) / Tlsubwidth)
+		h++;
+	bset(mo->x, mo->y, w, h, set);
+}
+
+static double
+octdist(Node *a, Node *b)
+{
+	int dx, dy;
+
+	dx = abs(a->x - b->x);
+	dy = abs(a->y - b->y);
+	return 1 * (dx + dy) + (SQRT2 - 2 * 1) * min(dx, dy);
+}
+
+/* FIXME: horrendous. use fucking tables you moron */
+static Node *
+jumpeast(int x, int y, int w, int h, Node *b, int *ofs, int left, int rot)
+{
+	int nbits, steps, stop, end, *u, *v, ss, Δu, Δug, Δug2, Δvg;
+	u64int bs, *row;
+	Node *n;
+
+	if(rot){
+		u = &y;
+		v = &x;
+		Δug = b->y - y;
+		Δvg = b->x - x;
+	}else{
+		u = &x;
+		v = &y;
+		Δug = b->x - x;
+		Δvg = b->y - y;
+	}
+	steps = 0;
+	nbits = 64 - w + 1;
+	ss = left ? -1 : 1;
+	(*v)--;
+	for(;;){
+		row = bload(x, y, w, h, 0, 2, left, rot);
+		bs = row[1];
+		if(left){
+			bs |= row[0] << 1 & ~row[0];
+			bs |= row[2] << 1 & ~row[2];
+		}else{
+			bs |= row[0] >> 1 & ~row[0];
+			bs |= row[2] >> 1 & ~row[2];
+		}
+		if(bs)
+			break;
+		(*u) += ss * nbits;
+		steps += nbits;
+	}
+	if(left){
+		stop = lsb(bs);
+		Δu = stop;
+	}else{
+		stop = msb(bs);
+		Δu = 63 - stop;
+	}
+	end = (row[1] & 1ULL << stop) != 0;
+	(*u) += ss * Δu;
+	(*v)++;
+	steps += Δu;
+	Δug2 = rot ? b->y - y : b->x - x;
+	if(ofs != nil)
+		*ofs = steps;
+	if(end && Δug2 == 0)
+		return nil;
+	if(Δvg == 0 && (Δug < 0) ^ (Δug2 < 0)){
+		b->Δg = steps - abs(Δug2);
+		return b;
+	}
+	if(end)
+		return nil;
+	assert(x < mapwidth && y < mapheight);
+	n = node + y * mapwidth + x;
+	n->x = x;
+	n->y = y;
+	n->Δg = steps;
+	return n;
+}
+
+static Node *
+jumpdiag(int x, int y, int w, int h, Node *b, int dir)
+{
+	int left1, ofs1, left2, ofs2, Δx, Δy, steps;
+	Node *n;
+
+	steps = 0;
+	left1 = left2 = Δx = Δy = 0;
+	switch(dir){
+	case θNE: left1 = 1; left2 = 0; Δx = 1; Δy = -1; break;
+	case θSW: left1 = 0; left2 = 1; Δx = -1; Δy = 1; break;
+	case θNW: left1 = 1; left2 = 1; Δx = -1; Δy = -1; break;
+	case θSE: left1 = 0; left2 = 0; Δx = 1; Δy = 1; break;
+	}
+	for(;;){
+		steps++;
+		x += Δx;
+		y += Δy;
+		if(*bload(x, y, w, h, 0, 0, 0, 0) & 1ULL << 63)
+			return nil;
+		if(jumpeast(x, y, w, h, b, &ofs1, left1, 1) != nil
+		|| jumpeast(x, y, w, h, b, &ofs2, left2, 0) != nil)
+			break;
+		if(ofs1 == 0 || ofs2 == 0)
+			return nil;
+	}
+	assert(x < mapwidth && y < mapheight);
+	n = node + y * mapwidth + x;
+	n->x = x;
+	n->y = y;
+	n->Δg = steps;
+	return n;
+}
+
+static Node *
+jump(int x, int y, int w, int h, Node *b, int dir)
+{
+	Node *n;
+
+	switch(dir){
+	case θE: n = jumpeast(x, y, w, h, b, nil, 0, 0); break;
+	case θW: n = jumpeast(x, y, w, h, b, nil, 1, 0); break;
+	case θS: n = jumpeast(x, y, w, h, b, nil, 0, 1); break;
+	case θN: n = jumpeast(x, y, w, h, b, nil, 1, 1); break;
+	default: n = jumpdiag(x, y, w, h, b, dir); break;
+	}
+	return n;
+}
+
+/* 2012, harabor and grastien: disabling corner cutting implies that only moves in
+ * a cardinal direction may produce forced neighbors */
+static int
+forced(int n, int dir)
+{
+	int m;
+
+	m = 0;
+	switch(dir){
+	case θN:
+		if((n & (1<<8 | 1<<5)) == 1<<8) m |= 1<<5 | 1<<2;
+		if((n & (1<<6 | 1<<3)) == 1<<6) m |= 1<<3 | 1<<0;
+		break;
+	case θE:
+		if((n & (1<<2 | 1<<1)) == 1<<2) m |= 1<<1 | 1<<0;
+		if((n & (1<<8 | 1<<7)) == 1<<8) m |= 1<<7 | 1<<6;
+		break;
+	case θS:
+		if((n & (1<<2 | 1<<5)) == 1<<2) m |= 1<<5 | 1<<8;
+		if((n & (1<<0 | 1<<3)) == 1<<0) m |= 1<<3 | 1<<6;
+		break;
+	case θW:
+		if((n & (1<<0 | 1<<1)) == 1<<0) m |= 1<<1 | 1<<2;
+		if((n & (1<<6 | 1<<7)) == 1<<6) m |= 1<<7 | 1<<8;
+		break;
+	}
+	return m;
+}
+
+static int
+natural(int n, int dir)
+{
+	int m;
+
+	switch(dir){
+	/* disallow corner coasting on the very first move */
+	default:
+		if((n & (1<<1 | 1<<3)) != 0)
+			n |= 1<<0;
+		if((n & (1<<7 | 1<<3)) != 0)
+			n |= 1<<6;
+		if((n & (1<<7 | 1<<5)) != 0)
+			n |= 1<<8;
+		if((n & (1<<1 | 1<<5)) != 0)
+			n |= 1<<2;
+		return n;
+	case θN: return n | ~(1<<1);
+	case θE: return n | ~(1<<3);
+	case θS: return n | ~(1<<7);
+	case θW: return n | ~(1<<5);
+	case θNE: m = 1<<1 | 1<<3; return (n & m) == 0 ? n | ~(1<<0 | m) : n | 1<<0;
+	case θSE: m = 1<<7 | 1<<3; return (n & m) == 0 ? n | ~(1<<6 | m) : n | 1<<6;
+	case θSW: m = 1<<7 | 1<<5; return (n & m) == 0 ? n | ~(1<<8 | m) : n | 1<<8;
+	case θNW: m = 1<<1 | 1<<5; return (n & m) == 0 ? n | ~(1<<2 | m) : n | 1<<2;
+	}
+}
+
+static int
+prune(int n, int dir)
+{
+	return natural(n, dir) & ~forced(n, dir);
+}
+
+static int
+neighbors(int x, int y, int w, int h)
+{
+	u64int *row;
+
+	row = bload(x-1, y-1, w, h, 2, 2, 1, 0);
+	return (row[2] & 7) << 6 | (row[1] & 7) << 3 | row[0] & 7;
+}
+
+static Node **
+successors(Node *n, int w, int h, Node *b)
+{
+	static Node *dir[8+1];
+	static dtab[2*(nelem(dir)-1)]={
+		1<<1, θN, 1<<3, θE, 1<<7, θS, 1<<5, θW,
+		1<<0, θNE, 1<<6, θSE, 1<<8, θSW, 1<<2, θNW
+	};
+	int i, ns;
+	Node *s, **p;
+
+	ns = neighbors(n->x, n->y, w, h);
+	ns = prune(ns, n->dir);
+	memset(dir, 0, sizeof dir);
+	for(i=0, p=dir; i<nelem(dtab); i+=2){
+		if(ns & dtab[i])
+			continue;
+		if((s = jump(n->x, n->y, w, h, b, dtab[i+1])) != nil){
+			s->dir = dtab[i+1];
+			*p++ = s;
+		}
+	}
+	return dir;
+}
+
+static Node *
+a∗(Node *a, Node *b, Mobj *mo)
+{
+	double g, Δg;
+	Node *x, *n, **dp;
+	Pairheap *pn;
+
+	if(a == b){
+		werrstr("a∗: moving in place");
+		return nil;
+	}
+	x = a;
+	a->h = octdist(a, b);
+	pushqueue(a, &queue);
+	while((pn = popqueue(&queue)) != nil){
+		x = pn->n;
+		free(pn);
+		if(x == b)
+			break;
+		x->closed = 1;
+		dp = successors(x, mo->o->w, mo->o->h, b);
+		for(n=*dp++; n!=nil; n=*dp++){
+			if(n->closed)
+				continue;
+			g = x->g + n->Δg;
+			Δg = n->g - g;
+			if(!n->open){
+				n->from = x;
+				n->g = g;
+				n->h = octdist(n, b);
+				n->open = 1;
+				n->step = x->step + 1;
+				pushqueue(n, &queue);
+			}else if(Δg > 0){
+				n->from = x;
+				n->step = x->step + 1;
+				n->g -= Δg;
+				decreasekey(n->p, Δg, &queue);
+			}
+			if(nearest == nil || n->h < nearest->h)
+				nearest = n;
+		}
+	}
+	return x;
+}
+
+static void
+backtrack(Node *n, Node *a, Mobj *mo)
+{
+	int x, y;
+	Point *p;
+
+	assert(n != a && n->step > 0);
+	if(mo->npathbuf < n->step){
+		mo->paths = erealloc(mo->paths,
+			n->step * sizeof mo->paths,
+			mo->npathbuf * sizeof mo->paths);
+		mo->npathbuf = n->step;
+	}
+	p = mo->paths + n->step;
+	mo->pathe = p--;
+	for(; n!=a; n=n->from){
+		x = n->x;
+		y = n->y;
+		*p-- = (Point){x, y};
+	}
+	assert(p == mo->paths - 1);
+}
+
+static Node *
+nearestnonjump(Node *n, Node *b, Mobj *mo)
+{
+	static Point dirtab[] = {
+		{0,-1},
+		{1,0},
+		{0,1},
+		{-1,0},
+	};
+	int i, x, y;
+	Node *m, *min;
+
+	min = n;
+	for(i=0; i<nelem(dirtab); i++){
+		x = n->x + dirtab[i].x;
+		y = n->y + dirtab[i].y;
+		while(!isblocked(x, y, mo->o)){
+			m = node + y * mapwidth + x;
+			m->x = x;
+			m->y = y;
+			m->h = octdist(m, b);
+			if(min->h < m->h)
+				break;
+			min = m;
+			x += dirtab[i].x;
+			y += dirtab[i].y;
+		}
+	}
+	if(min != n){
+		min->from = n;
+		min->open = 1;
+		min->step = n->step + 1;
+	}
+	return min;
+}
+
+void
+setgoal(Point *p, Mobj *mo, Mobj *block)
+{
+	int x, y, e;
+	double Δ, Δ´;
+	Node *n1, *n2, *pm;
+
+	if(block == nil){
+		mo->goalblocked = 0;
+		return;
+	}
+	mo->goalblocked = 1;
+	dprint("setgoal: moving goal %d,%d in block %#p ", p->x, p->y, block);
+	pm = node + p->y * mapwidth + p->x;
+	pm->x = p->x;
+	pm->y = p->y;
+	Δ = 0x7ffffff;
+	x = block->x;
+	y = block->y;
+	n1 = node + y * mapwidth + x;
+	n2 = n1 + (block->o->h - 1) * mapwidth;
+	for(e=x+block->o->w; x<e; x++, n1++, n2++){
+		n1->x = x;
+		n1->y = y;
+		Δ´ = octdist(pm, n1);
+		if(Δ´ < Δ){
+			Δ = Δ´;
+			p->x = x;
+			p->y = y;
+		}
+		n2->x = x;
+		n2->y = y + block->o->h - 1;
+		Δ´ = octdist(pm, n2);
+		if(Δ´ < Δ){
+			Δ = Δ´;
+			p->x = x;
+			p->y = y + block->o->h - 1;
+		}
+	}
+	x = block->x;
+	y = block->y + 1;
+	n1 = node + y * mapwidth + x;
+	n2 = n1 + block->o->w - 1;
+	for(e=y+block->o->h-2; y<e; y++, n1+=mapwidth, n2+=mapwidth){
+		n1->x = x;
+		n1->y = y;
+		Δ´ = octdist(pm, n1);
+		if(Δ´ < Δ){
+			Δ = Δ´;
+			p->x = x;
+			p->y = y;
+		}
+		n2->x = x + block->o->w - 1;
+		n2->y = y;
+		Δ´ = octdist(pm, n2);
+		if(Δ´ < Δ){
+			Δ = Δ´;
+			p->x = x + block->o->w - 1;
+			p->y = y;
+		}
+	}
+	dprint("to %d,%d\n", p->x, p->y);
+}
+
+int
+findpath(Point p, Mobj *mo)
+{
+	Node *a, *b, *n;
+
+	dprint("findpath %d,%d → %d,%d\n", mo->x, mo->y, p.x, p.y);
+	clearpath();
+	a = node + mo->y * mapwidth + mo->x;
+	a->x = mo->x;
+	a->y = mo->y;
+	b = node + p.y * mapwidth + p.x;
+	b->x = p.x;
+	b->y = p.y;
+	markmobj(mo, 0);
+	n = a∗(a, b, mo);
+	if(n != b){
+		dprint("findpath: goal unreachable\n");
+		if((n = nearest) == a || n == nil || a->h < n->h){
+			werrstr("a∗: can't move");
+			markmobj(mo, 1);
+			return -1;
+		}
+		dprint("nearest: %#p %d,%d dist %f\n", n, n->x, n->y, n->h);
+		b = nearestnonjump(n, b, mo);
+		if(b == a){
+			werrstr("a∗: really can't move");
+			markmobj(mo, 1);
+			return -1;
+		}
+		clearpath();
+		a->x = mo->x;
+		a->y = mo->y;
+		b->x = (b - node) % mapwidth;
+		b->y = (b - node) / mapwidth;
+		if((n = a∗(a, b, mo)) == nil)
+			sysfatal("findpath: phase error");
+	}
+	markmobj(mo, 1);
+	backtrack(n, a, mo);
+	return 0;
+}
--- /dev/null
+++ b/pheap.c
@@ -1,0 +1,86 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.h>
+#include "dat.h"
+#include "fns.h"
+
+static Pairheap *
+mergequeue(Pairheap *a, Pairheap *b)
+{
+	if(b == nil)
+		return a;
+	else if(a->sum < b->sum){
+		b->right = a->left;
+		a->left = b;
+		b->parent = a;
+		return a;
+	}else{
+		a->right = b->left;
+		b->left = a;
+		a->parent = b;
+		return b;
+	}
+}
+
+static Pairheap *
+mergepairs(Pairheap *a)
+{
+	Pairheap *b, *c;
+
+	if(a == nil)
+		return nil;
+	a->parent = nil;
+	b = a->right;
+	if(b == nil)
+		return a;
+	a->right = nil;
+	b->parent = nil;
+	c = b->right;
+	b->right = nil;
+	return mergequeue(mergequeue(a, b), mergepairs(c));
+}
+
+void
+nukequeue(Pairheap **queue)
+{
+	Pairheap *p;
+
+	while((p = popqueue(queue)) != nil)
+		free(p);
+}
+
+Pairheap *
+popqueue(Pairheap **queue)
+{
+	Pairheap *p;
+
+	p = *queue;
+	if(p == nil)
+		return nil;
+	*queue = mergepairs(p->left);
+	return p;
+}
+
+void
+decreasekey(Pairheap *p, double Δ, Pairheap **queue)
+{
+	p->sum -= Δ;
+	p->n->g -= Δ;
+	if(p->parent != nil && p->sum < p->parent->sum){
+		p->parent->left = nil;
+		p->parent = nil;
+		*queue = mergequeue(p, *queue);
+	}
+}
+
+void
+pushqueue(Node *n, Pairheap **queue)
+{
+	Pairheap *p;
+
+	p = emalloc(sizeof *p);
+	p->n = n;
+	p->sum = n->h + n->g;
+	n->p = p;
+	*queue = mergequeue(p, *queue);
+}
--- a/sce.c
+++ b/sce.c
@@ -16,6 +16,7 @@
 char *progname = "sce", *dbname, *prefix, *mapname = "map1.db";
 int clon;
 vlong tc;
+int pause, debugmap;
 
 typedef struct Kev Kev;
 typedef struct Mev Mev;
@@ -37,42 +38,8 @@
 };
 static int tv = Tfast, tdiv;
 static vlong Δtc;
-static int pause;
 static Channel *reszc, *kc, *mc;
 
-char *
-estrdup(char *s)
-{
-	if((s = strdup(s)) == nil)
-		sysfatal("estrdup: %r");
-	setmalloctag(s, getcallerpc(&s));
-	return s;
-}
-
-void *
-emalloc(ulong n)
-{
-	void *p;
-
-	if((p = mallocz(n, 1)) == nil)
-		sysfatal("emalloc: %r");
-	setmalloctag(p, getcallerpc(&n));
-	return p;
-}
-
-vlong
-flen(int fd)
-{
-	vlong l;
-	Dir *d;
-
-	if((d = dirfstat(fd)) == nil) 
-		sysfatal("flen: %r");
-	l = d->length;
-	free(d);
-	return l;
-}
-
 static void
 mproc(void *)
 {
@@ -179,9 +146,8 @@
 		if(!ke.down)
 			continue;
 		switch(ke.r){
-		case ' ':
-			pause ^= 1;
-			break;
+		case KF|1: debugmap ^= 1; pause ^= 1; break;
+		case ' ': pause ^= 1; break;
 		case Kdel: quit(); break;
 		}
 	}
@@ -229,7 +195,7 @@
 static void
 usage(void)
 {
-	fprint(2, "usage: %s [-l port] [-m map] [-n name] [-s scale] [-t speed] [-x netmtpt] [sys]\n", argv0);
+	fprint(2, "usage: %s [-D] [-l port] [-m map] [-n name] [-s scale] [-t speed] [-x netmtpt] [sys]\n", argv0);
 	threadexits("usage");
 }
 
@@ -239,6 +205,7 @@
 	vlong t, t0, dt;
 
 	ARGBEGIN{
+	case 'D': debug = 1; break;
 	case 'l': lport = strtol(EARGF(usage()), nil, 0); break;
 	case 'm': mapname = EARGF(usage()); break;
 	case 'n': progname = EARGF(usage()); break;
--- a/sce/sce.db
+++ b/sce/sce.db
@@ -3,10 +3,10 @@
 resource,vespene gas,0
 attack,fusion cutter,5,1,15
 attack,spines,5,1,22
-obj,scv,32,3,1,1,60,0,5,7,1,50,0,20,fusion cutter,
-obj,drone,32,1,1,1,40,0,5,7,1,50,0,20,spines,
-obj,control,1,8,4,3,1500,1,0,1,10,400,0,1800,,
-obj,hatchery,1,8,4,3,1250,1,0,1,10,300,0,1800,,
+obj,scv,32,3,4,4,60,0,5,7,1,50,0,20,fusion cutter,
+obj,drone,32,1,4,4,40,0,5,7,1,50,0,20,spines,
+obj,control,1,8,16,12,1500,1,0,1,10,400,0,1800,,
+obj,hatchery,1,8,16,12,1250,1,0,1,10,300,0,1800,,
 spawn,control,scv
 spr,scv,1,0
 spr,scv,0x8001,0
--- a/sim.c
+++ b/sim.c
@@ -9,202 +9,133 @@
 int nteam;
 int initres[Nresource], foodcap;
 
-static Lobj vlist = {.lo = &vlist, .lp = &vlist };
+static Mobjl moving0 = {.l = &moving0, .lp = &moving0}, *moving = &moving0;
 
-/* FIXME: networking: recvbuf and sendbuf for accumulating messages to flush
- * to all clients */
-/* FIXME: acceleration, deceleration, turning speed (360°) */
-/* FIXME: minerals: 4 spaces in every direction forbidding cc placement */
-/* FIXME: resource tiles: take 2x1 tiles, drawn on top of rest
- *	-> actual (immutable) object, not terrain (remove resource= from
- *	   terrain shit, move to objects)
- *	-> minerals: min0?.grp, three types depending on abundance, with
- *	   several variants each
- *	-> Geyser.grp (terrain pal?) */
-/* FIXME: rip mineral sprites and implement terrain objects layer */
-/* FIXME: buildings are aligned to map grid, while units are aligned to
- * path grid -> building placement uses Map, not Path */
-/* FIXME: verify that path node centering does in fact work correctly, esp
- * viz blockmap and .subp; if it does, do centering at spawn */
-/* FIXME: fix land spawning to always work if adjacent space can be found */
-/* FIXME: once spawning is fixed, remove race-specific mentions and units from
- * map spec, having only starts instead, resolving to a race's cc and spawning
- * 4 workers by default (marked in db) */
-
-/* FIXME:
- - networking
- 	. server: spawn server + local client (by default)
- 	. client: connect to server
- 	. both initialize a simulation, but only the server modifies state
- - command line: choose whether or not to spawn a server and/or a client
-   (default: both)
- - always spawn a server, always initialize loopback channel to it; client
-   should do the same amount of work but the server always has the last word
-   	. don't systematically announce a port
- - client: join observers on connect
- - program a lobby for both client and server
- 	. server: kick/ban ip's, rate limit, set teams and rules
- 	. master client -> server priviledges
- 	. master client == local client
- 	. if spawning a server only, local client just implements the lobby
- 	  and a console interface, same as lobby, for controlling the server
- 	. client: choose slot
- */
-/* FIXME: db: build tree specification */
-
-static Lobj *
-lalloc(Mobj *mo, ulong sz)
+static Mobjl *
+linkmobj(Mobjl *l, Mobj *mo, Mobjl *p)
 {
-	Lobj *lo, *l;
-
-	lo = emalloc(sz * sizeof *lo);
-	for(l=lo; sz>0; sz--, l++)
-		l->mo = mo;
-	return lo;
+	if(p == nil)
+		p = emalloc(sizeof *p);
+	p->mo = mo;
+	p->l = l->l;
+	p->lp = l;
+	l->l->lp = p;
+	l->l = p;
+	return p;
 }
 
-void
-llink(Lobj *lo, Lobj *lp)
+static void
+unlinkmobj(Mobjl *ml)
 {
-	lo->lo = lp->lo;
-	lo->lp = lp;
-	lp->lo->lp = lo;
-	lp->lo = lo;
+	if(ml == nil || ml->l == nil || ml->lp == nil)
+		return;
+	ml->lp->l = ml->l;
+	ml->l->lp = ml->lp;
+	ml->lp = ml->l = nil;
 }
 
 void
-lunlink(Lobj *lo)
+linktomap(Mobj *mo)
 {
-	lo->lp->lo = lo->lo;
-	lo->lo->lp = lo->lp;
-}
+	Map *m;
 
-static void
-lfree(Lobj *lo)
-{
-	lunlink(lo);
-	free(lo);
+	m = map + mo->y * mapwidth + mo->x;
+	mo->mapp = linkmobj(mo->f & Fair ? m->ml.lp : &m->ml, mo, mo->mapp);
 }
 
 static void
-freepath(Mobj *mo)
+resetcoords(Mobj *mo)
 {
-	if(mo->path == nil)
-		return;
-	free(mo->path);
-	mo->path = mo->pathp = mo->pathe = nil;
-	lunlink(mo->vl);
+	markmobj(mo, 0);
+	mo->subpx = mo->px << Subpxshift;
+	mo->subpy = mo->py << Subpxshift;
+	markmobj(mo, 1);
 }
 
-static void
-nextpath(Mobj *mo)
+static int
+facemobj(Point p, Mobj *mo)
 {
-	int Δθ, vx, vy;
-	double θ, l;
-	Point p;
+	int dx, dy;
+	double vx, vy, θ, d;
 
-	p = *mo->pathp++;
-	vx = p.x - mo->p.x;
-	vy = p.y - mo->p.y;
-	l = sqrt(vx * vx + vy * vy);
-	mo->vx = vx / l;
-	mo->vy = vy / l;
-	mo->vv = mo->o->speed;
-	θ = atan2(mo->vy, mo->vx) + PI / 2;
+	dx = p.x - mo->x;
+	dy = p.y - mo->y;
+	d = sqrt(dx * dx + dy * dy);
+	vx = dx / d;
+	vy = dy / d;
+	mo->u = vx;
+	mo->v = vy;
+	θ = atan2(vy, vx) + PI / 2;
 	if(θ < 0)
 		θ += 2 * PI;
 	else if(θ >= 2 * PI)
 		θ -= 2 * PI;
-	Δθ = (θ / (2*PI) * 360) / (90. / (Nrot/4)) - mo->θ;
+	return (θ / (2 * PI) * 360) / (90. / (Nrot / 4));
+}
+
+static void
+freemove(Mobj *mo)
+{
+	unlinkmobj(mo->movingp);
+	mo->pathp = nil;
+	mo->pics = &mo->o->pidle;
+	resetcoords(mo);
+}
+
+static void
+nextmove(Mobj *mo)
+{
+	int Δθ;
+
+	resetcoords(mo);
+	Δθ = facemobj(*mo->pathp, mo) - mo->θ;
 	if(Δθ <= -Nrot / 2)
 		Δθ += Nrot;
 	else if(Δθ >= Nrot / 2)
 		Δθ -= Nrot;
 	mo->Δθ = Δθ;
+	mo->speed = mo->o->speed;
 }
 
 static int
-repath(Mobj *mo, Point *p)
+repath(Point p, Mobj *mo)
 {
-	freepath(mo);
-	if(findpath(mo, p) < 0){
-		fprint(2, "repath: move to %d,%d: %r\n", p->x, p->y);
+	freemove(mo);
+	mo->target = p;
+	if(findpath(p, mo) < 0){
+		mo->θ = facemobj(p, mo);
 		return -1;
 	}
-	if(mo->vl == nil)
-		mo->vl = lalloc(mo, 1);
-	llink(mo->vl, vlist.lp);
+	mo->movingp = linkmobj(moving, mo, mo->movingp);
+	mo->pathp = mo->paths;
 	mo->pics = mo->o->pmove.p != nil ? &mo->o->pmove : &mo->o->pidle;
-	nextpath(mo);
+	nextmove(mo);
 	return 0;
 }
 
-static int
-canmove(int x, int y, Mobj **op)
-{
-	/* FIXME: attempt to move in the given direction even if impassible */
-	USED(x, y, op);
-	return 1;
-}
-
 int
-move(int x, int y, Mobj **op)
+moveone(Point p, Mobj *mo, Mobj *block)
 {
-	Mobj *mo, **mp;
-	Point p;
-
-	if(!canmove(x, y, op))
+	if(mo->o->speed == 0){
+		dprint("move: obj %s can't move\n", mo->o->name);
 		return -1;
-	for(mp=op; (mo=*mp)!=nil; mp++){
-		/* FIXME: offset sprite size */
-		p = (Point){x & ~Tlsubmask, y & ~Tlsubmask};
-		if(mo->o->speed != 0 && repath(mo, &p) < 0)
-			continue;
 	}
+	setgoal(&p, mo, block);
+	if(repath(p, mo) < 0){
+		dprint("move to %d,%d: %r\n", p.x, p.y);
+		return -1;
+	}
 	return 0;
 }
 
-/* FIXME: we're not actually spawning a unit at a location, are we? it's a
- * unit or structure that spawns a unit, the placement is determined based on
- * available space -> the spawning mechanism works the same; initial units are
- * always the same and are spawned in the same manner */
-static int
-canspawn(Map *m, Mobj *mo)
-{
-	Point p;
-
-	/* FIXME: find space, unless not a unit */
-	p.x = m->tx * (Tlwidth / Tlsubwidth);
-	p.y = m->ty * (Tlheight / Tlsubheight);
-	if(isblocked(&p, mo)){
-		werrstr("no available space");
-		return 0;
-	}
-	return 1;
-}
-
 int
-spawn(Map *m, Obj *o, int n)
+spawn(int x, int y, Obj *o, int n)
 {
 	Mobj *mo;
 
-	mo = emalloc(sizeof *mo);
-	mo->o = o;
-	mo->p.x = m->x;
-	mo->p.y = m->y;
-	if(!canspawn(m, mo)){
-		free(mo);
+	if((mo = mapspawn(x, y, o)) == nil)
 		return -1;
-	}
-	mo->x = m->x / Tlsubwidth;
-	mo->y = m->y / Tlsubheight;
 	mo->team = n;
-	mo->f = o->f;
-	mo->hp = o->hp;
-	mo->zl = lalloc(mo, 1);
-	llink(mo->zl, &m->lo);
-	mo->blk = lalloc(mo, mo->o->w * (Tlwidth / Tlsubwidth) * mo->o->h * (Tlheight / Tlsubheight));
-	setblk(mo, 0);
 	mo->pics = &mo->o->pidle;
 	if(mo->f & Fbuild)
 		team[n].nbuild++;
@@ -218,7 +149,10 @@
 {
 	int Δθ;
 
-	Δθ = mo->Δθ < 0 ? -1 : 1;
+	if(mo->Δθ < 0)
+		Δθ = mo->Δθ < -4 ? -4 : mo->Δθ;
+	else
+		Δθ = mo->Δθ > 4 ? 4 : mo->Δθ;
 	mo->θ = mo->θ + Δθ & Nrot - 1;
 	mo->Δθ -= Δθ;
 }
@@ -226,111 +160,132 @@
 static int
 trymove(Mobj *mo)
 {
-	int Δr, sx, sy;
-	Point subΔr, subp, p, pp;
+	int x, y, sx, sy, Δx, Δy, Δu, Δv, Δrx, Δry, Δpx, Δpy;
 
-	subΔr.x = mo->vx * mo->vv * (1 << Tlshift);
-	subΔr.y = mo->vy * mo->vv * (1 << Tlshift);
-	sx = subΔr.x < 0 ? -1 : 1;
-	sy = subΔr.y < 0 ? -1 : 1;
-	subΔr.x *= sx;
-	subΔr.y *= sy;
-	Δr = sx * (mo->pathp[-1].x - mo->p.x << Tlshift) - mo->subp.x;
-	if(subΔr.x > Δr)
-		subΔr.x = Δr;
-	Δr = sy * (mo->pathp[-1].y - mo->p.y << Tlshift) - mo->subp.y;
-	if(subΔr.y > Δr)
-		subΔr.y = Δr;
-	while(subΔr.x > 0 || subΔr.y > 0){
-		p = mo->p;
-		subp = mo->subp;
-		if(subΔr.x > 0){
-			Δr = (Tlsubwidth << Tlshift) - subp.x;
-			if(Δr <= subΔr.x){
-				p.x += sx * Tlsubwidth;
-				subp.x = 0;
-			}else{
-				subp.x += subΔr.x;
-				p.x += sx * (subp.x >> Tlshift);
-				subp.x &= (1 << Tlshift) - 1;
-			}
-			subΔr.x -= Δr;
+	markmobj(mo, 0);
+	sx = mo->subpx;
+	sy = mo->subpy;
+	Δu = mo->u * (1 << Subpxshift);
+	Δv = mo->v * (1 << Subpxshift);
+	Δx = abs(Δu);
+	Δy = abs(Δv);
+	Δrx = Δx * mo->speed;
+	Δry = Δy * mo->speed;
+	Δpx = abs((mo->pathp->x * Tlsubwidth << Subpxshift) - sx);
+	Δpy = abs((mo->pathp->y * Tlsubwidth << Subpxshift) - sy);
+	if(Δpx < Δrx)
+		Δrx = Δpx;
+	if(Δpy < Δry)
+		Δry = Δpy;
+	while(Δrx > 0 || Δry > 0){
+		x = mo->x;
+		y = mo->y;
+		if(Δrx > 0){
+			sx += Δu;
+			Δrx -= Δx;
+			if(Δrx < 0)
+				sx += mo->u < 0 ? -Δrx : Δrx;
+			x = (sx >> Subpxshift) + ((sx & Subpxmask) != 0);
+			x /= Tlsubwidth;
 		}
-		if(subΔr.y > 0){
-			Δr = (Tlsubheight << Tlshift) - subp.y;
-			if(Δr <= subΔr.y){
-				p.y += sy * Tlsubheight;
-				subp.y = 0;
-			}else{
-				subp.y += subΔr.y;
-				p.y += sy * (subp.y >> Tlshift);
-				subp.y &= (1 << Tlshift) - 1;
-			}
-			subΔr.y -= Δr;
+		if(Δry > 0){
+			sy += Δv;
+			Δry -= Δy;
+			if(Δry < 0)
+				sy += mo->v < 0 ? -Δry : Δry;
+			y = (sy >> Subpxshift) + ((sy & Subpxmask) != 0);
+			y /= Tlsubwidth;
 		}
-		pp.x = p.x / Tlsubwidth;
-		pp.y = p.y / Tlsubheight;
-		if(mo->x != pp.x || mo->y != pp.y){
-			if(isblocked(&pp, mo))
-				return -1;
-			setblk(mo, 1);
-			mo->x = pp.x;
-			mo->y = pp.y;
-			setblk(mo, 0);
+		if(isblocked(x, y, mo->o))
+			goto end;
+		/* disallow corner coasting */
+		if(x != mo->x && y != mo->y
+		&& (isblocked(x, mo->y, mo->o) || isblocked(mo->x, y, mo->o))){
+			dprint("detected corner coasting %d,%d vs %d,%d\n",
+				x, y, mo->x, mo->y);
+			goto end;
 		}
-		mo->subp = subp;
-		mo->p = p;
+		mo->subpx = sx;
+		mo->subpy = sy;
+		mo->px = sx >> Subpxshift;
+		mo->py = sy >> Subpxshift;
+		mo->x = mo->px / Tlsubwidth;
+		mo->y = mo->py / Tlsubheight;
 	}
+	markmobj(mo, 1);
 	return 0;
+end:
+	werrstr("trymove: can't move to %d,%d", x, y);
+	mo->subpx = mo->px << Subpxshift;
+	mo->subpy = mo->py << Subpxshift;
+	markmobj(mo, 1);
+	return -1;
 }
 
 static void
 stepmove(Mobj *mo)
 {
-	Point pp;
-	Map *m, *m´;
+	int r, n;
 
-	/* FIXME: constant turn speed for now, but is it always so? */
-	/* FIXME: too slow */
+	n = 0;
+restart:
+	n++;
 	if(mo->Δθ != 0){
 		tryturn(mo);
 		return;
 	}
-	m = map + mo->y / (Tlheight / Tlsubheight) * mapwidth
-		+ mo->x / (Tlwidth / Tlsubwidth);
-	/* FIXME: update speed (based on range from src and to target?) */
-	/* FIXME: update speed: accel, decel, turning speed */
-	if(trymove(mo) < 0){
-		mo->vv = 0.0;
-		pp = mo->pathe[-1];
-		fprint(2, "mo %#p blocked at %d,%d goal %d,%d\n", mo, mo->x * Tlsubwidth, mo->y * Tlsubheight, mo->pathp[-1].x, mo->pathp[-1].y);
-		/* FIXME: if path now blocked, move towards target anyway */
-		repath(mo, &pp);
-		return;
+	unlinkmobj(mo->mapp);
+	r = trymove(mo);
+	linktomap(mo);
+	if(r < 0){
+		if(n > 1){
+			fprint(2, "stepmove: %s %#p bug inducing infinite loop!\n",
+				mo->o->name, mo);
+			return;
+		}
+		dprint("stepmove: failed to move: %r\n");
+		if(repath(mo->target, mo) < 0){
+			dprint("stepmove: %s %#p moving towards target: %r\n",
+				mo->o->name, mo);
+			return;
+		}
+		goto restart;
 	}
-	if(mo->p.x == mo->pathp[-1].x && mo->p.y == mo->pathp[-1].y){
-		if(mo->pathp < mo->pathe)
-			nextpath(mo);
-		else{
-			freepath(mo);
-			mo->pics = &mo->o->pidle;
+	if(mo->x == mo->pathp->x && mo->y == mo->pathp->y){
+		mo->pathp++;
+		if(mo->pathp < mo->pathe){
+			nextmove(mo);
+			return;
+		}else if(mo->x == mo->target.x && mo->y == mo->target.y){
+			mo->npatherr = 0;
+			freemove(mo);
+			return;
 		}
+		dprint("stepmove: %s %#p reached final node, but not target\n",
+			mo->o->name, mo);
+		if(mo->goalblocked && isblocked(mo->target.x, mo->target.y, mo->o)){
+			dprint("stepmove: %s %#p goal still blocked, stopping\n",
+				mo->o->name, mo);
+			freemove(mo);
+			return;
+		}
+		if(mo->npatherr++ > 1
+		|| repath(mo->target, mo) < 0){
+			dprint("stepmove: %s %#p trying to find target: %r\n",
+				mo->o->name, mo);
+			mo->npatherr = 0;
+			freemove(mo);
+		}
 	}
-	m´ = map + mo->y / (Tlheight / Tlsubheight) * mapwidth
-		+ mo->x / (Tlwidth / Tlsubwidth);
-	if(m != m´){
-		lunlink(mo->zl);
-		llink(mo->zl, &m´->lo);
-	}
 }
 
 void
 stepsim(void)
 {
-	Lobj *lo;
+	Mobjl *ml, *oml;
 
-	for(lo=vlist.lo; lo!=&vlist; lo=lo->lo)
-		stepmove(lo->mo);
+	for(oml=moving->l, ml=oml->l; oml!=moving; oml=ml, ml=ml->l)
+		stepmove(oml->mo);
 }
 
 static void
--- /dev/null
+++ b/util.c
@@ -1,0 +1,76 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.h>
+#include "dat.h"
+#include "fns.h"
+
+int debug;
+
+int
+max(int a, int b)
+{
+	return a > b ? a : b;
+}
+
+int
+min(int a, int b)
+{
+	return a < b ? a : b;
+}
+
+void
+dprint(char *fmt, ...)
+{
+	char s[256];
+	va_list arg;
+
+	if(!debug)
+		return;
+	va_start(arg, fmt);
+	vseprint(s, s+sizeof s, fmt, arg);
+	va_end(arg);
+	fprint(2, "%s\n", s);
+}
+
+char *
+estrdup(char *s)
+{
+	if((s = strdup(s)) == nil)
+		sysfatal("estrdup: %r");
+	setmalloctag(s, getcallerpc(&s));
+	return s;
+}
+
+void *
+erealloc(void *p, ulong n, ulong oldn)
+{
+	if((p = realloc(p, n)) == nil)
+		sysfatal("realloc: %r");
+	setrealloctag(p, getcallerpc(&p));
+	memset((uchar *)p + oldn, 0, n - oldn);
+	return p;
+}
+
+void *
+emalloc(ulong n)
+{
+	void *p;
+
+	if((p = mallocz(n, 1)) == nil)
+		sysfatal("emalloc: %r");
+	setmalloctag(p, getcallerpc(&n));
+	return p;
+}
+
+vlong
+flen(int fd)
+{
+	vlong l;
+	Dir *d;
+
+	if((d = dirfstat(fd)) == nil) 
+		sysfatal("flen: %r");
+	l = d->length;
+	free(d);
+	return l;
+}