Processual… casa com gerador de quartos

74

Eu estive analisando alguns algoritmos e artigos sobre como gerar uma masmorra proceduralmente. O problema é que estou tentando gerar uma casa com quartos e eles não parecem atender às minhas necessidades.

Por um lado, as masmorras têm corredores, onde as casas têm corredores. E embora inicialmente pareçam iguais, um salão nada mais é do que a área que não é um quarto, enquanto um corredor é projetado especificamente para conectar uma área a outra.

Outra diferença importante em uma casa é que você tem uma largura e altura específicas e precisa preencher a coisa toda com salas e corredores, enquanto que em uma masmorra, há espaço vazio.

Acho que os corredores de uma casa são algo entre um corredor de masmorra (leva você para outros cômodos) e um espaço vazio na masmorra (não está explicitamente definido no código).

Mais especificamente, os requisitos são:

  • Há um conjunto de salas predefinidas
    que não consigo criar paredes e portas em tempo real.
  • Os quartos podem ser rotacionados, mas não redimensionados
    Novamente, porque eu tenho um conjunto predefinido de quartos, só posso girá-los, não redimensioná-los.
  • As dimensões da casa são definidas e devem ser totalmente preenchidas com salas (ou salões). Ou
    seja, eu quero preencher uma casa 14x20 com as salas disponíveis, certificando-se de que não haja espaço vazio.

Aqui estão algumas imagens para deixar isso um pouco mais claro:

Gerador típico de masmorra Calabouço sem corredores Resultado do gerador da casa

Como você pode ver, na casa, o "espaço vazio" ainda pode ser percorrido e leva você de um cômodo para outro.

Então, tendo dito tudo isso, talvez uma casa seja apenas uma masmorra muito bem cheia de corredores. Ou é algo mais fácil do que uma masmorra. Talvez haja algo por aí e eu não o encontrei porque realmente não sei o que procurar.

É aqui que eu gostaria da sua ajuda: você poderia me dar dicas sobre como criar esse algoritmo? Alguma idéia de quais medidas serão necessárias? Se você criou um gerador de masmorra, como você o modificaria para atender aos meus requisitos? Você pode ser tão específico ou genérico quanto desejar. Eu estou olhando para escolher o seu cérebro, realmente.

