Building a model of a Doom level
This is the second post in a series about working with Doom in Unity. You can read the first part here, about writing a Doom-style shader.
I’ve been working on a project over the past few weeks bringing Doom and it’s various bits and pieces into Unity, along the way attempting to write a library to let people access the data in a friendly way. It’s been a very interesting project and a fun application of the many years I’ve spent delving into the inner-workings of the game.
The first step with my project was to take the data Doom uses to store a map, and create a Mesh out of it. Simple, right?
(Note: I’m going to avoid talking about parsing the actual data, for the sake of brevity. I will possibly cover that in a future post.)
Build That Wall (~)
Let’s start with the walls. Walls are easy. The geometry of a wall in Doom is split into two parts: the Linedef, and the Vertexes (yeah, they aren’t called Vertices here). A linedef has a bunch of information, but the bits we care about a where it starts and ends. The vertexes, which are just (x, y) points, tell us that.
Well, that was easy. Just iterate through the Linedefs, take the start and end points, and build a vertical wall. If I want to get the texture information, I just need to get the associated Sidedefs for the lines and apply the texture. Something’s wrong here; this is going very well.
(Another note: I didn’t talk about calculating the height of walls, nor upper/lower/2sided walls; it wasn’t very interesting.)
Build That Floor
Let’s move on, now we have the walls lets build that bit in-between them: The floors. We can take a look at the Sectors to see where to start.
A sector entry specifies the following:
Ceiling flat — Name of the flat (texture) used on the ceiling of the sector.
Floor flat — Name of the flat used on the floor.
Ceiling height — Height of the ceiling.
Floor height — Height of the floor.
Lighting — How bright the sector is.
Sector tag — A number that makes the sector a target of the action specified by any linedef with the same tag number. Used, for example, to alter the sector’s ceiling and/or floor height, lighting level or flats.
Sector type — Special properties of the sector. This is used to give the sector a damaging floor (for things like lava and slime), have the sector’s light level change constantly, enable wind or currents or even push the player in a certain direction. See below.
Huh, ok. There doesn’t seem to be any information here on *where* the sector is, or what shape it is. I wonder if-
A sector does not have to be a single polygon. For instance, two squares can be separate and non-contiguous, but still be part of the same sector.
Oh.
How To Build That Which Does Not Exist
So floors and ceilings in Doom kind of Don’t Exist. They’re only implied by the walls surrounding them. The engine knows where a floor is because the player is always inside one looking out. (Which makes for some interesting behaviour when you aren’t inside one)
This means that they can be absolutely any shape: They don’t need to be convex, they don’t need to be contiguous (one connected shape), they can have holes, and they don’t necessarily even need to be closed shapes. It’s very literally impossible to build a mesh of them, there aren’t enough constraints.
That didn’t stop me trying.
It turns out the only thing you need to assume is this: all sectors are closed, and if they aren’t, they probably were supposed to. It turns out all the other constraints are possible to deal with, and closing sectors automatically causes zero intended effects to break. (Within reason. There are edge cases, but let’s call them out of scope. I’m looking at you, lilith.pk3)
Triangulation is a Solved Problem. However, our specific case means that implementing a library or other method that can build a set of triangles is very difficult. There will still be a lot of steps to have organised enough information for a triangulation algorithm to deal with.
To build the sectors, I wanted to do it step by step, so I could see and evaluate my progress. To this end, if my code failed for any particular reason to build a sector, I would just move on to the next one. This way, I always had at least partial levels built; I didn’t need to get it 100% working before I could see results or try other things out.
Ear Clipping
The triangulation approach I used, which was also used for the map editor Doom Builder 2, is documented here. I worked through it step by step to solve more and more sectors that Doom threw at me.
The first step was to implement the Ear Clip algorithm, only on already contiguous and closed sectors with no holes.
The premise is rather simple. You start with some shape, and you take a point and if you can connect a line between the two neighbouring points, you can “remove” that point and call it a triangle.
This worked really well for all sectors that fit my constraints I aimed for, it took a while to write up enough of the algorithm to reach the point where I could test it, but it definitely worked really well in all the situations I expected it to.
The next step was to disconnect non-contiguous sectors. The way I approached this was to trace lines from a point in a sector, and make a list of all the lines that it touched when going from one to the next. The idea is I would be able to create a set of shapes that are completely unconnected from one another, and triangulate them separately.
When I have two separate shapes, there is a (likely) chance that one of them is actually inside the other, which indicates a hole. I knew that I could handle the situation of them being completely separated, so I first attempted to detect holes and ignore them.
For this, I needed to pick a point and ask whether it was inside a given set of lines. This confounded me for a while until I read about a surprisingly simple but effective method: the Ray casting algorithm.
If a point is within an arbitrary shape, a line from that point to somewhere you know is outside the shape (for instance +1000 in the X coordinate) will cross an odd number of lines of the shape. A point outside will cross an even number of lines (including zero).
So all I had to do was check if the points of the separate shapes were inside each other. The result of this would be one of two things: a list of shapes with nothing inside them, or a list of “shells”, which in turn contains a list of “holes”.
I could already triangulate the empty shells, which meant the next step was to move onto triangulating the shells that contained a hole. Would I need to have a new triangulation algorithm that knew how to deal with holes? There’s no way that ear clipping will know what to do when it encounters one, so it can’t really work.
It turns out the answer is don’t try and triangulate a sector with a hole: just make the sector not have any holes any more!
If you pick a point on a hole, and trace a line to somewhere on the shell, you can make a cut. The cut will then be treated as part of the shell, which connects to all the lines in the hole, which are now part of the shell too. The two points used for making the cut will be duplicated, so the ear clipping can clip them twice.
To handle multiple holes, you just need to order them and cut them sequentially; once a hole is cut, it is a valid part of the shell to cut to.
This set of processes also handles working with sectors inside holes inside other sectors, too, which I’m really glad about since trying to think about that isn’t fun.
Unfortunately, this isn’t the end. Most sectors are building really nicely at this point, but regardless of all the trouble it took me to get to this point (which I didn’t go much into, to keep this work-safe), there are a lot more situations to deal with.
Because of how the software renderer works, you can often confuse it into creating impressive visual effects. These include the Mordeth Bridge, or the Deep Water effect.
So as always, there is more to do. I would love to tackle these tricks and get them working, since they seem like a fun problem to solve. For now though, I’m going to move on from my endless triangulation nightmare and add other interesting features to my engine. I am fast approaching something that can roughly Play Doom, which is very exciting. I’ll hopefully be back soon with more!
Thank you so much for reading! You can follow the continued development of my Doom project on my twitter: twitter.com/jmickle_, and you can support continued development of this and other projects through my Patreon. 💜
