Core Concepts
Before we get too down and in the weeds with the implementation, there are a few things we should go over. First, VHDL is one of the standard hardware description languages for modern hardware design. It's syntax allows you to define the "black box" of a system as well as the underlying architecture driving that black box through a multitude of different approachs, including logical statements, direct mappings and if statement-style syntax.
For example, if we wanted to create a circuit that detects if the input is the number 5 given a 3 bit input, we could write the following VHDL to define the API and architecture:
entity FIVE_DETECTOR is
port( A0, A1, A2 : in std_logic;
Y : out std_logic);
end entity FIVE_DETECTOR;
architecture LOGICAL of FIVE_DETECTOR is
Y <= A0 and not A1 and A2;
end architecture LOGICAL;
To start, this syntax is what I aim to implement in the RHDL system. There are some more advanced features of VHDL that I would love to have, but I plan to work through after the core system is proven out.
Architecture Overview
This entire system being designed from scratch required a collection of sub-modules all working together. The goal of translating hardware descriptions directly into a 3D entity in a video game is obviously very involved, and therefore benefits from several intermediate representations that make our jobs easier:
[VHDL source] => [High Level Entity and Architectures] => [Gate Level Circuit] \\
||
[NBT Entity] <= [Minecraft Block Description] <=//
In essence, we need to parse our VHDL, represent the output mappings as a boolean logic circuit, map this circuit into 3D grid space composed up out of the different gates, and finally generate the NBT entity file that Minecraft expects. Simple, right?
1. Parsing VHDL
Parsing VHDL was actually a very enjoyable process, as the language is very explicit in the different types of statements that may exist. To start, after tokenizing the input file into keywords and operators we actually care about, parsing is as simple as reading the first word of any top-level description, and following the unique rules for that statement. Both architecture and entity blocks begin by literally saying their name, and end by saying end {their name}! This is mangificent!
Thanks to this lovely gift from the IEEE 1064 Specification, we can also derive what the first AST we parse this into should look like. Our desired output should be a list of these TopLevel descriptions, being a variant of either entity or architecture. For an entity, we should track the name as well as all inputs and outputs with their specific data type (std_logic is a single bit, std_logic_vector describes a list with a specific set size). Architectures should then track their name and the name of what entity they implement, as well as a list of all mappings from input(s) to output(s) as described by a more traditional AST.
This makes parsing a very straightforward process, as most of the work we need to do is just asserting certain tokens and keywords are in the proper order before doing some simple recursive descent parsing on the *worst* branches. For instance, for the statement A <= B and not C; we would create a mapping to the AST:
[AND]
|
---------
/ \
[B] [NOT]
|
[C]
If we wanted to evaluate this as some sort of VHDL interpreter, we could simply do a tree-walk. But we don't want to interpret, we want to build a circuit... which can also just be done through a recursive tree-walk :D
Finally, before we move into the next IR, there is one final pass through of all TopLevels we must do to make things easier. We will combine all Entities and Architectures that are referring to the same system (same name) so that we have all input/output names and mappings in one nice package for the next subsystem to consume.
2. Circuit Intermediate Representation
Now that we have a distilled version of the *intent* of the hardware description, we can work our way towards a representation that is easier for us to translate into a 3D Minecraft circuit. As such, all we really need to do on this step is translate our high level Expression ASTs into concrete circuit entities that point to same inputs. I implemented this circuit as a Graph-like structure using a SlotMap as the underlying data structure, meaning we just pass around Graph Indices instead of node pointers (a pattern I learned from the more strict world of Rust that I just like for problems like this now). As such, the Circuit API allows us to request a type of gate to be created, and returns the Gate ID of that created gate. This makes chained graph construction super nice, as can be illustrated in the pseudocode below:
circuit = new Circuit();
A = circuit.input("A");
B = circuit.input("B");
C = circuit.and(A, B);
not_C = circuit.not(C);
output = circuit.output(not_C);
I mean that just feels great the write out, and luckily for us our AST walker agrees. Translating from high level expression into a circuit is as simple as walking the expr tree recursively depending on the expression type:
- If we're a binary expr, first eval both left and right, get their Gate IDs and then create a new gate with those IDs as operands
- If we're unary, do the same but with only the single child expr
- If we're an input, just return the ID of the input that was already added during the Entity definition
And just like that, we have created a circuit graph! This is great because it both combines all the expressions from our parsing step into a single circuit that can be used later, and it also is a great area for translating from some higher level VHDL statements into their digital logic equivalents, allowing us to implement some more complex features without needing to change any of the later steps.
3. Mapping to a 3D Grid Circuit
Oh boy, this section's going to be a lot. Coming in to this subsystem, we have a flat circuit graph representation of the desired logical behavior that our original VHDL was describing. Coming out of this system, we need a 3D functional representation of this system using Minecraft blocks. We have to take into account all of the problems that come with building something real, including signal strength, positioning of gates, input to output pathfinding, collision mitigation, gate resizing based on child sizes, and so much more.
3.1. The Basics
Before we get too overwhelmed let's just start with what we need: a 3D graph that can have Minecraft blocks 'placed' within it. As such, we will describe a new struct CircuitEntity as a collection of blocks with points. The positional data about a block will be stored through a Point -> Block HashMap, and blocks will be defined as a tagged union with additional metadata based on what the block needs. We will also store inputs and outputs as lists of Points, which will be useful for combining circuits by strining outputs of one to inputs of another. Finally, we'll also store the total size of the circuit by always tracking the most extreme points that may push past the previous size boundaries.
3.2. The Gates
Our circuit will always be composed out of smaller basic gates: AND, OR, NOT and XOR. As such, these gates can be almost hardcoded as convenience functions that let us very easily create one when need be. As such, we will create methods that return a new CircuitEntity object for each of them. One important design choice we'll make for later is to allow for a "padding" argument in these gate constructors, this will greatly help us later.
As touched on earlier, Minecraft is Turing complete in that each of these gates can have their truth tables represented by some configuration of Redstone wire and the many components Minecraft lets you have access to. These components are as follows:
- Repeaters: they take in a Redstone signal from one end and repeat it with the highest strength at the output. There is a configurable delay you can add between the propagation of input to output, with the lowest delay being a single tick of Redstone activity. This component is very important for our giant circuits because a redstone signal dies over the span of 15 or so blocks. Placing repeaters will allow this signal to go further at the cost of an increasted propagation delay.
- Comparators: A comparator... I am less confident in my explanation. They have 3 inputs: the back and both sides and send an output based on the mode they are in. There are two modes: subtraction and comparison. Subtraction outputs a 1 if the back input is greater than the max of either side's input. Comparision mode will output the back input if it is greater than or equal to both side inputs.
- Redstone Torch: A power source!
From these components, we can generate any gate as a construction of them.
Redstone Wire: *
Redstone Torch: !
Repeater: #
Comparator: %
OR Gate:
NOT Gate:
XOR Gate:
AND Gate:
Do I understand exactly how all of these gates work? Not at all. Did I see some diagrams online and play around with them until I had gates you could dynamically pad? Yes!
3.3. Combining Gates
The next logical step is to take our smaller gates and create some way of connecting and combining them together. This is where tracking inputs and outputs in a CircuitEntity comes in handy! We can create a method that will take two CircuitEntitiys and wire the output of one to the input of another, modifying the second circuit. By doing this, all we have to do is shift the second circuit entirely over until the input matches the same X coordinate as the output of the other circuit, and then shift the circuit up along the Z axis until no collisions occur. After this, we can do some simple pathfinding to run a redstone wire between the points.
This works perfectly fine ASSUMING that the parent gate (the one getting it's input wired to) has a large enough padding so that any other gate going to another input of the parent gate would not be caught in some form of collision, which would be no fun. To solve this, we can use the recursive power of our circuit definition to create some dynamic rules for the padding of a gate!
- For input gates, we only need a padding of 1 block on both sides so nothing overlaps with the wires
- For Binary gates, we need some specific padding to the gate size plus the largest padding necessary from either child to ensure that child doesn't overlap the other child
- For unary gates, we simple need the maximum between the gate's size and the size of the child's padding
This creates a nice little system that allows us to always know how much padding each gate needs before we create it, allowing us to avoid those nasty collisions! This does make the circuit ultimately bigger than an optimal version would be, but regardless I was quite happy with this solution.
3.4. Input Grids
We now have a system where walking a circuit will generate all of the gates we need as 3D Minecraft CircuitEntitys. We could stop here and we would technically have succeeded in our goal of mapping VHDL functionality to Minecraft Redstone. But there's one more thing that would make using our system much more convenient, an Input Grid.
Take for instance a Full Adder component. This module has 3 inputs, Bit A, Bit B and the Carry Bit CIN from the previous adder for a ripple carry adder. It has two outputs it derives, Carry Out and the Sum bit of A B and CIN. These outputs both depend on our 3 inputs several different times, creating a resultant series of gates that require multiple different points of input for a single one of these input bits. It would be great if we could instead have our 3 inputs on 1 side, and automatically route them to all spots that expect that input.
Let's do it.
The basic concept is pretty simple to track. Once we have our final circuit fully generated, we'll just shift it up the Z axis enough times to fit some inputs, and then run redstone wire along the X axis below the circuit, with a lever at the start of each wrire for our input. For example, let's say we generated a circuit that just gives A OR B. The input grid and gate would start off as:
*
*****
# #
B* A*
A*********
B*********
Now all we need to do is connect! Except.. we can't just do that. Because we'd collide B's wire with A...
3.5. Bridging
To handle cases like the above where a wire collision is *unavoidable*, we need to branch out into the 3rd dimension. Our pathfinding logic will now check for if the current point we're going to move to is currently occupied or not. If it is, we'll push up our current position by 1 y value, place a wool block below our wire, place another block above the obstruction and move along our way 2 y levels above. Once we see that the ground is safe again, we can do the opposite process and bridge down.
And just like that, after a couple weeks of debugging and collisions on larger level circuits, we were finally generating properly functional 3D circuit representations of VHDL files as Minecraft Redstone logic! We're in the home stretch, now all we need to do is emit this data in a format that Minecraft understands.
4. Exporting to NBT
The Named Binary Tag (NBT) format was designed by Minecraft's original creator to be the data storage format for all saved components of a Minecraft world, from chunk defintions to (what we're interested in) structures. The original spec was originally a text file found on Minecraft's website, but has since been removed and can only be found archived. It's a relatively simple binary format, with the core packets being defined by a single byte tag type, an optional name, and a payload defined by the tag type. There are 11 total tags that range in complexity:
- Tag_end: Denotes the end of a list or compound
- Tag_Byte: Single byte
- Tag_Short: A signed 16 bit big-endian integer
- Tag_Int: A signed 32 bit big-endian integer
- Tag_Long: A signed 64 bit big-endian integer
- Tag_Float: A 32 bit floating point value
- Tag_Double: A 64 bit floating point value
- Tag_Byte_Array: A list of bytes with a specified 32-bit unsigned length
- Tag_String: A list of bytes with a specified 16-bit unsigned length
- Tag_List: A list of a specific tag type where the tag and number of elements is specified
- Tag_Compound: A nested list of any Tag, a Compound ends with Tag_end
The final note of the spec is that after this initial binary representation is constructed, the entire file is GZIP'd to compress it further and save space. Cool.
4.1. Basic Spec Implementation
To better understand each of these formats, I first wrote a parser before going the other way. This allowed me to generate a known valid NBT file, parse it, and then serialize it again to ensure I had both steps working properly. The definition for both parsing and serializing the NBT format was a very fun recursive method that matched on the tag type byte and reacted accordingly. For whatever reason I decided not to use an arena allocator here for the elements, which made me also define a recursive deinitialization method that would ensure the children of lists and compounds did not leak.
4.2. Circuit to NBT
Now that I had utilities in place for creating NBT files, I had to learn the actual format that a Minecraft structure entity expects. Thanks to this amazing online NBT visualizer by irath96, I was able to load a structure I generated from Minecraft to see what form the NBT takes. The root tag was a compound of the following components:
- size: a list of 3 IntTags describing the length, height and width
- palette: a collection of every block in every state used by the structure. This allows us to reference indices in the palette when "placing" blocks, allowing us to just use an integer instead of a full blown object. The palette entries contain a string for the name, as well as a compound list of properties specific to the object (direction facing for directional objects like the repeater).
- blocks: A compound of objects composed of the palette ID they represent as well as the xyz location relative to the bottom right corner of the structure.
With this structure in mind, the plan I had was to first generate the palette by creating a hashset of all unique block states used by the circuit. Then as we build up the blocks, the index of that element in the hashset would correlate directly to the index in the exported palette. The state of a block was a tagged union so that blocks such as the comparator could have their unique properties (direction facing and if we're in subtract or compare mode). Once this was all up and working, the NBT binary file generated was properly formed and loaded into Minecraft without a hitch!
5. Conclusions
Overall, with this project in a functioning state, I am super happy with the system I was able to construct. It taught me valuable lessons in separation of concerns and creating separate subsystems to keep systems small and testable in and of themselves. This is by far the coolest codebase I have been able to work on, and for it all to go towards such a silly end product is all the more rewarding. I see a lot of RHDL work in my future, with new VHDL features being implemented, and work to minimize circuit propagation times and size, but overall I am happy with the first steps I had to make to make such a fun project a reality :)