shithub: sce

Download patch

ref: bd88b3b3ca104c8c301ff080dcc2e30415947066
parent: 2cef4a8a6f20f884d368fc98a3a020fba74088af
author: qwx <qwx@sciops.net>
date: Thu Dec 2 11:57:23 EST 2021 

refactoring: use actual vectors and Points

- a bunch of code duplicated what are essentially resizable
arrays; i don't like casting pointers, but not sure what's a
better way
- for pathing, just traverse vector backwards instead of
pushing points in a complicated way
- using Points right now simplifies and clarifies a lot of
code, there's no reason not to use them
- com: stop parsing message if one was invalid since we won't
even get an offset
- don't use anonymous Path struct, names are too confusing

all of this makes a bunch of code easier to look at and
arguably less bug-prone.

regarding the "hashing": an actual hash table wouldn't really
provide any benefits or more guarantees.
the Mobj references (idx/uuid) are a poor man's hash table,
but it's a simple solution to this.


--- a/com.c
+++ b/com.c
@@ -65,9 +65,8 @@
 
 	if((mo = derefmobj(r->idx, r->uuid)) == nil)
 		return nil;
-	if(mo->x != r->x || mo->y != r->y){
-		werrstr("phase error: req mobj at %d,%d, found %M",
-			r->x, r->y, mo);
+	if(!eqpt(mo->Point, r->Point)){
+		werrstr("phase error: req mobj at %P, found %M", r->Point, mo);
 		return nil;
 	}
 	return mo;
@@ -221,9 +220,10 @@
 			return 0;
 		default: fprint(2, "parsemsg: invalid message type %ux\n", type); return -1;
 		}
-		if((n = fn(p, e)) < 0)
+		if((n = fn(p, e)) < 0){
 			fprint(2, "parsemsg: %r\n");
-		else
+			return -1;
+		}else
 			p += n;
 	}
 	return 0;
--- a/dat.h
+++ b/dat.h
@@ -16,6 +16,7 @@
 typedef struct Team Team;
 typedef struct Cbuf Cbuf;
 typedef struct Msg Msg;
+typedef struct Vector Vector;
 
 enum{
 	Nresource = 3,
@@ -36,9 +37,11 @@
 	Subpxmask = (1 << Subpxshift) - 1,
 };
 
