Reaxion UTL

Análisis de los algoritmos para generación de ambientes virtuales aleatorios.

Analysis of the algorithms to create random virtual environments.
Instituto de Estudios Superiores A.C. Puebla.


Por: Mario Alberto Rivera Legarreta, Mónica Pérez Castañeda, Héctor Adrián Díaz Furlong, Alberto Roman Flores.

Año 4, Número 1. Septiembre - Diciembre, 2016.

Resumen

Cuando se trata de desarrollar un ambiente virtual para un videojuego, se necesita tiempo y esfuerzo para la elaboración de dicho contenido, cualquier tecnología que permita hacer este desarrollo de forma más rápida y eficiente será bienvenido para su uso. En este trabajo se realizó una comparación entre los distintos algoritmos para la generación procedural de contenido (PCG), enfocada al desarrollo de ambientes virtuales en videojuegos.

Palabras Clave: PCG, SBPCG, PRNG, EDPCG, ItSub.


Abstract

When developing a virtual environment for a videogame, time and effort are required to elaborate said content, any technology that allow a quicker and efficient development will be welcomed. In this paper, a comparison between diferent algorithms for procedural generation of content (PCG) has been made, focused on virtual environments and videogames.

Key words: PCG, SBPCG, PRNG, EDPCG, ItSub.


Introducción

La generación de contenido procedural (PCG) hace referencia a la creación de contenido de una determinada parte de un juego de forma automática, es decir con la ayuda de un algoritmo que desarrolle esta parte sin necesidad de hacerlo de forma manual. Por contenido de un videojuego se entienden todos los aspectos de un videojuego que afectan el modo de jugarlo, como los niveles, la historia, los personajes, las reglas etc., excluyendo los comportamientos de los NPC’s (Non Player Characters) y el motor del juego. La generación procedural ofrece varias ventajas a los desarrolladores de videojuegos, tales como el menor consumo de memoria, un menor costo y tiempo de producción y la creación de nuevos tipos de juegos con mecánicas basadas en la generación de contenidos.


Metodología

Los artículos utilizados en este documento fueron empleados por el contenido específico de generación procedural; además de que los autores hacen énfasis a la implementación de distintos algoritmos para posteriormente hacer un análisis en tiempo de ejecución tomando en cuenta los distintos factores que influyen la entrada y la salida. La palabra clave que se empleó para la búsqueda de información fue PCG y ambientes virtuales, en bases de datos indexadas.


Generación aleatoria

El desarrollo en la industria de los videojuegos ha abierto muchas puertas en cuanto al desarrollo independiente. Sin embargo, el costo y desarrollo de un videojuego no es tan trivial; debido a que para desarrollarlo se requiere tiempo, así como un gran costo para su producción.

PCG se ha utilizado en juegos digitales desde principios de 1980, con el juego Rogue que utilizaba la generación procedural para mazmorras y Elite para generar galaxias de forma procedural que proveían al jugador la posibilidad de explorar espacios inesperados de gran tamaño. Desde ese entonces ha sido utilizado en muchos otros juegos, algunas muestras de la generación de territorio de forma aleatoria, pueden encontrarse en juegos como Civilization (2005) para explorar el mapa y Minecraft (2011) para crear el mundo1.

Juegos como Minecraft generan la parte visible de un terreno potencialmente infinita en tiempo real. Esto significa que es capaz de calcular alturas alrededor de 105 puntos en 160 segundos por cada cuadro de animación. La generación de terreno es un claro ejemplo de lo que se conoce en la industria de los videojuegos como generación de contenido procedural.

La generación de contenido de forma procedural debe considerar tres propiedades importantes2.

  1. La generación tiene que ser rápida, lo que significa que tiene que utilizar solamente una fracción de la potencia de cálculo disponible para la computadora.
  2. Al azar y estructurado de manera que se crea contenido que es variable e interesante.
  3. Debe ser controlable de forma natural e intuitiva.

Generación procedural de contenido

Existen distintas técnicas para el desarrollo de contenido procedural de un videojuego, por ejemplo, para hacer mundos de juego complejos en una cantidad limitada de tiempo sin poner una gran carga para los diseñadores de contenido. La idea principal del procedimiento es que el contenido no se genere manualmente por diseñadores humanos, sino por ordenadores que ejecutan un procedimiento bien definido. Para evitar la pérdida de control sobre el proceso de diseño, es indispensable que artistas y diseñadores influyan en el producto final mediante ajustes de los parámetros del procedimiento3.

