¿Cómo puedo generar incrementalmente un gráfico?

8

Acabo de comenzar un nuevo proyecto en el que me gustaría que el mundo del juego constara de ubicaciones generadas por procedimientos conectadas por teletransportadores. Después de un poco de investigación, descubrí que esto se llama "teoría de grafos" o "sangrientamente complicado", dependiendo de quién lo esté discutiendo. Desafortunadamente, he encontrado muy poca información sobre la generación de gráficos; La mayoría de las herramientas que he visto están dirigidas a examinar los gráficos existentes.

Suponiendo que tengo la terminología correctamente ordenada, mis requisitos son que el gráfico sea:

  • simple: ninguna ubicación (vértice) debe tener un teletransportador (borde) que se conecte de nuevo a sí mismo, ni dos vértices deben tener múltiples bordes que los conecten
  • conectado: debería ser posible viajar entre dos vértices en el gráfico (aunque no preveo la necesidad de encontrar el camino; simplemente saber que el jugador podría encontrar uno si lo desea es suficiente)
  • cíclico: debe haber más de una ruta entre dos vértices
  • no dirigido: todos los bordes se pueden recorrer en cualquier dirección
  • infinito: si el jugador lo desea, debería poder viajar indefinidamente, y el gráfico continuará generando incrementalmente a medida que se acerque a sus vértices más inexplorados.
  • localmente finito: el grado de vértice nunca debe cambiar después de que el jugador lo haya visitado
  • etiquetado de manera estable: cada vértice representa una ubicación que se generará a partir de una semilla; la misma semilla debe asignarse a un vértice independientemente de la ruta que el jugador usó para viajar allí o qué tan grande es el gráfico cuando lo hacen

He tenido algunas ideas (que aún no he intentado implementar) con respecto al uso de los máximos locales del ruido de perlin 2D como vértices (la entrada x e y podrían usarse como su etiqueta), pero eso se siente torpe y complicado.

¿Hay una mejor manera de generar un gráfico como este? Estoy desarrollando en Python 2.6 usando Panda3D y numpy, ¡y por supuesto estaría dispuesto a incluir otras bibliotecas si ayudan con este problema!

Editar

Creo que he hecho un mal trabajo explicando algunos de mis requisitos, ¡así que es hora de ilustración! Con suerte, esto aclarará las cosas.

Lo que quiero decir con tener etiquetas estables es que quiero, por ejemplo, que el Jugador A pueda explorar y encontrar, entre otras cosas, un camino cíclico de regreso a su ubicación inicial y una montaña que parezca un gato. Su juego ahora se parece a lo siguiente (los vértices están numerados con sus semillas y bordes con el orden en que los atravesó el jugador). Comenzó en el vértice 8329 (verde) y Happycat Mountain está en el vértice 6745 (azul).

Gráfico mundial del jugador A

Buen amigo del jugador A El jugador B es un fanático de los gatos, por lo que quiere mostrárselo. Él le da la semilla raíz de su mundo y direcciones a lo largo de la ruta más corta a la montaña de interés. Su juego ahora debería verse así:

Gráfico mundial del jugador B

El problema con el que actualmente tengo más dificultades es "¿Cómo genero las mismas semillas para el Jugador B cuando su exploración no ha seguido el mismo camino?" Eso es lo que me llevó a la idea de usar el ruido Perlin: mientras se use la misma semilla raíz, los máximos no se moverán, por lo que sus coordenadas podrían usarse como semillas de vértices estables.

Ben Blank
fuente
¿Por qué una gráfica conectada no se ajusta a esto? mathworld.wolfram.com/ConnectedGraph.html Sin embargo, puedo estar perdiendo el punto. Si un usuario quiere ir de una ubicación a otra y todos están conectados, dele una lista de ubicaciones y mueva su posición en el mapa mundial a la nueva ubicación.
Brandon
@brandon - "Conectado" es la segunda propiedad que enumero. :-)
Ben Blank
Mi punto es, si puedes ir de un nodo a otro. Cuando visiten un teletransportador, deles una lista de todos los nodos que han visitado, excepto este. No es necesario tener un gráfico, mantienes una lista de todos los nodos visitados y sus ubicaciones y solo te teletransportas a la ubicación que eligen. ¿Estoy malentendido?
Brandon
Casi todas sus descripciones de esos términos son correctas, excepto "cíclico" y "localmente finito". El primero restringe sus gráficos para que sean como suenan: un círculo. Un término que podría usar para el requisito de que haya más de una ruta de un vértice a otro es "2-conectado". "Localmente finito" solo significa que cada vértice tiene un número finito de aristas.
Harry Stern
@ Harry Stern: entiendo que los gráficos cíclicos son gráficos que contienen al menos un ciclo de gráfico . Parece que estás hablando de un gráfico de ciclo , que es un gráfico que consiste en un solo ciclo de gráfico y nada más. Específicamente no busco gráficos que estén "conectados 2" (ver "simple"). Y sí, eso es lo que quise decir con "localmente finito".
Ben Blank

