Gerando processualmente um edifício de área específica

15

Eu e uma equipe estamos trabalhando em um jogo de construtor de fábrica que fornece ao jogador uma fábrica aleatória no início do jogo. Para tentar garantir que haja uma sensação de "justiça", idealmente, a fábrica gerada aleatoriamente teria uma área dentro de algumas unidades de (valor do espaço reservado) 30.

É relativamente simples escrever um gerador de retângulo aleatório básico para atender a essas especificações, mas nosso objetivo é que a fábrica seja mais complexa, talvez composta de 2, 3 ou até 4 retângulos que se cruzam, produzindo formas mais complexas (pense em L, Edifícios em forma de U e O).

Tentei gerar um retângulo aleatório e depois usar álgebra básica para preencher um segundo retângulo, mas até agora não tive sorte implementando mais de 2 retângulos, e mesmo assim estou descontente com os resultados de apenas um design de 2 retângulos .

Algumas informações mais relevantes: 2D de cima para baixo Algumas das mecânicas são do estilo fatorio, de modo que as salas devem ter comprimento e largura razoáveis ​​para permitir espaço para máquinas Atualmente em Java e Lua (pode usar bibliotecas integradas, se necessário)

Desde já, obrigado!

EDIT: Quando digo saídas "boas" ou "ruins", uma saída ruim seria qualquer saída que tenha espaço inutilizável pelo player. O formato da fábrica limita onde o jogador pode colocar máquinas de fábrica, como correias transportadoras. Idealmente, a fábrica não deve ter áreas com apenas 1 a 2 blocos de largura, a forma não deve ter um ou dois retângulos grandes com uma linha de 1 a 2 blocos "pendurados" para um lado. Uma boa saída seria onde todo o espaço físico é "viável"; portanto, todas as áreas têm pelo menos 3-4 blocos de largura. Uma boa saída nem sempre precisa ser complexa (1 ou 2 retângulos são aceitáveis), mas deve ter uma boa chance se for composta por mais de 1-2 retângulos.

user2129189
fonte

Respostas:

7

Você poderia usar poliaminoinos pré-gerados como meta-formas para construir uma variedade de edifícios.

Digamos que sua distância mínima aceitável seja de 3 quarteirões. Então, a menor unidade aceitável de construção que consideraremos é 3x3. Por conveniência, vou chamar isso de célula e isso dá uma área de 9 blocos. Em seguida, pegue a área inicial de destino e divida-a pela área da célula. Usando o valor inicial que você forneceu, obtemos 3,333; então 3 células dariam a você um pouco menos do que você deseja e 4 células dariam a você mais.

A partir daqui, você tem algumas opções. Se você é flexível em sua área inicial, use qualquer método que funcione melhor para você escolher o número de células que fornece uma quantidade aceitável (por exemplo, arredondar para o valor mais próximo, arredondar para cima, etc). Vou chamar isso de contagem de células.

Em seguida, selecione aleatoriamente o polyomino com a contagem de células desejada. Substitua cada quadrado no polyomino por uma célula de construção e você terá sua forma final.

Para ilustrar, digamos que escolhemos arredondar para baixo. Aqui estão todos os poliaminos de tamanho 3 (sem incluir rotações / inversões):

insira a descrição da imagem aqui

Vamos assumir que escolhemos aleatoriamente a forma de L e aplicamos uma rotação aleatória, sua construção teria o seguinte layout:

insira a descrição da imagem aqui

Algumas questões. Primeiro, há um limite no número de células que você pode usar. A Wikipedia fornecerá todos os poliomatos até o tamanho 8 ( octomino ). Ele inclui dados resumidos para o tamanho 12, mas não sei se há uma listagem on-line para todos eles. Segundo, a solução acima funciona exatamente para tamanhos de construção que são múltiplos de 9. Existem algumas maneiras de solucionar alguns desses problemas:

1) Use um tamanho de célula diferente. Por exemplo, 3x4, 4x4, etc.

2) Adicione células adicionais a um poliomino inicial. Isso pode ser complicado se você precisar garantir que todas as formas sejam igualmente prováveis, mas as chances são de que, para a maioria dos desenvolvedores de jogos, você não precise de uma distribuição verdadeiramente uniforme das formas de construção.

3) Almofadar um edifício para aumentá-lo. Voltando ao exemplo, se você usasse 3 células, seu prédio teria uma área de 27 quadrados, deixando você com 3 pontos curtos. Você poderia digitalizar o perímetro em busca de um local para colar um grupo de quadrados tamanho 1x3. Desde que seu grupo de maquiagem seja pelo menos AxB, em que A seja pelo menos a sua distância mínima aceitável, seu resultado não violará sua restrição de distância mínima aceitável. Criando o exemplo acima, aqui está uma ilustração de um resultado possível:

insira a descrição da imagem aqui

4) Em vez de preencher um prédio pequeno demais, você pode aparar um prédio grande demais. Garantir que sua restrição de distância mínima aceitável seja seguida é mais complexo que a opção de preenchimento, mas ofereceria mais alternativas a serem consideradas.

Alguns outros comentários:

Só porque você poderia usar todos os poliaminos possíveis de um determinado tamanho não significa que você deveria. Se alguns deles não são divertidos, quebram o tema, são ofensivos para o público (padrões de suástica) ou causam algum outro problema, remova-os. Além disso, você pode ponderar sua rotina de seleção se alguns padrões forem interessantes, mas muito estranhos para aparecer rotineiramente. Por fim, você pode usar esta solução em combinação com sua estratégia atual. Talvez 70% do tempo você gere edifícios retangulares e 30% do tempo use a abordagem polyomino. Ou talvez você comece com um edifício retangular e cole um pequeno poliomino no exterior.

