shithub: sce

Download patch

ref: db005316eeb552c68b6c54c7392bc119a69b12e0
parent: 061c814196f6de2003d37dba588360267e6822d9
author: qwx <qwx@sciops.net>
date: Wed Mar 31 14:53:23 EDT 2021 

clear distinction between map and node grids and misc fixes

- biggest change: move obj lists to map grid rather than node grid:
the idea was to attempt to find a better compromise between looking
up units for drawing and selection, etc.  map objects can be bigger
than both map and node grids, but we want minimum redundancy, so we
only store object lists in one place.  we don't want to redraw the
same object multiple times when scanning the drawing window, but we
also want to be able to easily look up map objects at a given
coordinate (client select or server map manipulation).  we could
segment the map as with k-d trees or r-trees variants, but this
blows up complexity for nothing.  quadtrees would still work with
buckets of units and don't solve overlaps.
previously, we just enlarged the search window to make sure we don't
miss units that are farther back (x or y axis) than the given node,
and it doesn't seem we can do better.
besides renaming and cleaning up everything for clarity, moving
object lists to the map grid reduces the number of nodes to scan by
a factor of 4.  we enlarge draw window 256px top and left (largest
unit assumed between 128 and 256px at most), and take scale into
account.
the problem really isn't completely solved either way: air/ground
units can overlap (esp. flocks of air units), and there has to be
some kind of heuristic to pick one out of all intersects.  ground
units intersect building pixels as well.
- unit spawns: don't just check if there is a unit there already,
check if there is a corresponding spawner
- node[] → nodemap, tilemap[] → map, merge Tile and Map structs
as it should be, rename Mobj.mapp → Mobj.mobjl for clarity


--- a/bmap.c
+++ b/bmap.c
@@ -192,14 +192,14 @@
 {
 	int i;
 
-	bmapwidth = (mapwidth >> Bshift) + 2 * Npad;
-	bmapheight = mapheight + 2 * Npad;
-	rbmapwidth = (mapheight >> Bshift) + 2 * Npad;
-	rbmapheight = mapwidth + 2 * Npad;
+	bmapwidth = (nodemapwidth >> Bshift) + 2 * Npad;
+	bmapheight = nodemapheight + 2 * Npad;
+	rbmapwidth = (nodemapheight >> Bshift) + 2 * Npad;
+	rbmapheight = nodemapwidth + 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 + i * nodemapwidth, 0xff, bmapwidth * sizeof *bmap);
 		memset(bmap + (bmapheight - i - 1) * bmapwidth, 0xff,
 			bmapwidth * sizeof *bmap);
 		memset(rbmap + i * rbmapwidth, 0xff, rbmapwidth * sizeof *rbmap);
--- a/dat.h
+++ b/dat.h
@@ -56,7 +56,8 @@
 	Node *from;
 	Pairheap *p;
 };
-extern Node *node;
+extern Node *nodemap;
+extern int nodemapwidth, nodemapheight;
 
 struct Attack{
 	char *name;
@@ -150,7 +151,7 @@
 	double v;
 	double speed;
 	Mobjl *movingp;
-	Mobjl *mapp;
+	Mobjl *mobjl;
 	int f;
 	int team;
 	int hp;
@@ -165,10 +166,8 @@
 struct Tile{
 	Pic *p;
 };
-extern Tile **tilemap;
-extern tilemapwidth, tilemapheight;
-
 struct Map{
+	Tile *t;
 	Mobjl ml;
 };
 extern Map *map;
--- a/drw.c
+++ b/drw.c
@@ -235,7 +235,7 @@
 }
 
 static void