Respuestas:

6

No puedes hacer un gráfico infinito. Su memoria es finita, por lo tanto, el número de vértices y aristas también es finito. Lo que puede hacer es hacer un gráfico finito y luego agregarle más. Parece que te has dado cuenta de esto, pero creo que es importante que se establezca explícitamente para que no vayas por un camino sin salida.

Debes tener mucho cuidado al hablar de los "vértices más externos". Un gráfico es un conjunto de vértices, un conjunto de aristas y una función que relaciona los dos. No hay una interpretación geométrica establecida a menos que aplique una. Por ejemplo: ambas imágenes muestran exactamente el mismo gráfico. En la primera imagen, el vértice 2 podría considerarse un vértice "más externo", pero en la segunda imagen el vértice 2 no se consideraría "más externo". Si consideró tres dimensiones, podría decir que todos los vértices son "más externos".

Gráfica 1 Gráfica 2

Esto significa que debe tener alguna otra información para poder saber qué es un vértice "más externo". Podrías usar pares (x, y) ya que eso te daría una representación geométrica fácil de visualizar, sin embargo, no creo que necesites ir tan lejos. Por lo que dices, todo lo que necesitas saber es qué vértices ya están en el gráfico.

Si ejecutó esto cada vez que visitó un 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;
}

su gráfico satisfaría todos sus requisitos, excepto ser cíclico. No sé si realmente necesitas una garantía. Si lo hace, entonces podría seleccionar específicamente un nodo no visitado y hacer una conexión, eso garantizaría una ruta entre el nodo actual y un nodo ya visitado ya que todos los nodos no visitados están conectados al menos a un nodo visitado y dado que tuvo que haber visitado un El nodo visitado para llegar a donde estás ahora tiene al menos dos rutas.

Es simple porque hay una comprobación explícita, conectado porque todos los nodos nuevos obtienen al menos una conexión, localmente finito porque los bordes solo se agregan antes de su visita o en su primera visita, y solo a nodos no visitados. Técnicamente no es indirecto, pero funcionalmente es lo mismo que crea un borde direccional en ambas direcciones. Puedes etiquetar el nodo como quieras, yo uso el número aleatorio generado, pero puedes agregar otros parámetros al constructor, uno de ellos es tu semilla.

Chemball masticable
fuente
Usted percibe exactamente lo que quise decir con "infinito" y su punto de vista sobre "lo más externo" está bien entendido: he modificado la palabrería en mi pregunta. Sin embargo, o no entiendo su generador correctamente o le expliqué mal mis necesidades, ya que parece que esto no generaría las mismas semillas para diferentes caminos hacia el mismo vértice. He agregado algunas ilustraciones a mi pregunta que espero aclaren más lo que estoy tratando de lograr. :-)
Ben Blank
Ahora entiendo lo que quieres decir. Eso es un poco más difícil. Lo que debería hacer es cambiar la llamada genRandomNumbers a una función que siempre devuelva el mismo conjunto de números para su entrada, y usar la semilla del nodo como argumento. Esto garantizaría que obtendría las mismas conexiones y semillas sin importar qué camino tome o con qué nodo comience. Tendría que tener cuidado de que el conjunto de números para el nodo B al que se conecta A también contenga A para que obtenga su propiedad de gráfico no dirigida. Si no haces esto, obtienes un gráfico dirigido.
Chewy Gumball
1

Un 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()

Hay muchos detalles que omití, pero esto debería capturar la idea general. Es posible que desee mantener vecinos en la memoria que estén más alejados de la ubicación actual, dependiendo de la distancia mundial que exista entre los portales, la cantidad de memoria disponible, etc.

Jiahua Wang
fuente