Continuing a series of blog posts about Debian packages I have adopted (Previously: smartmontools; duc), in January this year I also adopted glBSP.

I was surprised to see glBSP come up for adoption; I found out when I was installing something entirely unrelated, thanks to the how-can-i-help package. (This package is a great idea: it tells you about packages you have installed which are in danger of being removed from Debian, or have other interesting bugs filed against them. Give it a go!) glBSP is a dependency on another of my packages, WadC, so I adopted it fairly urgently.

glBSP is a node-building tool for Doom maps. A Map in Doom is defined in a handful of different lumps of data. The top-level, canonical data structures are relatively simple: THINGS is a list of things (type, coordinates, angle facing); VERTEXES is a list of points for geometry (X/Y coordinates); SECTORS define regions (light level, floor height and texture,…), etc. Map authoring tools can build these lumps of data relatively easily. (I've done it myself: I generate them all in liquorice, that I should write more about one day.)

During gameplay, Doom needs to answer questions such as: the player is at location (X,Y) and has made a noise. Can Monster Z hear that noise? Or: the player is at location (X,Y) at facing Z°, what walls need to be drawn? These decisions needed to be made very quickly on the target hardware of 1993 (a 486 CPU) in order to maintain the desired frame-rate (35fps). To facilitate this, various additional data structures are derived from the canonical lumps. glBSP is one of a class of tools called node builders that calculate these extra lumps. The name "node-builder" comes from one of the lumps (NODES), which encodes a binary-space partition of the map geometry (and that's where "BSP" comes from).

If you would be interested to know more about these algorithms (and they are fascinating, honest!), I recommend picking up Fabien Sanglard's forthcoming book "Game Engine Black Book: DOOM". You can pre-order an ebook from Google Play here. It will be available as a physical book (and ebook) via Amazon on publication date, which will be December 10, marking Doom's 25th anniversary.

The glBSP package could do with some work to bring it up to the modern standards and conventions of Debian packages. I haven't bothered to do that, because I'm planning to replace it with another node-builder. glBSP is effectively abandoned upstream. There are loads of other node builders that could be included: glBSP and Eureka author Andrew Apted started a new one called AJBSP, and my long-time friend Kim Roar Foldøy Hauge has one called zokumbsp. The best candidate as an all-round useful node-builder is probably ZDBSP, which was originally developed as an internal node-builder for the ZDoom engine, and was designed for speed. It also copes well with some torture-test maps, such as WadC's "choz.wl", which brought glBSP to its knees. I've submitted a package of ZDBSP to Debian and I'm waiting to see if it is accepted by the FTP masters. After that, we could consider removing glBSP.


Comments