Como posso gerar um gráfico incrementalmente?

8

Acabei de iniciar um novo projeto no qual gostaria que o mundo do jogo consistisse em locais gerados processualmente, conectados por teleportadores. Depois de um pouco de pesquisa, descobri que isso é chamado de "teoria dos grafos" ou "muito complicado", dependendo de quem está discutindo. Infelizmente, encontrei muito pouca informação sobre a geração de gráficos; a maioria das ferramentas que vi são direcionadas para o exame de gráficos existentes.

Supondo que eu tenha a terminologia corretamente resolvida, meus requisitos são que o gráfico seja:

  • simple - nenhum local (vértice) deve ter um teletransportador (borda) que se conecte de volta a si mesmo, nem dois vértices devem ter várias arestas conectando-os
  • conectado - deve ser possível viajar entre dois vértices no gráfico (embora eu não preveja a necessidade de encontrar o caminho; basta saber que o jogador pode encontrar um, se preferir, é suficiente)
  • cíclico - deve haver mais de um caminho entre dois vértices
  • sem direção - todas as arestas podem ser percorridas em qualquer direção
  • infinito - se o jogador desejar, ele poderá viajar indefinidamente, com o gráfico continuando a gerar incrementalmente à medida que se aproxima de seus vértices inexplorados mais externos
  • localmente finito - o grau de um vértice nunca deve mudar depois que o jogador o visita
  • rotulado de forma estável - cada vértice representa um local que será gerado proceduralmente a partir de uma semente; a mesma semente deve ser atribuída a um vértice, independentemente do caminho que o jogador percorreu até lá ou do tamanho do gráfico ao percorrer

Eu tive algumas idéias (que ainda não tentei implementar) sobre o uso dos máximos locais do ruído perlin 2D como vértices (a entrada x e y poderiam então ser usados ​​como seu rótulo), mas isso parece desajeitado e complicado demais.

Existe uma maneira melhor de gerar um gráfico como este? Estou desenvolvendo no Python 2.6 usando o Panda3D e o numpy e, é claro, gostaria de incluir outras bibliotecas se elas ajudarem com esse problema!

Editar

Acho que fiz um péssimo trabalho explicando alguns dos meus requisitos, então é hora da ilustração! Felizmente, isso vai esclarecer as coisas.

O que quero dizer com rótulos estáveis ​​é que eu quero, por exemplo, que o Jogador A seja capaz de explorar e encontrar, entre outras coisas, um caminho cíclico de volta ao local inicial e uma montanha que parece um gato. Seu jogo agora se parece com o seguinte (os vértices são numerados com suas sementes e arestas com a ordem em que o jogador os atravessou). Ele começou no vértice 8329 (verde) e a Happycat Mountain está no vértice 6745 (azul).

Gráfico mundial do jogador A

O bom amigo do jogador A, jogador B, é um fã de gatos, então ele quer mostrar a ela. Ele dá a ela a raiz do seu mundo e direções ao longo do caminho mais curto para a montanha de interesse. O jogo dela agora deve ficar assim:

Gráfico mundial do jogador B

O problema com o qual estou tendo mais dificuldade atualmente é "Como eu gero as mesmas sementes para o Jogador B quando a exploração dela não segue o mesmo caminho?" Foi isso que me levou à ideia de usar o ruído Perlin - desde que a mesma semente de raiz seja usada, o máximo não se moverá, então suas coordenadas poderão ser usadas como sementes de vértice estáveis.

Ben Blank
fonte
Por que um gráfico conectado não se adequaria a isso? mathworld.wolfram.com/ConnectedGraph.html No entanto, talvez eu esteja perdendo o objetivo. Se um usuário quiser ir de um local para outro e todos estiverem conectados, forneça uma lista de locais e mova sua posição no mapa do mundo para o novo local.
22412
@brandon - "Conectado" é a segunda propriedade que listo. :-)
Ben Blank
O que quero dizer é que se você pode ir de um nó para outro. Quando eles visitarem um teletransportador, forneça uma lista de todos os nós que visitaram, exceto este. Não é necessário ter um gráfico, você mantém uma lista de todos os nós visitados e seus locais e apenas se teleporta para o local escolhido. Estou entendendo mal?
Brandon
quase todas as descrições desses termos estão corretas, exceto "cíclico" e "localmente finito". O primeiro restringe seus gráficos para que eles pareçam - um círculo. Um termo que você pode usar para o requisito de que haja mais de um caminho de um vértice para outro é "2-conectado". "Localmente finito" significa apenas que cada vértice tem um número finito de arestas.
Harry Stern
@ Harry Stern - Meu entendimento é que gráficos cíclicos são gráficos que contêm pelo menos um ciclo gráfico . Parece que você está falando de um gráfico de ciclo , que é um gráfico que consiste em um único ciclo de gráfico e nada mais. Eu especificamente estou não à procura de gráficos que são "2-conectados" (ver "simples"). E sim, é isso que eu quis dizer com "localmente finito".
22111 Ben Ben

