Contexto de la investigación

Videojuegos

Software de entretenimiento

Mercado lider indiscutible a nivel internacional

La industria cinematográfica deja paso a la industria del videojuego

Problema

Videojuegos requieren mapas

Consumo de recursos (horas/persona)

Solución

Elaborar un generador de mapas

$\implies$ ahorro de recursos

Especificaciones

Coordinación

Cada juego tiene sus reglas y mecánicas

El sistema generador debe estar adaptado

Especificaciones de este proyecto han sido impuestas por

Definición del tipo de juego

• Mapas de tiles en 2D
• El jugador comienza en una habitación
• Objetivo: llegar a una habitación considerada como final
• Vista cenital



Captura de Action Hollywood, publicado por TCH en 1995 para recreativas

Especificaciones para la generación (I)

• Partir de una lista de habitaciones previamente creadas
• Maximizar el camino desde la habitación de inicio hasta la final
• Fomentar caminos alternativos
• Fomentar la variabilidad en los niveles generados

Especificaciones para la generación (II)

• Mapa generado al inicio de la partida
• No importa habitaciones inicial y final
• Debe funcionar en sistemas móviles modernos
• No hay restricción fuerte del tamaño del mapa

Estado del arte

Generación procedimental de contenido

Inicios en la demoscene

Campo emergente en la aplicación a videojuegos:

• Generación de mapas
• Storytelling procedimental
• Generación de puzles

Representación

Topología de los elementos

Representación física de mapas y habitaciones: matriz de dos dimensiones

$\begin{matrix} 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{matrix}$

$\leftrightarrow$

Habitaciones

Lista de puertas que servirán para conectar habitaciones

Representación dividida en:

• Prefab: clase de una habitación
• Instancia: instancia concreta de una habitación

Prefab de habitación

También nos referiremos como clase o modelo.

Contiene la matriz 2D asociada al modelo de habitación.

Puertas potenciales precomputadas

Puertas potenciales

¿Cuándo un tile $t(x,y)$ es una puerta potencial?

$o(x,y) = outer(x,y)$: tile vacío exterior
$i(x,y) = inner(x,y)$: tile vacío interior
$s(x,y) = solid(x,y)$: tile sólido (pared)

Instancia de habitación

Contiene un subconjunto de todas las puertas potenciales del modelo asociado

Referencia al modelo

Además,

• Lista de puertas activas
• Lista de puertas no activas
• Posición de la instancia en el mapa (si procede)

Mapa

Matriz 2D con habitaciones colocadas

Suficientemente grande como para colocar todas las habitaciones

Conexiones entre habitaciones, empleando una matriz superior

Estrategia constructiva

Definición

Construiremos el mapa a partir de movimientos $M_i(R_i,P_i)$ compuestos por:

• $R_i$: modelo de habitación a colocar
• $P_i$: posición del mapa donde se coloca

Cómputo de posibles movimientos

Dado un estado concreto del proceso

• Lista de habitaciones colocadas
• Lista de habitaciones por colocar

La lista de posibles movimientos se computará a partir de las posibles conexiones entre las puertas potenciales del mapa y de las habitaciones restantes

$$\bigcup_{r \in RR}posiblesConexiones(map, r)$$

$$RR = habitacionesRestantes$$

Conexiones entre el mapa y una habitación

$possibleConnections(map, r) =$
$\bigcup_{p \in rooms(map)} \left\{ cx(map,r,p,u,v,w) : \neg col(map, r, w) \right\}$

$w = v - u + \begin{cases} (-1,0) \\ (+1,0) \\ (0,-1) \\ (0,+1) \\ \end{cases}$

$potentialDoor(u, r), potentialDoor(v, p)$

Ejemplo de conexión entre mapa y habitación

Flujo del algoritmo

Interfaz de selección de movimiento

Delegamos la selección de un movimiento entre todos los posibles a una interfaz que implementaremos

interface IMovementSelector {
    Movimiento ElegirMovimiento( Mapa mapa, List<Movimiento> movimientos );
}

Mapa GenerarMapa( List<Habitacion> habitaciones, IMovementSelector mapSolver ) {
  Mapa mapa = MapaVacio();
  while( !habitaciones.isEmpty() ) {
    List<Movimiento> movimientos = GenerarMovimientos( mapa, habitaciones );
    Movimiento elegido = mapSolver.ElegirMovimiento( mapa, movimientos );
    mapa.InsertarHabitacion( elegido.habitacion, elegido.posicion );
    habitaciones.remove( elegido.habitacion );
    GuardarMovimiento( elegido );
  }
  EstablecerRecorridoPrincipal( mapa );
  return mapa;
}
						

Guardado de movimientos

La selección de un movimiento será el cuello de botella

Guardamos la lista de movimientos necesaria para reconstruir el mapa

Sirve para mejora añadiendo backtracking, permitiéndonos reconstruir el mapa rápidamente

Implementación de interfaz de selección aleatoria

Propiedades

No tiene interés computacional

Elige un movimiento de forma aleatoria

Resultados buenos pero no proporciona ningún tipo de control

Eficiencia computacional

Ejemplo

Implementación de interfaz de selección basada en búsqueda

Método de búsqueda

Encontrar una solución que satisfaga el enunciado del problema

Problema debe ser discreto, accesible, estático, observable y determinista

Definición de acciones posibles en los estados (movimientos)

Búsqueda no informada

Estado inicial: mapa vacío

Función objetivo: todas las habitaciones colocadas

Función de coste.

Estrategia básica

