< published February 07, 2016

DarkFO Devlog Part VIII: Lighting

---

There is a feature that has been a work in progress for perhaps over a year; a feature that I consider imperative for perhaps no reason other than stubbornness and a refusal to concede to what should be a simple problem.

This feature, of course, is Fallout 2’s floor lighting.

Description

This is how the game looks without floor lighting:

And then with floor lighting (as of a current version of DarkFO):

This is not perfect (there are still inaccuracies in the lightmap generation, but it’s Close Enough™).

It adds quite a bit of ambiance to the world, making especially New Reno feel more gritty and dark. Note that objects themselves are not lit yet, though it is easy to do.

So what’s the big deal, looks easy to me!

The problem is that it is undocumented, so I had to reverse engineer it. The other problem is that it’s somewhat complicated, and relies on a few steps, so it’s not as simple as merely replicating one function.

It’s also not feasible (to me, at least) to attempt to implement it blindly, as there are a lot of factors involved in it.

A glossary first:

A lightmap is what I call the tilemap that stores light levels of every floor tile. Light levels range from 0 to 65536, inclusive.

The lightbuffer is what I call the framebuffer which rasterized triangles are written to.

As you can hopefully see from the screenshots above, the lighting works by rasterizing triangles (into the lightbuffer) based on the lightmap.

Essentially, it proceeds in a few separate phases:

• The lightmap is generated for the map on load
• Whenever an object changes position, the lightmap is modified in-place as an optimization

Then when we want to render the floor, for each tile we:

• Compute the light level of each triangle vertex based on surrounding tiles
• If the light level of each vertex is equal, as an optimization we can bail out and just render a uniformly lit tile.
• We then rasterize the set of rightside-up triangles (pointy side up), and then the set of upside-down triangles (pointy side down) into the lightbuffer. This is achieved by using lookup tables and an algorithm which linearly interpolates lighting between vertices, at each pixel of the triangle.
• We then blend the pixels of the tile with pixels from the lightbuffer, using another set of lookup tables (remember that Fallout 2 uses paletted images)
• We can then write that out to the screen framebuffer

If any of that sounds complicated, then you can imagine how hard it was to actually figure it all out. :)

If you were wondering, this is how rasterized triangles look (with a constant light level):

That’s all possible configurations of upside-down triangles.

This is how all triangles (rightside-up and upside-down) look mashed together into one composite, which is how they’d be blended onto a tile:

Don’t ask me how that works, or why they did it that way.

What about the lightmap?

The lightmap is generated by, for each object, manipulating the light level at that object with respect to surrounding objects. This takes into account their respective light levels, their flags (such as the light pass-through flag), their type (walls block light), etc.

Objects that block light obviously block light beyond them, so that light cannot bleed through walls, and you can get a shadow effect around certain solid objects.

So what was really the hard part?

Well, I would have been done much sooner, but there was a crucial bug for a long time where there were these “void pixels” or “void streaks”, as they were dubbed: pixels of black which were drawn to the sides of tiles.

And shown with the lightbuffer only:

I had searched for months to find out what was wrong in my algorithms, reverse engineering the remaining small pieces of code I had neglected (turns out, they were as irrelevant as I had thought :)), to no avail… Everything seemed to match up to me.

A friend of mine then offered their help, and we began working through parts of the reversed program I did not understand. We then ran some basic (and hacky) debugging through it to see if something obvious (or not-so-obvious) was wrong. Nothing came up (except, as my friend claims, the Fallout 2 developers added a hack themselves, offsetting the starting row of the lightbuffer by one. Probably to offset (pun intended) issues such as this.)

However, since we noted they only occur on tile boundaries, we had the idea to draw tiles in a different order.

…

It turns out, the order is significant, and tiles are not all of the same size/shape in Fallout 2, so certain tiles may overlap others, and as a result we were overwriting black pixels onto a tile that should have been overlapped. Sigh.

So, with the problem mostly fixed by rendering tiles correctly, the problem is mostly put to rest.

I can now fairly safely say that there are very few people in the world who know how Fallout 2’s lighting works, and I am barely one of them. :)

What tools helped you?

IDA is an invaluable tool for reverse engineering and debugging.

I ended up writing many tools myself for tackling this problem.

After annotating a lot of the relevant functions in IDA, I wanted to play around with the program more dynamically, so I wrote a disassembler in Python which dumped the relevant procedure, preserving symbols where possible.

Using this, I manually fixed up the output and I could then assemble it with yasm (an excellent assembler).

I then wrote a code injector in C so that I could take the resulting binary and run Fallout 2 with my modified code. This means that I can change the lighting procedure at will, and see what changing certain code does, disabling code, etc. It is useful to visually draw the triangles using solid colors to see how they match up.

Conclusion

I am glad I can finally put this large issue to rest. There is still more minor work to be done, such as refactoring more of the code and making the lightmap generation more accurate with Fallout 2.

Object maps are also in need of optimization, since for now I simply store all objects in a flat array, resulting in a linear lookup every time I want to find an object by position. This kills the lightmap generator’s performance, as it may look up several times per object, resulting in O(n^2) time complexity.

This might be mitigated by updating the lightmap in-place like Fallout 2 does, but I do not currently. This might be feasible once the lightmap generator is more accurate.

In any case, this was a fun project to tackle, even if it took over a year to get it right. I played around with a lot of different strategies and had a bunch of fun spending long hours debugging and learning about Fallout 2 internals.

If you’re considering getting into the internals of old programs, I highly suggest you do. It can be a highly rewarding and informative experience.

I think it’s a shame that some of these clever and interesting systems are lost to time. We need more software archaeologists to share the fun!

Now let’s illuminate these classics!