Can Doom Run It? An Adding Machine in Doom

Yes.

For years, we’ve asked ourselves “Can it run Doom?”. Now we can lastly make the supreme punchline: “Can Doom run it?”

I show that it is possible to run any bounded calculation in Doom, minus restraints on level size. I have actually not shown that Doom is Turing total (see the area later on in this short article).

This deals with the vanilla MS-DOS release of Doom 2 (v1.9). No mods or anything!

I like tasks like these. I was motivated by the mystical devices in other video games such as Minecraft and RollerCoaster Tycoon

Demonstration

Source code

If you’re curious about how this works, I launched the source code to construct the map here:

https://github.com/nukep/doom-calculator

NAND: The universal reasoning gate

My very first expedition into this subject was to carry out a NAND gate If I might carry out NAND, I understood I might execute anything.

NAND is a universal reasoning gate In other words, universal reasoning gates can be made up to produce all possible reasoning gates.

NAND fact table:

e.g. if a holds true and b holds true, the outcome is False.

Specifically, NAND represents 2 on/off inputs, and one on/off output. If both inputs are on, then the output is off. If any of the inputs are off, then the output is on.

It ends up that from simply a measley reasoning gate, you can integrate NAND – you can feed NAND into other NANDs – and you can develop any reality table. In impact, all bounded calculations are possible.

My procedure to finding out if this was convenient in Doom was to experiment with a Doom level editor – particularly, SLADE. I simply needed to execute one NAND gate. After great deals of experimentation with lifts, actions, teleporters, switches, doors, beasts, and even replicate gamers, I discovered a system that was basic and robust.

Binary Decision Diagrams

A repercussion of my findings was that my system might represent any boolean reasoning as explained in a binary choice diagram

We can represent NAND from earlier utilizing a binary choice diagram.

There are 2 nodes for variables a and b. The dotted lines represent off, or 0. The strong lines represent on, or 1.

If we begin at “a” and “a” is 0, then we will go left and come to the outcome of “1” and our work is done. If we begin at “a” and “a” is 1, then we go right and we show up at “b”. If “b” is 0, then the outcome is “1”. If “b” is 1, then the outcome is “0”.

We might choose to chain NANDs together and produce a lot more intricate diagrams. In my case, I chose not to simply chain NANDs together, since this does not develop extremely effective diagrams. In practice, we’re much better off chaining together other reasoning gates such as AND, OR, XOR, and so on – or to straight transform a reality table to a diagram.

As a Doom level

Visual of a NAND gate (a=1, b=0):

Binary choice diagrams can be represented in Doom in a really direct way.

A node ends up being a little space, with 2 doors for 0 and 1. Root nodes have beasts in them.

An edge of a node ends up being a teleportation from a teleporter behind a door to another space, if that door is to be opened.

The doors are opened by switches triggered by the gamer. They can likewise be opened by other beasts (I discuss why this works later on).

I decided to represent 0 and 1 with 2 changes each. Initially it may appear more sensible to have a single switch for each variable. I discovered it simpler to be specific about setting a variable to 0 or 1, and for the estimation to wait till they’re set.

In the last calculator WAD, I do have private switches for each digit, however this is absolutely nothing more than a visual impression. These are privately variables where the 0/1 sets are divided into 2 digits each: (0,1) ->> a; (2,3) ->> b; (4,5) ->> c; (6,7) ->> d; (8,9) ->> e. E.g. “6” suggests “d=0”, “7” indicates “d=1”.

How do we include numbers with this?

It can be tough to think of how beasts teleporting to locations can represent addition. This is among those issues that’s much easier to comprehend in smaller sized pieces going bottom-up.

We went from NAND, and after that to binary choice diagrams. Next, let’s attempt including 2 binary digits.

There are 2 binary digits: 0 and 1.

The guidelines for addition over binary digits are:

We can likewise choose to analyze the above guidelines as a reality table. This is referred to as a half-adder

A half-adder is comparable to the reasoning gates:

• bring=a and b
• amount=a xor b

This is terrific for including 2 binary digits … however we wish to include larger numbers!

It’s completely legitimate to integrate great deals of half-adders together to develop an including maker. In practice it’s more effective to execute unique reasoning to include 3 bits: 2 numbers and a bring bit. This is referred to as a full-adder

i.e. with 3 terms such as: “1 + 0 + 1=0, bring the 1”.

A full-adder is comparable to the reasoning gates:

• bring=(a and b) or (b and c) or (c and a)
• amount=a xor b xor c

It’s now possible to chain a half-adder with numerous full-adders to produce an n-bit-adder(where n is the number of bits we desire). It works much like conventional addition: Add 2 numbers, then bring the 1 over to the left set of digits, then include those, and so on.

We’re interested in including numbers from 0 to 9 How do we represent that? It ends up we require a minimum of 4 binary digits to represent the numbers from 0 to 9 (where 0=0000, and 9=1001). We utilize a 4-bit-adder.

There’s a significant concern nevertheless, and it’s that we wish to show lead to base 10, and not binary or hexadecimal.

We fix this by adhering the outcomes of a 4-bit binary adder. The resulting reasoning is called a BCD adder(binary-coded decimal adder).

