O que é uma boa estratégia para a construção de um grafo direcionado para um mapa do jogo (em Python)?

Question

Estou desenvolvendo um mundo de jogo processualmente gerado em Python. A estrutura do mundo será semelhante ao paradigma MUD / MUSH de quartos e saídas dispostas como um grafo orientado (quartos são nodos, as saídas são arestas). (Note-se que este é não , necessariamente, um grafo acíclico, embora eu estou disposto a considerar soluções acíclicos).

Para o algoritmo de geração mundo, quartos de diferentes tipos serão distinguidos por atributo de cada quarto "tags" (um conjunto de cordas). Depois de terem sido instanciado, os quartos podem ser consultados e selecionados por tags (tag única, tag intersecção, união tag, best-candidatos).

Eu vou ser a criação de tipos específicos de quartos usando um sistema glorificado de objetos do molde e métodos de fábrica - Eu não acho que os detalhes são importantes aqui, como a implementação atual provavelmente irá mudar para coincidir com a estratégia escolhida. (Por exemplo, seria possível adicionar tags e tag-consultas para o sistema modelo de sala.)

Por exemplo, eu vou ter quartos destes tipos:

side_street, main_street, plaza, bar, hotel, restaurant, shop, office

Finalmente, a pergunta: o que é uma boa estratégia para instanciar e organizar estes quartos para criar um gráfico que podem corresponder às regras dadas?

Algumas regras podem incluir: uma praça por 10.000 habitantes; main_street conecta a plaza; side_street conecta a main_street ou side_street; hotel favorece conexões main_street ou plaza, e recebe outras etiquetas em conformidade; etc.

Os pontos de bónus se uma estratégia sugerida permitiria uma implementação baseada em dados.

Answer 1

Em primeiro lugar, você precisa de algum senso de Localização. Seus vários objetos ocupam uma certa quantidade de espaço de coordenadas.

Você tem que decidir como regular, essas várias coisas são. No caso trivial, você pode deixá-los em seu espaço de coordenadas como rectângulos simples (ou sólidos retangulares) para fazer locais mais simples de planear para fora.

Se as coisas são irregulares - e densamente -. A vida é um pouco mais complexa

Definir um mapa para conter locais. Cada local tem um espaço de coordenadas; se você trabalha com retângulos simples, então cada local pode ter um (, superior, direita, inferior esquerda) tupla.

Seu Mapa terá métodos para determinar quem é residente em um determinado espaço, eo que é adjacente ao espaço, etc.

Você pode, em seguida, teste de unidade isso com um conjunto fixo de locais que você trabalhou fora, que podem todos ser deixado cair no mapa e passar algumas verificações básicas de sanidade para não conflitantes, ao lado, e similares.

---

Em segundo lugar, você precisa de um tipo de "gerador de labirinto". Um labirinto simplesmente-conectado é facilmente gerado como uma estrutura de árvore que é dobrada para dentro do espaço dado.

O labirinto / árvore tem um nó "raiz" que será o centro do labirinto. Não necessariamente o centro físico do seu espaço, mas o nó raiz será o meio da estrutura de labirinto.

O ideal é que um ramo a partir deste nó contém uma "entrada" a todo o espaço.

O outro ramo a partir deste nó contém uma "saída" de todo o espaço.

Alguém pode passear de entrada para saída, visitar um monte de locais "beco sem saída" ao longo do caminho.

Escolha um tipo de espaço para o nó raiz. Soltá-lo em seu espaço Mapa. ??

Isto terá 1 - n entradas, cada um dos quais é um sub-árvore com um nó raiz e 1 - n entradas. É esse negócio de múltipla entrada que faz com que uma árvore um ajuste natural para esta estrutura. Também uma árvore adequada é sempre bem-conectados em seções que você nunca isolados que não podem ser alcançados.

Você vai - de forma recursiva - espalham a partir do nó raiz, escolhendo locais e soltando-os no espaço disponível.

teste Unidade isso para ter certeza de que preenche o espaço razoavelmente bem.

---

O resto são as suas necessidades de ajuste fino no caminho os locais picaretas gerador de labirinto.

O mais fácil é ter uma tabela de pesos e escolhas aleatórias. Escolha um número aleatório, compará-lo com os pesos para ver qual tipo de localização fica identificada.

---

A sua definição de espaço pode ser 2D ou 3D - ambos são muito racional. Para o crédito do bônus, pense em como você implementar um 2D espaço pavimentado com hexágonos ao invés de quadrados.

Esta "geometria" pode ser uma Estratégia plug-in para os vários algoritmos. Se você pode substituir quadrado 2D com 2D hexagonal, você fez um bom trabalho de OO projeto.

Answer 2

Confira as discussões sobre O MUD Connector - há algumas grandes discussões sobre o layout mundo e geração, e diferentes tipos de coordenar / sistemas de navegação no fórum "Codificação avançada e design" (ou similar).