Hace poco hice esta pregunta y la conclusión parece ser que el uso de la programación genética ( GP ) para la creación de contenido de juego de procedimiento no se ha hecho realmente. Quiero cambiar eso.

Estoy bastante seguro de que GP podría implementarse para ayudar a encontrar un nuevo generador de terreno. La pregunta a la que me dirijo es ¿cómo podría lograrse esto?

Todos los médicos de cabecera tienen algunas partes básicas que pueden generalizarse para todos los médicos de cabecera (selección de padres, recombinación, mutación, supervivencia). Puedo resolverlos por mi cuenta. El problema surge en las partes específicas del problema. Así es como representa el problema en el código (esto generalmente usa un árbol) y cómo evalúa qué tan bueno puede ser un generador (puede ser uno o más valores).

Las preguntas en pocas palabras:

• ¿Cómo representaría un generador de terreno de manera que pueda analizarse en un árbol?
  

• ¿Qué tipo de terreno tendría que generar esto? (mapa de altura, gráfico de vértice, ...)
  

  Cuanto menos se base en un hightmap, mejor.
  

• ¿Qué se usaría para evaluar la idoneidad de una solución?
  

  Ej: queremos un terreno interesante para que uno de los valores sea el cambio promedio en las normales para cada vértice en el terreno.

Puede tener suerte con un enfoque similar a las imágenes genéticas de Karl Sims .

Utiliza un conjunto simple de operadores en un lenguaje similar a LISP, de modo que la salida de cualquier operador puede utilizarse para influir en la imagen, de manera similar a en algunos lenguajes de sombreado (es decir, un escalar sería un valor en escala de grises, un vector3sería RGB, etc.) )

Aunque supongo que eso es material de implementación, entonces lo que probablemente quieras son sus palabras clave, que (iirc) contienen todos los conceptos básicos:

• funciones trigonométricas ( sin, cos, tan, etc.)
• posición ( x, y)
• operadores matemáticos básicos ( sqrt, pow, abs, inverse)
• funciones de ruido ( fBm, noise2, noise3)
• otros fractales ( mandelbrot, julia)
• funciones de interpolación ( lerp, quad, step, smoothstep)

(Algunos de los anteriores pueden no estar en su implementación; encontré su trabajo hace mucho tiempo y en realidad he hecho algunos intentos de lo que estás describiendo a lo largo de los años, por lo que los recuerdos pueden estar perdiendo :)

Manteniéndolo interesante (y rápido)

Tuve un poco de suerte con un enfoque de varias capas que redujo enormemente la cantidad de evoluciones muertas.

1. Se genera un conjunto de rangos para cada operador (o mutado de rondas anteriores)
   • estos idealmente mantienen los valores dentro de un rango "sensato" para cada función, pero pueden evolucionar en rangos que tienen resultados sorprendentemente útiles, lo que parece ser lo "correcto"
2. generar algunos árboles de algoritmos
   • para cada uno de estos generar algunos mapas de altura en posiciones aleatorias y evaluar la forma física
   • si tenemos muchas coincidencias buenas, evolucione un poco hacia abajo en esta rama, perturbando ligeramente los rangos del paso 1 en cada niño
   • de lo contrario, probablemente tengamos rangos malos, regrese al paso 1

Sin embargo...

Ahora he omitido convenientemente el algoritmo de acondicionamiento físico , en su mayoría usé el enfoque de Karl Sims de "selección antinatural" en el que ves a la generación actual en el cuadrado medio de un grupo de descendientes (popularizado por las herramientas eléctricas de Kai en el día: aquí está una imagen de lo que quiero decir ) ..

Sin embargo, probablemente podría tener un conjunto de imágenes de entrenamiento, tal vez algunas de imágenes satelitales y algunas artificiales con cualidades particulares y luego tal vez usar wavelet o análisis FFT 2D en ellas en comparación con el terreno que está probando.

Este es un tema interesante, pero dudo de qué necesita una respuesta :)

EDITAR: ahh. tuve que eliminar un montón de enlaces porque soy un nuevo usuario: - |

No estoy seguro de que pueda responder esta pregunta, pero siento una explicación de por qué podría ser una respuesta lo suficientemente útil. Entonces, Respuestas en pocas palabras:

