Generación del nivel

Este probablemente sea el devlog más largo hasta ahora, ya que reúne tres semanas de trabajo en una sola publicación. Intentaré que la lectura sea lo más amena posible.

Generación cíclica

Primero lo primero: dado que estoy utilizando la técnica de Generación Cíclica (Cyclic Generation), considero importante definir este concepto. Esta técnica, desarrollada por el Dr. Joris Dormans, busca resolver un problema recurrente en la generación procedural: los niveles generados tienden a formar árboles ramificados.

En la siguiente imagen, se observa la diferencia entre una estructura ramificada y la forma de ciclo que sugiere esta técnica. La ventaja principal es que los jugadores no necesitan retroceder por caminos ya explorados (backtracking). Para una explicación más detallada, recomiendo este video.

Implementación

La implementación original de esta técnica sugiere utilizar reescritura de grafos (Graph Grammars) para introducir ciclos en los niveles. Sin embargo, resultó ser más complicado de lo esperado. Encontré una alternativa en GitHub, desarrollada por patrykferenc. Él también se encontró con la complejidad de la reescritura de grafos y menciona que al Dr. Dormans le tomó varios años de investigación lograr implementarla en un juego.

La solución de patrykferenc crea una estructura de grafo y selecciona un nodo aleatorio como entrada. A partir de ahí, marca un nodo vecino como inicio del ciclo y comienza a desplazarse lo más lejos posible, marcando los nodos por los que pasa como parte del ciclo. Luego, selecciona un nodo vecino al azar y lo marca como final del ciclo. Finalmente, utiliza el algoritmo A* para encontrar la ruta más corta desde ese nodo final hasta el inicio del ciclo, marcando todos los nodos de esa ruta como parte del ciclo.

Yo adapté esta implementación: selecciono dos nodos aleatorios como entrada y salida del ciclo y utilizo A* para conectarlos, logrando resultados similares. Un ejemplo es el siguiente:

.......
.......
..g....
..FCCC.
..CCCS.
.....e.
.......

Después de generar la estructura del grafo, definí patrones de diseño para los niveles. Implementé dos: uno en el que el camino está cubierto de enemigos y otro en el que la salida está bloqueada, requiriendo encontrar una llave al final del ciclo para abrirla.

public override void applyDesign(Graph t_graph) {
    Debug.Log("SimpleKeyAndLockCycle applied");
    Node exitNode = t_graph.getFirstNodeOfType(NodeType.Goal);
    Node penultimateNode = t_graph.pathB[^2];
    Node cycleEntranceNode = t_graph.getFirstNodeOfType(NodeType.CycleEntrance);
    Node cycleExitNode = t_graph.getFirstNodeOfType(NodeType.CycleEnd);
    t_graph.lockAndKey.Add(new LockAndKey(exitNode, penultimateNode, KeyType.Key));
    t_graph.lockAndKey.Add(new LockAndKey(penultimateNode, penultimateNode, KeyType.Valve));
    Edge exitEdge = t_graph.getEdge(new Edge(cycleExitNode, exitNode, EdgeType.OpenConnection));
    Edge penultimateEdge = t_graph.getEdge(new Edge(penultimateNode, cycleEntranceNode, EdgeType.OpenConnection));
    exitEdge.setEdgeType(EdgeType.Door);
    penultimateEdge.setEdgeType(EdgeType.Door);
}

Este enfoque da lugar a niveles con diferentes ambientes, como interiores de castillos, cuevas y campamentos goblin.

Siguientes pasos

El próximo paso es decorar los cuartos con trampas, puertas y llaves para desbloquear las secciones cerradas.

Level Generation

This is probably the longest devlog so far, as it covers three weeks of work in a single post. I’ll do my best to make it an easy read.

Cyclic Generation

First things first: since I’m using Cyclic Generation, it’s important to define the concept. This technique, developed by Dr. Joris Dormans, addresses a common issue with procedural generation, where levels tend to form branching trees.

The image below shows the difference between a branching structure and the cycle proposed by this technique. The main advantage is that players don’t need to backtrack through already explored paths. For a more detailed explanation, I recommend this video.

Implementation

The original implementation of this technique recommends using Graph Grammars to create cycles within levels. However, this proved to be more challenging than expected. I found an alternative by patrykferenc on GitHub.He also found graph rewriting to be highly complex, and it took Dr. Dormans several years of research to implement it in a game.

Patrykferenc’s solution involves creating a graph structure, selecting a random node as the entry point, and marking a neighboring node as the cycle start. The algorithm then moves away from the starting node, marking nodes along the way as part of the cycle. Next, it selects a random neighbor and marks it as the cycle end. Finally, it uses the A* algorithm to find the shortest path back to the cycle start, marking all nodes along the route as part of the cycle.

I adapted this solution: I select two random nodes as the entry and exit of the cycle, use A* to connect them, and achieve similar results. Here is an example:

.......
.......
..g....
..FCCC.
..CCCS.
.....e.
.......

After generating the graph structure, I defined level design patterns. I implemented two: one where the path is filled with enemies and another where the exit is blocked, requiring a key found at the end of the cycle to unlock it.

public override void applyDesign(Graph t_graph) {
    Debug.Log("SimpleKeyAndLockCycle applied");
    Node exitNode = t_graph.getFirstNodeOfType(NodeType.Goal);
    Node penultimateNode = t_graph.pathB[^2];
    Node cycleEntranceNode = t_graph.getFirstNodeOfType(NodeType.CycleEntrance);
    Node cycleExitNode = t_graph.getFirstNodeOfType(NodeType.CycleEnd);
    t_graph.lockAndKey.Add(new LockAndKey(exitNode, penultimateNode, KeyType.Key));
    t_graph.lockAndKey.Add(new LockAndKey(penultimateNode, penultimateNode, KeyType.Valve));
    Edge exitEdge = t_graph.getEdge(new Edge(cycleExitNode, exitNode, EdgeType.OpenConnection));
    Edge penultimateEdge = t_graph.getEdge(new Edge(penultimateNode, cycleEntranceNode, EdgeType.OpenConnection));
    exitEdge.setEdgeType(EdgeType.Door);
    penultimateEdge.setEdgeType(EdgeType.Door);
}

This approach results in levels with various environments, such as castle interiors, caves, and goblin camps.

Next Steps

The next step is to decorate the rooms with traps, doors, and keys to unlock closed sections.