Developer Runs Doom Using Regular Expressions, Achieving 180 Seconds Per Frame

Doom on Regular Expressions

Developer Artem Lytkin has managed to run the classic 1992 game Doom using only regular expressions. This unconventional implementation highlights the computational capabilities of regex, typically used for text pattern matching and substitution.

Technical Implementation

Lytkin created a 96 MB plain-text string that functions as a virtual machine, containing sections for CPU registers, RAM, video output (framebuffer), and game data. Regular expressions then perform text-matching and character substitutions within this string to simulate processor operations and memory access. Memory access was optimized using a binary tree structure to avoid scanning the entire 96 MB string repeatedly.

Performance and Limitations

The performance of this regex-based Doom is extremely slow, requiring approximately 180 seconds to produce a single frame of game output. Each frame involves nearly 14 million text substitutions, with the engine processing 80,000 substitutions per second. Despite the slowness, the output is byte-identical to the original Doom, and the game can be controlled, though the experience is described as akin to "correspondence chess with a shotgun."

Significance

This project serves as a demonstration of the Turing completeness of regular expressions, proving that they can theoretically perform any computation. While impractical for actual gaming, it showcases creative problem-solving within programming constraints and contributes to the ongoing tradition of running Doom on unusual platforms.