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;
+}