8
\$\begingroup\$

I want to implement a power-system like the redstone system in minecraft.

I have n power sources and m cables. If I disconnect the power source or a cable the circuit should turn off. model of cable system

How do I avoid circles? If each cable with the status "on" powers the nearby cables I can create infinite circles where there is no power source involved (see image). Plus site is that it runs in T=m

I could send power burst through the graph starting at every power source and in each update call I turn every cable off. Problem is it runs in T=n*m.

Is there a best practice? In Minecraft the redstone system was very slow so I think I overlooked something.

EDIT: The system should work without a distance based decay.

\$\endgroup\$
  • \$\begingroup\$ This depends on what model you are attempting to implement. For example, a power source could provide x units of power which are consumed upon use. Another model is that your power source has a potential which limits the load you can place on the circuit which functions as long as you supply power to your power source. \$\endgroup\$ – user3730788 Oct 2 '15 at 13:33
7
\$\begingroup\$

Recursive propagation. For example, you have a lamp connected by N cable objects to a battery. The lamp asks the Nth cable if it's powered (this is the cable attached directly to the lamp). The Nth cable then asks the N-1 cable if it's powered and so on. Each time an object is asked if it's powered or not, it sets a lastEvaluated variable to the current frame time. The recursion bottoms out on an end node, like a battery, or when it reaches an object that's already been evaluated that frame (this avoids infinite recursion). These propagations only occur when the system changes. Changes include adding/removing parts or switches being toggled.

There is no distance decay or similar restraints with this system. I used it to create a logic gate simulator and it works for various logic examples like a flip-flop.

\$\endgroup\$
  • \$\begingroup\$ This. Plus I would add a reference to the powersource. If an element is changed, tell the referenced source to update the network it is powering. This way you not only have to update when something changes, you also know what elements are affected. Changes in your network can also be identified easily: would a change require reevaluation or not, etc. \$\endgroup\$ – Felsir Oct 3 '15 at 7:43
  • \$\begingroup\$ @Felsir You could do that, but I wouldn't recommend it. It increases the complexity without much gain. There can be multiple sources of power and multiple sinks per source. It would be easier just to trust the evaluation, and it's really not that resource intensive. \$\endgroup\$ – MichaelHouse Oct 3 '15 at 15:30
  • \$\begingroup\$ The solution lacks one thing I think: if you have a cable in the middle and one has power and the other end has not only one will get the change. You basically have created a tree with the "lastEvauluated" variable by stripping circles. Now the change propagate upwards in the tree but not down. I will try it in my implementation by pushing the changes down after pulling them up. \$\endgroup\$ – Benedikt S. Vogler Nov 22 '15 at 17:36
  • \$\begingroup\$ I added the solution to your answer in one edit because my addition to the algorithm works. \$\endgroup\$ – Benedikt S. Vogler Nov 22 '15 at 19:13
  • 1
    \$\begingroup\$ @Benedikt You describe expected behavior. That's because my system uses inputs and outputs. AND gates and OR gates are not bidirectional (these use the diode implementation). So, if I wanted power to travel to something beyond the B node, I'd direct an output that way. I'd suggest you create a new answer to describe your bidirectional system. \$\endgroup\$ – MichaelHouse Nov 23 '15 at 16:25
2
\$\begingroup\$

In minecraft there is a distance based decay with a very short decay distance (16 blocks range).

What you need it a connectivity test between graphs.

One way to do it would be repeatedly take each edge and combine the connected nodes and into a single node. After all edges are gone you will end up with a node for each network. Then sending power is trivial.

\$\endgroup\$
  • \$\begingroup\$ Saving a subgraph in a node seems very clever, however I have to think a bit about a concrete implementation because this answer feels a bit vague only mentioning the "connectivity test between graphs" which seems to be a rather important part of this solution. \$\endgroup\$ – Benedikt S. Vogler Oct 2 '15 at 14:14
  • \$\begingroup\$ actually that description is a variant on Karger's algorithm for finding min cuts. But instead you continue on until there are not more edges to contract. \$\endgroup\$ – ratchet freak Oct 2 '15 at 14:41
1
\$\begingroup\$

A powered block has several input/output connections, but at a starting point, we do not know whenever it is input or output.

Each block has a "Voltage" which is the energy that arrive to it minus the lost/used.

A powered block will provide power to all surrounding blocks, and each block take as input the higher voltage from surrounding blocks. You could also complicate the system by defining an Intensity, but I will stay with Voltage only for simplicity.

Every time a change is performed to the circuit, by adding/removing blocks, or by the circuit itself, the change need to be propagate to all the circuit until stability.

I would suggest you to design an interface for any powered object (cube in MC):

class PowerInterface
{
protected:
    std::vector<shared_ptr<PowerInterface>> sibling;

    double energy=0;
    bool   isActive = false;

    virtual void propagate(double inEnergy) = 0;

    virtual void addSibling(shared_ptr<PowerInterface> newSibling) = 0;
    virtual void removeSibling( shared_ptr<PowerInterface> remSibling) =0;
};

So supposing you implement the addSibling and removeSibling, the most important part is the propagate function:

void PoweredCube::propagate( double inEnergy ) 
{
    // Define the behaviour
    energy = inEnergy-1.0; // Normal device
    energy = inEnergy-0.1; // Normal cable
    energy = 10.0;         // Normal source of power.

    if (energy<0.0)
    { 
        energy = 0.0;
        isActive = false;
        // No energy, so do not propagate anymore
        return;
    }
    isActive = true;

    // Propagate
    for (auto &s: sibling)
    {
        // Only propagate to sibling with less energy. 
        if (energy > s->energy) s->propagate( energy);
    }
}

As a recursive solution, each block should reduce a bit the energy, never increase it. The source of power can set a fixed value, but never increase based on inputs. That should not be an issue as all "real" system work in this way.

\$\endgroup\$
  • \$\begingroup\$ But with this solution each loop needs "n=1 / decrease" calls before it is shut down. Isn't this a bit costly? \$\endgroup\$ – Benedikt S. Vogler Oct 2 '15 at 14:04
  • \$\begingroup\$ No, you only update on changes: when you create/delete/edit a block, or when a block produce an active change. If you look the code, most of the changes will propagate only a few blocks. Off course, you could simplify the graph as the @BenediktS.Vogler say, but IMHO, it will be quite fast already. Lets supose 1000 active block in the active zone, which is already a huge mechanism. Even in the worst case of a full update it is only a few operations *1000, which is short. Usually only few block are updated \$\endgroup\$ – Adrian Maire Oct 2 '15 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.