Successfully running 'DOOM' using only regular expressions, rendering one frame takes approximately 180 seconds.
Programmer Artem Ritkin has unveiled ' DOOM on regex ,' a project that runs the classic FPS 'DOOM' using only 'regular expressions' used for string searching and replacement. DOOM on regex packs everything from registers, RAM, frame buffers, the DOOM game itself, and WAD data into a single string of approximately 96.6MB, creating a virtual computer that runs on just 544 replacement rules. Drawing one frame of the DOOM screen requires approximately 13.99 million replacements using parallel processing on five machines, taking about 180 seconds.
DOOM on regex - find & replace as a computer
GitHub - 4RH1T3CT0R7/doom-regex: DOOM running on nothing but regex find-and-replace. One 96 MB string, 544 rules, byte-identical to native DOOM · GitHub
https://github.com/4RH1T3CT0R7/doom-regex
Regular expressions are a mechanism for searching for specific strings within text or replacing parts that match certain conditions with other strings. They are typically used for extracting email addresses or phone numbers, or for batch text transformations, but by combining complex conditional branching and string manipulation, they can also be used to express calculations.
DOOM on regex doesn't directly rewrite DOOM using regular expressions. Instead, it creates a small 32-bit virtual CPU called 'RVM-1' that operates solely on regular expression search and replace, and runs DOOM on this virtual CPU. The DOOM core itself is a portable implementation of doomgeneric, which is then converted into RVM-1 instruction sequences using the C compiler 8cc and ELVM .
In the following GIF animation, one frame of the DOOM screen is drawn on the left, while the execution of the replacement rules flows on the right. The bright green areas on the left are the pixels being written by the replacement at that moment. Walls are painted one vertical row at a time, and floors are painted in horizontal blocks at a time. While the brush is stopped, the BSP tree is traversed to determine the next target to paint.
The mechanism of iterative substitution using regular expressions is
the Markov algorithm
itself, a classical computational model, and is theoretically a ' Turing complete ' mechanism capable of performing the same types of calculations as a regular computer. Therefore, Litkin says, it should have been possible to run DOOM using only regular expressions from the beginning. Litkin states that the two questions that were actually worth asking were whether it could be run before the universe reached its thermal death, and how to prove that no cheating occurred along the way.The state of the virtual computer is stored as a single massive string of text, approximately 96.6 MB in size. This string contains, in plain text, the CPU registers, RAM, the program being executed, the frame buffer that holds the screen, the DOOM game engine, WAD data containing stages and graphics, and input/output areas.
During execution, the driver repeatedly checks 544 regular expression substitution rules in a predetermined order. The first rule that matches the conditions at that point is applied only once, replacing part of the string with another character; this process corresponds to one step in the virtual computer. Litkin explains that when a rule is deleted, all that remains is a huge, non-functional text file, and the calculations and interpretation of instructions are not being outsourced to an external program.
For example, when a virtual CPU adds numbers, it uses regular expressions to reference an addition table consisting of 512 items, and performs the calculation while carrying over any carries. When accessing memory, it constructs a jump distance according to each bit that makes up the address, and moves directly to the target location within a string of approximately 96.6 MB using a mechanism similar to a binary tree. Processing time is reduced by not searching the entire string from the beginning each time.
In the image below, the parts shown in green are the pixels currently being rewritten by the regular expression replacement process. The screen is not generated all at once; areas such as walls and floors are drawn gradually.
The regular expression rules that run the virtual CPU are listed below, and operations such as 'fetch' and 'mov' are reproduced as substitution rules.
The initial version only managed 7 substitutions per second, and it took 12 hours just to process the last 295,000 substitutions in a single frame. Subsequently, by introducing a mechanism to directly jump to the target location by traversing each digit of the address, flattening the memory area, and implementing measures to avoid copying the long, unchanging first part of the file after substitution, the processing speed improved to approximately 80,000 substitutions per second per core with PCRE2 JIT compilation enabled.
This single frame of DOOM was completed after approximately 13.99 million substitution operations. This corresponds to the 60th frame of the 'E1M1' time demo, the first stage of DOOM. According to Litkin, it matches the same frame rendered by a normal DOOM game down to the byte level, and the SHA-256 hash value also matches. Furthermore, recognizing that there was a possibility of luck with just one frame, he also calculated the 100 frames from the 160th to the 259th frame of the same time demo, spending approximately 1.25 billion substitution operations before all 100 frames matched those of a normal DOOM game down to the byte level.
The final calculations are distributed across five machines, generating one frame approximately every three minutes. While this is extremely slow compared to typical games that display dozens of frames per second, Litkin explains the feel of the gameplay as 'closer to a game of chess using a shotgun than a shooting game that demands quick reflexes.'
A demo is also available for Windows that allows you to run an actual regular expression machine. You can move using the WASD keys or arrow keys, shoot with the Ctrl key, and open doors with the spacebar. Input is recorded to a file and then passed to DOOM via I/O instructions of the virtual CPU. In the demo screen, you can see in real time which substitution rules are being executed, what is being read, and which characters are being written, alongside the rendering of DOOM.
To ensure it works correctly, Litkin has prepared a reference emulator that implements the same instruction set in Python, and tests whether the string matches the emulator's state byte by byte after each substitution. According to Litkin, there are no other known examples of applying fixed regular expression rules cyclically to run games and videos like DOOM. The source code for DOOM on regex is available on GitHub, and a demo has also been released.
Related Posts:
