Identifying Connected Components in Minecraft
I’m working on a Minecraft mod called Electric Blocks for my senior capstone project. Electric Blocks is a Minecraft Forge mod that allows you to run realistic power flow simulations for educational and engineering purposes. This mod makes designing and testing an electrical grid quicker, simpler, and more intuitive. A link to the project is listed at the end of this article.
One of the major challenges that I faced when designing this mod is how the mod would detect the connections between various electrical components. In a traditional environment, you can represent all of the components using a graph with the wires between each component as edges. This is usually easy to do in a single line. Here is an example using PandaPower:
My mod actually uses PandaPower as the backend for performing the power flow study and so my code does make a call just like this. Unfortunately, it’s not so simple in a block based environment. In PandaPower, a line is a single monolithic entity, but in Minecraft a wire is made out of many blocks. Since each line is made of many blocks and each line is a single entity, how can the mod tell which electrical component is connected to the others? I’ll show you an example:
The green block on the left represents a connection to the electrical grid and the checkered pink block on the right is a lit 60 watt lamp. The grid is connected to the lamp by three wire blocks. When the player right clicks on the lamp to turn it on, the mod needs to figure out what the lamp is connected to. Ultimately we need to reduce those three wire blocks down to a single connection so that the simulation can run and the lamp will turn on if properly connected to power:
To do this, I created an algorithm that fans out and searches starting with the first block that was updated. The algorithm creates a list of checked blocks and unchecked blocks. The starting block is added to the unchecked block list. We then start a loop that continues as long as the unchecked block list is not empty. We grab the first block in the list and check if it has a SimulationTileEntity attached to it. SimulationTileEntities are attached to all electrical component blocks and so this is checking if the block is an electrical component or a wire. If it does have one attached then we add it to the simulation network. After that we check if an existing connection exists and if so we terminate the new connection at this block. We then add all surrounding blocks that are at least 1 block away to the unchecked blocks list. Finally we add the block we just checked to the checked list and continue the loop. Here’s the algorithm as a flowchart:
While this should give you an idea of how the algorithm works, it isn’t very intuitive. I believe a visual explanation makes this much easier to understand. When you first right click on the lamp to turn it on, it is added and then immediately dequeued from the list. Since it is an electrical component it is added to the simulation network. It then adds all surrounding blocks and creates a new connection:
The translucent red blocks indicate a nearby block, but it doesn’t contain anything that we’re interested in. The translucent blue block indicates a wire block that is added to the unchecked list. Now the lamp is in the checked list and the first wire is in the unchecked list. In the next loop iteration, this wire block is dequeued and we repeat the process:
Here the translucent pink block represents the lamp, but this block is in the checked list so it is ignored. The translucent red and blue blocks are the same. We now have the middle wire block in the unchecked list with the lamp and right wire blocks in the checked list. Hopefully you can see how this process will continue.
The process is the same when checking the middle block.
Now when we check the far left wire, we finally run into another actual electrical component. This is the electrical grid represented by the translucent green block. This is the last item to get added to the unchecked list. Finally, we check the electrical grid block:
Now that we’ve reached another electrical element, the connection is terminated and we can tell that the lamp block is connected to the electrical grid with a wire that is 3 blocks (3 meters) long.
And that is how the Electric Blocks mod is capable of detecting which blocks are connected by wires to which other blocks. The actual implementation is a little bit more complicated. It has some logic to detect and discard loops if one is detected and takes advantage of an inner-class to store information about what the previous block was and what it was connected to. This creates a sort of linked list. You can see the details in the source code here: https://github.com/ElectricBlocks/electricblocks/blob/master/src/main/java/edu/uidaho/electricblocks/simulation/SimulationNetwork.java
Hopefully this gives you an idea of how this project works. If you would like more information, you can check the projects source code on Github or read more about it on our wiki page!
Github: https://github.com/ElectricBlocks/
Project Wiki: http://mindworks.shoutwiki.com/wiki/Electric_Power_Flow_Modeling_in_Minecraft