Asignar una puntuación a cada movimiento (fitness)

Elegiremos movimiento con mejor puntuación

Delegamos el cómputo del fitness a una interfaz

interface IFitnessSolver {
    float ComputarFitness( Mapa mapa, Movimiento m );
}

class SearchMovementSelector implements IMovementSelector {
    IFitnessSolver fitnessSolver;
    Movimiento ElegirMovimiento( Mapa mapa, List<Movimiento> movimientos ) {
        List<Float> fitness;
        for( Movimiento m : movimientos ) {
            fitness[m.index] = fitnessSolver.ComputarFitness( mapa, m );
        }
        Movimiento elegido = ObtenerMejor( movimientos, fitness );
        return elegido;
    }
}
						

Árbol de búsqueda

Generado implícitamente

Múltiples objetivos

• Tamaño del camino principal
• Caminos no-principales
• Cantidad de bifurcaciones (extra)

Fitness basado en múltiples objetivos

Implementamos la interfaz IFitnessSolver

Adición de interfaz para combinar todos los objetivos

interface IFitnessCombinator {
    float Combinar( float[] fitnesses );
}

class MultiObjectiveFitnessSolver implements IFitnessSolver {
    IFitnessCombinator fitnessCombinator;
    float ComputarFitness( Mapa mapa, Movimiento m ) {
        float fitness = new float[3];
        fitness[0] = ComputarObjetivo0( mapa, m );
        fitness[1] = ComputarObjetivo1( mapa, m );
        fitness[2] = ComputarObjetivo2( mapa, m );
        fitnessCombinator.Combinar( fitness );
    }
}
						

Tipos de combinadores de fitness

Combinador parametrizado

Combinador parametrizado adaptativo

Fitness Caché

Cómputo de fitness es el cuello de botella del sistema

Se ha ideado una caché que evita computar todos los fitness en cada paso

Sacrifica calidad del algoritmo pero es posible controlar el impacto

Flujo con caché

Fitness Caché (II)

interface IFitnessCache {
    Fitness Get( Movimiento m );
    void Cachear( Movimiento m, float fitness );
}
class SearchMovementSelector implements IMovementSelector {
    IFitnessSolver fitnessSolver;
    IFitnessCache fitnessCache;
    Movimiento ElegirMovimiento( Mapa mapa, List<Movimiento> movimientos ) {
        List<Float> fitness;
        for( Movimiento m : movimientos ) {
            Fitness f = fitnessCache.Get(m);
            if( f != null ) {
                fitness[m.index] = fitnessSolver.ComputarFitness( mapa, m );
                fitnessCache.Cachear( m, fitness[m.index] );
            } else {
                fitness[m.index] = f;
            }
        }
        Movimiento elegido = ObtenerMejor( movimientos, fitness );
        return elegido;
    }
}
						

Tipos de caché

Se han creado 3 tipos de caché:

• NoCaché. Por defecto. No cachea nunca.
• AlwaysCaché. Se cachea siempre.
• Refresher. Se vacía la caché cada N habitaciones colocadas

Además, gracias a que se implementan con una interfaz, es posible idear otros tipos distintos.

Resumen de diseño

Otros componentes

Gestor de instancias por prefab

1 prefab - N instancias

En cómputo de posibles movimientos, comprobamos 1 instancia por modelo

Instancias a comprobar = número de prefabs

Conseguimos agilizar el sistema

Selector de prefabs

Tener control sobre tipo de habitacion elegida en cada paso

Divisor de movimientos

Elige un subconjunto entre todos los movimientos posibles

Basado en porcentaje

Experimentación

Parametrización

Una vez construido el sistema, es necesario configurar el generador con distintos parámetros

De esta forma, el desarrollador podrá adaptar los mapas generados a sus preferencias según el juego que vaya a construir

Combinador parametrizado (I)

Combinador parametrizado (II)

Combinador parametrizado (III)

Combinador parametrizado (IV)

Combinador parametrizado (V)

Combinador adaptativo (I)

Combinador adaptativo (II)

Combinador adaptativo (III)

Impacto de divisor de movimientos (parámetros)

Impacto de divisor de movimientos (datos)

Impacto de divisor de movimientos (comparativa)

Impacto de subconjunto de puertas (parámetros)

Impacto de subconjunto de puertas (datos)

Impacto de subconjunto de puertas (comparativa)

Impacto de caché refresher

Impacto de caché refresher (datos)

Impacto de caché refresher (comparativa)

Configuración AlwaysCaché

Configuración NoCaché

Configuración personalizada

Ejemplo real usando la configuración personalizada

Tamaños y parámetros parecidos a los necesitados según las especificaciones

Ejemplo grande usando la configuración personalizada

Ejemplo con mucha variabilidad usando la configuración personalizada

Pasaremos a añadir muchos modelos distintos

Arreglo de ejemplo con mucha variabilidad

Trabajo futuro.

Más tipos de caché

Cachear cada N movimientos

Cachear con probabilidad

Selección de puertas

Permitir al desarrollador elegir un subconjunto de puertas entre todas las posibles

Combinadores

Attack y decay personalizados por cada objetivo

Adición de objetivos

Verticalidad y horizontalidad

Condensación

Backtracking (I)

Según nuestro modelo actual, no se permite backtracking

Guardamos la lista de movimientos, el cual representa un estado concreto del sistema

Esto permite reanudar la búsqueda cuando sea conveniente

Para fomentar que el camino sea distinto, se puede forzar a elegir una posición con una distancia mínima a la elegida anteriormente

Backtracking (II)