pek
fonte
2
Uma recomendação estranha: eu recomendo vivamente os livros de Christopher Alexander, The Timeless Way Of Building e A Pattern Language , os livros de arquitetura que formaram a base original para a noção de um padrão (de software); eles essencialmente descrevem uma linguagem explícita para edifícios e espaços que podem ser transformados em um método de construção processual de cima para baixo.
Steven Stadnicki
Pessoalmente, eu tentaria criar um algoritmo como a resposta da egarcias. Comece gerando espaços reservados para salas (grandes áreas que podem ser preenchidas com vários números de salas. É necessário que cada espaço reservado para salas tenha um espaço de tamanho específico (ou aleatório, com limites mais baixos) entre eles. O espaço de espaço é o que seria considerado um espaço corredor ou seja, que está na casa, mas não em um quarto, e os titulares quarto lugar seria preenchido por quartos de tamanho aleatórios semelhantes ao seu 'calabouço sem corredores' exemplo.
Benjamin Perigo Johnson
@pek Crie uma resposta para a sua solução, não a coloque na pergunta.
MichaelHouse
@ Byte56 Concluído. Só para deixar claro, fiz isso porque não queria obter crédito, pois só fiz o que as outras pessoas sugeriram. No entanto, entendo por que isso não é ideal para o formato do site, então adicionei minha resposta.
28613 pek
Obrigado @pek. Não se preocupe em obter crédito, ele é merecido e é útil para as pessoas que acessam o site para ver a solução (e vê-la onde é esperado é o melhor).
MichaelHouse

Respostas:

50

Eu acho que esse é um bom caso para usar a partição de espaço binário ou ternário.

Na primeira passagem, divida o espaço da casa em corredores e {blocos de quartos}. Pegue o próximo pedaço grande, divida-o em {hall and chunk} ou {2 chunks and hall between they}. A cada passo, gire a direção do corte em 90 graus. Pare quando {não houver mais pedaços grandes} ou {área total do salão atingido o limite}.

Na segunda passagem, divida os pedaços restantes em salas. Pegue o próximo pedaço grande e divida-o. Pule dividindo alguns pedaços não tão grandes aleatoriamente, para ter alguns quartos grandes.

Se algum corredor estiver voltado para um corredor muito mais antigo, coloque uma parede (ou parede com porta) lá.

Conecte salas com salas diretamente ou através de outras salas já conectadas.

Por exemplo, você pode ver meu resultado criado manualmente ou C ++ - pseudo-código parcialmente feito . Tiro final:

tiro final

Sombras na chuva
fonte
Foi aí que minha pesquisa resultou em particionamento de espaço. Seu exemplo com código me deu um começo muito, muito bom. Atualmente, estou lendo sobre algoritmos. Porém, uma pergunta: um dos meus requisitos é que as salas sejam predefinidas (ou seja, existem salas 2x2 com uma porta, 1x1 com duas portas, mas não 2x2 com três portas), portanto, não posso iniciar o particionamento e decidir onde colocarei as portas. . Acho que tenho que ter em mente minhas limitações enquanto particiono. Você tem uma sugestão de como eu faria isso? De qualquer forma, muito obrigado pela sua resposta e esforço!
pek
@pek Não tenho certeza se o mero mortal pode encontrar uma solução acadêmica para esse problema. Você pode tentar definir condições adicionais para separador de pedaços e separador de caixas e, em seguida, gerar e reduzir níveis até encontrar um em que todas as condições possam ser atendidas.
Sombras na chuva
Sim, eu esperava que estivesse perdendo alguma coisa. Minha primeira abordagem foi usar o A * para descobrir como ajustar as salas em um determinado espaço, mas faltava lógica para os corredores. Agora, estou pensando que posso usar o BSP para colocar corredores e, em seguida, usar A * nos blocos. O que mais me preocupa é que pode ser muito caro e nem sempre produzir um resultado. Mas vou ter que testar isso primeiro. Talvez não seja tão ruim assim?
pek
2
@pek Encontrei algo útil, se você ainda estiver interessado. Veja isso , também no google L-system.
Shadows In Rain
24

Você pode aproveitar o fato de que o design desejado agrupa as salas em salas retangulares cercadas por corredores. Com isso em mente, eu faria o seguinte:

  1. Projete os corredores e os "grandes espaços" para salas
  2. Preencha cada "grande espaço" com quartos

2 passos

O preenchimento de grandes espaços com salas pode ser feito facilmente se você começar com as salas nas bordas - elas têm restrições específicas, por exemplo, as salas voltadas para um corredor podem ter uma porta nessa parede, mas as salas voltadas para as "paredes externas" não pode (eles poderiam ter janelas, talvez). Os quartos "dentro" dos grandes blocos de quartos precisarão de pelo menos uma entrada.

egarcia
fonte
15

Então, aqui está como eu resolvi esse problema. Mas, primeiro, gostaria de agradecer a @Shadows In Rain e @egarcia por suas respostas. Eles me deram uma boa direção que me ajudou a obter alguns resultados.

Usei o particionamento espacial do Shadows In Rain para gerar uma casa básica e depois segui o conselho da egarcia para preencher a área com quartos.

O particionamento de espaço foi bem direto, pois 90% do código foi feito pelo Shadows. A parte "preencher os quartos" foi um pouco mais desafiadora. Decidi usar um sistema de pseudo AI Planning que usa A * para posicionar as salas adequadamente. O bom de usar o planejamento em vez de apenas A * é que as condições prévias ajudam a reduzir significativamente o espaço de pesquisa.

Aqui estão algumas capturas de tela com os resultados:

Fase de geração da planta Fase de geração da planta

Fase de colocação do quarto Fase de colocação do quarto

Agora com portas de conexão!
Agora com portas de conexão!

pek
fonte
11

Dahl & Rinde têm um trabalho de tese sobre a geração processual de ambientes internos que utiliza uma abordagem de esqueleto e regiões para preencher interiores de edifícios com salas e corredores. O documento inclui diagramas de classes para seu protótipo. Há também algumas boas referências em sua bibliografia, incluindo a mencionada A Pattern Language .

Seu trabalho foi desenvolvido com base nas seguintes suposições simplificadoras:

  • lidando apenas com prédios de apartamentos
  • sem níveis de divisão
  • limitar a forma dos edifícios (envelope) deve ser poligonal
  • sem buracos no envelope
  • espessura da envolvente semelhante ou com alteração linear (IE sem formas de ampulheta)
  • lidando apenas com edifícios que precisam de corredores

Aqui está uma breve visão geral do processo deles:

  • Encontre o esqueleto para o envelope. Os corredores são então colocados ao longo do esqueleto com base na distância do envelope, na proximidade de portas ou escadas e na proximidade dos corredores anteriormente colocados.
  • Em seguida, o espaço restante fora do corredor é particionado em áreas conectadas máximas, cada uma com um único limite contínuo. Em alguns casos, isso exigirá a inserção de uma parede.
  • Essas regiões são então divididas em apartamentos tentando alocar pelo menos uma janela por apartamento. Em alguns casos, divisões menores serão mescladas para evitar apartamentos excessivamente pequenos. Regiões sem janelas são simplesmente ignoradas.
  • Finalmente, os apartamentos são divididos em quartos usando um diagrama ponderado do tipo Voronoi como base:

    • Os pesos das sementes são usados ​​para influenciar o tamanho da sala. As sementes são adicionadas às portas e janelas. Sementes adicionais são adicionadas, geralmente uma por sala desejada; Embora não seja explicitamente declarado, parece que as sementes são colocadas ao longo das paredes externas do apartamento.
    • Começando com o ponto mais distante, uma linha entre a semente especificada e todos os outros pontos é calculada e, em seguida, bissecada uma distância relativa aos pesos respectivos dos pontos finais (por exemplo, se A e B tivessem pesos de 1 e 4, o ponto de bissecção seria 1/4 do caminho de A a B). A coleção de linhas de bissecção, juntamente com a parede externa, forma a célula para a semente.
    • Em seguida, um esqueleto de parede do S-Space (conforme Peponis et al 1997) é criado particionando a área com linhas originadas perpendicularmente a partir dos pontos médios entre pares vizinhos de elementos da parede externa (janelas ou portas).
    • Finalmente, as paredes são selecionadas a partir do esqueleto do espaço S que 'corresponde o melhor possível às paredes celulares de Voronoi'.
Pikalek
fonte
3
Você pode incluir fotos? Isso seria bom. Eu escovei o papel e os quartos que eles geravam pareciam bons de um ponto de vista arquitetônico.
congusbongus
Método muito interessante, vou ter que examiná-lo mais de perto para obter idéias que possam tirar dele.
Draco18s
Eu vim aqui para relaxar do trabalho ... Surpreenda meu tópico de pesquisa. Estou com preguiça de escrever uma resposta com base em minha própria pesquisa (ainda só projetei os esqueletos do algoirthm, então não vale a pena de qualquer maneira) ou descrevo as abordagens de Danil Nagy para o problema, então vou deixar isso aqui autodeskresearch.com/publications/…
Felipe Gutierrez