If the outcome is higher than 9, then include 6. Apply modulo 8 to it. Set the bring bit.

This method, an operation like “9 + 5=14” would yield “1001 + 0101=0100, bring the 1”.

BCD adder pseudocode:

 zc, z3, z2, z1, z0=cin + (a3, a2, a1, a0) + (b3, b2, b1, b0) cout=zc  or(z3  and z2)  or(z3  and z1) s0=z0 cc1, s1=z1 + cout cc2, s2=cc1 + z2 + cout _, s3=cc2 + z3 

The resulting (unoptimized) binary choice diagram appears like this (input variables are colored blue, short-lived variables are colored yellow):

Go here for a complete variation

To summarize: The above diagram represents including 2 digits from 0 to 9, and getting a 0 to 9 digit with bring.

There are numerous trees to facilitate this. Some will set variables whose sole function is to be utilized in other subsequent trees.

To envision the above diagram with beasts and teleporters, the top of each tree (the root node) will have a beast in it. All non-root nodes will be locations for beasts. There are 14 beasts in overall, for 14 trees.

Linking outputs to variables

In order to make up diagrams from numerous smaller sized diagrams, it’s beneficial to state “this output ought to be a variable”. You might have observed that the BCD adder depends upon this.

The variation of this in a Doom level is “a beast going through a teleporter must open other doors”.

In vanilla Doom, beasts can’t trigger switches or remote-open doors. What I’ve chosen to do rather, is make use of a peculiarity in the Doom engine All doors are connected with a sector If a door shares a sector with another door, then the 2 doors will constantly open and close together. Beasts can’t open remote doors, however they can open regional doors. If that regional door shares a sector with other doors, then beasts can from another location open doors!

So in location of a last location, a beast teleports to a space with a single door that they’re required to keep open. That door shares a sector with several other doors that will then be opened.

There are numerous restrictions to this peculiarity. Shared sectors need to have the precise very same flooring and ceiling textures, as well as heights. This does not hinder performance, so we’re great with it. Numerous Doom level editors (such as SLADE) likewise attempt to “unshare” sectors if you attempt to modify unique polygons, so if you’re modifying the map later on, it needs care.

Digit display screens

I figured that simply revealing binary worths was too dull. I needed to drive the point house and go huge with revealing real numbers.

The method I approached the digit display screens, was to produce a reality table for each pixel of the screen.

A number from 0 to 9 can be represented with 4 binary digits (0/1). I’ll take the pixel at row 1 column 2 and reveal its fact table. Keep in mind that for readability I’m condensing 4 inputs into one column of the table.

This can be revealed as the following binary choice diagram:

There are binary worths 10 thru 15 that are undefined, since we’re not anticipated to experience them. The algorithm I composed to produce the diagram will designate approximate outputs for 10 thru 15, depending upon which enhances the diagram more. (in practice, for digits, “bit 3=1” simply describes 8 and 9. if 8 and 9 have the exact same outcome, we understand the outcome for “bit 3=1”)

Generating the level with code

I didn’t make the including maker in a level editor. Doing it all by hand would be exceptionally laborious and error-prone. I composed code!

The code to create the WAD file is composed in the programs language Clojure

Lisp abides by the code-is-data approach, so it’s rather instinctive to compose tree structures as code.

We can represent the NAND gate from earlier utilizing Lisp syntax.

( a 1( b 1 0)) 

This is a tree information structure. It’s made up of embedded lists in the kind of ( variable on-0 on-1)

We can likewise imagine this as a sideways tree that checks out left-to-right:

But the actually cool part, is that this works doubly as code. If a and b are functions that return the left or ideal type, you can really perform this and get an outcome!

( defn a [Best] ) ( defn b [ Best] ) ( a 1( b 1 0)) 

We can execute more intricate reasoning in a really concise syntax:

( cin( a( b 0 1) ( b 1 0)) ( a( b 1 0) ( b 0 1))) ( cin( a 0( b 0 1)) ( a( b 0 1)  1)) 

The application of those functions depends on what you’re attempting to do. In my case for producing levels, all functions for variables discharge an adjacency list for a chart, where the nodes are recognized by auto-incrementing numbers.

Many binary choice diagrams are not trees, nevertheless, however charts. Nodes in a binary choice diagram can have more than one moms and dad. How do we reveal charts?

This is in fact a stealthily simple issue to fix. If we assert that all trees are immutable mathematical worths, then we can state whether 2 trees are comparable. Comparable trees are deduplicated, efficiently developing charts in memory.

Optimizing trees

I utilize a range of methods to enhance trees:

1. If a tree “a” indicate trees “b” and “c” and b=c, then a=b=c
2. If a variable “v” is just utilized as soon as anywhere, remains in a root tree “a” and the tree indicate trees “b” and “c”, then v. 0=b and v. 1=c
3. Remove all trees that do not ultimately add to outputs (where beasts would appear).

