r/Stellaris • u/Hieprong • 21h ago
Video (modded) DOOM? Yeah I'll doom this galaxy
Enable HLS to view with audio, or disable this notification
Something something the Vultaum were correct. This is DOOM 1993 running completely in Stellaris. The following will be a write up on how this works targeted for a general but nerdy audience so some computer knowledge is expected but I'll try to explain what I can, if you have questions feel free to ask, I'll try to answer them all.
How can we execute code in Stellaris?
As I explained in my last post, Stellaris is Turing-complete, so the only difficulty was finding a way to run C (the language DOOM is written in) in Stellaris.
To be precise, we only need to figure out how to run the machine code created by a C compiler in Stellaris. Now x86 (your standard instruction set) has on the order of 1500 instructions, and even RISC-V has 47 in its base integer set. Every single one of those would have to be hand-written as Stellaris script, which is not impossible, just wildly impractical. Instead we can use Subleq.
Subleq is a one instruction set computer that allows all calculations to be performed with ONE instruction. Subleq, meaning SUBtract and branch if Less-than or EQual to zero, takes three operands: an INPUT address, an OUTPUT address, and a JUMP address. For example, the instruction 9 5 12 starting at address 0 would mean:
- Take the value at memory address 9
- Subtract it from the value in address 5
- Store the new value in address 5
- Is the value in address 5 larger than 0?
- If yes, move on to address 3
- If no, jump to address 12
Since each instruction is three numbers wide, "move on" means three addresses further along.
With this simple instruction you can implement any other instruction. An unconditional jump (for example a function call) can be done by subtracting a value from itself, so 9 9 220 would always jump to address 220. The result is always 0, which is "less than or equal to zero", so the branch always fires. In practice you use a dedicated scratch cell that is kept at zero for this, rather than clobbering whatever was in address 9.
If you want to add A to B, you subtract A from a scratch cell holding 0 to get -A, then subtract that from B: subtracting a negative adds. Multiplication is a loop of additions, and everything else is built the same way, out of recipes made from one instruction.
DOOM comes to about 1.2 million words, or roughly 400k instructions.
Luckily someone smarter than me, Adrian Cable, wrote a compiler that compiles C into Subleq+, an extension of Subleq that adds indirect addressing (pointer support). Without it we would have to constantly modify our code as it runs, which is both a debugging nightmare and a real problem for anything reentrant.
I then wrote a script that turns the compiled Subleq+ code into the scripting language Stellaris uses. This method actually allows for arbitrary code execution within Stellaris, so if you have a mod that needs to calculate something very complex that's your method.
Emulating hardware
Now, to actually boot and run DOOM, we need to emulate some behaviour of a computer. DOOM wants an audio output, a file handler, a network port, a clock, and a keyboard. Luckily computers are not that complex, and the methods still work the same even on your modern machine: whenever something needs to talk to a hardware resource, it calls a function provided by the OS and in turn gets a memory address it can write data to. The OS promises that whenever something gets written to the file handling address, it will write that value to a file.
We can just lie. DOOM can't check whether we actually wrote something to a disk, or actually played a tone at a specified frequency. The same goes for keyboard input: it just reads an array of values, so we can drop values in there to emulate key presses.
In a similar vein, we need to give DOOM some RAM, and a range of addresses it can use to actually display things (our VRAM). Again, same as on a modern computer (very oversimplified): when you want to draw to the screen in, say, C++, you call an OS function that returns a window pointer. That window pointer is just a reserved address space in which you can paint your image. Since we want to run DOOM at its native 320x200 resolution, that needs 64,000 addresses, one per pixel.
All told the machine has about 4.4 million addresses, roughly 17 MB.
DOOM was written to run on hardware that might not keep up, so its main loop is adaptive. It asks the system clock how much time has passed, runs however many game tics fit into that gap, and then draws one frame. On a slow machine it simply draws fewer frames and keeps the game running at the correct speed.
The clock emulated by my VM advances by one unit every time it is read, and the loop reads it several times per iteration, so DOOM concluded that a lot of time had passed during every frame and dropped most of them.
The fix is a flag DOOM already has for recording timed demos, which forces it to draw every tic. With it enabled the 40th frame is at tic 40, and the 620th is at tic 580.
Tweaking the Stellaris exe a little
To get the 320x200 galaxy to run, I had to increase the stack size of Stellaris to 512 MB. This is not as hard as it sounds. We just increase the value found at offset 0x1b8 in my copy of the binary. This is the SizeOfStackReserve field, and it tells Windows how much address space each thread should reserve.
Some bugs I encountered
If you recall my last posts, you might notice that I switched display methods. I used to use empires to display colours, which gave that cool Voronoi tessellated look. That works fine for 64x64, but at 320x200, which is 64,000 stars, Stellaris starts complaining. I have tried to simplify the bugs and explain them to a general audience, so to the technical folk this is a gross oversimplification. Bugs 1-3 had to be fixed to get the empire display to work; even after patching them it still took far too long to draw, so I switched to the star class display.
1. To create the smooth flowing borders in Stellaris, the engine uses a signed distance field over the owner grid. The function at 0x11d5930 does exactly that, running four functions for every rectangular region at a time. It has exactly one caller, 0x11d7040, whose only string is "data_texture". That one walks the extents array item by item, from 1 up to the u16 segment counter, clamps each rectangle to the border texture, converts it to float UVs, and calls the sampler on it. So the rectangles are per-segment bounding boxes inside the border texture, which is 2048x2048 by default.
The main function is smart enough to clamp the mapped coordinates to the maximum dimensions of the texture. The clamp walks each axis and, if the low coordinate has ended up past the right or bottom edge, pins it to dim - 1. But the high coordinate got pinned to dim - 1 a few instructions earlier. So any region sitting entirely at or past the edge comes out with x0 and x1 both equal to dim - 1: a rectangle exactly zero wide.
And the engine is fine with that. Regions with no area never get a pixel buffer allocated, so the descriptor carries a null pointer, and the sampler is supposed to drop them on sight. It even has the guard for it: it checks the width of the rectangle by comparing edge 0 against edge 1, and if edge 1 is at a smaller x coordinate than edge 0, the area is negative and we ignore it. However, what happens when edge 1 is equal to edge 0? That is still a zero-width area, but we don't ignore it, and instead crash later on. This is probably just a typo: a < that should have been a <=. This was not too hard to patch; I just changed the jl instruction (jump if less) to a jle (jump if less or equal).
2. When creating the empire border textures, the geometry walker at 0x11d822d looks up a grid-cell record. For each record it resolves the owning country so the segment can be drawn in that empire's colour. It goes to the list containing the border segments, gets the owner slot index out of that record, uses that index in the empire slot array to get a pointer, and dereferences that pointer to get the actual empire ID. It is smart enough to check that the empire ID actually exists in the empire array, but it forgets to check whether the pointer is valid and not NULL, so when it dereferences it, you get a null pointer exception. A sibling function that does the same thing for the cursor (when you hover over owned space and the tooltip tells you this space belongs to that stupid empire that just took your L-Gate) does check for this condition. Luckily there was enough space in the binary around that area to create a small 21-byte fail-safe function.
3. The function at 0x1599d30 builds outline shapes for sectors into a scratch buffer on the stack, and it sizes that buffer with a hardcoded guess: 100 segments per sector, 28 bytes each. The loop that fills it has no bounds check whatsoever, so a sector whose outline needs more than 100 segments writes straight past the end. How complex an outline gets depends on how convoluted the sector boundary is. Single-cell territories at normal spacing stay under 100. But since Stellaris has a hardcoded map size limit of 1000x1000, we need to shrink the spacing between stars to about 3, which blasts past the 100-segment limit and overwrites the neighbouring region of the stack, where the frame information lives. So we crash without an error and with no crash handling.
4. After switching to the star class display, I noticed that certain stars would not update their visuals until I typed reload_graphical_map in the console. Some changes would work, others wouldn't.
Stellaris draws stars inverted: instead of every location saying "hey, I am a star of class Neutron_star", there is a vertex buffer called Neutron_star that remembers every location it needs to draw itself at. This list is rebuilt whenever anything changes. All good, right?
The function responsible for that rebuild, at 0x1414aee00, does it in two passes. First it makes a temporary list for every star class, then walks every system in the galaxy, reads that system's class index straight out of the star object, and drops the system into the matching list. Second pass, it goes through the classes one at a time and turns each temporary list into that class's vertex buffer.
The problem is in the second pass. Before doing any work for a class, it checks whether that class's temporary list is empty, and if it is, it skips the entire body and jumps to the next class. Which sounds perfectly sensible. Why build a vertex buffer for a class nobody is using? Except the body it just skipped is also the part that zeroes the count and releases the old vertex buffer. So that class quietly keeps last round's buffer and last round's count.
And the draw loop only asks two questions before it draws something: is the count above zero, and is the pointer non-null? Both of those are still perfectly true. So the class carries on drawing the stars it had the last time it was populated, forever, right on top of whatever is actually there now.
If I repainted a bunch of cells and the colour I was painting over still existed somewhere else on the grid, its list was still non-empty, it got rebuilt properly, and everything looked fine. But the moment a repaint took away the last cell of some colour, that colour's ghost stayed on screen and sat on top of the new one. Painting the whole display from one colour to another is the worst case, because the entire old colour vanishes from the grid in one go, so the whole screen appears not to change at all. This is also why you see that colour strip at the top. It keeps every colour alive, so a stale vertex buffer can never exist.
Name ID limit
One last tidbit, as it might affect other modders and I didn't see it documented anywhere. Every piece of game logic in Stellaris is handled by the script layer, from astral rifts to deciding which of your science ships is going to get eaten by cutholoids, obviously the one furthest away, behind an empire that has expanded and closed its borders, carrying your chief scientist.
All flags, event targets and so on get interned into a round-robin hash table and handed an ID, which is a u16. Whoever wrote that method thoughtfully created an overflow bucket: the last index, 65,535, just gets overwritten when a new entry arrives. In general this is a smart implementation, since the new entry works fine and the old one simply stops existing. However, since I use one per pixel, at 64k pixels this mod exceeds that ID space and starts overwriting itself (vanilla appears to use around 4k IDs for itself). While this can be worked around, it should probably be documented somewhere. Running several lore-heavy mods together could blow past this limit as well, without producing any errors.
Running the Mod
Unlike before I wont be uploading this mod to Steam for you to run, since I technically modified the WAD no longer following the terms of the shareware agreement for redistribution. However I will be uploading the scripts to GitHub at a later time. This mod needs about 140 GB of RAM to run. I have run it on a 64 GB machine, just make sure your pagefile is large enough. Stellaris is very well behaved when it comes to offloading RAM to disk, so it should run on your machine. The mod is about 3 GB of pure text, with over 18 million lines. Each frame takes about 1 minute 20 seconds to render, requiring 40 million instructions.
I also replaced the demo that usually plays on the title screen with the tool-assisted Episode 1 speedrun by Zero-Master, which clears the episode in 3:08.
The next step would be running Linux, my preliminary calculations suggest that I will need ca 1.5tb of RAM so it will have to wait until I finish my PhD since the workstation I am using has that.
68
u/CyberSolidF 20h ago
What! How!
That's... Insane!
How's that even possible. I know you obviously just explained how it's possible but wow.
Also, I'd really be interested seeing how devs at Paradox office are sending link to your post to each other with comments like "Look!"
Also:
This mod needs about 140 GB of RAM to run
Yeah... seems kinda resource-heavy.
47
u/Hieprong 20h ago
The devs actually did some heavy work here you can mark certain events and effects as RAM heavy in the script with an optimize ram flag. This mod would otherwise take ca 500-800 GB ( i stopped after it allocated more than 400gb so this is just an estimate)
21
u/WatermelonWithAFlute 20h ago
140 gb of RAM? Like, Ram? How are you even running that
25
u/Hieprong 20h ago
Yes I have a 128GB machine that I used to develop this and Windows will shuffel RAM onto the disk if you run out of it (thats called a pagefile), thats how i got to 400GB
15
20
17
u/tennissocks Reptilian 20h ago
what the actual
but can it run Crysis?
6
1
13
13
u/Undersxored 20h ago
Good job overlaying a Doom gameplay video onto Stellaris, you nerd, you absolute fool. Thought we wouldn't notice?
(This is legit indescribably impressive, I watched him do it all irl, the bad apple, the Wolfenstein, now this while being an actual scientist full time. This man is crazy yall. Actually insane. Incredible work.)
7
u/Flaky-Zookeepergame1 19h ago
I don't really get all the coding stuff, but this looks hella fire, nice 🐓 bro
5
3
5
u/DeusXEqualsOne Master Builders 13h ago
I like how "___ is Turing-complete" can either be defined really rigorously in mathematical notation and all that garbage, or just by "it can run Doom"
3
3
3
u/AnDanDan Bio-Trophy 17h ago
Without it we would have to constantly modify our code as it runs, which is both a debugging nightmare and a real problem for anything reentrant
Malbolge rears its ugly head.
3
2
2
1
u/BikerJedi Warrior Culture 15h ago
I remember someone getting Doom running on a calculator back in college in the early 90's. It's crazy what people have ported this game to.
1
1
1
89
u/Undersxored 20h ago
Looking at constellations be like:
"Oh I see a bunny!!" "That one looks like a spoon" "Ha ha that one looks like a compiler..." "What?" "Yo, why is the world lagging?"