Después de tres décadas de investigación, existen hoy diversos métodos para generar proceduralmente diferentes tipos de contenido para juegos. Uno de los métodos más simples se basa en la generación de números pseudoaleatorios (pseudo-random number generation PRNG). El juego Elite utiliza este enfoque desde la década de 1980 para generar universos muy grandes. Un enfoque similar puede ser utilizado para generar texturas para los objetos de juego “kkrieger” por ejemplo, es un juego 3D en primera persona semejante en género a Halo, este implementa técnicas y procedimientos para generar texturas, mallas y sonidos que se utilizan en la creación de un juego complejo. Este requiere de menos de 100 kb de almacenamiento y tres-cuartas partes de magnitud de disco que un juego similar3.

Se conocen distintos tipos de juegos y contenidos que pueden ser generados procesalmente, Hendrikx3 realizó un análisis del diferente tipo de contenido que puede ser generado para un videojuego y lo dividió en distintas categorías. En la ilustración 1 se muestran las diferentes secciones y el método de generación de procedimiento para cada categoría.

 
2.6/4.6
Derived Content
6.1
New and Boadcast
6.2
Leaderboards
 
2.5/4.5
Game Design
5.1
System Design
5.2
World Design
 
2.4/4.4
Game Scenarios
4.1
Puzzles
4.2
Storyboards
4.3
Story
4.4
Levels
2.3/4.3
Game Systems
3.1
Ecosystems
3.2
Road Networks
3.3
Urban Environments
3.4
Entity Behavior
2.2/4.2
Game Space
2.1
Indor Maps
2.2
Outdoor Maps
2.3
Bodies of Water
 
2.1/4.1
Game Bits
1.1
Textures
1.2
Sound
1.3
Vegetation
1.4
Buildings
  1.5
Behavior
1.6
Fire, Water, Stone & Clouds
 

Ilustración 1. Relación de métodos y secciones generable.
Fuente: Procedural Content Generation for Games: A Survey3.

Hendrikx3 desarrolló en su trabajo una taxonomía utilizada para generar contenidos proceduralmente ordenadas por complejidad para todo el espectro de tipos de contenido, con un énfasis en los métodos que han demostrado ser útiles en aplicaciones comerciales.


Generación de ambientes virtuales

La representación más común de un terreno es regularmente por campo de altura (una cuadrícula 2D, donde el valor del vértice representa la elevación en su ubicación). Los campos de altura también llamados mapas de altura son fáciles de implementar, además puede ser comprimido y almacenado en la GPU de manera eficiente. La elevación de terreno puede ser generada proceduralmente, ya que la elevación montañosa se asemeja a los producidos por los fractales. Una limitación inherente de los campos de altura es la incapacidad de proporcionar aleros y curvas, por lo que las técnicas alternativas para almacenar los terrenos son estructurados en capas, datos o mallas 3D4.

Gamito y Musgrave proponen un modelo de sistema de terreno que resulta en voladeros regulares5. Algunos algoritmos de generación de mapas de altura se basaron en métodos de subdivisión, por lo que un mapa de altura es iterativo, cada iteración introduce una gran cantidad de aleatoriedad para generar mayor detalle de elevación. Una manera común de ajustar el comportamiento del algoritmo consiste en ajustar el número de pasos de subdivisiones y el desplazamiento inicial. Sin embargo, estos métodos no proporcionan ninguna manera para influir en las características, tales como montañas o valles.

Existen otros métodos estocásticos para la generación de mapas de altura, en su mayoría sobre la base de los generadores de ruido4. Similar al método de desplazamiento de punto medio, el control estocástico para mapas de altura se limita a la elección de parámetros iniciales para la generación. El significado de los parámetros puede ser no intuitivo, y con frecuencia solo una gama limitada de posibles valores da resultados plausibles. El rendimiento de los algoritmos de ruido es excelente, es muy adecuado para el procesamiento paralelo, ya que cada punto de la cuadrícula puede ser computado de forma independiente de los valores de los puntos vecinos, similar al algoritmo del k-vecino más cercano. Por otro lado, Olsen6 describe mediante una representación de altura en dos dimensiones de mapas utilizando valores de punto flotante entre 0 y 1. A menos que se indique lo contrario, todos los ejemplos utilizan cuadrados de mapas con una longitud de lado N = 29 = 512, dando un total de N 2 = 262144 células, cada célula contiene un valor de altura. El mapa de altura se denota con H y las células individuales son denotadas con h i,j , donde i y j son coordenadas entre los rangos 0 hasta 5116. Algunos cálculos se abordan fuera de esos rangos, en ese caso, el módulo se utiliza para envolver las coordenadas alrededor de cada módulo de modo que sea con el vecino más cerca de la célula del lado derecho y ser la más cercada del lado izquierdo en la misma fila6.

