Determinar se um conjunto de blocos em uma grade forma uma forma fechada

Dado um conjunto de peças em uma grade, quero determinar:

• Se as peças formarem uma figura fechada
• Se os ladrilhos formarem uma figura fechada quando você contar os lados do quadro como uma aresta da figura
• Se qualquer uma das duas instruções anteriores for verdadeira, quais blocos adicionais caem dentro da figura em anexo, o formulário inicial dos blocos.

O jogador começará pressionando uma peça e arrastando o dedo para outras peças para criar uma cadeia de peças da mesma cor. Vou verificar como vou ver se o próximo bloco é válido. Ex. Se o jogador começa em um azulejo vermelho, sua única próxima jogada válida é uma telha vermelha adjacente (diagonais fazer contagem). Quando o usuário levanta o dedo, preciso verificar os 3 itens acima.

Então, meu pensamento inicial era que, desde que eu estava checando a validade da corrente toda vez que fui, quando o jogador levantou o dedo, eu pude verificar se o primeiro e o último ladrilho eram adjacentes. (Eu já sei que eles são da mesma cor.) Se eles fossem adjacentes, eu tinha um pressentimento de que eu tinha feito uma figura fechada, e eu viria aqui para tentar ver se estava perdendo algo grande e conseguir algum tipo de prova lógica / matemática de que meu palpite estava correto (ou um exemplo provando que está incorreto).

Mas foi aí que pensei no item número 2: também tenho que dar conta de correntes que usam uma borda do quadro como um lado da figura em anexo. Nesse caso, o primeiro e o último item da cadeia não seriam adjacentes, mas eu ainda teria uma figura em anexo. Então agora estou de volta à estaca zero, um pouco.

O que posso fazer com essa cadeia de coordenadas da grade para descobrir se elas formam uma figura fechada ou não? E uma vez que sei que tenho uma figura fechada, qual é a melhor maneira de obter uma lista adicional de todos os blocos que caem dentro de seus limites?

Acima, desenhei o que espero que os 4 resultados possíveis deste teste possam ser.

1. A corrente não faz uma figura fechada.

2. A corrente faz uma figura fechada.

3. Se você contar os lados do quadro como uma aresta (ou mais de uma aresta) da figura, a corrente formará uma figura fechada.

4. A cadeia cria uma figura em anexo, mas existem pontos de dados extras (selecionados validamente pelo usuário como parte da cadeia) que não fazem parte da figura criada.

O caso 4 é o mais complicado, porque você teria que extrair os elos de corrente "extras" para encontrar a figura fechada e as peças que caem dentro dela (mas não em torno da área "não fechada").

Então ... Alguém tem uma idéia de uma boa maneira de resolver isso, ou apenas um ponto de partida para mim? Estou meio que circulando neste momento e poderia usar outro par de olhos.

1. Detectando um loop de peças

O problema parece semelhante à detecção de um ciclo (loop) em um gráfico, veja aqui ou aqui .

• O conjunto de nós Vdesse gráfico G=(V, E)são os blocos,
• e = (v1, v2)existe uma aresta entre dois nós diferentes, se os blocos forem vizinhos diretos ou diagonais

2. Manuseando o estojo da borda da tela

A borda da tela consiste nos ladrilhos imaginários que formariam uma borda larga de um ladrilho em torno da tela dos ladrilhos visíveis.

De acordo com sua especificação, parte da borda da tela formaria uma parte implícita de um loop fechado. Apenas para detectar um loop fechado, seria suficiente estender o gráfico Gpara um gráfico G'honrando a conexão por meio desta regra:

• existe outra aresta entre dois nós diferentes, se os dois blocos estiverem posicionados diretamente perto da borda da tela

Assim, os ladrilhos em (0,0) e (1,0) seriam parte de um loop fechado, juntamente com os "ladrilhos de borda" (-1,0), (-1, -1), (0, -1) , (1, -1).

3. A parte interna de uma área em loop

Eu iria em uma direção semelhante ao que o usuário Arthur Wulf White sugeriu:

Limitando o conjunto de ladrilhos, precisamos examinar pela caixa delimitadora dos ladrilhos de loop.

Em seguida, use um preenchimento de inundação para selecionar todos os blocos dentro da caixa delimitadora que são externos ou internos ao loop fechado. Só pode ser um desses dois casos. Qual nós temos que descobrir depois.

Estender a caixa delimitadora por um ladrilho em cada direção também seria uma boa idéia, produzindo o extbb, portanto, acabamos com um conjunto de pontos externos conectados, caso tenhamos começado o preenchimento de inundação com um ladrilho externo.

Assim que tivermos a área de preenchimento, calcularemos também sua caixa delimitadora, a ffbb. No caso de começarmos com um bloco externo, ele deve ser idêntico à caixa delimitadora do loop estendido.