-enum{
-	Bshift = 6,
-	Bmask = (1 << Bshift) - 1,
+struct Vector{
+	void *p;
+	ulong n;
+	ulong bufsz;
+	int firstempty;
 };
 
 struct Pairheap{
@@ -49,9 +52,12 @@
 	Pairheap *right;
 };
 
+enum{
+	Bshift = 6,
+	Bmask = (1 << Bshift) - 1,
+};
 struct Node{
-	int x;
-	int y;
+	Point;
 	int closed;
 	int open;
 	double g;
@@ -166,13 +172,11 @@
 };
 struct Path{
 	Point target;
-	int goalblocked;
-	int npatherr;
-	int npathbuf;
-	double pathlen;
-	Point *paths;
-	Point *pathp;
-	Point *pathe;
+	int blocked;
+	double dist;
+	Vector moves;
+	Point *step;
+	int nerr;
 };
 struct Mresource{
 	int amount;
@@ -185,7 +189,7 @@
 	double θ;
 	double Δθ;
 	int Δθs;
-	Path;
+	Path path;
 	double u;
 	double v;
 	double speed;
@@ -252,12 +256,8 @@
 	int r[Nresource];
 	int nunit;
 	int nbuild;
-	Mobj **mo;
-	int sz;
-	int firstempty;
-	Mobj **drop;
-	int dropsz;
-	int ndrop;
+	Vector mobj;
+	Vector drops;
 };
 extern Team teams[Nteam];
 extern int nteam;
--- a/drw.c
+++ b/drw.c
@@ -292,9 +292,10 @@
 {
 	int x, y;
 	u64int *row, v, m;
+	Point *p;
+	Path *pp;
 	Node *n;
 	Mobj *mo;
-	Point *p;
 
 	r = Rpt(mulpt(r.min, Node2Tile), mulpt(r.max, Node2Tile));
 	for(y=r.min.y, n=nodemap+y*nodemapwidth+r.min.x; y<r.max.y; y++){
@@ -310,16 +311,19 @@
 			if(v & m)
 				compose(x, y, 0xff0000);
 			if(n->closed)
-				compose(x, y, 0x0000ff);
+				compose(x, y, 0x000077);
 			else if(n->open)
-				compose(x, y, 0xffff00);
+				compose(x, y, 0x007777);
 		}
 		n += nodemapwidth - (r.max.x - r.min.x);
 	}
-	if((mo = selected[0]) != nil && mo->pathp != nil){
-		for(p=mo->paths; p<mo->pathe; p++)
+	if((mo = selected[0]) != nil){
+		pp = &mo->path;
+		if(pp->step == nil)
+			return;
+		for(p=pp->step; p>=pp->moves.p; p--)
 			compose(p->x / Nodewidth, p->y / Nodeheight, 0x00ff00);
-		compose(mo->target.x, mo->target.y, 0x00ffff);
+		compose(pp->target.x, pp->target.y, 0x00ff77);
 	}
 }
 
--- a/fns.h
+++ b/fns.h
@@ -46,15 +46,15 @@
 double	octdist(Node*, Node*);
 void	setgoal(Point*, Mobj*, Mobj*);
 Mobj*	unitat(int, int);
-int	isblocked(int, int, Obj*);
+int	isblocked(Point, Obj*);
 void	markmobj(Mobj*, int);
 int	isnextto(Mobj*, Mobj*);
 int	findpath(Point, Mobj*);
-Mobj*	mapspawn(int, int, Obj*);
+Mobj*	mapspawn(Point, Obj*);
 void	initmap(void);
 Mobj*	derefmobj(int, long);
-int	spawnunit(int, int, Obj*, int);
-int	spawnresource(int, int, Obj*, int);
+int	spawnunit(Point, Obj*, int);
+int	spawnresource(Point, Obj*, int);
 void	nukequeue(Pairheap**);
 Pairheap*	popqueue(Pairheap**);
 void	decreasekey(Pairheap*, double, Pairheap**);
@@ -70,6 +70,9 @@
 void	dprint(char *, ...);
 int	max(int, int);
 int	min(int, int);
+void	clearvec(Vector*, int);
+void*	pushsparsevec(Vector*, void*);
+void*	pushvec(Vector*, void*, int);
 char*	estrdup(char*);
 void*	erealloc(void*, ulong, ulong);
 void*	emalloc(ulong);
--- a/fs.c
+++ b/fs.c
@@ -15,8 +15,7 @@
 struct Objp{
 	Obj *o;
 	int resource;
-	int x;
-	int y;
+	Point;
 	int team;
 	int amount;
 };
@@ -605,20 +604,19 @@
 static void
 initmapobj(void)
 {
-	int x, y;
 	Objp *op;
 	Map *m;
+	Point p;
 
 	for(m=map; m<map+mapwidth*mapheight; m++)
 		m->ml.l = m->ml.lp = &m->ml;
 	for(op=objp; op<objp+nobjp; op++){
-		x = op->x * Node2Tile;
-		y = op->y * Node2Tile;
+		p = mulpt(op->Point, Node2Tile);
 		if(op->resource){
-			if(spawnresource(x, y, op->o, op->amount) < 0)
-				sysfatal("initmapobj: %s at %d,%d: %r", op->o->name, op->x, op->y);
-		}else if(spawnunit(x, y, op->o, op->team) < 0)
-			sysfatal("initmapobj: %s team %d at %d,%d: %r", op->o->name, op->team, op->x, op->y);
+			if(spawnresource(p, op->o, op->amount) < 0)
+				sysfatal("initmapobj: %s at %P: %r", op->o->name, op->Point);
+		}else if(spawnunit(p, op->o, op->team) < 0)
+			sysfatal("initmapobj: %s team %d at %P: %r", op->o->name, op->team, op->Point);
 	}
 	free(objp);
 }