Se deben tomar en cuenta distintas características al momento de definir el comportamiento para la generación de un terreno; una de ellas es la erosión. El termino erosión cubre muchos fenómenos naturales y el terreno difiere en cuanto a cambios climáticos, que producirán muchos tipos de cambios en un paisaje. En este artículo no se abordará la síntesis para la simulación de la erosión, en cambio, se enfocará en el algoritmo de desplazamiento de punto medio.


Desplazamiento de punto medio

Otro enfoque a la simulación del ruido 1/f es por un método de desplazamiento de punto medio, en este caso el algoritmo de diamante-cuadro. Jacob Olsen indica en su trabajo que en vez del cálculo de cada célula se hará en varias octavas (hasta 9 octavas con N= 29) y luego sumando las octavas, el valor de cada celda solo necesita ser calculado una vez6.

El método de desplazamiento del punto medio funciona de forma recursiva calculando los valores faltantes hasta la mitad entre los valores ya conocidos y luego al azar compensando los valores dentro de un rango determinado por la profundidad actual de la recursión. Con una persistencia de 0.5, este rango se reduce a la mitad con cada paso recursivo y una aproximación de 1/f del ruido es creado6.

Idealmente, las compensaciones al azar deben tener una distribución de Gauss en el interior del desplazamiento, pero para el proceso de sintetizar terreno, los valores distribuidos de manera uniforme son aceptables y más rápido el cálculo.

Por otro lado, Emilien en su trabajo de generación de modelado procesal para pequeñas ciudades europeas introduce un procedimiento de tres pasos como método de generación.

En primer lugar, se propone un proceso iterativo basado en mapas de interés que se utiliza para generar progresivamente semillas de asentamiento y los caminos que los conectan. En seguida se toma en cuenta el hecho de que una nueva carretera atrae colonos, mientras que una casa nueva con frecuencia conduce a alguna extensión de la red de carreteras, ambos aspectos se toman en cuenta en la generación de mapas. Para implementarlo se usa un método de conquista anisotrópico para segmentar la tierra en parcelas alrededor de liquidación de semillas. Por último, se introduce de forma abierta una gramática mar para generar la geometría 3D7.

En su trabajo se demuestra la eficacia de su método mediante la generación de distintos tipos de aldeas en terrenos arbitrarios de una aldea de montaña a un pueblo de pescadores, y validar mediante la comparación con los datos reales.

Tabla 1. Tiempo computado para la generación de villas en minutos.

Pescador Montaña Fortificado
Esqueleto 4:00 5:00 7:00
Encomiendas 7:00 11:00 13:00
Geometría 0:20 0:30 0:30

Fuente: Procedural Generation of Villages on Arbitrary Terrains7.

En la tabla 1, se puede observar que en el último paso para la generación tridimensional de la aldea, incluyendo carreteras, edificios y vegetación, se obtuvieron variaciones de tiempo significativas cuando se genera un esqueleto, la encomienda y la geometría para cada uno de los modelos del ambiente.

Yoav Parish & Pascal Müller en su trabajo de modelado procedural para ciudades nos plantea una serie de problemas a los gráficos del ordenador. Cada zona urbana cuenta con una red de transporte que sigue la población y las influencias ambientales y un supuesto plan de patrón. Los edificios en este trabajo siguen siendo históricos, estéticos y tienen reglas estatutarias. Para crear una ciudad virtual, una hoja de ruta tiene que ser diseñada y un gran número de edificios tienen que ser generados (caso similar al juego de Gran Theft Auto 5). Para ello proponen un sistema que utiliza un enfoque de procedimiento basado en sistemas L para modelar ciudades. A partir de diversos mapas de imagen dada como entrada, tales como límites de tierra y agua y la densidad de la población, su sistema genera un sistema de carreteras y calles, divide la tierra en lotes, y crea la geometría adecuada de los edificios de las respectivas asignaciones8. Para la creación de este sistema ampliaron su funcionamiento con distintos métodos; primero un sistema L que genera la geometría y un sistema basado en la textura de los elementos y métodos procedurales que componen los edificios.