ffbb == extbb

No caso de começarmos com um ladrilho interno, ele deve gerar uma caixa delimitadora distintamente menor, porque os ladrilhos de loop precisam ser encaixados entre as duas caixas delimitadoras.

ffbb < extbb

O bloco inicial inicial para o preenchimento de inundação pode ser qualquer bloco dentro do extbbqual é um bloco livre. Talvez escolher um aleatoriamente seja a melhor abordagem.

Se eu soubesse antes que o interior é menor que o exterior, eu começaria em torno do centro de massa dos pontos de loop que está no interior para muitas áreas (exemplo: área em forma de C), caso contrário, na borda do extbb. Mas não tenho ideia de como estimar isso.

Considerações finais

Normalmente eu diria que uma simples caminhada a partir de algum bloco e manter uma lista de blocos visitados seria suficiente para detectar um ciclo, mas essa condição de limite da tela pode gerar um gráfico mais complicado, portanto, você deve estar do lado seguro com um algoritmo de gráfico .

Abaixo está um exemplo em que o interior não está conectado; por outro lado, a detecção de ciclo deve encontrar dois loops; nesse caso, um deve ser descartado.

Você pode resolver isso:

1. Encontrando a caixa delimitadora dessa forma.
2. Aumentando o tamanho em 1 em cada direção.
3. Iterando sobre o quadro da nova caixa delimitadora ligeiramente aumentada e aplicando o preenchimento.
4. Se houver algum bloco que você não marcou com preenchimento que não esteja nessa cadeia, eles serão fechados. Suponho que, por sua definição, se houver ladrilhos fechados, a forma será uma figura fechada.

Para fazer um, iterar sobre todas as peças na cadeia e encontrar o seu minX, minY, maxXe maxYe que é a sua caixa delimitadora ou AABB.

Dois é trivial.

A iteração sobre o quadro é simples, apenas certifique-se de não preencher fora da grade. Você pode aprender a preencher na Wikipedia .

Para o número quatro, você pode começar verificando apenas os blocos adjacentes à corrente. Você pode preencher com preenchimento qualquer bloco que não esteja marcado para localizar mais blocos.

Sua intuição está certa, supondo que a cadeia termine assim que o usuário tentar selecionar um bloco que já selecionou. Nesse caso, a forma em geral se parece com um laço, na sua foto (4). Se eles podem continuar passando, então eles podem desenhar muitos loops, e as coisas ficam mais complicadas. O que você quer fazer é responder à pergunta dos pontos no polígono .

Primeiro, precisamos definir o problema. Vou assumir que a situação se parece com (2), ou seja, qualquer cauda foi arrancada e o final se conecta de volta ao início, de modo que cada peça tenha exatamente um "predecessor" e exatamente um "sucessor" na cadeia (onde o antecessor do sucessor do bloco X é sempre o bloco X). Além disso, se você seguir os "sucessores" por tempo suficiente, eventualmente retornará ao ponto em que começou. Você pode usar a sugestão de Gurgadurgen para detectar se o loop realmente se repete a qualquer momento. Supondo que você finalize a entrada do usuário quando isso ocorrer, será semelhante a uma série de nós em uma linha, seguidos por um loop. Você pode retirar a linha do loop.

Agora nós, para cada linha, fazemos o seguinte:

1. Comece na borda esquerda e acompanhe um booleano para cada bloco que indica se estamos IN ou OUT. Começar.
2. Se o bloco atual fizer parte da cadeia, observe o sucessor e o predecessor (que devem ser adjacentes). Se um deles estiver estritamente acima (ou seja, norte, nordeste ou noroeste do bloco atual), defina o estado do bloco atual no lado oposto do bloco à sua esquerda. Caso contrário, defina-o da mesma forma que o bloco à esquerda. Vá para 4.
3. Se o bloco atual não fizer parte da cadeia, defina o bloco no estado do título à sua esquerda. Vá para 4.
4. O bloco à direita agora é o bloco atual. Vá para 2.

Agora pegue todas as peças que estão IN, adicione as peças na borda (incluindo uma cauda se você a tirou antes ou não, sua escolha) e chame isso de região.

Se você deseja permitir que o usuário use bordas, lembre-se de que isso não define e IN / OUT no quadro, mas apenas o divide em duas partes. Você pode selecionar a região menor, por exemplo, ou exigir que o usuário use dois lados adjacentes (ou seja, esquerdo e inferior, mas não superior / inferior ou esquerdo / direito).

Uma otimização é que você só precisa criar linhas que contenham alguma borda (se não puder usar os lados). Suponho que sua placa seja pequena o suficiente para que iterar sobre cada bloco e fazer um cálculo muito simples não seja um problema, mesmo no sistema móvel mais fraco. (Você precisa renderizá-las, afinal, o que é uma tarefa muito mais complexa).