Como posso detectar "salas" em um jogo de rolagem lateral 2D?

Estou procurando criar um sistema que reconheça certos tipos de edifícios e salas que você pode criar no jogo, como a Terraria detecta "residências". Nesse jogo, uma casa pode ser construída em um mundo baseado em blocos, construindo uma zona de blocos que satisfaz um conjunto de condições:

1. A zona é completamente isolada do "exterior" por blocos colocados por jogadores.
2. A zona pode caber em um retângulo 5x7.
3. existe pelo menos uma mesa, uma fonte de luz e cadeira na área fechada.
4. Há uma porta que sai da zona.
5. Terraria tem uma camada de mosaico em primeiro e segundo plano. Todo o plano de fundo da zona deve ser preenchido com blocos colocados por jogadores.

Como posso detectar com eficiência quando um jogador construiu uma área de tamanho adequado e como posso verificar com eficiência se a área contém toda a mobília / componentes necessários?

Exemplo de uma zona interior que satisfaz todos os requisitos de alojamento:

Não estou familiarizado com Terraria, mas isso pode ser feito facilmente usando um algoritmo de preenchimento de inundação .

Em vez de pixel, você verifica os blocos e, para cada bloco verificado, avalia se o algoritmo pode continuar verificando outros blocos, enquanto armazena em uma matriz ou lista quais objetos são encontrados durante o processo.

O algoritmo começa no bloco em que o personagem está. Você pode começar a cada 1 segundo, 2 ... é uma questão de ajustar para encontrar o melhor intervalo.

Também é uma boa idéia impedir que o algoritmo seja executado por muito tempo, o que pode ser conseguido limitando o número de blocos que o algoritmo pode executar por execução; caso contrário, seu algoritmo causará atrasos longos quando o personagem estiver em uma área aberta.

Editar

Conforme mencionado nos comentários, você pode usar outras abordagens sobre quando iniciar o algoritmo, como quando o jogador altera um bloco ou os blocos que possuem uma am I modified?variável que, se trueiniciar o algoritmo. No entanto, você deve ter cuidado com esta abordagem:

• E se um bloco que faz parte da sala, mas não um bloco em que seu personagem estiver, for modificado? Talvez o ladrilho tenha sido alterado por outro jogador, ou um evento do ambiente, ou o tempo de vida do ladrilho terminou. Seu personagem não terá conhecimento da modificação e não executará o algoritmo para detectar a sala atualizada, uma situação propensa a erros.

Você pode implementar algum tipo de abordagem para detectar essas modificações nos blocos em que seu personagem não está, mas executar o algoritmo em intervalos é a abordagem mais simples e menos propensa a erros. Apenas certifique-se de não executar o preenchimento em todos os quadros.

Fim da edição

Como o @Ferreira da Selva disse, tente o algoritmo de preenchimento. No entanto, você pode usar alguns critérios diferentes ao executar o algoritmo para determinar se ele está incluso.

Por exemplo, para cada bloco, você verifica se existe um bloco de plano de fundo e, se não existe, sabe que não está fechado. Ou você pode executar uma execução adiada, separando-a em vários quadros, aliviando a carga no processador e reduzindo o atraso. Ou você pode criar um limite de tamanho de sala que o jogador teria que aderir.

O uso de uma combinação dessas opções permitirá que você faça isso de maneira mais eficiente e eficaz.

Existem 2 problemas difíceis na ciência da computação. Atribuindo nomes a nomes, invalidação de cache e erros pontuais.

Este é um problema de invalidação de cache.

Se você tem um registro de "é isso aí dentro", sempre que um bloco é colocado ou removido, é muito fácil atualizá-lo e sua região por meio de um preenchimento de inundação.

Para otimizar isso, convém ter um conjunto de camadas de "insididez".

Uma "célula" é uma região cercada por blocos colocados por jogadores (até um determinado tamanho).

Uma "sala" é uma célula com blocos de plano de fundo.

"Inside" é uma sala com uma porta, uma luz e uma cadeira.

Ao colocar um bloco de primeiro plano colocado pelo jogador, faça uma caminhada no sentido horário / anti-horário para ver se uma nova célula é formada. Ao remover um bloco de primeiro plano colocado pelo jogador, examine se ele quebra alguma célula - se houver, veja se uma nova célula é formada ao mesclar as duas.

Quando uma nova célula é formada ou não formada, verifique se é uma sala ou um interior.

As células podem acompanhar quantos blocos de plano de fundo precisam ser uma sala. Em seguida, uma contagem simples quando uma célula é formada, um bloco de segundo plano é adicionado ou removido da célula pode determinar se é uma sala.

Da mesma forma, as células podem acompanhar quantas cadeiras e fontes de luz (e de fato objetos de todos os tipos) estão dentro delas. Então a verificação interna é trivial.

Uma contagem de entradas também pode ser feita.

Então, aumentamos o mapa com "células". Quando os blocos são adicionados ou removidos, verificamos a célula do local e aumentamos / diminuímos a contagem na célula.

Use uma caminhada no sentido horário / anti-horário para definir o interior e o exterior de uma célula quando um bloco em primeiro plano for adicionado ou removido. Como o tamanho das células é limitado, essa caminhada terá um número limitado de etapas.

Como bônus, agora você tem uma maneira barata de falar sobre salas "opulantes" ou "a sala é abençoada por uma fonte sagrada" ou qualquer outra coisa sobre uma sala, pois as salas têm uma contagem de cada tipo de objeto dentro delas. (Ou, como as salas são limitadas em tamanho, basta fazer uma iteração; isso remove um cache).

Cada local está em no máximo uma célula, para que você possa armazenar o ID da célula de cada local no mapa principal.

Ao usar o algoritmo de preenchimento, faça também uma variável, que será incrementada com cada bloco marcado; portanto, se for maior que 35 (7 * 5, o tamanho máximo da sala), ele simplesmente interrompe a verificação!