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:
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
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
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.
Semelhante ao item 3, nesse cenário eu também poderia obter sucesso tratando os objetos como um.
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 ...
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.
fonte
Respostas:
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.
fonte
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:
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.
fonte