Su sistema llamado CityEngine consta de varias herramientas que forman el proceso gráfico que se muestra en la ilustración 2.

herramienta de creación Procedural Modeling of Cities8

Ilustración 2. Herramienta de creación.
Fuente: Procedural Modeling of Cities8.

En una primera etapa, los datos de entrada alimentan al sistema de generación de carreteras utilizando un sistema L; las áreas entre las carreteras se subdividen para definir las asignaciones de los edificios que son colocados. En una tercera etapa, mediante la aplicación de otro sistema L, los edificios se generan como una representación de cadena booleana de operaciones en forma de solidos simples. Por último, un analizador interpreta todos los resultados para el software de visualización. El software de visualización debe ser capaz de procesar la geometría poligonal y la textura de mapas. Este es el caso práctico para casi cualquier renderizado 3D. Además, la mayoría de los procesadores actuales compatibles, soportan la línea de exploración de texturas por procedimiento, por lo que el mecanismo propuesto para generar fachadas de los edificios puede ser implementado sin ningún problema8.

George Kelly & Hugh McCabe en su artículo “A Survey of Procedural Techniques for City Generation” mencionan que la propiedad clave de la generación por procedimiento es el que describe la entidad, ya sea la geometría, textura o efecto, en términos de una secuencia de instrucciones de generación en lugar de como un bloque estático. Las instrucciones pueden ser entonces instancias de los activos y la descripción se puede parametrizar para permitir que la generación de instancias tenga características diferentes9.

Una de las técnicas que proponen es utilizar la generación de primitivas 3D como parámetros aleatorios, por ejemplo, un cubo con altura al azar9. Algunos algoritmos simples que utilizan funciones pseudo-aleatorias se pueden emplear para generar ruido para su uso en la texturización y formaciones naturales, algoritmos recursivos más complejos tales como fractales o sistemas L descritos por Yoav Parish y Pascal Müller en su trabajo, con la variante que George Kelly las utiliza para recrear estructuras orgánicas que se encuentran en la naturaleza como copos de nieve y árboles.

Ebert10 identifica las siguientes características importantes de las técnicas de generación por procedimientos:

  1. Abstracción: Geométrica y textura de datos en vez de detalles son abstraídos en un algoritmo o conjunto de procedimientos.
  2. Control paramétrico: Los parámetros se definen y son ajustados de forman que correspondan directamente a un comportamiento específico en la generación por procedimientos.
  3. Flexibilidad: Es posible capturar la esencia de una entidad sin que limita explícitamente su comportamiento en el mundo real9.
En los tiempos modernos, la PCG se utiliza generalmente solo en roles estrictamente especializados y casi siempre durante el desarrollo del juego. La técnica probablemente más utilizada es SpeedTree, que genera automáticamente un gran número de árboles similares, pero no idénticos para poblar terrenos.


Alternativas a la PCG

Georgios y Julian hacen énfasis a un nuevo enfoque para PCG, llamado Experience-Driven Procedural Content Generation (EDPCG). El enfoque que proponen se enfoca únicamente en la experiencia del jugador y su vinculación con la generación procedural de contenidos11.

Tomando en cuenta el contenido desarrollo a través de los estudios en el marco de EDPCG se considera como ámbitos claves el contenido del juego tomado como segmento para la construcción del mismo, así como la totalidad del juego maximiza el conocimiento y la experiencia del jugador. Dicho lo anterior, el contenido puede ser visto como bloques de construcción que no afectan directamente la experiencia del jugador pero que, si definen un componente principal para el control del ciclo de juego, es decir, la secuencia de acciones que se llevan a cabo en la ejecución11. Los principales componentes que se abordaran para el EDPCG son los siguientes:

  1. Modelado de la experiencia del jugador: Se modela como una función del contenido del juego y el jugador.
  2. Calidad del contenido: La calidad del contenido generado es evaluado y vinculada a la experiencia del modelado del jugador.
  3. Representación de contenido: El contenido está representado en consecuencia, para maximizar la eficacia, rendimiento y robustez del generador.
  4. Generador de contenido: El generador de búsquedas a través de contenidos de espacio que optimiza la experiencia del jugador según el modelo adquirido11.