Pikalek
fonte
16

Uma maneira simples de criar um gerador de procedimentos é:

  1. Construir coisas aleatoriamente
  2. Execute uma função que verifique se a saída é boa
  3. Se a saída não for boa, vá para o passo 1

Mesmo que sejam necessárias milhares de execuções para concluir, a maioria dos geradores simples se sai bem com essa abordagem. A vantagem é que não há muita inteligência necessária no gerador e, desde que verificar se algo está bom é muito mais fácil do que construir algo bom 100% do tempo, essa abordagem é muito fácil.

Você listou algumas medidas objetivas para determinar se uma saída é boa; isso deve ser suficiente para você criar um gerador rápido e sujo. Coloque retângulos aleatoriamente dentro de uma área e rejeite a saída se, por exemplo, houver áreas com apenas 1 a 2 blocos de largura.

Comece com isso, melhore e otimize posteriormente.

congusbongus
fonte
Obrigado! Lembro-me de considerar isso, mas o pensamento de haver uma chance por alguns segundos + tempo de carregamento me parou. Agora percebo o quão incrivelmente pequena é essa chance. Vou ter que tentar isso, mas posso esperar para ver se alguém tem uma solução mais direta primeiro.
User2129189 23/08
@ user2129189 Quando o gerador está funcionando, você ainda pode ajustar seus intervalos de números aleatórios para evitar a criação de layouts que dificilmente serão aprovados no teste. Também é possível paralelizar esse algoritmo de geração de tentativa e erro em vários núcleos, fazendo com que cada núcleo gere um layout de cada vez.
Philipp
3
Eu mesmo não sou fã de métodos de geração de rejeitar e repetir. Eles são rápidos o suficiente quando o gerador está fazendo apenas uma coisa simples, mas para os níveis de jogo, geralmente começamos a colocar mais recursos e etapas de geração em camadas para criar mapas mais ricos. Nesse ponto, a probabilidade de atingir um mapa viável é o produto da probabilidade de cada etapa ser bem-sucedida, que pode encolher rapidamente. Isso não é apenas uma preocupação acadêmica - conversei com desenvolvedores que tiveram que implementar um sistema de cache de sementes bom / ruim para evitar tempos de geração excessivos, quando um gerador de passagem única de correção por construção seria mais fácil.
DMGregory
@DMGregory sim, eu definitivamente posso ver isso. Um gerador aleatório básico funcionaria 99% do tempo dentro de algumas passagens para o meu caso, mas se eu quiser adicionar mais complexidade posteriormente, ele poderá diminuir significativamente. Alguém conhece alguma aplicação de programação / jogo da vida real do modelo de palpite e cheque?
User2129189
Talvez possa haver funções e verificações de camadas de gerações, tomando o cuidado de corresponder o fraseado das condições ao nível atual de geração. Dessa forma, todo o nível não precisa ser gerado novamente apenas com base no erro encontrado ao colocar um item levemente incorreto.
Pysis 23/08/17
7

Dada uma restrição de "todas as áreas estão com pelo menos 3 a 4 blocos de largura", a primeira ideia que me vem à cabeça é algo como o seguinte:

  1. escolha um dos 3x3, 3x4, 4x3 ou 4x4
  2. coloque um bloco desse tamanho no centro da grade
  3. escolha uma direção (cima, esquerda, direita, baixo)
  4. tente colocar um bloco 3x3 ao lado de blocos previamente colocados nessa direção
  5. se for bem-sucedido, com alguma probabilidade, tente expandir o bloco para um bloco 4x3 em uma das direções que você não escolheu
  6. com alguma probabilidade, mova a para a borda aleatória dos blocos preenchidos
  7. repita as etapas 3 a 6 até que a área seja grande o suficiente

A idéia básica é que, como você deseja que todas as áreas tenham pelo menos um determinado tamanho, trabalhe apenas em áreas desse tamanho. De maneira mais geral, se você deseja que algo seja verdadeiro para todas as saídas geradas, veja se isso pode ser verdadeiro para todas as saídas geradas parcialmente.

Ryan1729
fonte
4
Eu simplificaria as coisas sempre começando de um bloco 3x3 e adicionando blocos 3x1 em posições aleatórias, onde cada quadrado é adjacente a um bloco existente. Adicionando a um bloco 3x3, existem quatro posições possíveis. Todos oferecem um bloco 3x4, com seis posições possíveis para a próxima. A partir daí, fica mais complicado, mas não tão ruim.
JollyJoker
0

Considere usar os booleanos NOT e UNION e escolher entre eles aleatoriamente.

  1. Coloque um retângulo aleatório.
  2. Coloque um segundo retângulo aleatório.
  3. Escolha aleatoriamente se deseja uni-los ou SUBTRAIR o segundo do primeiro.
  4. Repita para vários retângulos. Embora apenas dois ou três possam dar resultados razoáveis ​​o suficiente.

Então, eu calcularia a área e a escalaria para cima ou para baixo para corresponder mais ao tamanho aproximado que você procura e, em seguida, testaria se não há dimensões inferiores a uma quantidade mínima necessária.

Polvo
fonte
Sua idéia de escala para obter a área desejada é realmente silenciosa e inteligente. Eu poderia implementar algo silencioso um pouco assim.
user2129189