shithub: dmap

Download patch

ref: 901503e77b462db789885a3b9424ad00434b0699
author: qwx <qwx@sciops.net>
date: Mon May 27 17:44:46 EDT 2019

initial import

--- /dev/null	Thu Dec 31 12:39:09 2020
+++ b/bsp.c	Mon May 27 17:44:46 2019
@@ -0,0 +1,354 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.h>
+#include "dat.h"
+#include "fns.h"
+
+/* a grid 8 is used for maps; points are considered on a line if they are
+ * within 8px of it; this accounts for floating error */
+
+typedef struct Bsp Bsp;
+typedef struct Divline Divline;
+typedef struct Node Node;
+
+enum{
+	Maxv = 0x7fffffff,
+};
+
+struct Divline{
+	Point p;
+	float dx;
+	float dy;
+};
+struct Bsp{
+	Seg *s;
+	Divline;
+	Bsp *side[2];
+};
+Seg *segs;
+
+struct Node{
+	short x;
+	short y;
+	short dx;
+	short dy;
+	short bound[2][4];
+	ushort child[2];
+};
+Node *nodes;
+int nnodes;
+
+static float bbox[4];
+
+void *
+erealloc(void *p, ulong n)
+{
+	if((p = realloc(p, n)) == nil)
+		sysfatal("realloc: %r");
+	return p;
+}
+
+int
+subsect(Seg *s)
+{
+	USED(s);
+	return 0;
+}
+
+int
+mknodes(Bsp *b, short box[4])
+{
+	int i, f;
+	short sbox[2][4];
+
+	if(b->s != nil){
+		f = subsect(b->s);
+		for(i=0; i<4; i++)
+			box[i] = bbox[i];
+		return f | 1<<15;
+	}
+	/* ... */
+	return 0;
+}
+
+static int
+fsign(float f)
+{
+	return f < 0. ? -1 : f > 0.;
+}
+
+static float
+fround(float x)
+{
+	if(x > 0.){
+		if(x - (int)x < 0.1)
+			return (int)x;
+		else if(x - (int)x > 0.9)
+			return (int)x + 1;
+		else
+			return x;
+	}
+	if((int)x - x < 0.1)
+		return (int)x;
+	else if((int)x - x > 0.9)
+		return (int)x - 1;
+	return x;
+}
+
+static void
+divline(Divline *d, Seg *s)
+{
+	d->p = s->p1;
+	d->dx = s->p2.x - s->p1.x;
+	d->dy = s->p2.y - s->p1.y;
+}
+
+/* fractional intercept point along first vector */
+static float
+InterceptVector(Divline *v2, Divline *v1)
+{
+	float frac, num, den;
+
+	den = v1->dy * v2->dx - v1->dx * v2->dy;
+	if(den == 0.)
+		sysfatal("InterceptVector: parallel");
+	num = (v1->p.x - v2->p.x) * v1->dy + (v2->p.y - v1->p.y) * v1->dx;
+	frac = num / den;
+	if(frac <= 0. || frac >= 1.)
+		sysfatal("InterceptVector: intersection outside line");
+	return frac;
+}
+
+static int
+ptside(Point *p, Divline *l)
+{
+	float dx, dy, left, right, a, b, c, d;
+
+	if(l->dx == 0){
+		if (p->x > l->p.x - 2 && p->x < l->p.x + 2)
+			return -1;
+		if (p->x < l->p.x)
+			return l->dy > 0;
+		return l->dy < 0;
+	}
+	if(l->dy == 0){
+		if(p->y > l->p.y - 2 && p->y < l->p.y + 2)
+			return -1;
+		if(p->y < l->p.y)
+			return l->dx < 0;
+		return l->dx > 0;
+	}
+	dx = l->p.x - p->x;
+	dy = l->p.y - p->y;
+	a = l->dx * l->dx + l->dy * l->dy;
+	b = 2 * (l->dx*dx + l->dy * dy);
+	c = dx * dx + dy * dy - 2 * 2;	/* 2 unit radius */
+	d = b * b - 4 * a * c;
+	if(d > 0)
+		return -1; /* colinear: within 4px of line */
+	dx = p->x - l->p.x;
+	dy = p->y - l->p.y;
+	left = l->dy * dx;
+	right = dy * l->dx;
+	if(abs(left - right) < 0.5)	/* allow slope on line */
+		return -1;
+	if(right < left)
+		return 0;	/* front */
+	return 1;	/* back */
+}
+
+/* if the line is colinear, it will be placed on the front side if going
+ * the same direction as the dividing line */
+static int
+lineside(Seg *wl, Divline *bl)
+{
+	int s1, s2;
+	float dx, dy;
+
+	s1 = ptside(&wl->p1, bl);
+	s2 = ptside(&wl->p2, bl);
+	if(s1 == s2){	/* colinear: see if the directions are the same */
+		if(s1 == -1){
+			dx = wl->p2.x - wl->p1.x;
+			dy = wl->p2.y - wl->p1.y;
+			if(fsign(dx) == fsign(bl->dx)
+			&& fsign(dy) == fsign(bl->dy))
+				return 0;
+			return 1;
+		}
+		return s1;
+	}
+	if(s1 == -1)
+		return s2;
+	if(s2 == -1)
+		return s1;
+	return -2;	/* line must be split */
+}
+
+/* truncate given world line to the front side of the divline and return
+ * the cut off back side in a newly allocated world line */
+static Seg *
+cutline(Seg *s, Divline *bl)
+{
+	int side, ofs;
+	float f;
+	Point intr;
+	Seg *p;
+	Divline d;
+
+	divline(&d, s);
+	p = emalloc(sizeof *p);
+	*p = *s;
+	f = InterceptVector(&d, bl);
+	intr.x = d.p.x + fround(d.dx * f);
+	intr.y = d.p.y + fround(d.dy * f);
+	ofs = s->ofs + fround(f * sqrt(d.dx * d.dx + d.dy * d.dy));
+	side = ptside(&s->p1, bl);
+	if(side == 0){	/* line starts on front side */
+		s->p2 = intr;
+		p->p1 = intr;
+		p->ofs = ofs;
+	}else{	/* line starts on back side */
+		s->p1 = intr;
+		s->ofs = ofs;
+		p->p2 = intr;
+	}
+	return p;
+}
+
+static void
+addnode(Seg **ss, int *n, Seg *s, Seg *p)
+{
+	if(s - *ss >= *n){
+		*n += 64;
+		*ss = erealloc(*ss, *n * sizeof **ss);
+	}
+	*s = *p;
+}
+
+/* actually split line list as EvaluateLines predicted */
+static void
+split(Seg *ss, Seg *s, Seg **front, Seg **back)
+{
+	int side, be, fe;
+	Seg *p, *q, *b, *f;
+	Divline d;
+
+	fe = be = ss->e - s;
+	f = *front = emalloc(fe * sizeof **front);
+	b = *back = emalloc(be * sizeof **back);
+	for(p=ss; p<ss->e; p++){
+		side = p == s ? 0 : lineside(p, &d);
+		switch(side){
+		case 0: addnode(front, &fe, f++, p); break;
+		case 1: addnode(back, &be, b++, p); break;
+		case -2:
+			q = cutline(p, &d);
+			addnode(front, &fe, f++, p);
+			addnode(back, &be, b++, q);
+			break;
+		}
+	}
+	(*front)->e = f;
+	(*back)->e = b;
+}
+
+/* grade quality of a split along given line for the current list of lines.
+ * evaluation is halted as soon as it is determined that a better split
+ * already exists. a split is good if it divides the lines evenly without
+ * cutting many lines. a horizontal or vertical split is better than a sloped
+ * split. the lower the returned value, the better. if the split line does
+ * not divide any of the lines at all, Maxv is returned */
+static int
+evalsplit(Seg *ss, Seg *s, int bestv)
+{
+	int side, s1, s2, v;
+	Divline d;
+	Seg *p;
+
+	divline(&d, s);
+	for(p=ss, v=s1=s2=0; p<ss->e; p++){
+		side = p == s ? 0 : lineside(p, &d);
+		switch(side){
+		case -2: s2++; /* wet floor */
+		case 0: s1++; break;
+		case 1: s2++; break;
+		}
+		v = (s1 > s2 ? s1 : s2) + (s1 + s2 - (p - ss)) * 8;
+		if(v > bestv)
+			return v;
+	}
+	if(s1 == 0 || s2 == 0)
+		return Maxv;
+	return v;
+}
+
+/* recursively partition seg list */
+static Bsp *
+bsp(Seg *ss)
+{
+	int v, bestv;
+	Bsp *b;
+	Seg *s, *bests, *front, *back;
+
+	b = emalloc(sizeof *b);
+	/* find the best line to partition on */
+	for(s=ss, bestv=Maxv, bests=nil; s<ss->e; s++){
+		v = evalsplit(ss, s, bestv);
+		if(v < bestv){
+			bestv = v;
+			bests = s;
+		}
+	}
+	/* if none of the lines should be split, the remaining lines
+	 * are convex, and form a terminal node */
+	if(bestv == Maxv){
+		b->s = ss;
+		return b;
+	}
+	/* divide the line list into two nodes along the best split line */
+	divline(b, bests);
+	split(ss, bests, &front, &back);
+	/* recursively divide the lists */
+	b->side[0] = bsp(front);
+	b->side[1] = bsp(back);
+	return b;
+}
+
+static void
+mkseg(void)
+{
+	Line *l;
+	Seg *s;
+
+	/* FIXME: free all nodes and segs first */
+	segs = emalloc(nsides * sizeof *segs);
+	for(s=segs, l=lines; l<lines+nlines; s++, l++){
+		s->p1 = *l->v;
+		s->p2 = *l->w;
+		s->l = l;
+		s->s = l->r;
+		if(l->f & LFtwosd){
+			s++;
+			s->p1 = *l->v;
+			s->p2 = *l->w;
+			s->l = l;
+			s->s = l->l;
+		}
+	}
+	segs->e = s;
+}
+
+void
+buildnodes(void)
+{
+	Bsp *b;
+	short bounds[4];
+
+	mkseg();
+	b = bsp(segs);
+	nnodes = nsides;
+	nodes = emalloc(nnodes * sizeof *nodes);
+	mknodes(b, bounds);
+	/* FIXME: free everything */
+}
--- /dev/null	Thu Dec 31 12:39:09 2020
+++ b/dat.h	Mon May 27 17:44:46 2019
@@ -0,0 +1,104 @@
+typedef struct Thing Thing;
+typedef struct Line Line;
+typedef struct Side Side;
+typedef struct Vertex Vertex;
+typedef struct Sector Sector;
+typedef struct Seg Seg;
+
+enum{
+	CFline = 1<<23,
+	CFthing = 1<<22,
+	CFvert = 1<<21,
+};
+
+struct Vertex{
+	int i;
+	Point;
+	uchar sel[4];
+};
+extern Vertex *verts;
+extern int nverts;
+
+struct Sector{
+	int i;
+	Point;	/* floor z, ceiling z */
+	char fflat[8+1];
+	char cflat[8+1];
+	short lum;
+	short type;
+	short tag;
+};
+extern Sector *sects;
+extern int nsects;
+
+struct Side{
+	int i;
+	Point;	/* Δ */
+	char high[8+1];
+	char low[8+1];
+	char mid[8+1];
+	int sid;
+	Sector *s;
+};
+extern Side *sides;
+extern int nsides;
+
+enum{
+	LFimpass = 1<<0,
+	LFmblock = 1<<1,
+	LFtwosd = 1<<2,
+	LFuunpeg = 1<<3,
+	LFdunpeg = 1<<4,
+	LFsecret = 1<<5,
+	LFsblock = 1<<6,
+	LFnodraw = 1<<7,
+	LFmapped = 1<<8
+};
+struct Line{
+	int i;
+	int vid;
+	int wid;
+	Vertex *v;
+	Vertex *w;
+	int rid;
+	int lid;
+	Side *r;	/* FIXME: front/back, not right/left? */
+	Side *l;
+	short type;
+	short f;
+	short tag;
+	uchar sel[4];
+};
+extern Line *lines;
+extern int nlines;
+
+enum{
+	TFbaby = 1<<0,
+	TFeasy = TFbaby,
+	TFmed = 1<<1,
+	TFhard = 1<<2,
+	TFnite = TFhard,
+	TFdeaf = 1<<3,
+	TFmponly = 1<<4
+};
+struct Thing{
+	int i;
+	Point;
+	short an;
+	short type;
+	short f;
+	uchar sel[4];
+};
+extern Thing *things;
+extern int nthings;
+
+struct Seg{
+	Point p1;
+	Point p2;
+	Line *l;
+	Side *s;
+	int ofs;
+	int grouped;
+	Seg *e;
+};
+extern Seg *segs;
--- /dev/null	Thu Dec 31 12:39:09 2020
+++ b/dmap.c	Mon May 27 17:44:46 2019
@@ -0,0 +1,405 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.h>
+#include <thread.h>
+#include <keyboard.h>
+#include <mouse.h>
+#include "dat.h"
+#include "fns.h"
+
+/* FIXME: inserting/modifying vertices/things: snap to grid is essential */
+/* FIXME: need a node builder to test shit */
+
+enum{
+	Cbg,
+	Cwall,
+	Cline,
+	Cthing,
+	Cvert,
+	Cgrid,
+	Ctext,
+	Cend,
+
+	Nview = 1000,
+	Nzoom = 300,
+};
+
+static int viewdiv = Nzoom;
+static int grunit = 128;
+static int skipms, mode, join;
+static Image *col[Cend], *fb, *fbsel, *fbselc;
+static Point center, view;
+static Keyboardctl *kc;
+static Mousectl *mc;
+
+void *
+emalloc(ulong n)
+{
+	void *p;
+
+	if((p = mallocz(n, 1)) == nil)
+		sysfatal("mallocz: %r");
+	setmalloctag(p, getcallerpc(&n));
+	return p;
+}
+
+Image *
+eallocimage(Rectangle r, ulong chan, int repl, ulong c)
+{
+	Image *i;
+
+	if((i = allocimage(display, r, chan, repl, c)) == nil)
+		sysfatal("allocimage: %r");
+	return i;
+}
+
+Point
+viewpt(Point p)
+{
+	double f;
+
+	f = (double)viewdiv / Nview;
+	p.x = view.x + p.x * f;
+	p.y = view.y + p.y * f;
+	return p;
+}
+
+Point
+abspt(Point p)
+{
+	double f;
+
+	f = (double)viewdiv / Nview;
+	p.x = (p.x - view.x) / f;
+	p.y = (p.y - view.y) / f;
+	return p;
+}
+
+void
+drawgrid(void)
+{
+	Point p, v;
+
+	p = Pt(0, 0);
+	for(;;){
+		v = viewpt(p);
+		if(v.x >= fb->r.max.x && v.y >= fb->r.max.y)
+			break;
+		line(fb, Pt(0, v.y), Pt(Dx(fb->r), v.y), 0, 0, 0, col[Cgrid], ZP);
+		line(fb, Pt(v.x, 0), Pt(v.x, Dy(fb->r)), 0, 0, 0, col[Cgrid], ZP);
+		p.x += grunit;
+		p.y += grunit;
+	}
+	p = Pt(0 - grunit, 0 - grunit);
+	for(;;){
+		v = viewpt(p);
+		if(v.x <= fb->r.min.x && v.y <= fb->r.min.y)
+			break;
+		line(fb, Pt(0, v.y), Pt(Dx(fb->r), v.y), 0, 0, 0, col[Cgrid], ZP);
+		line(fb, Pt(v.x, 0), Pt(v.x, Dy(fb->r)), 0, 0, 0, col[Cgrid], ZP);
+		p.x -= grunit;
+		p.y -= grunit;
+	}
+}
+
+void
+doline(Point m1, Point m2, int type, uchar *sel)
+{
+	int et;
+	Image *c;
+
+	c = col[type];
+	et = type == Cthing && mode == 2 || type != Cthing && mode == 1 ? Endarrow : 0;
+	line(fb, m1, m2, 0, et, 0, c, ZP);
+	loadimage(fbselc, fbselc->r, sel, 4);
+	line(fbsel, m1, m2, 0, et, 0, fbselc, ZP);
+}
+
+void
+doellipse(Point p, int r, int type, uchar *sel)
+{
+	fillellipse(fb, p, r, r, col[type], ZP);
+	loadimage(fbselc, fbselc->r, sel, 4);
+	fillellipse(fbsel, p, r, r, fbselc, ZP);
+}
+
+void
+drawlines(void)
+{
+	Line *l;
+	Point m1, m2;
+
+	for(l=lines; l<lines+nlines; l++){
+		m1 = viewpt(*l->v);
+		m2 = viewpt(*l->w);
+		if(!ptinrect(m1, fb->r) && !ptinrect(m2, fb->r)
+		&& !((m1.x >= 0 && m1.x < Dx(fb->r) && (m1.y < 0 || m1.y >= Dy(fb->r)))
+		|| (m2.x >= 0 && m2.x < Dx(fb->r) && (m2.y < 0 || m2.y >= Dy(fb->r)))))
+			continue;
+		doline(m1, m2, l->f & LFimpass ? Cwall : Cline, l->sel);
+	}
+
+}
+
+void
+drawvertices(void)
+{
+	Vertex *v;
+	Point p;
+	int r;
+
+	r = mode==0 ? 2 : 1;
+	for(v=verts; v<verts+nverts; v++){
+		p = viewpt(*v);
+		if(!ptinrect(p, fb->r))
+			continue;
+		doellipse(p, r, Cvert, v->sel);
+	}
+}
+
+void
+drawthings(void)
+{
+	Thing *t;
+	Point m1, m2;
+
+	for(t=things; t<things+nthings; t++){
+		m1 = viewpt(*t);
+		if(!ptinrect(m1, fb->r))
+			continue;
+		if(mode != 2)
+			doellipse(m1, 1, Cthing, t->sel);
+		else{
+			m2 = t->an == 0 ? (Point){m1.x+1, m1.y}
+				: t->an == 45 ? (Point){m1.x+1, m1.y-1}
+				: t->an == 90 ? (Point){m1.x, m1.y-1}
+				: t->an == 135 ? (Point){m1.x-1, m1.y-1}
+				: t->an == 180 ? (Point){m1.x-1, m1.y}
+				: t->an == 225 ? (Point){m1.x-1, m1.y+1}
+				: t->an == 270 ? (Point){m1.x, m1.y+1}
+				: t->an == 315 ? (Point){m1.x+1, m1.y+1}
+				: m1;
+			doline(m1, m2, Cthing, t->sel);
+		}
+	}
+}
+
+void
+redraw(void)
+{
+	draw(fb, fb->r, col[Cbg], nil, ZP);
+	draw(fbsel, fbsel->r, col[Cbg], nil, ZP);
+	drawgrid();
+	drawlines();
+	drawvertices();
+	drawthings();
+	string(fb, Pt(0,0), col[Ctext], Pt(0,0), font, join ? "join" : "split");
+	draw(screen, screen->r, fb, nil, ZP);
+	flushimage(display, 1);
+}
+
+void
+drawstats(Point p)
+{
+	char buf[128];
+	uchar sel[4];
+	u32int x;
+	Line *l;
+	Thing *t;
+	Side *d;
+	Sector *s;
+	Vertex *v;
+
+	unloadimage(fbsel, rectaddpt(fbselc->r, p), sel, sizeof sel);
+	x = sel[3] << 24 | sel[2] << 16 | sel[1] << 8 | sel[0];
+	draw(screen, screen->r, fb, nil, ZP);
+	p = abspt(p);
+	sprint(buf, "%d,%d", p.x & ~(grunit-1), p.y & ~(grunit-1));
+	p = Pt(screen->r.max.x - strlen(buf) * font->width,
+		screen->r.max.y - font->height);
+	string(screen, p, col[Ctext], Pt(0,0), font, buf);
+	if(x == 0)
+		goto end;
+	p = Pt(screen->r.min.x, screen->r.max.y - font->height * 5);
+	switch(x & 7<<21){
+	case CFline:
+		l = lines + (x & 0xffff);
+		sprint(buf, "(%d,%d %d,%d len N) type %d tag %d",
+			l->v->x, l->v->y, l->w->x, l->w->y, l->type, l->tag);
+		string(screen, p, col[Ctext], Pt(0,0), font, buf);
+		p.y += font->height;
+		d = l->r;
+		sprint(buf, "front: %-8s %-8s %-8s ofs %d,%d",
+			d->high, d->mid, d->low, d->x, d->y);
+		string(screen, p, col[Ctext], Pt(0,0), font, buf);
+		p.y += font->height;
+		s = d->s;
+		sprint(buf, "floor %d %-8s ceiling %d %-8s (height %d) light %d type %d tag %d",
+			s->x, s->fflat, s->y, s->cflat, s->y - s->x,
+			s->lum, s->type, s->tag);
+		string(screen, p, col[Ctext], Pt(0,0), font, buf);
+		p.y += font->height;
+		if((l->f & LFtwosd) == 0)
+			goto end;
+		d = l->l;
+		sprint(buf, "back:  %-8s %-8s %-8s ofs %d,%d",
+			d->high, d->mid, d->low, d->x, d->y);
+		string(screen, p, col[Ctext], Pt(0,0), font, buf);
+		p.y += font->height;
+		s = d->s;
+		sprint(buf, "floor %d %-8s ceiling %d %-8s (height %d) light %d type %d tag %d",
+			s->x, s->fflat, s->y, s->cflat, s->y - s->x,
+			s->lum, s->type, s->tag);
+		string(screen, p, col[Ctext], Pt(0,0), font, buf);
+		break;
+	case CFthing:
+		t = things + (x & 0xffff);
+		p.y += font->height * 4;
+		sprint(buf, "%d,%d ∠ %d type %d flags %#08ux",
+			t->x, t->y, t->an, t->type, t->f);
+		string(screen, p, col[Ctext], Pt(0,0), font, buf);
+		break;
+	case CFvert:
+		v = verts + (x & 0xffff);
+		p.y += font->height * 4;
+		sprint(buf, "%d,%d", v->x, v->y);
+		string(screen, p, col[Ctext], Pt(0,0), font, buf);
+		break;
+	}
+end:
+	flushimage(display, 1);
+}
+
+void
+initfb(int v)
+{
+	Rectangle r;
+
+	center = divpt(subpt(screen->r.max, screen->r.min), 2);
+	if(v)
+		view = center;
+	r = rectsubpt(screen->r, screen->r.min);
+	freeimage(fb);
+	fb = eallocimage(r, screen->chan, 0, DNofill);
+	freeimage(fbsel);
+	fbsel = eallocimage(r, XRGB32, 0, DNofill);
+	redraw();
+	skipms++;
+}
+
+void
+usage(void)
+{
+	fprint(2, "%s [mapdir]\n", argv0);
+	threadexitsall("usage");
+}
+
+void
+threadmain(int argc, char *argv[])
+{
+	Mouse m;
+	Point mo;
+	double f, vx, vy;
+	Rune r;
+
+	ARGBEGIN{
+	default:
+		usage();
+	}ARGEND
+	if(initdraw(nil, nil, "dmap") < 0)
+		sysfatal("initdraw: %r");
+	load(*argv);
+	if((kc = initkeyboard(nil)) == nil)
+		sysfatal("initkeyboard: %r");
+	if((mc = initmouse(nil, screen)) == nil)
+		sysfatal("initmouse: %r");
+	col[Cbg] = display->black,
+	col[Cwall] = eallocimage(Rect(0,0,1,1), screen->chan, 1, 0xccccccff);
+	col[Cline] = eallocimage(Rect(0,0,1,1), screen->chan, 1, 0x5f5f5fff);
+	col[Cthing] = eallocimage(Rect(0,0,1,1), screen->chan, 1, DGreen);
+	col[Cvert] = eallocimage(Rect(0,0,1,1), screen->chan, 1, DGreyblue);
+	col[Cgrid] = eallocimage(Rect(0,0,1,1), screen->chan, 1, 0x101010ff);
+	col[Ctext] = eallocimage(Rect(0,0,1,1), screen->chan, 1, 0x884400ff);
+	fbselc = eallocimage(Rect(0,0,1,1), XRGB32, 1, DNofill);
+	initfb(1);
+	vx = view.x - center.x;
+	vy = view.y - center.y;
+
+	Alt a[] = {
+		{mc->resizec, nil, CHANRCV},
+		{mc->c, &m, CHANRCV},
+		{kc->c, &r, CHANRCV},
+		{nil, nil, CHANEND}
+	};
+	for(;;){
+		switch(alt(a)){
+		case 0:
+			if(getwindow(display, Refnone) < 0)
+				sysfatal("getwindow: %r");
+			initfb(0);
+			break;
+		case 1:
+			if(skipms){
+				skipms = 0;
+				goto skip;
+			}
+			if(m.buttons & 2){
+				f = (double)viewdiv / Nview;
+				viewdiv += (m.xy.y - mo.y) / 2;
+				if(viewdiv > 10 * Nview)
+					viewdiv = 10 * Nview;
+				else if(viewdiv < 1)
+					viewdiv = 1;
+				f = ((double)viewdiv / Nview) / f;
+				vx *= f;
+				vy *= f;
+				view = addpt(center, Pt(vx, vy));
+				redraw();
+			}
+			if(m.buttons & 4){
+				mo = subpt(m.xy, mo);
+				view = addpt(view, mo);
+				vx = view.x - center.x;
+				vy = view.y - center.y;
+				redraw();
+			}
+			if(ptinrect(m.xy, screen->r))
+				drawstats(subpt(m.xy, screen->r.min));
+		skip:
+			mo = m.xy;
+			break;
+		case 2:
+			switch(r){
+			paint: redraw(); break;
+			case Kdel:
+			case 'q': threadexitsall(nil);
+			case 'a': mode = (mode + 1) % 3; goto paint;
+			case 'j': join ^= 1; goto paint;
+			case 'r':
+				view = center;
+				vx = view.x - center.x;
+				vy = view.y - center.y;
+				goto paint;
+			case '+':
+			case '=':
+				if(grunit < 1024){
+					grunit <<= 1;
+					goto paint;
+				}
+				break;
+			case '-':
+				if(grunit > 1){
+					grunit >>= 1;
+					goto paint;
+				}
+				break;
+			case 'z':
+				viewdiv = Nzoom;
+				goto paint;
+			}
+			break;
+		default:
+			threadexitsall("alt: %r");
+		}
+	}
+}
--- /dev/null	Thu Dec 31 12:39:09 2020
+++ b/fns.h	Mon May 27 17:44:46 2019
@@ -0,0 +1,3 @@
+void	buildnodes(void);
+void	load(char*);
+void*	emalloc(ulong);
--- /dev/null	Thu Dec 31 12:39:09 2020
+++ b/fs.c	Mon May 27 17:44:46 2019
@@ -0,0 +1,238 @@
+#include <u.h>
+#include <libc.h>
+#include <draw.h>
+#include <bio.h>
+#include "dat.h"
+#include "fns.h"
+
+enum{
+	Vertsz = 4,
+	Sectsz = 26,
+	Sidesz = 30,
+	Linesz = 14,
+	Thingsz = 10
+};
+
+Vertex *verts;
+int nverts;
+Sector *sects;
+int nsects;
+Side *sides;
+int nsides;
+Line *lines;
+int nlines;
+Thing *things;
+int nthings;
+
+#define	PBIT32(p,v)	(p)[0]=(v);(p)[1]=(v)>>8;(p)[2]=(v)>>16;(p)[3]=(v)>>24
+
+static vlong
+filelen(int fd)
+{
+	vlong l;
+	Dir *d;
+
+	d = dirfstat(fd);
+	if(d == nil)
+		sysfatal("filelen: %r");
+	l = d->length;
+	free(d);
+	return l;
+}
+
+static void
+loadthings(char *f)
+{
+	int n;
+	vlong l;
+	char *s;
+	uchar u[Thingsz];
+	Biobuf *bf;
+	Thing *p;
+	static u32int sel = CFthing;
+
+	s = smprint("%s/things", f);
+	bf = Bopen(s, OREAD);
+	if(bf == nil)
+		sysfatal("loadthings: %r");
+	free(s);
+	l = filelen(Bfildes(bf));
+	if(l % sizeof u != 0)
+		sysfatal("invalid THINGS lump");
+	n = l / sizeof u;
+	things = emalloc(n * sizeof *things);
+	Blethal(bf, nil);
+	for(p=things; Bread(bf, u, sizeof u) == sizeof u; p++, sel++){
+		if(nthings++ == n)
+			sysfatal("loadthings: overflow\n");
+		p->i = nthings;
+		p->x = (s16int)(u[0] | u[1]<<8);
+		p->y = -(s16int)(u[2] | u[3]<<8);
+		p->an = (s16int)(u[4] | u[5]<<8);
+		p->type = (s16int)(u[6] | u[7]<<8);
+		p->f = (s16int)(u[7] | u[8]<<8);
+		PBIT32(p->sel, sel);
+	}
+	Bterm(bf);
+}
+
+static void
+loadlines(char *f)
+{
+	int n;
+	vlong l;
+	char *s;
+	uchar u[Linesz];
+	Biobuf *bf;
+	Line *p;
+	static u32int sel = CFline;
+
+	s = smprint("%s/linedefs", f);
+	bf = Bopen(s, OREAD);
+	if(bf == nil)
+		sysfatal("loadlines: %r");
+	free(s);
+	l = filelen(Bfildes(bf));
+	if(l % sizeof u != 0)
+		sysfatal("invalid LINEDEFS lump");
+	n = l / sizeof u;
+	lines = emalloc(n * sizeof *lines);
+	Blethal(bf, nil);
+	for(p=lines; Bread(bf, u, sizeof u) == sizeof u; p++, sel++){
+		if(nlines++ == n)
+			sysfatal("loadsides: overflow\n");
+		p->i = nlines;
+		/* FIXME: are these supposed to be sign extended? */
+		p->vid = (s16int)(u[0] | u[1]<<8);
+		p->v = verts + p->vid;
+		p->wid = (s16int)(u[2] | u[3]<<8);
+		p->w = verts + p->wid;
+		p->f = (s16int)(u[4] | u[5]<<8);
+		p->type = (s16int)(u[6] | u[7]<<8);
+		p->tag = (s16int)(u[8] | u[9]<<8);
+		/* FIXME: if == (s16int)-1, dont set pointer */
+		p->rid = (s16int)(u[10] | u[11]<<8);
+		p->r = sides + p->rid;
+		p->lid = (s16int)(u[12] | u[13]<<8);
+		p->l = sides + p->lid;
+		PBIT32(p->sel, sel);
+	}
+	Bterm(bf);
+}
+
+static void
+loadsides(char *f)
+{
+	int n;
+	vlong l;
+	char *s;
+	uchar u[Sidesz];
+	Biobuf *bf;
+	Side *p;
+
+	s = smprint("%s/sidedefs", f);
+	bf = Bopen(s, OREAD);
+	if(bf == nil)
+		sysfatal("loadsides: %r");
+	free(s);
+	l = filelen(Bfildes(bf));
+	if(l % sizeof u != 0)
+		sysfatal("invalid SIDEDEFS lump");
+	n = l / sizeof u;
+	sides = emalloc(n * sizeof *sides);
+	Blethal(bf, nil);
+	for(p=sides; Bread(bf, u, sizeof u) == sizeof u; p++){
+		if(nsides++ == n)
+			sysfatal("loadsides: overflow\n");
+		p->i = nsides;
+		p->x = (s16int)(u[0] | u[1]<<8);
+		p->y = -(s16int)(u[2] | u[3]<<8);
+		memcpy(p->high, u+4, 8);
+		memcpy(p->low, u+12, 8);
+		memcpy(p->mid, u+20, 8);
+		p->sid = (s16int)(u[28] | u[29]<<8);
+		p->s = sects + p->sid;
+	}
+	Bterm(bf);
+}
+
+static void
+loadsects(char *f)
+{
+	int n;
+	vlong l;
+	char *s;
+	uchar u[Sectsz];
+	Biobuf *bf;
+	Sector *p;
+
+	s = smprint("%s/sectors", f);
+	bf = Bopen(s, OREAD);
+	if(bf == nil)
+		sysfatal("loadsects: %r");
+	free(s);
+	l = filelen(Bfildes(bf));
+	if(l % sizeof u != 0)
+		sysfatal("invalid SECTORS lump");
+	n = l / sizeof u;
+	sects = emalloc(n * sizeof *sects);
+	Blethal(bf, nil);
+	for(p=sects; Bread(bf, u, sizeof u) == sizeof u; p++){
+		if(nsects++ == n)
+			sysfatal("loadsects: overflow\n");
+		p->i = nsects;
+		p->y = (s16int)(u[0] | u[1]<<8);
+		p->x = -(s16int)(u[2] | u[3]<<8);
+		memcpy(p->fflat, u+4, 8);
+		memcpy(p->cflat, u+12, 8);
+		p->lum = (s16int)(u[20] | u[21]<<8);
+		p->type = (s16int)(u[22] | u[23]<<8);
+		p->tag = (s16int)(u[24] | u[25]<<8);
+	}
+	Bterm(bf);
+}
+
+static void
+loadverts(char *f)
+{
+	int n;
+	vlong l;
+	char *s;
+	uchar u[Vertsz];
+	Biobuf *bf;
+	Vertex *p;
+	static u32int sel = CFvert;
+
+	s = smprint("%s/vertexes", f);
+	bf = Bopen(s, OREAD);
+	if(bf == nil)
+		sysfatal("loadverts: %r");
+	free(s);
+	l = filelen(Bfildes(bf));
+	if(l % sizeof u != 0)
+		sysfatal("invalid VERTEXES lump");
+	n = l / sizeof u;
+	verts = emalloc(n * sizeof *verts);
+	Blethal(bf, nil);
+	for(p=verts; Bread(bf, u, sizeof u) == sizeof u; p++, sel++){
+		if(nverts++ == n)
+			sysfatal("loadverts: overflow\n");
+		p->i = nverts;
+		p->x = (s16int)(u[0] | u[1]<<8);
+		p->y = -(s16int)(u[2] | u[3]<<8);
+		PBIT32(p->sel, sel);
+	}
+	Bterm(bf);
+}
+
+void
+load(char *f)
+{
+	if(f == nil)
+		f = ".";
+	loadverts(f);
+	loadsects(f);
+	loadsides(f);
+	loadlines(f);
+	loadthings(f);
+}
--- /dev/null	Thu Dec 31 12:39:09 2020
+++ b/mkfile	Mon May 27 17:44:46 2019
@@ -0,0 +1,12 @@
+</$objtype/mkfile
+
+BIN=$home/bin/$objtype
+TARG=dmap
+OFILES=\
+	bsp.$O\
+	dmap.$O\
+	fs.$O\
+
+HFILES=dat.h fns.h
+
+</sys/src/cmd/mkone