Optimization 3 was one I selected to carry out utilizing adjacency matrices. Where K is an adjacency matrix of trees to trees, I calculate K ^ 0 + K ^ 1 + K ^ 2 + …, which offers us a result of all obtainable trees. The code for it is here: https://github.com/nukep/doom-calculator/blob/e3dd9c0c6de19830 febd0d1f845 befca70 advertisement632 d/src/doomcalc/ tree.clj #L217

Drawing the level

Doom’s level format is WAD. Heap formally means “Where’s All the Data?” according to Tom Hall’s “Doom Bible”.

Despite the video game being 3D, Doom maps exist on a flat 2D cartesian aircraft. Height is attained by specifying variable flooring and ceiling heights for polygonal shapes in the map (Doom calls these shapes “sectors”).

WAD is thankfully an extremely basic file format, so I had the ability to carry out a WAD author from scratch.

Because the levels are represented in 2D, regimens to draw the level resemble drawing vector graphics in general. E.g. “draw line from a to b”.

Overcoming vanilla Doom peculiarities

I discovered that beasts opening doors operated in GZDoom, however it in some cases didn’t operate in Chocolate Doom or the vanilla MS-DOS Doom.

To find out why, I did what any smartly sane individual would do: Look at the Doom source code. (whatever else I’ve done has actually plainly been sane approximately this point)

The main source code release for Doom from id Software can be discovered here: https://github.com/id-Software/DOOM

I Ctrl+ F’s some keywords such as “open” and “door”, and ultimately came across the code where beasts attempt to open doors by themselves.

I began with the P_Move() function here: https://github.com/id-Software/DOOM/blob/77735 c3ff0772609 e9c8d29 e3ce2ab42 ff54 d20 b/linuxdoom -1.10/ p_enemy. c# L272

The treatment for beasts opening doors is the following, as pseudocode. I overlooked a great deal of ireelevant information.

 def P_Move( star): try_position=actor.position + actor.speed actor.direction actor_moved= False spechit=[]  for each line within the star radius  from try_position:  if line has no back face:  break if line obstructs gamers  or beasts:  break if line has an unique action: spechit.push( line)  if loop did  not break:  if brand-new flooring  is within 24 systems ( not too expensive  or low):  if star can fit  in the space: move the star to try_position actor_moved= True for each line  in spechit,  in reverse order:  if star strolls over line: set off line spechit=[]  if not actor_moved:  for each line  in spechit,  in reverse order: utilize line spechit=[] 

These were the most essential findings:

• The video game look for all unique lines within the beast’s radius, from where the beast is attempting to go (not where it is).
• There’s an international selection that’s added with unique lines “spechit”. Up to 8 can be kept, however the video game does not stop at 8 (possible buffer overflow).
• Blockmaps are browsed in column-major order (bottom-up, then left-right)
• The model regular stops early if any line in reach of the beast has the “block gamers” or “obstruct gamers and beasts” flag made it possible for.
• It likewise gives up early if it discovers a wall without any back face (such as the external edge of the map).

To permit beasts to open door, we follow some rule-of-thumb constraints:

• No lines with “block players/monsters” flags within beast radius+ speed (for Pinky: 30.0 + 10.0=40.0 systems)
• No one-sided lines (such as the map boundary) within beast radius+ speed (400 systems)
• Keep any doors you do not desire opened by a beast beyond beast radius+ speed (400 systems)

Interactive Demo: Digit display screens

Press among the buttons listed below to replicate the digit screen.

This is real to what occurs in the Doom map.

Does this mean Doom is Turing total?

My observations didn’t show it. This would be a fantastic claim though, since it would indicate we might run anything, consisting of Doom itself (well … if we got rid of map and memory restrictions).

To clarify, Doom is absolutely functionally total That is, if we were to eliminate all the technical restrictions, it can run all reasoning gates.

For Doom to be Turing total, it needs to enable some sort of unbounded looping construct.

My system is not Turing total, and it’s due to the fact that it does not have unbounded loops and state. When beasts get to their location, they remain there permanently. There’s no chance to “reset” beasts. This can most likely be done by selectively remembering (teleporting) specific beasts so they can function as input to the next model of the computation. This is most likely the next action to showing whether Doom is Turing total.

Am I positive that it’s Turing total? Yeah! It needs more work prior to we can with confidence state so.

If it’s ultimately thought to be Turing total, we can show Turing efficiency by executing something that is. If we can execute Game of Life or Rule 110, then that would suffice evidence. (I’m partial to Game of Life, since of the paradox of “Game of Life” remaining in a computer game about eliminating devils).

Someone else got reasoning gates in Doom, too!

So, I was really dealing with this task on-and-off for 2 plus years. Throughout it, Jared Candelaria beat me to it! Even had the very same concept for the post title!

https://calabi-yau.space/blog/doom.html

Their method was various from mine, and includes lifts and integrating with the timing of those lifts. They declare it’s Turing total, however I have doubts about this (comparable to the reasons mine isn’t).

Download the WAD

If you’re running it, I suggest a modern-day source port like GZDoom.

I likewise offer a variation of the WAD that runs in the MS-DOS release of Doom 2 (v1.9), albeit with a great deal of visual problems. It’s practical, and real to the constraints of vanilla Doom!

Here!

https://github.com/nukep/doom-calculator/releases/

READ MORE