Blocos caindo e formas complexas

10

Atualmente, tenho um jogo simples do tipo Tetris e me deparei com um problema que não consigo resolver.

Ao contrário de Tetris, onde há uma única forma em queda, tenho várias formas potencialmente interligadas que precisam cair; Eu preciso calcular suas posições finais. Considere o seguinte:

exemplos do problema dos blocos em queda

  1. Para calcular a posição final da forma verde, simplesmente digitalizo para baixo cada quadrado até atingir outro quadrado ou a borda do quadro. Feito

  2. Para várias formas simples, eu caminho até o quadro. Assim, o vermelho não precisa ser movido, a laranja diminui em um, o verde diminui em três. Feito

  3. Não sei como tratar as formas verdes e vermelhas entrelaçadas. Usando a lógica do número 2, acabaríamos "presos" flutuando no ar. Se eu procurar a forma verde, encontro o vermelho e, portanto, não me movo, e vice-versa para o vermelho. A solução pode ser tratar as duas formas como uma.

  4. Semelhante ao item 3, nesse cenário eu também poderia obter sucesso tratando os objetos como um.

  5. Ao contrário dos nºs 3 e 4, eu não poderia tratar a forma como uma, pois a forma laranja acabaria flutuando um quadrado muito alto ...

  6. Outra variação do problema # 6.

Pode haver outros cenários nos quais tenho muitas formas que se entrelaçam em cenários cada vez mais complexos, mas acho que o exposto acima cobre as partes mais fundamentais do problema.

Sinto que há uma solução elegante que ainda tenho que encontrar / pensar e ficaria muito grato por qualquer insight, idéias ou recursos.

SOLUÇÃO

A solução que eu encontrei é realmente elegante, com base na resposta de @ user35958 abaixo, criei a seguinte função recursiva (pseudo-código)

function stop(square1, square2){
    // Skip if we're already stopped
    if(square1.stopped){
        return;
    }
    // Are we comparing squares?
    if(!square2){
        // We are NOT comparing squares, simply stop.
        square1.stopped = true;
    } else {
        // Stop IF
        // square1 is directly above square2
        // square1 is connected to square2 (part of the same complex shape)
        if(square1.x == square2.x && square1.y == (square2.y+1) || isConnected(square1, square2)){
            square1.stopped = true;
        }
    }
    // If we're now stopped, we must recurse to our neighbours
    stop(square1, squareAbove);
    stop(square1, squareBelow);
    stop(square1, squareRight);
    stop(square1, squareDown);
}

GIF animado mostrando cada passo da solução

Para resumir:

  • Ao "parar" um quadrado, também paramos:
    • QUALQUER quadrado acima dele. SEMPRE.
    • Praça vizinha à qual estamos conectados (ou seja, a mesma forma).
  • Paramos toda a linha inferior e a função se repete através dos quadrados.
  • Repetimos até que todos os quadrados sejam parados.
  • Então nós animamos.

GIF animado mostrando cada passagem da sequência lógica

oodavid
fonte
Eu imagino que se você resolvesse 5 que 6 seria resolvido também. De fato, acredito que resolver 5 provavelmente resolveria todas essas situações.
precisa
+1 obrigado por compartilhar. Solução incrível. Amo a animação :)
ashes999
Elogios ashes999, eu acho que preciso de uma nova animação com setas que mostram a forma como a lógica stop "flui" para cima da linha de fundo e prolifera por todo o palco ...
oodavid

Respostas:

4

Bem, você não precisa tratar as formas como uma só, se houver uma distinção entre formas que estão se movendo e formas que estão em repouso. Uma forma (A) pode detectar uma forma (B) diretamente abaixo dela e se estiver em movimento, então a forma B pode ver se há algo diretamente abaixo dela, e se houver uma forma de repouso, A e B agora estão descansando e se não houver nada, os dois se moverão para baixo, mas se houver uma forma móvel, essa nova forma será tratada por A e B como A tratada B, então é meio recursivo. Lembre-se de que, para cada etapa, as formas mais baixas precisam verificar as formas abaixo delas primeiro.

Portanto, para o problema nº 6, a forma verde é a forma móvel mais baixa e veria que a única forma que está diretamente abaixo dela é a forma vermelha; portanto, a forma vermelha não detectaria nada diretamente abaixo dela e se moveriam para baixo . Uma vez que a forma verde é adjacente à forma laranja, ela descansa e a forma vermelha desce e então detecta a forma verde em repouso, e também descansa.

awsumpwner27
fonte
Estou certo ao pensar que teríamos que assumir que todas as formas não estão em repouso até provarmos o contrário?
Oodavid
Passei algum tempo pensando sobre isso e devo dizer que parece uma técnica muito boa. Vou tentar amanhã / fim de semana e ver como ele se desenrola.
oodavid
3

Parece que o problema com os casos 5 e 6 deriva de uma única raiz: você está executando apenas uma verificação de passagem.Você deve continuar movendo as coisas para baixo (vamos chamá-lo de "passagem da gravidade") até que você saiba que nada se moveu.

Por exemplo, no caso 6, é isso que aconteceria se você usasse várias passagens:

  • Laranja se move para baixo
  • Verde se move para baixo
  • Laranja se move para baixo
  • Verde se move para baixo
  • Laranja se move para baixo
  • Nada desce (pronto!)

Essa estratégia de vários passes de gravidade também pode resolver o 5, embora não ajude nos casos 3 e 4, onde parece que você precisa tratá-los como um todo.

Para distinguir quando duas ou mais peças devem ser tratadas como uma peça única, acho que o algoritmo mais fácil é verificar se há algum "furo" no espaço combinado de todas as peças. Se houver, pode ser tratado como várias peças.

ashes999
fonte
1
Nos números 3 e 4, também pode haver variações em que, digamos, as formas 2 ou 3 são totalmente encerradas por uma forma maior em "C", descobrindo se as peças são coaguladas e isso pode trazer mais problemas. Vou tentar e ver o que acontece! Felicidades @ ashes999
oodavid
@oodavid suas necessidades / design parece desnecessariamente complicado para mim. Comece com algo mais simples e suba à medida que resolve esses problemas.
ashes999
Nahhhh, o problema acima é uma maneira completamente simplificada / abstrata de descrever um problema muito mais complexo. Estou fazendo isso pela emoção da perseguição!
oodavid