• Deberá elegir una generación de terreno en la que ciertos aspectos se basen simplemente en valores de datos. Esto no es difícil de hacer, pero requiere que elija una generación de terreno. Dado que el área en la que estoy trabajando es en la generación de vóxeles, cosas como las tasas de muestreo, los pasos de túnel, los niveles de elevación, etc. serían cosas que se pueden poner en los datos y 'evolucionar'.
• Un poco va de la mano con la primera parte. Realmente no importa con qué forma de generación vaya, siempre que pueda establecer diferentes propiedades de la misma. Esta elección debería tener más que ver con el tipo de juego que estás buscando hacer.
• Aquí es donde se descompone. No puedo pensar en una manera de medir esto aparte de una Persona que realmente mira el mundo y dice "Oh, eso es bueno". Pero esto elimina la computadora haciendo su propia auto iteración. Esto también implica que vas a utilizar esta forma de generación para crear un mundo al final, buscando el "mejor" en lugar de uno aleatorio cada vez.

Los algoritmos genéticos generalmente se usan para resolver un problema conocido en el que puede definir el entorno a través de reglas. Luego, puede crear conjuntos de datos que representan diferentes propiedades que afectan la forma en que las cosas reaccionan a las reglas. Luego, la computadora juega una 'ronda' con el conjunto de datos inicial, selecciona el número X superior, mezcla sus valores después de emparejarlos y realiza otra ronda. Un ejemplo común de esto es 'criar un troll mejor' (hacer la cría para encuentre un conjunto de valores en los que el troll generalmente se desempeña muy bien en su entorno (es capaz de cazar y comer, ya sea matar o mantenerse alejado de los aldeanos, puede recoger el botín y acumular todos los objetos brillantes que desea, etc.).

No estoy seguro de que lo que intentas lograr sea aplicable en el ámbito de la generación del terreno. Lo único que se me ocurre es el tipo de evaluaciones de contenido del juego en las que no querías planear un mundo pero querías hacer uno en el que la ruta de inteligencia artificial se pueda calcular muy bien o algo así. Incluso con esto, sin embargo, está buscando un conjunto único o al menos limitado de mundos.

¿Qué tipo de terreno tendría que generar esto? (mapa de altura, gráfico de vértice, ...)

Definitivamente un gráfico de vértice (una malla), es compacto en cuanto al almacenamiento y se puede rasterizar (testear) a pedido.

¿Cómo representaría un generador de terreno de manera que pueda analizarse en un árbol?

Autómata celular. Se me ocurren dos implementaciones:

1. Autómatas de conjunto de reglas, tal vez con elementos de autómatas finitos (cuando se tiene en cuenta el estado actual, como intentos de contador o tiempo de inactividad).

   • Cada nodo se inicializa con un estado aleatorio
   • Cada nodo tiene una instancia de solucionador conectada
   • Cada solucionador sigue calculando el siguiente estado hasta que se quede sin reglas o alcance su estado ideal (ya he terminado aquí)
   • Todos los siguientes estados se calculan primero y luego se aplican todos a la vez antes de que comiencen los siguientes cálculos, por lo que el orden de cálculo no importará

El conjunto de reglas en sí puede representarse como un árbol de decisión de ramificación o un lote de comandos simple (no estoy seguro de si funcionará)

Es solo un conjunto de reglas para cada nodo

2. Constructores del mundo. En lugar de aplicar un solucionador para cada nodo, puede crear solo un montón de ellos y permitirles navegar por la malla.

   • Cada constructor tiene su propio conjunto de reglas
   • Evitar que entren en el nodo ocupado por otro constructor
   • Cada constructor puede ser representado como una rama del árbol.
   • Durante la evolución, los constructores pueden duplicar

Aún así, me temo que el segundo enfoque debe estar respaldado por el primero: la aleatoriedad inicial debe suavizarse y no estoy seguro de si los constructores pueden hacer el truco. Cada célula viva tiene mitocondrias después de todo.

¿Qué se usaría para evaluar la idoneidad de una solución?

La integridad del terreno resultante: no debería verse como una mezcolanza. Y la diversidad: en general, queremos que se represente la mayor cantidad posible de variaciones disponibles (el páramo plano de un extremo a otro no es divertido). Tal vez algo más complejo como cómo los nodos vecinos se ajustan entre sí (tundra en medio del desierto, ¿qué?)

Tengo que probarlo por mí mismo con mi generador de malla cuando / si tengo algo de tiempo libre =)