Componentes principales de EDPCG

Ilustración 3. Componentes principales de EDPCG.
Fuente: Experience-Driven Procedural Content Generation11.

Una vez conocidos las distintas técnicas para generación procedural por contenido es necesario conocer los distintos parámetros que se necesitan evaluar cuando se genera dicho contenido. Por ello nos basaremos en los criterios de Kelly y McCabe “Generación Procedural de Ciudades”; pero dándole un enfoque diferente que pueda ser aplicado a cualquier tipo de terreno. Los criterios que propone George Kelly son los siguientes:

  1. Realismo: El nivel de detalle para que el ambiente generado parezca real.
  2. Escala: El ambiente está a una escala determinada.
  3. Variación: Puede recrear distintas variaciones o si es siempre homogéneo.
  4. Entrada: Conocer la entrada de datos mínimos necesarios para generar la producción básica y qué datos de entrada se requieren para tener la mejor salida.
  5. Eficiencia: Cuanto tiempo es necesario para crear los ejemplos que se muestran y que tipo de hardware se utilizaron para generarlos.
  6. Control: La generación puede cambiar por influencia del usuario de manera inmediata.
  7. Tiempo real: La ciudad se puede ver en tiempo real, además de que existan técnicas para optimizar la exploración en tiempo real9.

En su trabajo George Kelly menciona tres puntos principales para el desarrollo del contenido:

  1. Accesible – Los datos de entrada como datos geo-estadísticos o reglas no deben ser obligadas a tomar en cuenta dentro del sistema.
  2. Interactivo – El sistema no debe ser capaz de generar totalmente de forma autónoma, sino también facilitar con un control interactivo.
  3. Tiempo real – Las técnicas de optimización como “culling”, “paging” y “level of detail” deben ser implementadas9.

En resumen, su investigación fue crear un sistema de generación de ciudad adecuado para aplicaciones en tiempo real capaz de crear de forma realista, variada y gran escala de forma eficiente.

Mientras que los métodos anteriores para la generación de carreteras, terrenos, ambientes virtuales han demostrado ser eficientes en distintas maneras, vienen a costa de la complejidad de la programación. Nicholas Rudzicz & Clark Verbrugge manejan un enfoque diferente; el problema se basa en un método eficiente y conceptualmente sencillo que, conserva la flexibilidad y realismo comentado en los algoritmos anteriores12.

Dicho todo esto, su enfoque se basa exclusivamente en la subdivisión repetida de polígonos (ItSub – Iterated Subdivision). Este algoritmo inicial se extiende primero a través de la imposición de varias restricciones para asegurar salidas realistas, y finalmente, permite parametrizar la salida, a través de un uso modular de mapas de bits.

El algoritmo funciona colocando un número de vectores de semillas al azar en un “canvas” de dos dimensiones y repetidamente dibujando en forma perpendicular segmentos de líneas a partir de estos vectores iniciales y otros nuevos segmentos creados. La apariencia y calidad son impulsadas por el método de asignación, también por la formación de dibujo de vectores y el rango permitido de tamaños12.

En su forma más simple, el algoritmo ItSub requiere una entrada predefinida, un simple polígono P, un mínimo y máximo de área – Amin y Amax, respectivamente, para las subdivisiones resultantes o asignaciones. El algoritmo entonces bisecciona P al azar, resultando en dos nuevos polígonos. El último entonces puede ser aceptado o rechazado en base a sus áreas individuales: los polígonos más grandes se subdividen, mientras los de un tamaño aceptable se reservan de manera completa para dividirse12. El proceso descrito se puede apreciar en la ilustración 4.

Algoritmo ItSub

Ilustración 4. Algoritmo ItSub
Fuente:An Iterated subdivision algorithm for procedural road plan generation12.