--- a/map.c
+++ b/map.c
@@ -14,10 +14,10 @@
 {
 	Mobj *bmo;
 
-	if(isblocked(mo->x, mo->y, mo->o)){
+	if(isblocked(mo->Point, mo->o)){
 		bmo = unitat(mo->x, mo->y);
-		sysfatal("markmobj: attempt to place %s at %d,%d, non-free block having %s at %d,%d",
-			mo->o->name, mo->x, mo->y, bmo->o->name, bmo->x, bmo->y);
+		sysfatal("markmobj: attempt to place %s at %P, non-free block having %s at %P",
+			mo->o->name, mo->Point, bmo->o->name, bmo->Point);
 	}
 	linktomap(mo);
 	markmobj(mo, 1);
@@ -24,51 +24,52 @@
 }
 
 static int
-findspawn(int *nx, int *ny, int ofs, Obj *o, Obj *spawn)
+findspawn(Point *pp, int ofs, Obj *o, Obj *spawn)
 {
-	int x, y, minx, miny, maxx, maxy;
+	int minx, miny, maxx, maxy;
+	Point p;
 
-	minx = *nx - (ofs+1) * o->w;
-	miny = *ny - (ofs+1) * o->h;
-	maxx = *nx + spawn->w + ofs * o->w;
-	maxy = *ny + spawn->h + ofs * o->h;
-	for(x=minx+o->w, y=maxy; x<maxx; x++)
-		if(!isblocked(x, y, o))
+	p = *pp;
+	minx = p.x - (ofs+1) * o->w;
+	miny = p.y - (ofs+1) * o->h;
+	maxx = p.x + spawn->w + ofs * o->w;
+	maxy = p.y + spawn->h + ofs * o->h;
+	for(p.x=minx+o->w, p.y=maxy; p.x<maxx; p.x++)
+		if(!isblocked(p, o))
 			goto found;
-	for(x=maxx, y=maxy; y>miny; y--)
-		if(!isblocked(x, y, o))
+	for(p.x=maxx, p.y=maxy; p.y>miny; p.y--)
+		if(!isblocked(p, o))
 			goto found;
-	for(x=maxx, y=miny; x>minx; x--)
-		if(!isblocked(x, y, o))
+	for(p.x=maxx, p.y=miny; p.x>minx; p.x--)
+		if(!isblocked(p, o))
 			goto found;
-	for(x=minx, y=miny; y<=maxy; y++)
-		if(!isblocked(x, y, o))
+	for(p.x=minx, p.y=miny; p.y<=maxy; p.y++)
+		if(!isblocked(p, o))
 			goto found;
 	return -1;
 found:
-	*nx = x;
-	*ny = y;
+	*pp = p;
 	return 0;
 }
 
 static int
-getspawn(int *nx, int *ny, Obj *o)
+getspawn(Point *pp, Obj *o)
 {
-	int n, x, y;
+	int n;
+	Point p;
 	Map *m;
 	Mobjl *ml;
 	Mobj *mo;
 	Obj **os;
 
-	x = *nx;
-	y = *ny;
+	p = *pp;
 	if(o->f & (Fbuild|Fimmutable)){
-		if(isblocked(x, y, o)){
-			werrstr("getspawn: building placement at %d,%d blocked", x, y);
+		if(isblocked(p, o)){
+			werrstr("getspawn: building placement at %P blocked", p);
 			return -1;
 		}
 	}else{
-		m = map + y / Node2Tile * mapwidth + x / Node2Tile;
+		m = map + p.y / Node2Tile * mapwidth + p.x / Node2Tile;
 		for(mo=nil, ml=m->ml.l; ml!=&m->ml; ml=ml->l){
 			mo = ml->mo;
 			for(os=mo->o->spawn, n=mo->o->nspawn; n>0; n--, os++)
@@ -78,40 +79,38 @@
 				break;
 		}
 		if(ml == &m->ml){
-			werrstr("getspawn: no spawn object at %d,%d", x, y);
+			werrstr("getspawn: no spawn object at %P", p);
 			return -1;
 		}
 		for(n=0; n<3; n++)
-			if(findspawn(&x, &y, n, o, mo->o) >= 0)
+			if(findspawn(&p, n, o, mo->o) >= 0)
 				break;
 		if(n == 3){
-			werrstr("getspawn: no free spot for %s at %d,%d",
-				o->name, x, y);
+			werrstr("getspawn: no free spot for %s at %P",
+				o->name, p);
 			return -1;
 		}
 	}
-	*nx = x;
-	*ny = y;
+	*pp = p;
 	return 0;
 }
 
 Mobj *
-mapspawn(int x, int y, Obj *o)
+mapspawn(Point p, Obj *o)
 {
 	Mobj *mo;
 
-	if(o->f & (Fbuild|Fimmutable) && (x & Node2Tile-1 || y & Node2Tile-1)){
-		werrstr("mapspawn: building spawn %d,%d not aligned to tile map", x, y);
+	if(o->f & (Fbuild|Fimmutable) && (p.x & Node2Tile-1 || p.y & Node2Tile-1)){
+		werrstr("mapspawn: building spawn %P not aligned to tile map", p);
 		return nil;
 	}
-	if(getspawn(&x, &y, o) < 0)
+	if(getspawn(&p, o) < 0)
 		return nil;
 	mo = emalloc(sizeof *mo);
 	mo->uuid = lrand();
-	mo->x = x;
-	mo->y = y;
-	mo->px = x * Nodewidth;
-	mo->py = y * Nodeheight;
+	mo->Point = p;
+	mo->px = p.x * Nodewidth;
+	mo->py = p.y * Nodeheight;
 	mo->subpx = mo->px << Subpxshift;
 	mo->subpy = mo->py << Subpxshift;
 	mo->o = o;
--- a/path.c
+++ b/path.c
@@ -67,13 +67,13 @@
 }
 
 int
-isblocked(int x, int y, Obj *o)
+isblocked(Point p, Obj *o)
 {
 	u64int *row;
 
 	if(o->f & Fair)
 		return 0;
-	row = bload(x, y, o->w, o->h, 0, 0, 0, 0);
+	row = bload(p.x, p.y, o->w, o->h, 0, 0, 0, 0);
 	return (*row & 1ULL << 63) != 0;
 }
 
@@ -406,42 +406,34 @@
 }
 
 static void
-resizepathbuf(Mobj *mo, int nstep)
-{
-	if(mo->npathbuf >= nstep)
-		return;
-	nstep = nstep + 16;
-	mo->paths = erealloc(mo->paths, nstep * sizeof mo->paths, mo->npathbuf * sizeof mo->paths);
-	mo->npathbuf = nstep;
-}
-
-static void
 directpath(Node *a, Node *g, Mobj *mo)
 {
-	resizepathbuf(mo, 1);
-	mo->pathlen = eucdist(a, g);
-	mo->pathe = mo->paths + 1;
-	mo->paths->x = g->x * Nodewidth;
-	mo->paths->y = g->y * Nodewidth;
+	Point p;
+	Path *pp;
+
+	pp = &mo->path;
+	pp->dist = eucdist(a, g);
+	clearvec(&pp->moves, sizeof p);
+	p = Pt(g->x * Nodewidth, g->y * Nodeheight);
+	pushvec(&pp->moves, &p, sizeof p);
+	pp->step = (Point *)pp->moves.p + pp->moves.n - 1;
 }
 
 static void
 backtrack(Node *n, Node *a, Mobj *mo)
 {
-	int x, y;
-	Point *p;
+	Point p;
+	Path *pp;
 
+	pp = &mo->path;
 	assert(n != a && n->step > 0);
-	resizepathbuf(mo, n->step);
-	mo->pathlen = n->len;
-	p = mo->paths + n->step;
-	mo->pathe = p--;
+	pp->dist = n->len;
+	clearvec(&pp->moves, sizeof p);
 	for(; n!=a; n=n->from){
-		x = n->x * Nodewidth;
-		y = n->y * Nodeheight;
-		*p-- = (Point){x, y};
+		p = Pt(n->x * Nodewidth, n->y * Nodeheight);
+		pushvec(&pp->moves, &p, sizeof p);
 	}
-	assert(p == mo->paths - 1);
+	pp->step = (Point *)pp->moves.p + pp->moves.n - 1;
 }
 
 int
@@ -474,7 +466,7 @@
 	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)){
+		while(!isblocked(Pt(x, y), mo->o)){
 			m = nodemap + y * nodemapwidth + x;
 			m->x = x;
 			m->y = y;
@@ -502,10 +494,10 @@
 	Node *n1, *n2, *pm;
 
 	if(mo->o->f & Fair || block == nil){
-		mo->goalblocked = 0;
+		mo->path.blocked = 0;
 		return;
 	}
-	mo->goalblocked = 1;
+	mo->path.blocked = 1;
 	dprint("%M setgoal: moving goal %d,%d in block %#p ", mo, p->x, p->y, block);
 	pm = nodemap + p->y * nodemapwidth + p->x;
 	pm->x = p->x;
--- a/sce.c
+++ b/sce.c
@@ -191,6 +191,8 @@
 	if(prefix == nil)
 		prefix = smprint("/sys/games/lib/%s", progname);
 	srand(time(nil));
+	fmtinstall('P', Pfmt);
+	fmtinstall('R', Rfmt);
 	fmtinstall('M', mobjfmt);
 	initfs();
 	initsv(tv, *argv);
--- a/sim.c
+++ b/sim.c
@@ -42,8 +42,9 @@
 void
 refmobj(Mobj *mo)
 {
-	int n, i;
+	int n;
 	Team *t;
+	Mobj **p;
 
 	mo->mobjl = linkmobj(mobjl, mo, nil);
 	t = teams + mo->team;
@@ -51,24 +52,11 @@
 		t->nbuild++;
 	else
 		t->nunit++;
-	n = t->firstempty;
-	if(n == t->sz){
-		t->mo = erealloc(t->mo, (t->sz + 32) * sizeof *t->mo, t->sz * sizeof *t->mo);
-		t->sz += 32;
-	}
-	t->mo[n] = mo;
+	p = pushsparsevec(&t->mobj, &mo);
+	n = p - (Mobj **)t->mobj.p;
 	mo->idx = mo->team << Teamshift | n;
-	for(i=t->firstempty+1; i<t->sz; i++)
-		if(t->mo[i] == nil)
-			break;
-	t->firstempty = i;
-	if(mo->o->f & Fdropoff){
-		if(t->ndrop == t->dropsz){
-			t->drop = erealloc(t->drop, (t->dropsz + 32) * sizeof *t->drop, t->dropsz * sizeof *t->drop);
-			t->dropsz += 32;
-		}
-		t->drop[t->ndrop++] = mo;
-	}
+	if(mo->o->f & Fdropoff)
+		pushvec(&t->drops, &mo, sizeof mo);
 }
 
 void
--- a/sim.move.c
+++ b/sim.move.c
@@ -67,15 +67,16 @@
 nextpathnode(Mobj *mo)
 {
 	resetcoords(mo);
-	facegoal(*mo->pathp, mo);
+	facegoal(*mo->path.step, mo);
 }
 
 static void
 clearpath(Mobj *mo)
 {
-	mo->speed = 0.0;
-	mo->pathp = nil;
 	resetcoords(mo);
+	mo->speed = 0.0;
+	mo->path.step = nil;
+	clearvec(&mo->path.moves, sizeof *mo->path.step);
 }
 
 static void
@@ -82,10 +83,10 @@
 cleanup(Mobj *mo)
 {
 	clearpath(mo);
-	mo->target = (Point){0,0};
-	mo->goalblocked = 0;
-	mo->pathlen = 0.0;
-	mo->npatherr = 0;
+	mo->path.target = (Point){0,0};
+	mo->path.blocked = 0;
+	mo->path.dist = 0.0;
+	mo->path.nerr = 0;
 }
 
 static void
@@ -125,12 +126,11 @@
 repath(Point p, Mobj *mo)
 {
 	clearpath(mo);
-	mo->target = p;
+	mo->path.target = p;
 	if(findpath(p, mo) < 0){
 		mo->θ = facegoal(p, mo);
 		return -1;
 	}
-	mo->pathp = mo->paths;
 	nextpathnode(mo);
 	return 0;
 }
@@ -138,7 +138,7 @@
 static void
 accelerate(Mobj *mo)
 {
-	if(1 + mo->pathlen < (mo->speed / 8) * (mo->speed / 8) / 2 / (mo->o->accel / 8)){
+	if(1 + mo->path.dist < (mo->speed / 8) * (mo->speed / 8) / 2 / (mo->o->accel / 8)){
 		mo->speed -= mo->o->accel;
 		if(mo->speed < 0.0)
 			mo->speed = 0.0;
@@ -152,8 +152,9 @@
 static int
 trymove(Mobj *mo)
 {
-	int x, y, px, py, sx, sy, Δx, Δy, Δu, Δv, Δrx, Δry, Δpx, Δpy;
+	int px, py, sx, sy, Δx, Δy, Δu, Δv, Δrx, Δry, Δpx, Δpy;
 	double dx, dy;
+	Point p;
 
 	markmobj(mo, 0);
 	px = mo->px;
@@ -166,22 +167,21 @@
 	Δy = abs(Δv);
 	Δrx = fabs(mo->u * mo->speed) * (1 << Subpxshift);
 	Δry = fabs(mo->v * mo->speed) * (1 << Subpxshift);
-	Δpx = abs((mo->pathp->x << Subpxshift) - sx);
-	Δpy = abs((mo->pathp->y << Subpxshift) - sy);
+	Δpx = abs((mo->path.step->x << Subpxshift) - sx);
+	Δpy = abs((mo->path.step->y << Subpxshift) - sy);
 	if(Δpx < Δrx)
 		Δrx = Δpx;
 	if(Δpy < Δry)
 		Δry = Δpy;
 	while(Δrx > 0 || Δry > 0){
-		x = mo->x;
-		y = mo->y;
+		p = mo->Point;
 		if(Δrx > 0){
 			sx += Δu;
 			Δrx -= Δx;
 			if(Δrx < 0)
 				sx += mo->u < 0 ? -Δrx : Δrx;
-			x = (sx >> Subpxshift) + ((sx & Subpxmask) != 0);
-			x /= Nodewidth;
+			p.x = (sx >> Subpxshift) + ((sx & Subpxmask) != 0);
+			p.x /= Nodewidth;
 		}
 		if(Δry > 0){
 			sy += Δv;
@@ -188,16 +188,16 @@
 			Δry -= Δy;
 			if(Δry < 0)
 				sy += mo->v < 0 ? -Δry : Δry;
-			y = (sy >> Subpxshift) + ((sy & Subpxmask) != 0);
-			y /= Nodewidth;
+			p.y = (sy >> Subpxshift) + ((sy & Subpxmask) != 0);
+			p.y /= Nodewidth;
 		}
-		if(isblocked(x, y, mo->o))
+		if(isblocked(p, 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("%M detected corner coasting at %d,%d\n",
-				mo, x, y);
+		if(p.x != mo->x && p.y != mo->y
+		&& (isblocked(Pt(p.x, mo->y), mo->o)
+		|| isblocked(Pt(mo->x, p.y), mo->o))){
+			dprint("%M detected corner coasting at %P\n", mo, p);
 			goto end;
 		}
 		mo->subpx = sx;
@@ -212,10 +212,10 @@
 	dx *= dx;
 	dy = mo->py - py;
 	dy *= dy;
-	mo->pathlen -= sqrt(dx + dy) / Nodewidth;
+	mo->path.dist -= sqrt(dx + dy) / Nodewidth;
 	return 0;
 end:
-	werrstr("trymove: can't move to %d,%d", x, y);
+	werrstr("trymove: can't move to %P", p);
 	mo->subpx = mo->px << Subpxshift;
 	mo->subpy = mo->py << Subpxshift;
 	markmobj(mo, 1);
@@ -223,7 +223,7 @@
 	dx *= dx;
 	dy = mo->py - py;
 	dy *= dy;
-	mo->pathlen -= sqrt(dx + dy) / Nodewidth;
+	mo->path.dist -= sqrt(dx + dy) / Nodewidth;
 	return -1;
 }
 
@@ -270,7 +270,7 @@
 static int
 nodereached(Mobj *mo)
 {
-	return mo->px == mo->pathp->x && mo->py == mo->pathp->y;
+	return mo->px == mo->path.step->x && mo->py == mo->path.step->y;
 }
 
 static void
@@ -287,9 +287,9 @@
 			fprint(2, "%M stepmove: bug: infinite loop!\n", mo);
 			return;
 		}
-		dprint("%M stepmove: failed moving from %d,%d to %d,%d: %r\n",
-			mo, mo->px, mo->py, mo->pathp->x, mo->pathp->y);
-		if(repath(mo->target, mo) < 0){
+		dprint("%M stepmove: failed moving from %d,%d to %P: %r\n",
+			mo, mo->px, mo->py, *mo->path.step);
+		if(repath(mo->path.target, mo) < 0){
 			dprint("%M stepmove: failed moving towards target: %r\n", mo);
 			abortcommands(mo);
 			return;
@@ -299,11 +299,11 @@
 	}
 	if(!nodereached(mo))
 		return;
-	mo->pathp++;
-	if(mo->pathp < mo->pathe){
+	mo->path.step--;
+	if(mo->path.step >= mo->path.moves.p){
 		nextpathnode(mo);
 		return;
-	}else if(mo->x == mo->target.x && mo->y == mo->target.y){
+	}else if(eqpt(mo->Point, mo->path.target)){
 		movedone(mo);
 		return;
 	}
@@ -314,13 +314,13 @@
 		return;
 	}
 	dprint("%M stepmove: reached final node, but not target\n", mo);
-	if(mo->goalblocked && isblocked(mo->target.x, mo->target.y, mo->o)){
+	if(mo->path.blocked && isblocked(mo->path.target, mo->o)){
 		dprint("%M stepmove: goal still blocked, stopping\n", mo);
 		abortmove(mo);
 		return;
 	}
 	dprint("%M stepmove: trying again\n", mo);
-	if(mo->npatherr++ > 1 || repath(mo->target, mo) < 0){
+	if(mo->path.nerr++ > 1 || repath(mo->path.target, mo) < 0){
 		dprint("%M stepmove: still can't reach target: %r\n", mo);
 		abortmove(mo);
 		return;
--- a/sim.return.c
+++ b/sim.return.c
@@ -48,20 +48,19 @@
 {
 	double d, d´;
 	Team *t;
-	Mobj *wo, *w, **wp;
+	Mobj *wo, *w, **wp, **we;
 	Node *a, *b;
 
 	t = teams + mo->team;
-	if(t->ndrop <= 0){
+	if(t->drops.n < 1){
 		werrstr("no drops");
 		return nil;
 	}
-	assert(t->drop != nil);
 	a = nodemap + mo->y * nodemapwidth + mo->x;
 	a->x = mo->x;
 	a->y = mo->y;
 	d = nodemapwidth * nodemapheight;
-	for(wp=t->drop, wo=nil; wp<t->drop+t->ndrop; t++){
+	for(wp=t->drops.p, we=wp+t->drops.n, wo=nil; wp<we; wp++){
 		w = *wp;
 		b = nodemap + w->y * nodemapwidth + w->x;
 		b->x = w->x;
--- a/sim.spawn.c
+++ b/sim.spawn.c
@@ -18,7 +18,7 @@
 	}
 	t = teams + n;
 	n = idx & Teamidxmask;
-	if(n > t->sz || (mo = t->mo[n]) == nil){
+	if(n >= t->mobj.n || (mo = ((Mobj **)t->mobj.p)[n]) == nil){
 		werrstr("mobj index %d out of bounds or missing", n);
 		return nil;
 	}
@@ -31,11 +31,11 @@
 }
 
 int
-spawnunit(int x, int y, Obj *o, int team)
+spawnunit(Point p, Obj *o, int team)
 {
 	Mobj *mo;
 
-	if((mo = mapspawn(x, y, o)) == nil)
+	if((mo = mapspawn(p, o)) == nil)
 		return -1;
 	mo->team = team;
 	mo->θ = frand() * 256;
@@ -46,7 +46,7 @@
 }
 
 int
-spawnresource(int x, int y, Obj *o, int amount)
+spawnresource(Point p, Obj *o, int amount)
 {
 	Mobj *mo;
 
@@ -54,7 +54,7 @@
 		werrstr("spawnresource: invalid amount");
 		return -1;
 	}
-	if((mo = mapspawn(x, y, o)) == nil)
+	if((mo = mapspawn(p, o)) == nil)
 		return -1;
 	mo->team = 0;
 	mo->amount = amount;
--- a/util.c
+++ b/util.c
@@ -6,6 +6,10 @@
 
 int debug;
 
+enum{
+	Nvecinc = 32,
+};
+
 int
 max(int a, int b)
 {
@@ -26,7 +30,7 @@
 	mo = va_arg(fmt->args, Mobj*);
 	if(mo == nil)
 		return fmtstrcpy(fmt, "[]");
-	return fmtprint(fmt, "[%s:%#p:%d,%d]", mo->o->name, mo, mo->x, mo->y);
+	return fmtprint(fmt, "[%s:%#p:%P]", mo->o->name, mo, mo->Point);
 }
 
 void
@@ -41,6 +45,53 @@
 	vseprint(s, s+sizeof s, fmt, arg);
 	va_end(arg);
 	fprint(2, "%s", s);
+}
+
+void
+clearvec(Vector *v, int sz)
+{
+	if(v->p == nil)
+		return;
+	memset(v->p, 0, v->bufsz * sz);
+	v->firstempty = 0;
+	v->n = 0;
+}
+
+void *
+pushsparsevec(Vector *v, void *e)
+{
+	int i;
+	uchar *p, *q;
+
+	i = v->firstempty;
+	if(i == v->bufsz){
+		v->p = erealloc(v->p, (v->bufsz + Nvecinc) * sizeof e,
+			v->bufsz * sizeof e);
+		v->bufsz += Nvecinc;
+	}
+	p = (uchar *)v->p + i * sizeof e;
+	memcpy(p, e, sizeof e);
+	for(i++, q=p+1; i<v->n; q++, i++)
+		if(memcmp(p, nil, sizeof p) == 0)
+			break;
+	v->firstempty = i;
+	v->n++;
+	return p;
+}
+
+void *
+pushvec(Vector *v, void *e, int sz)
+{
+	void *p;
+
+	if(v->n == v->bufsz){
+		v->p = erealloc(v->p, (v->bufsz + Nvecinc) * sz, v->bufsz * sz);
+		v->bufsz += Nvecinc;
+	}
+	p = (uchar *)v->p + v->n * sz;
+	memcpy(p, e, sz);
+	v->n++;
+	return p;
 }
 
 char *