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;