El componente clave del algoritmo es el conjunto de polígonos de gran tamaño, que contiene todos los polígonos con una superficie superior a Amax. Inicializado solamente con el polígono P original, y devuelve un solo polígono a la vez. Una línea bisectriz se genera dentro de este polígono de trabajo para la elección de un borde al azar, y después un punto se genera de forma aleatoria a lo largo de este borde. La línea generada es extraída a través de este borde (no paralelo al borde mismo) y se dividirá en dos polígonos, a los cuales nombraremos p1 y p2. Estos polígonos resultantes se evalúan individualmente. En primer lugar, si cualquiera de los polígonos es demasiado pequeño (tiene un área menos de Amin), entonces la bisectriz se rechaza y se genera uno nuevo, de lo contrario es aceptado. Entonces, si un polígono todavía es de gran tamaño, es añadido de nuevo, mientras que si su tamaño es aceptable se añade al conjunto final de todos los polígonos generados o asignaciones. El algoritmo va a continuar hasta que no encuentre polígonos de gran tamaño para procesar12.

Nicholas Rudzicz & Clark Verbrugge hicieron una comparación con el algoritmo ItSub tomando en cuenta el uso de mapa de bits y cuando no se utiliza, teniendo una mejoría en cuanto al tiempo y al número de caminos generados cuando no se utilizó mapa de bits. La influencia del número de caminos en tiempo real y el tiempo se describen en la tabla 2.

Tabla 2. Tiempo de generación y caminos generados.

No bitmaps All bitmaps  
Roads Time (ms) Roads Time (ms)
200 386 60 944
1015 1190 301 1710
2043 2437 639 2459
4074 4392 1366 3521
    4259 9877

Fuente: "An Iterated subdivision algorithm for procedural road plan generation"12.


Resultados

Los distintos trabajos descritos en este documento permitieron poder conocer el orden de eficiencia de cada uno de los algoritmos descritos, tomando en cuenta como punto de comparación el tiempo de generación del ambiente; sin embargo, en cada uno de los trabajos la generación es distinta, algunos autores realizaron sus trabajos de forma distinta con terrenos, ciudades, edificios, carreteras o combinaciones de estos modelos. Parish & Müller en su trabajo tuvieron los siguientes resultados con un algoritmo de sistemas en L como se muestra en la tabla 3.

Tabla 3. Resultados de generación de ciudades

Parámetro Tiempo
Ciudad 10 minutos

Fuente: Procedural Modeling of Cities8.

George Kelly & Hugh McCabe obtuvieron resultados mejores dependiendo del parámetro de medición obtenido en este caso utilizando generación de primitivas 3D como parámetros aleatorios, también utilizando sistemas en L. Se puede apreciar en la tabla 4 que los resultados de generación en cuanto a ciudad son muy parecidos, teniendo en cuenta que se genera una ciudad con sistemas L.

Tabla 4. Resultados de generación de ciudades

Parámetro    Tiempo
Calles 10 segundos
Ciudad 10 minutos
Edificios 15 minutos
Texturas- Edificios 3 segundos

Fuente: A survey of Procedural Techniques for City Generation9.

Emilien7 con su método iterativo de generación de mapas consiguió resultados descritos anteriormente en la tabla 1 donde los tiempos de generación fueron de más de 5 segundos en cuanto a la creación de solo terreno.

Olsen6 en su trabajo por método de desplazamiento de punto medio obtuvo tiempos distintos tomando en cuenta diferentes características para el terreno como se muestra en la tabla 5; siendo mejores que los reportados por la generación iterativa de mapas por Emilien7.

Tabla 5: Resultados de tiempo de generación de terreno

Terrain type ε Υ Β γ
Base terrain 0.665 0.713 0.002 0.001
Reference thermal erosion, 50 iterations 0.614 0.980 0.002 0.001
Optimized thermal erosion, 50 iterations 0.626 0.983 0.002 0.001
Reference hydraulic erosion, 100 iterations 0.916 0.834 0.050 0.039
Optimized hydraulic erosion, 100 iterations 1.077 0.828 0.157 0.140
New algorithm, 50 iterations, T = 8/N 1.339 0.303 0.173 0.070
New algorithm, 50 iterations, T = 12/N 1.850 0.752 0.393 0.580
New algorithm, 50 iterations, T = 16/N 2.204 0.905 0.434 0.877
New algorithm, 50 iterations, T = 20/N 2.340 0.949 0.429 0.953

Fuente: Realtime Procedural Terrain Generation6.