-drawmap(Rectangle *r)
+drawmap(Rectangle r)
 {
 	int x, y;
 	u64int *row, v, m;
@@ -243,12 +243,13 @@
 	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;
+	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++){
+		x = r.min.x;
 		row = baddr(x, y);
 		v = *row++;
 		m = 1ULL << 63 - (x & Bmask);
-		for(; x<r->max.x; x++, n++, m>>=1){
+		for(; x<r.max.x; x++, n++, m>>=1){
 			if(m == 0){
 				v = *row++;
 				m = 1ULL << 63;
@@ -260,7 +261,7 @@
 			else if(n->open)
 				compose(x, y, 0xffff00);
 		}
-		n += mapwidth - (r->max.x - r->min.x);
+		n += nodemapwidth - (r.max.x - r.min.x);
 	}
 	if((mo = selected[0]) != nil && mo->pathp != nil){
 		for(p=mo->paths; p<mo->pathe; p++)
@@ -296,38 +297,46 @@
 	return p;
 }
 
+static Rectangle
+setdrawrect(void)
+{
+	Rectangle r;
+
+	r.min.x = pan.x / scale / Tilewidth;
+	r.min.y = pan.y / scale / Tileheight;
+	r.max.x = r.min.x + (pan.x / scale % Tilewidth != 0);
+	r.max.x += fbw / Tilewidth + (fbw % Tilewidth != 0);
+	if(r.max.x > mapwidth)
+		r.max.x = mapwidth;
+	r.max.y = r.min.y + (pan.y / scale % Tileheight != 0);
+	r.max.y += fbh / Tileheight + (fbh % Tilewidth != 0);
+	if(r.max.y > mapheight)
+		r.max.y = mapheight;
+	/* enlarge window to capture units overlapping multiple tiles;
+	 * seems like the easiest way to take this into account */
+	r.min.x = max(r.min.x - 4 / scale, 0);
+	r.min.y = max(r.min.y - 4 / scale, 0);
+	return r;
+}
+
 void
 redraw(void)
 {
 	int x, y;
-	Rectangle mr, tr;
-	Tile **t;
+	Rectangle r;
 	Map *m;
 	Mobj *mo;
 	Mobjl *ml;
 
 	clearvis();
-	tr.min.x = pan.x / scale / Tilewidth;
-	tr.min.y = pan.y / scale / Tileheight;
-	tr.max.x = tr.min.x + (pan.x / scale % Tilewidth != 0);
-	tr.max.x += fbw / Tilewidth + (fbw % Tilewidth != 0);
-	if(tr.max.x > tilemapwidth)
-		tr.max.x = tilemapwidth;
-	tr.max.y = tr.min.y + (pan.y / scale % Tileheight != 0);
-	tr.max.y += fbh / Tileheight + (fbh % Tilewidth != 0);
-	if(tr.max.y > tilemapheight)
-		tr.max.y = tilemapheight;
-	mr.min.x = max(tr.min.x - 3, 0) * Node2Tile;
-	mr.min.y = max(tr.min.y - 3, 0) * Node2Tile;
-	mr.max.x = tr.max.x * Node2Tile;
-	mr.max.y = tr.max.y * Node2Tile;
-	for(y=tr.min.y, t=tilemap+y*tilemapwidth+tr.min.x; y<tr.max.y; y++){
-		for(x=tr.min.x; x<tr.max.x; x++, t++)
-			drawpic(x*Tilewidth, y*Tileheight, (*t)->p, -1);
-		t += tilemapwidth - (tr.max.x - tr.min.x);
+	r = setdrawrect();
+	for(y=r.min.y, m=map+y*mapwidth+r.min.x; y<r.max.y; y++){
+		for(x=r.min.x; x<r.max.x; x++, m++)
+			drawpic(x*Tilewidth, y*Tileheight, m->t->p, -1);
+		m += mapwidth - (r.max.x - r.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(y=r.min.y, m=map+y*mapwidth+r.min.x; y<r.max.y; y++){
+		for(x=r.min.x; x<r.max.x; x++, m++){
 			for(ml=m->ml.l; ml!=&m->ml; ml=ml->l){
 				mo = ml->mo;
 				if(mo->o->f & Fair)
@@ -341,10 +350,10 @@
 				drawpic(mo->px, mo->py, frm(mo, PTbase), addvis(mo));
 			}
 		}
-		m += mapwidth - (mr.max.x - mr.min.x);
+		m += mapwidth - (r.max.x - r.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(y=r.min.y, m=map+y*mapwidth+r.min.x; y<r.max.y; y++){
+		for(x=r.min.x; x<r.max.x; x++, m++){
 			for(ml=m->ml.l; ml!=&m->ml; ml=ml->l){
 				mo = ml->mo;
 				if(mo->o->f & Fair)
@@ -355,10 +364,10 @@
 				drawpicalpha(mo->px, mo->py, frm(mo, PTglow));
 			}
 		}
-		m += mapwidth - (mr.max.x - mr.min.x);
+		m += mapwidth - (r.max.x - r.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(y=r.min.y, m=map+y*mapwidth+r.min.x; y<r.max.y; y++){
+		for(x=r.min.x; x<r.max.x; x++, m++){
 			for(ml=m->ml.l; ml!=&m->ml; ml=ml->l){
 				mo = ml->mo;
 				if((mo->o->f & Fair) == 0)
@@ -372,10 +381,10 @@
 				drawpic(mo->px, mo->py, frm(mo, PTbase), addvis(mo));
 			}
 		}
-		m += mapwidth - (mr.max.x - mr.min.x);
+		m += mapwidth - (r.max.x - r.min.x);
 	}
 	if(debugmap)
-		drawmap(&mr);
+		drawmap(r);
 	drawhud();
 }
 
@@ -391,13 +400,13 @@
 void
 resetfb(void)
 {
-	fbws = min(mapwidth * Nodewidth * scale, Dx(screen->r));
-	fbh = min(mapheight * Nodeheight * scale, Dy(screen->r));
+	fbws = min(nodemapwidth * Nodewidth * scale, Dx(screen->r));
+	fbh = min(nodemapheight * Nodeheight * 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);
 	p0.y -= (p0.y - screen->r.min.y) % scale;
-	panmax.x = max(Nodewidth * mapwidth * scale - Dx(screen->r), 0);
-	panmax.y = max(Nodeheight * mapheight * scale - Dy(screen->r), 0);
+	panmax.x = max(Nodewidth * nodemapwidth * scale - Dx(screen->r), 0);
+	panmax.y = max(Nodeheight * nodemapheight * scale - Dy(screen->r), 0);
 	if(p0.y < selr.max.y){
 		panmax.y += selr.max.y - p0.y;
 		fbh -= selr.max.y - p0.y;
--- a/fs.c
+++ b/fs.c
@@ -333,16 +333,16 @@
 readmap(char **fld, int n, Table *tab)
 {
 	int x;
-	Tile **t;
+	Map *m;
 
 	if(tab->row == 0){
 		tab->ncol = n;
-		tilemapwidth = n;
-		tilemap = emalloc(tilemapheight * tilemapwidth * sizeof *tilemap);
+		mapwidth = n;
+		map = emalloc(mapheight * n * sizeof *map);
 	}
-	t = tilemap + tab->row * tilemapwidth;
-	for(x=0; x<n; x++, t++)
-		unpack(fld++, "t", t);
+	m = map + tab->row * mapwidth;
+	for(x=0; x<n; x++, m++)
+		unpack(fld++, "t", &m->t);
 }
 
 static void
@@ -463,7 +463,7 @@
 	[Tresource] {"resource", readresource, 2, &nresource},
 	[Tspawn] {"spawn", readspawn, -1, nil},
 	[Ttileset] {"tileset", readtileset, 1, nil},
-	[Tmap] {"map", readmap, -1, &tilemapheight},
+	[Tmap] {"map", readmap, -1, &mapheight},
 	[Tspr] {"spr", readspr, -1, nil},
 };
 
@@ -544,7 +544,10 @@
 initmapobj(void)
 {
 	Objp *op;
+	Map *m;
 
+	for(m=map; m<map+mapwidth*mapheight; m++)
+		m->ml.l = m->ml.lp = &m->ml;
 	for(op=objp; op<objp+nobjp; op++)
 		if(spawn(op->x * Node2Tile, op->y * Node2Tile, op->o, op->team) < 0)
 			sysfatal("initmapobj: %s team %d: %r", op->o->name, op->team);
@@ -596,9 +599,9 @@
 		sysfatal("checkdb: no tileset defined");
 	if(nresource != Nresource)
 		sysfatal("checkdb: incomplete resource specification");
-	if(tilemapwidth % 16 != 0 || tilemapheight % 16 != 0 || tilemapwidth * tilemapheight == 0)
+	if(mapwidth % 16 != 0 || mapheight % 16 != 0 || mapwidth * mapheight == 0)
 		sysfatal("checkdb: map size %d,%d not in multiples of 16",
-			tilemapwidth, tilemapheight);
+			mapwidth, mapheight);
 	if(nteam < 2)
 		sysfatal("checkdb: not enough teams");
 }
--- a/map.c
+++ b/map.c
@@ -4,11 +4,10 @@
 #include "dat.h"
 #include "fns.h"
 
-Tile **tilemap;
-int tilemapwidth, tilemapheight;
 Map *map;
 int mapwidth, mapheight;
-Node *node;
+Node *nodemap;
+int nodemapwidth, nodemapheight;
 
 static void
 updatemap(Mobj *mo)
@@ -50,8 +49,10 @@
 getspawn(int *nx, int *ny, Obj *o)
 {
 	int n, x, y;
-	Mobj *mo;
 	Map *m;
+	Mobjl *ml;
+	Mobj *mo;
+	Obj **os;
 
 	x = *nx;
 	y = *ny;
@@ -61,12 +62,19 @@
 			return -1;
 		}
 	}else if((o->f & Fair) == 0){
-		m = map + y * mapwidth + x;
-		if(m->ml.l == &m->ml || m->ml.l->mo == nil){
+		m = map + (y * mapwidth + 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++)
+				if(*os == o)
+					break;
+			if(n > 0)
+				break;
+		}
+		if(ml == &m->ml){
 			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;
@@ -110,15 +118,8 @@
 void
 initmap(void)
 {
-	int n;
-	Map *m;
-
-	mapwidth = tilemapwidth * Node2Tile;
-	mapheight = tilemapheight * Node2Tile;
-	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;
+	nodemapwidth = mapwidth * Node2Tile;
+	nodemapheight = mapheight * Node2Tile;
+	nodemap = emalloc(nodemapwidth * nodemapheight * sizeof *nodemap);
 	initbmap();
 }
--- a/path.c
+++ b/path.c
@@ -62,7 +62,7 @@
 clearpath(void)
 {
 	nukequeue(&queue);
-	memset(node, 0, mapwidth * mapheight * sizeof *node);
+	memset(nodemap, 0, nodemapwidth * nodemapheight * sizeof *nodemap);
 	nearest = nil;
 }
 
@@ -160,8 +160,8 @@
 	}
 	if(end)
 		return nil;
-	assert(x < mapwidth && y < mapheight);
-	n = node + y * mapwidth + x;
+	assert(x < nodemapwidth && y < nodemapheight);
+	n = nodemap + y * nodemapwidth + x;
 	n->x = x;
 	n->y = y;
 	n->Δg = steps;
@@ -195,8 +195,8 @@
 		if(ofs1 == 0 || ofs2 == 0)
 			return nil;
 	}
-	assert(x < mapwidth && y < mapheight);
-	n = node + y * mapwidth + x;
+	assert(x < nodemapwidth && y < nodemapheight);
+	n = nodemap + y * nodemapwidth + x;
 	n->x = x;
 	n->y = y;
 	n->Δg = steps;
@@ -405,7 +405,7 @@
 		x = n->x + dirtab[i].x;
 		y = n->y + dirtab[i].y;
 		while(!isblocked(x, y, mo->o)){
-			m = node + y * mapwidth + x;
+			m = nodemap + y * nodemapwidth + x;
 			m->x = x;
 			m->y = y;
 			m->h = octdist(m, b);
@@ -437,14 +437,14 @@
 	}
 	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 = nodemap + p->y * nodemapwidth + 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;
+	n1 = nodemap + y * nodemapwidth + x;
+	n2 = n1 + (block->o->h - 1) * nodemapwidth;
 	for(e=x+block->o->w; x<e; x++, n1++, n2++){
 		n1->x = x;
 		n1->y = y;
@@ -465,9 +465,9 @@
 	}
 	x = block->x;
 	y = block->y + 1;
-	n1 = node + y * mapwidth + x;
+	n1 = nodemap + y * nodemapwidth + x;
 	n2 = n1 + block->o->w - 1;
-	for(e=y+block->o->h-2; y<e; y++, n1+=mapwidth, n2+=mapwidth){
+	for(e=y+block->o->h-2; y<e; y++, n1+=nodemapwidth, n2+=nodemapwidth){
 		n1->x = x;
 		n1->y = y;
 		Δ´ = octdist(pm, n1);
@@ -495,10 +495,10 @@
 
 	dprint("findpath %d,%d → %d,%d\n", mo->x, mo->y, p.x, p.y);
 	clearpath();
-	a = node + mo->y * mapwidth + mo->x;
+	a = nodemap + mo->y * nodemapwidth + mo->x;
 	a->x = mo->x;
 	a->y = mo->y;
-	b = node + p.y * mapwidth + p.x;
+	b = nodemap + p.y * nodemapwidth + p.x;
 	b->x = p.x;
 	b->y = p.y;
 	markmobj(mo, 0);
@@ -520,8 +520,8 @@
 		clearpath();
 		a->x = mo->x;
 		a->y = mo->y;
-		b->x = (b - node) % mapwidth;
-		b->y = (b - node) / mapwidth;
+		b->x = (b - nodemap) % nodemapwidth;
+		b->y = (b - nodemap) / nodemapwidth;
 		if((n = a∗(a, b, mo)) == nil)
 			sysfatal("findpath: phase error");
 	}
--- a/sim.c
+++ b/sim.c
@@ -39,8 +39,8 @@
 {
 	Map *m;
 
-	m = map + mo->y * mapwidth + mo->x;
-	mo->mapp = linkmobj(mo->f & Fair ? m->ml.lp : &m->ml, mo, mo->mapp);
+	m = map + (mo->y * mapwidth + mo->x) / Node2Tile;
+	mo->mobjl = linkmobj(mo->f & Fair ? m->ml.lp : &m->ml, mo, mo->mobjl);
 }
 
 static void
@@ -267,7 +267,7 @@
 	int r;
 
 	updatespeed(mo);
-	unlinkmobj(mo->mapp);
+	unlinkmobj(mo->mobjl);
 	r = trymove(mo);
 	linktomap(mo);
 	return r;