Respostas:

6

Você não pode criar um gráfico infinito. Sua memória é finita, portanto, o número de vértices e arestas também é finito. O que você pode fazer é criar um gráfico finito e depois adicionar mais. Você parece ter percebido isso, mas acho importante que seja explicitamente declarado para que você não siga um caminho sem saída.

Você deve ter muito cuidado ao falar sobre "vértices mais externos". Um gráfico é um conjunto de vértices, um conjunto de arestas e uma função que relaciona os dois. Não há interpretação geométrica definida, a menos que você aplique uma. Por exemplo: ambas as imagens mostram exatamente o mesmo gráfico. Na primeira imagem, o vértice 2 poderia ser considerado um vértice "mais externo", mas na segunda imagem o vértice 2 não seria considerado "mais externo". Se você considerasse três dimensões, poderia dizer que todos os vértices são "ultraperiféricos".

Gráfico 1 Gráfico 2

Isso significa que você deve ter outras informações para poder saber o que é um vértice "externo". Você pode usar pares (x, y), pois isso lhe dará uma representação geométrica fácil de visualizar, no entanto, acho que você não precisa ir tão longe. Pelo que você diz, tudo que você precisa saber é quais vértices já estão no gráfico.

Se você executou isso toda vez que visitou um vértice:

if(this.needsNeighbours)
{
    List<int> connections = genRandomNumbers(n);
    foreach (int connection in connections)
    {
        //Simple graph
        if(connection == this.seed || this.hasNeighbour(connection))
        {
            continue;
        }
        //Connections to already existing, unvisited vertices
        else if(nodeMap.containsKey(connection) && 
                nodeMap.getByKey(connection).needsNeighbours)
        {
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
        //Grow graph with new vertices
        else
        {
            nodeMap.add(connection, new Node(connection));
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
    }
    this.needsNeighbours = false;
}

seu gráfico atenderia a todos os seus requisitos, exceto por ser cíclico. Não sei se você realmente precisa de uma garantia. Se você o fizer, poderá selecionar especificamente um nó não visitado e estabelecer uma conexão, o que garantiria um caminho entre o nó atual e um nó já visitado, pois todos os nós não visitados estão conectados a pelo menos um nó visitado e desde que você tenha visitado um nó visitado para chegar onde você está, agora existem pelo menos dois caminhos.

É simples porque existe uma verificação explícita, conectada porque todos os novos nós obtêm pelo menos uma conexão, localmente finita, porque as arestas são adicionadas apenas antes da sua visita ou na sua primeira visita e apenas para os nós não visitados. Tecnicamente, não é direcionado, mas funcionalmente é o mesmo que você cria uma aresta direcional nas duas direções. Você pode rotular o nó como quiser, eu uso o número aleatório gerado, mas você pode adicionar outros parâmetros ao construtor, sendo um deles sua semente.

Chewy Gumball
fonte
Você percebe exatamente o que eu quis dizer com "infinito" e seu argumento sobre "mais externo" está bem entendido - ajustei a palavreado na minha pergunta. No entanto, ou eu não estou entendendo seu gerador corretamente ou expliquei mal minhas necessidades, pois isso parece não gerar as mesmas sementes para caminhos diferentes para o mesmo vértice. Eu adicionei algumas ilustrações à minha pergunta, que espero tornar mais claro o que estou tentando realizar. :-)
Ben Blank
Entendo o que você quer dizer agora. Isso é um pouco mais difícil. O que você precisa fazer é alterar a chamada genRandomNumbers para uma função que sempre retorna o mesmo conjunto de números para sua entrada e usar a semente do nó como argumento. Isso garantiria que você obtivesse as mesmas conexões e sementes, independentemente do caminho que você seguir ou com o nó em que iniciar. Você deve ter cuidado para que o conjunto de números do nó B ao qual A se conecte também contenha A, para obter sua propriedade de gráfico não direcionado. Se você não fizer isso, receberá um gráfico direcionado.
Chewy Gumball
1

Um método:

init:
  root = generateLocation using random seed
  store root's seed
  place player in root location

when the player enters a new location:
  release the memory used by locations that are further than 1 edge away, but keep their seeds
  generate some neighbors for the new location. for every neighbor n:
    gen.seed(getSeed(n))
    n = generateLocation using n's random seed
    numCyclicEdges = gen.randint(0, 1)
    create numCycleEdges edges to existing locations

getSeed(n):
  if(n already has a seed) return n's seed
  else return randomSeed()

Eu deixei muitos detalhes de fora, mas isso deve capturar a ideia geral. Convém manter os vizinhos na memória que estão mais afastados do local atual, dependendo da distância do mundo entre os portais, a quantidade de memória disponível etc.

Jiahua Wang
fonte