Georgios y Julian11 tuvieron los mejores resultados en cuanto a generación, se pueden apreciar en la tabla 2. Estos tiempos fueron menores a 10 segundos tomando en cuenta que con su propuesta de algoritmo EDPCG, reducen el tiempo de generación además de que se enfoca en el desarrollo de carreteras de forma procedural en un terreno dado.


Conclusiones

En el presente trabajo se han presentado los distintos métodos, algoritmos y técnicas para generar una gran variedad de características en los ambientes virtuales en 3D. La PCG es un área de investigación presente que genera muchos resultados eficientes en cuanto al tiempo de desarrollo en tiempo real, incluyendo varias áreas y propósitos específicos, además, la aceptación y el uso de estas herramientas para ambientes virtuales han sido de un uso considerable en la mayoría de los juegos modernos. Cabe mencionar que el análisis descrito en este trabajo permitió conocer el orden de eficiencia en cuanto al tiempo en el uso de los distintos algoritmos, aportando diferentes características en cuanto a entradas y salidas; es por ello, que se puede hacer uso de las distintas técnicas para una sola generación, es decir, implementar algoritmos híbridos que puedan reducir aún más el tiempo de generación, tomando la salida deseada; que en este caso puede ser tanto terrenos, caminos, edificios y una gran variedad de características para generar. El análisis hecho de todos los algoritmos nos lleva a concluir que Georgios & Julian11 en su algoritmo de EDPCG permiten crear ambientes virtuales de forma rápida y eficiente, además de poder tener distintos modelos de entrada; teniendo también en cuenta que la salida puede ser cualquier modelo como edificios, terreno, carreteras o simplemente generar un nivel con diferentes características para un videojuego.


Referencias

1.- G. Smith. The Future of Procedural Content Generation in Games. Association for the Advancement of Artificial. [s.n]. pp. 2-3, 2014.
2.- I. Parberry. Designer Worlds: Procedural Generation of Infinite Terrain from USGS Elevation Data. Laboratory for Recreational Computing. Denton, USA:Texas, 2013.
3.- M. Hendrikx, [et al]. Procedural Content Generation for Games: A Survey. [en línea]. February 2011. ACM Transactions on Multimedia Computing, Communications and Applications. Disponible en: http://www.st.ewi.tudelft.nl/~iosup/pcg-g-survey11tomccap_rev_sub.pdf
4.- SMELIK, R.,TUTENEL, Tim., BIDARRA, R., [et al]. A survey on Procedural Modeling for Virtual Worlds. Modelling, Simulation & Gaming Department, TNO, The Netherlands, Computer Graphics and Visualization Group, Delf University of Technology, The Netherlands. Department of Computer Graphics Technology. Purdue University,USA.
5.- M. G, MUSGRAVE, F. Procedural landscapes with overhangs. In 10th Portuguese Computer Graphics Meeting. 2001. pp. 33–42.
6.- OLSEN, J. Realtime Procedural Terrain Generation. Department of Mathematics and Computer Science (IMADA). University of Southern Denmark. 31 october, 2004.
7.- EMILIEN, A., BERNHARDT, A., PEYTAVIE, A., [et al]. Procedural Generation of Villages on Arbitrary Terrains, Visual Computer. Springer Verlag. 2012, 28(6-8). pp.809-818.
8.- PARISH, Y., MÜLLER, P., Procedural Modeling of Cities, ETH Zürich, Switerzeland, Central Pictures. Switerzeland. [s.n]
9.- KELLY, G., MCCABE, H., A survey of Procedural Techniques for City Generation, School of Informatics and Engineering. Institute of Technology. Blanchardstown, Dublin 1. Ireland.
10.- EBERT, D., KENTON, F., PEACHY, D., [et al]. Texturing & Modelling - A Procedural Approach. Morgan Kaufmann. 2003.
11.- YANNAKAKIS, G., TOGELIUS, J. Experience-Driven Procedural Content Generation.[en línea]. Disponible en: http://julian.togelius.com/Yannakakis2011Experiencedriven.pdf
12.- RUDZICZ, N., VERBRUGGE, C. An Iterated subdivision algorithm for procedural road plan generation. School of Computer Science. McGill University. [s.n]


Fecha de recepción Fecha de aceptación Fecha de publicación
04/03/2016 11/04/2016 30/09/2016
Año 4, Número 1. Septiembre - Diciembre, 2016

Universidad Tecnológica de León. Todos los Derechos Reservados 2013 Licencia Creative Commons