Como um circuito ou sistema de energia (como redstone no Minecraft) deve ser implementado

8

Eu quero implementar um sistema de energia como o sistema redstone em minecraft.

Eu tenho n fontes de energia e m cabos. Se eu desconectar a fonte de alimentação ou um cabo, o circuito deve desligar. modelo de sistema de cabo

Como evito círculos? Se cada cabo com o status "ligado" alimenta os cabos próximos, posso criar círculos infinitos onde não há fonte de energia envolvida (veja a imagem). Além disso, o site é executado em T = m

Eu poderia enviar energia através do gráfico, iniciando em todas as fontes de energia e em cada chamada de atualização eu desligava todos os cabos. O problema é que ele roda em T = n * m.

Existe uma prática recomendada? No Minecraft, o sistema redstone era muito lento, então acho que esqueci alguma coisa.

EDIT: O sistema deve funcionar sem uma deterioração baseada na distância.

Benedikt S. Vogler
fonte
Isso depende de qual modelo você está tentando implementar. Por exemplo, uma fonte de energia pode fornecer x unidades de energia que são consumidas no uso. Outro modelo é que sua fonte de energia tem um potencial que limita a carga que você pode colocar no circuito, que funciona desde que você forneça energia à sua fonte de energia.
user3730788

Respostas:

7

Propagação recursiva. Por exemplo, você tem uma lâmpada conectada por N objetos do cabo a uma bateria. A lâmpada pergunta ao Nésimo cabo se está ligada (este é o cabo conectado diretamente à lâmpada). O cabo Nésimo pergunta ao cabo N-1 se está ligado e assim por diante. Cada vez que um objeto é perguntado se está energizado ou não, ele define uma lastEvaluatedvariável para o tempo de quadro atual. A recursão atinge um nó final, como uma bateria, ou quando atinge um objeto que já foi avaliado nesse quadro (isso evita a recursão infinita). Essas propagações ocorrem apenas quando o sistema é alterado. As alterações incluem adicionar / remover peças ou interruptores que estão sendo alternados.

Não há decaimento de distância ou restrições semelhantes neste sistema. Eu o usei para criar um simulador de portão lógico e funciona para vários exemplos de lógica, como um flip-flop.

MichaelHouse
fonte
Este. Além disso, gostaria de adicionar uma referência à fonte de alimentação. Se um elemento for alterado, informe à fonte referenciada para atualizar a rede que está sendo ligada. Dessa forma, você não apenas precisa atualizar quando algo muda, mas também sabe quais elementos são afetados. Mudanças em sua rede também pode ser identificada facilmente: seria uma mudança requerem reavaliação ou não, etc.
Felsir
@ Felsir Você poderia fazer isso, mas eu não recomendaria. Aumenta a complexidade sem muito ganho. Pode haver várias fontes de energia e vários sumidouros por fonte. Seria mais fácil confiar na avaliação, e realmente não é esse recurso intensivo.
MichaelHouse
Acho que a solução não tem uma coisa: se você tem um cabo no meio e um tem energia e a outra extremidade, não apenas um receberá a mudança. Você basicamente criou uma árvore com a variável "lastEvauluated" removendo círculos. Agora a mudança se propaga para cima na árvore, mas não para baixo. Vou tentar na minha implementação pressionando as alterações para baixo depois de puxá-las para cima.
Benedikt S. Vogler
Eu adicionei a solução à sua resposta em uma edição porque minha adição ao algoritmo funciona.
Benedikt S. Vogler 22/11
11
@Benedikt Você descreve o comportamento esperado. Isso ocorre porque meu sistema usa entradas e saídas. As portas AND e OR não são bidirecionais (elas usam a implementação do diodo). Portanto, se eu quisesse que o poder viajasse para algo além do nó B, direcionaria uma saída dessa maneira. Sugiro que você crie uma nova resposta para descrever seu sistema bidirecional.
MichaelHouse
2

Em minecraft, há um decaimento baseado na distância com uma distância muito curta (16 blocos de alcance).

O que você precisa é um teste de conectividade entre gráficos .

Uma maneira de fazer isso seria pegar repetidamente cada extremidade e combinar os nós conectados e em um único nó. Depois que todas as arestas desaparecerem, você terminará com um nó para cada rede. Então enviar energia é trivial.

catraca arrepiante
fonte
Salvar um subgráfico em um nó parece muito inteligente, no entanto, tenho que pensar um pouco em uma implementação concreta, porque essa resposta parece um pouco vaga, apenas mencionando o "teste de conectividade entre gráficos", que parece ser uma parte bastante importante dessa solução.
Benedikt S. Vogler
na verdade, essa descrição é uma variante do algoritmo de Karger para encontrar cortes mínimos. Mas, em vez disso, continue até que não haja mais arestas para contratar.
catraca aberração
1

Um bloco energizado possui várias conexões de entrada / saída, mas, no ponto inicial, não sabemos quando é entrada ou saída.

Cada bloco possui uma "Voltagem", que é a energia que chega a ele menos os perdidos / usados.

Um bloco energizado fornecerá energia a todos os blocos circundantes e cada bloco terá como entrada a tensão mais alta dos blocos circundantes. Você também pode complicar o sistema definindo uma intensidade, mas ficarei com a tensão apenas por simplicidade.

Toda vez que uma alteração é realizada no circuito, adicionando / removendo blocos, ou pelo próprio circuito, a alteração precisa ser propagada para todo o circuito até a estabilidade.

Eu sugiro que você crie uma interface para qualquer objeto energizado (cubo no 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;
};

Portanto, supondo que você implemente os addSibling e removeSibling, a parte mais importante é a função de propagação:

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);
    }
}

Como solução recursiva, cada bloco deve reduzir um pouco a energia, nunca aumentá-la. A fonte de energia pode definir um valor fixo, mas nunca aumenta com base nas entradas. Isso não deve ser um problema, pois todo sistema "real" funciona dessa maneira.

Adrian Maire
fonte
Mas com esta solução, cada loop precisa de chamadas "n = 1 / diminuir" antes de ser desligado. Isso não é um pouco caro?
Benedikt S. Vogler
Não, você atualiza apenas as alterações: quando você cria / exclui / edita um bloco ou quando um bloco produz uma alteração ativa. Se você procurar o código, a maioria das alterações propagará apenas alguns blocos. Claro, você pode simplificar o gráfico como dizem os @ BenediktS.Vogler, mas IMHO, já será bastante rápido. Vamos supor 1000 blocos ativos na zona ativa, o que já é um mecanismo enorme. Mesmo no pior caso de uma atualização completa, são apenas algumas operações * 1000, o que é curto. Normalmente, apenas alguns blocos são atualizados
Adrian Maire