Refactoring my “Fire in the Lake” software

Although I had been refactoring bunches of code present in some methods into other methods, and created a couple additional structs when the original structs were handling concerns beyond what they were originally created for, at this point of the project some structs were accumulating massive amounts of methods. Refactoring them would require identifying the general purposes of the methods involved, classifying them and then isolating them from the original code so that area of the codebase wouldn’t be so brittle. I focused first in the area that handles executing the player or bot commands. As a general overview, each of the four players will push through the mouth of the system some words that will relate to their intentions, what they want to do in this turn. If they push through words like “event”, “operation”, “pass”, the system needs to understand that the player wants to play the active card for the event, or wants to perform an operation, or intends to pass. However, we also have words like “6”, “an loc”, “saigon”, “pacify”, “rally”. The system should reliably handle what kind of operation the player wants to play, in what space or spaces of the board, or stuff like how many troops it wants to deploy. In my initial design I simply passed an array of Strings through the command execution system, and those methods had the responsibility to figure out the intention of the player from whatever subset of words the method received. That was a clear violation of the separation of concerns, given that those methods should simply have to focus on executing an operation, a special activity, or delegating declaring that player as having passed, for example.

Before dealing with that major issue, I needed to take some scissors to the execute commands function. The mess of switches and ifs ended up being distributed into isolated functions that handled executing the events, others that executed each kind of operation, others that executed each kind of special activity, another that handled passing, and the biggest group, one that handled atomic executions such as deploying some units somewhere, manipulating the resources of a faction, setting a space to a level of support, improving the trail that the NVA faction uses, etc. That refactorization into a couple dozen files passed the integration tests without much trouble; thankfully, the three almost end-to-end tests that I wrote and that simulated three entire turns of the game are very resistant to refactorization.

There was another section of the code that handled the entirety of the flow of the game: how to deal with the couple of current cards, how to determine what factions were eligible or ineligible, how to slot those factions so that other parts of the system would know that the choices of those factions were already occupied, etc. It ended up being a tremendous chunk of code. I found three major different concerns for the methods involved: some methods just handled the general game flow: setting the active card, informing whether the turn had ended, moving to the next eligible faction according to the order shown in the active card, taking in the general player choices, being able to answer to whoever asked whether the turn had ended or not, etc. Another concern involved handling all the different possibilities for the factions: whether some faction is eligible, whether all are eligible, whether some faction has passed, determining the eligibility of a faction depending on some previous one’s actions, etc. The final concern was related with slotting the factions and moving them around into “holes” that can only hold either one of them at a time or four (maximum number of players). Whether a player has chosen, for example, to perform an operation without a special activity, is very important in this game system, because that means that the following player can only do a limited operation, while if the first player had chosen to play the card’s event, the second player would have been able to do a full operation plus a special activity.

The most pressing concern regarding the following features I had to implement had to do with the fact that I was passing an array of words from the “mouth” of the system to the lowest levels that handled command execution (in some cases to the very lowest level of executing atomic commands). It reeked of primitive envy; what the system should truly know is whether the player intended to perform one of the main choices (passing, event, operation), what operation if the player went that route (ex. rally, train, sweep), whether the player chose to do the additional action allowed for some of the main operations (such as improving the trail), or if the player chose a special activity, which one. We also have the fact that the player might have written the names of spaces (can be cities, provinces or lines of communication), and the program has to figure out if those locations are related to the event, the operation or the special activity. So I refactored out the entirety of that system and created an interpreter that chews the initial commands and just registers the player intentions. It can be asked “does the player want to activate the event?”, which returns a boolean response, and it can be asked to provide the locations associated with the event, for example. Far, far cleaner than the original, system, and not particularly hard to write. It suffers from a case of “excess of switches/ifs”, but it’s not pressing to figure out how to refactor that out. It reads each word as it comes, and depending on what intentions had been “detected”, it will convert to internal enums stuff like the names of places. If it receives the name of a space, the program determines whether, for example, the name actually refers to a space, and in that case if the player had previously sent the word to perform a operation, and in that case if it also had sent the word to perform a special activity. In that case the following spaces would be sent to a list of spaces associated with the special activity, but they would get associated to the operation or the event in other cases.

Again, thanks to the integration tests, the first time I got the major changes to compile, they immediately passed all the tests, so I knew that the previously codified functionality remained intact. That’s the advantage of test driven design: you can dismantle main areas of the code, improve it substantially, and remain confident that everything keeps working as it should. You wouldn’t dare to risk major changes otherwise.

Rediseño del renderizador

Ahora que voy a pasar a otra etapa en el desarrollo de lo que algún día podría convertirse en un juego, no quería dejar algunos ámbitos vitales del motor como habían quedado. Durante el desarrollo, la implementación de la renderización se había dividido de manera que para dibujar algunos elementos se usaba una clase y para otros otra. Además, el hecho de que el dibujo se realizaba en capas tampoco se reflejaba en la arquitectura. Para ello he revisado todas las piezas funcionales y reducido la implementación a sus conceptos principales.

  • ¿En base a qué se divide una fase de renderización de otras? Por ejemplo, primero se dibuja el terreno, que include el suelo y el agua. El terreno lleva asociada una textura específica; cambiar de textura es una operación que cuesta bastante para la tarjeta gráfica, lo que ha hecho que la mayoría de juegos intenten incluir los gráficos en la menor cantidad de archivos de imagen posibles. Sin embargo, la misma textura se usa en otras fases del dibujo; cuando el usuario mira desde una altura considerable, sobre las casillas de terreno debe dibujarse una casilla traslúcida, y esas casillas leen de la misma textura. Algo similar pasa con la textura de donde se sacan los dibujos de las criaturas. Se lee de ellas durante la fase en la que se dibujan las criaturas situadas en la misma altura desde la que el usuario ve el mapa, y durante la fase en la que se dibujan las criaturas situadas bajo el nivel de altitud actual.
  • Lo que parece único de este proceso es el concepto de capas, o layers en inglés. Primero se dibuja la capa de terreno, luego la de actores bajo el nivel de altitud actual (si existen), luego las casillas traslúcidas, luego los actores en el mismo nivel de altitud, y sobre esas capas obligatorias también se utilizan, en algunos programas, una capa para mostrar las regiones (que no usa una textura, además), y por último una capa para dibujar los overlays, o iconos; por ejemplo, para indicar al usuario la casilla situada bajo el cursor del ratón.
  • No todas esas capas están activas en todos los programas. Es la responsabilidad del usuario activarlas.


Unas funciones aisladas se encargan de gestionar esa activación, lo que ha permitido refactorizar todo ese código para aislar lo poco que cambia.


  • Idealmente, la renderización de todas las capas debería poder realizarse con una sola llamada, en vez de que otras clases intercalaran renderizaciones cuando lo consideraran necesario. Por fortuna existen dos fases claras a la hora de interactuar con los renderizadores basados en OpenGL. En la primera fase se introducen los valores que componen los cuatro vértices de un cuadrado. Cada vértice puede tener hasta nueve valores en el sistema actual: tres valores para la posición, cuatro para el color y dos para la coordenada de la textura. Pero esos valores introducidos en el renderizador sólo se dibujan cuando se le exige que lo haga. Eso facilita dibujar las capas en sucesión.


  • Por desgracia uno de los programas, el que genera imágenes, ha evidenciado que no todo el renderizado puede reducirse al concepto de capas. Para ello se le permite registrar “órdenes de dibujo”, funciones que se ejecutarán durante la fase de dibujo, aunque se desconozcan los detalles de los renderizadores utilizados.

La única otra mejora que se me ocurre ahora mismo es limitar los cambios en los datos de los vértices a cuando el mapa se desplace, pero en el futuro algunas de las casillas podrían estar animadas, y para sólo cambiar los datos de esas casillas implicaría crear estructuras nuevas y registrar esas coordenadas específicas. Demasiada complicación para lo que me solucionaría ahora mismo.


Map manipulation

Before programming any significant part of the mechanics that one day could form a game, from the beginning I knew that I should base everything on a three dimensional map inspired by the legendary Dwarf Fortress. One should be able to manipulate that map as well: from digging into the mountains to building enormous castles. For that I needed to build from scratch a reliable pathfinding system. That led me to realize I would need to reinforce the pathfinding system with a hierarchical one, as I’ve shown in previous articles. Now that the implemented system satisfies me for the most part, I still had to figure out everything that needed to change once the user replaced a tile (of the around 32 thousand I’m working with at the moment). When a tile gets replaced, its movement rules will likely change, and the pathfinding system needs to update itself without blocking the entire program.

Every tile has an associated region number it belongs to, and those numbers get referenced by the edges of every sector. Those edges are used to know whether you can exit from a sector in those directions, and the adjacent sectors reference the region numbers of the sector of origin as well. That means that after replacing a tile, the next pathfinding request needs to receive updated data regarding the involved regions and sectors. Fortunately it’s not necessary to regenerate the corresponding sectors and edges after every tile gets replaced, just before the next pathfinding request. So I can get away with changing dozens of tiles, and I only launch the code that regenerates the corresponding sectors and edges immediately before the next pathfinding request. Months ago I programmed a tasks scheduler that launches programmed tasks when a turn ends.

  1. Whenever any tile of a sector (16x16x8) changes, it needs to be regenerated, because any change in the region numbers could have invalidated the edges not only of that sector but of the adjacent ones.
  2. Every single edge of that sector needs to be regenerated.
  3. From the adjacent sectors I only needed to regenerate the opposite edges. For example, from the western sector I regenerate the eastern edge.

I already had programmed a regions visualized. The following video shows how the regions have changed after creating a few structures.

The tiles replaced involved around three sectors. The regenerated regions understand that the stairs and the inside of the buildings are reachable. The region centers have been moved appropriately.

The following videos show different examples I used to push the limits of the hierarchical pathfinding system. Thanks to one of them I figured a nasty bug in the code that recognized the western edges. It caused some agents to become unable to walk left from one tile to the next, even if they were on an open space in same z level.

Although I’ll have to write some upgrades, for example allowing two agents that block each other’s path to find an intermediate tile instead of just resetting the route, now I can move on to programming parts more specific to the game I wanted to make: the agents’ bodies, or the artificial intelligence that handles finding food, building stuff, etc. I hope the pathfinding system keeps behaving in the meantime.

Manipulación del mapa

Antes de programar alguna parte significativa de lo que algún día podría convertirse en un juego, desde el principio tuve claro que la base debería sustentarse en un mapa en tres dimensions, basado en el legendario Dwarf Fortress, que pudiera manipularse de todas las maneras imaginables: desde abrir minas en las montañas a construir castillos. Para ello necesitaba perfeccionar un sistema de búsqueda de ruta fiable. Eso me llevó a darme cuenta de que necesitaría reforzar la búsqueda de ruta mediante un sistema jerárquico, como he mostrado en artículos anteriores. Ahora que ese sistema me satisface en su mayor parte, quedaba determinar qué debía implementar para que tras reemplazar cualquier casilla en el mapa (de las 32 mil y pico actuales), el sistema de búsqueda de ruta se actualizase correctamente sin bloquear por completo el programa.

Cada casilla del mapa, en lo que respecta al sistema de búsqueda de ruta, lleva asociado el número de región al que pertenece, y ese número lo referencian tanto los edges o bordes de mapa de ese sector, necesarios para saber si se puede salir del sector en esa dirección hacia el contiguo, como los bordes opuestos de los sectores adyacentes. Eso significa que tras reemplazar una sola casilla, la siguiente petición de búsqueda de ruta necesita recibir las regiones y los sectores actualizados. Por fortuna no es necesario regenerar los sectores y bordes correspondientes tras cada reemplazo de casilla: sólo antes de la siguiente búsqueda de ruta. Por lo tanto, un número de indeterminado de casillas pueden cambiar, y sólo inmediatamente antes de que el sistema gestione la siguiente búsqueda de ruta regenerará los sectores y bordes correspondientes.

  1. Cuando cualquier casilla de un sector (16x16x16) cambia, es necesario regenerarlo, ya que cualquier actualización en la asignación de los números de región puede haber invalidado las referencias de los bordes.
  2. Es necesario regenerar todos los bordes de ese sector. Cualquiera de ellos puede hacer referencia a números de región erróneos.
  3. De los sectores adjacentes sólo es necesario regenerar los bordes opuestos. Por ejemplo, del sector occidental con respecto al sector original sólo es necesario regenerar el borde oriental.

Yo ya había programado un visualizador de regiones. Los cambios en las regiones tras incorporar algunos edificios se ven en el siguiente vídeo corto:

Los reemplazos mostrados involucraban al menos tres sectores. Las regiones regeneradas entienden que las escaleras y los interiores de los edificios son accesibles. Los centros de región se han desplazado adecuadamente.

Los siguientes vídeos muestran diferentes ejemplos que me ayudaron a reforzar el sistema. Gracias a uno de ellos descubrí un bug tremendo en el código que reconocía los bordes occidentales, que hacía que los agentes no pudieran, por ejemplo, andar hacia el oeste en algunas circunstancias, incluso en un pasillo sin impedimentos.

Aunque tendré que programar algunas mejoras, como por ejemplo que dos agentes que se topan por el camino mientras siguen una ruta se aparten a una casilla libre en vez de bloquearse mutuamente, ahora puedo pasar a programar partes más específicas de un juego: los cuerpos de los agentes, o la inteligencia artificial de comportamientos como la persecución, la búsqueda de comida, etc. Espero que el sistema de búsqueda de ruta siga comportándose entonces.

Hierarchical pathfinding

Hierarchical pathfinding implies dividing searches into a high level one, based on the region centers contained in the identified sectors, and a low level one, based on every tile in the map. Once the map has been sectorized and the regions identified, the artificial intelligence needed to change so it would recognize the difference between both pathfinding requests and their states, apart from the interactions between both.

I based the agents’ intelligence on behavior trees. To build the definitive tree, one that would recognize all the possible states, I had to write about ten unit tests. The final graph is the following:

Move_to_destination Behavior (1).jpg

However, the last time I programmed a behavior tree in my engine I failed to implement a NOT node, which inverts the result of its child. Writing it in it has doubled the amount of usable conditions and actions, making it trivial to implement, for example, the first “sentence” of the logic shown on the image: “if the agent has a destination but he hasn’t reached it, attempt to figure out if it has a low level route”. A few of the texts I’ve read about behavior trees warned about complicating their composition inventing nodes, because any behavior can be represented using sequences (nodes that return success if all of their children succeed), selectors/fallbacks (nodes that return success if any of their children succeed), decorators and actions. Condition nodes are a type of action node that makes a check.

The following video shows hierarchical pathfinding requests in a 64x64x8 map with agents that have different movement capabilities; some walk, others fly, others swim in shallow waters and others in deep waters. Every tile has information about whether an agent with specific movement capabilities can move straight through, upwards, downwards, straight up or straight down.

Although the agents reach their destination, in other maps I’ve found out that some tiles are unreachable for no apparent reason, or the agents choose erroneous region centers. Now that I have implemented saving and loading maps, I imagine I will be able to isolate those issues and solve them through unit testing.

(UPDATE): indeed, isolating failing maps in unit tests allowed me to solve the bugs I’ve found until now in the pathfinding system. A future article will show pathfinding through complicated maps that feature buildings.

Búsqueda de ruta jerárquica

Una búsqueda de ruta jerárquica implica dividir las búsquedas en una de alto nivel, basada en los centros de región de los sectores identificados, y otra en una búsqueda de bajo nivel, basada en cada casilla presente en el mapa. Una vez el mapa está ya sectorizado y sus regiones se han identificado, es necesario modificar la inteligencia artificial para que reconozca la diferencia entre ambas búsquedas de ruta y sus estados, aparte de las interacciones entre ambas.

He basado la inteligencia de los agentes en los árboles de comportamiento. Para componer el árbol final, uno que reconociera todos los posibles estados, he necesitado unas diez pruebas unitarias. El esquema final es el siguiente:

Move_to_destination Behavior (1).jpg

Por pura vagancia, la última vez que usé un árbol de comportamiento no había creado el tipo de nodo NOT, que niega el resultado de su hijo. Implementarlo ha multiplicado por dos la cantidad de condiciones y acciones a usar, haciendo trivial implementar, por ejemplo, la primera parte de la lógica: “si el agente tiene un destino pero no está en su destino, procede a intentar averiguar si tiene una ruta de bajo nivel”. Varios textos que he leído sobre los árboles de comportamiento advierten sobre complicar su composición inventándose nodos, porque cualquier comportamiento puede representarse mediante sequencias (nodos que devuelven éxito si todos sus hijos devuelven éxito), selectores (nodos que devuelven éxito si alguno de sus hijos devuelve éxito), decoradores y acciones. Las condiciones son en realidad un tipo de acción que sencillamente hace una comprobación.

El siguiente vídeo muestra búsquedas de ruta jerárquicas en un mapa de 64x64x8 con agentes que tienen diferentes capacidades de movimiento; unos andan, otros vuelan, otros nadan por aguas poco profundas y otros por aguas profundas.

Aunque los agentes alcanzan su destino, en otros mapas he encontrado que ciertas casillas resultan inaccesibles por ningún motivo que comprenda en este momento, o eligen un centro de región erróneo aunque no deberían. Ahora que he implementado guardar y cargar los mapas, imagino que podré aislar esos problemas y solucionarlos mediante pruebas unitarias.

Sectorizing a three dimensional map

Implementing pathfinding in a three dimensional map has clarified for me why so many games refuse to exploit all three dimensions. Even in the relatively small space of 64x64x8 tiles (32,768 in total) I’ve needed to stop some of the pathfinding requests after 300 tile checks, because they blocked the main thread.

To solve that issue, first I intended to use multiprocessing: I would send the pathfinding requests to the other processor cores, and I would let them return the results whenever they calculated them. Unfortunately, every pathfinding request needs to use the block of memory that contains pathfinding information about the 32,768 tiles (which include for each the neighboring reachable coordinates). The size comes up to about 8 MB, too much to scatter to the other cores without freezing the main thread. If just scattering some data needed for the pathfinding requests takes more time than executing them in the main core, I can’t choose that route.

One of the issues with pathfinding is that there seems to be no way to tell, at this level of abstraction, if the agent can reach a walkable destination tile; for example, what if that tile is beyond a ravine that blocks off that part of the map? To figure out if a route exists to that blocked off tile, the A* algorithm, on which pathfinding is based, will check literally thousands of tiles of the potential 32,768.

The most interesting solution I discovered was hierarchical pathfinding. It consists in dividing the map in sectors of a fixed size (they recommended 16 tiles in all dimensions), and inside that sector identifying the accessible regions. In my case the case gets more complicated, because I not only include the third dimension, but different movement capabilities as well. My agents walk, swim in shallow waters, in deep waters, or fly. The system doesn’t forbid an agent from featuring a combination of those capabilities: for example, an amphibious creature, or some sort of bird that also dives in the water.

Once the map is divided in sectors and regions, I needed to calculate the center of mass of each region, and those region centers are the ones used in the high level pathfinding process to figure out a route. Now, figuring out if a walkable tile is inaccessible takes looking up about ten to twenty region centers, instead of literally thousands of tiles. Once a route has been determined through the region centers, the low level route can get calculated from one of those region centers to the next, which also limits those pathfinding requests to about 20 tiles.

To make sure the programming sectorized any map properly (maps that get generated each time through the Perlin noise algorithm), I made a visualizer. The following video shows my first attempt to implement the sectorization, but I failed at identifying the regions properly, as I will explain later.

The video shows the regions colored according to the number they have been assigned. In every sector the regions start from 1, and the counter goes up for as many new regions as the process identifies. The crosses indicate the region centers. That apparently contiguous regions showed different colors should have alerted me to the fact that something was wrong. Although the created regions seemed reasonable for flying and swimming agents, the changes in elevation screwed with the process that identifies the walkable regions. Every time the elevation changed, a new region was created, something that makes no sense because walking agents can use the ramps to move up and down.

Fortunately I had already programmed the very complicated reachability checks to find a route from tile to tile. Each tile of the original pathfinding map includes information about its reachable neighbors. For every one of those lists, I converted the coordinates to the coordinate system used inside each sector (from 0 to 15 in the x and y dimensions, and from 0 to 7 in the z), and added each coordinate as an internal neighbor as long as that neighbor existed in the same sector.

The following video shows the result.

It shows clearly, particularly in the upper left corner of the map, how the sectorizing process has considered that the changes of elevation belonged to the same region. In the upper right there is an interesting case: a sector includes both the top of a mountain and the base of a cliff, but they are identified correctly as different regions because you can’t move from one to the other, at least through the inside of the sector.

Sectorizing a map to implement pathfinding at this level also implies discovering the edges of every sector, and whether they are open for traffic in every direction (which includes diagonals, and up and down). Although I programmed it in, painstakingly, the visualizer doesn’t show it.

Now I need to adapt the A* pathfinding algorithm so it will only consider the region centers when the system requests a high level route, and it will do something similar to the following:


Sectorización de un mapa en tres dimensiones

Implementar la búsqueda de ruta en un mapa en tres dimensiones ha evidenciado por qué muchos juegos se resisten a explotar las tres dimensiones. Incluso en un espacio relativamente pequeño de 64x64x8 (32.768 casillas), he necesitado paralizar algunas de las búsquedas después de unas 300 peticiones de casillas, porque bloqueaba demasiado el sistema.

Para solucionarlo, en un primer momento pretendí utilizar el multiproceso: enviaría las búsquedas de ruta al resto de núcleos del procesador y que me devolvieran el resultado cuando lo lograran. Por desgracia, cada búsqueda de ruta necesita usar el bloque de memoria del mapa con toda la información sobre las 32.768 casillas (que además incluyen para cada una las coordenadas vecinas y accesibles). El tamaño alcanza unos ocho megas, una cantidad de datos demasiado grande para dispersar por el resto de núcleos sin que paralizara el núcleo principal. Si sólo diseminar las peticiones de búsqueda de ruta a otros núcleos del procesador tarda más que ejecutarlos en el mismo procesador, eso invalida la opción.

Uno de los problemas principales es que la búsqueda de ruta no entiende que por mucho que el destino sea una casilla atravesable por un agente no implica que pueda llegar hasta ella. Por ejemplo, una casilla en la cima de una montaña pero rodeada de acantilados es accesible si ya empiezas en ella, pero no si falta una ruta hasta la cima, y averiguarlo puede implicar que el algoritmo A*, que busca la ruta, pruebe literalmente miles de casillas de las potenciales 32.768.

La solución más interesante que descubrí es la búsqueda de ruta jerárquica: consiste en dividir un mapa en sectores de cierto tamaño (recomendaban 16 casillas en todas las dimensiones), y dentro de cada sector identificar las regiones de casillas accesibles. En mi caso el asunto se complica porque no sólo incluyo tres dimensiones, sino diferentes tipos de movimiento. Mis agentes andan, nadan por aguas poco profundas, por aguas profundas, o por el aire. No hay además impedimentos a nivel programático para que pudieran hacer una combinación de esas cosas: por ejemplo, alguna criatura anfibia, o pájaros que se sumergieran en el agua. Una vez el mapa original está dividido en sectores y regiones, se calcula el centro de masa de cada región para determinar su centro, y serán esos centros de región los que se usarán para buscar una ruta en el mapa. Eso conseguirá que descubrir que no se puede acceder a una casilla aislada se reduzca a mirar quizá unos diez centros de región, en vez de literalmente miles de casillas. Además, una vez se ha determinado una ruta a través de los centros de región, la ruta en el mapa entero puede realizarse de centro de región en centro de región, lo que también limita esas búsquedas a una media de unas 16-20 casillas.

Para asegurar que la programación sectorizaba los mapas correctamente (mapas que además se generan cada vez mediante el algoritmo de ruido Perlin), me planteé programar un visualizador. El siguiente vídeo muestra el primer intento de implementar la sectorización, pero fallé en identificar las regiones correctamente, como explicaré después.

El vídeo muestra las regiones coloreadas en función del número que se les ha asignado; en cada sector las regiones empiezan desde 1, y el contador sube tanto como necesita. Las cruces indican los centros de región. Que regiones aparentemente contiguas aparecieran coloreadas de maneras diferentes habría debido avisarme de que algo funcionaba mal. Aunque las regiones creadas parecían razonables para los agentes voladores y nadadores, los cambios de elevación destrozaban la identificación de regiones para los agentes que andan. Cada vez que la elevación cambiaba se creaba una región nueva, algo que no tiene sentido, ya que los agentes podrían usar las rampas para desplazarse.

Por fortuna yo ya había programado esas comprobaciones complicadísimas de accesibilidad para buscar la ruta de casilla en casilla. Cada casilla del mapa original incluye la información sobre sus vecinos accesibles. De cada una de esas listas convertí las coordenadas al sistema de coordenadas internas de cada sector (de 0 a 15 en las dimensiones x e y, y de 0 a 7 en la z), y las añadí como vecinos internos siempre que el vecino existiera en el mismo sector.

El resultado se ve en el siguiente vídeo.

Muestra con claridad, particularmente en el extremo superior izquierdo del mapa, cómo la sectorización ha considerado que los cambios de elevación formaban parte de la misma región. Hay un caso interesante en el extremo superior derecho del mapa, donde en un sector que coincide con la cima de la montaña se han identificado dos regiones distintas, una en la cima y la otra en la tierra que rodea la base, porque un acantilado impide la ruta.

La sectorización de un mapa para programar una búsqueda de ruta a este nivel implica también reconocer las fronteras de un sector, y si están abiertas al tránsito en esa dirección. Aunque está programado, el visualizador del vídeo no lo muestra.

Ahora queda adaptar el algoritmo A* de búsqueda de ruta, ya programado, para que sólo considere los centros de región, y hará algo similar a lo siguiente:


Generation of images with a neuroevolutionary algorithm

Thanks to my recently adquired knowledge about how to display stuff on screen with OpenGL, I have implemented in Python an experiment that years ago I wrote in Java: an algorithm that generates images through the NEAT neuroevolutionary method invented in the mid 2000s. When I implemented it in Java, I had to write the NEAT method from zero by reading the scientific papers, because the Java libraries that existed back then didn’t inspire me much confidence. Fortunately, these days and in Python there are a couple solid modules that free me from that responsibility.

I’ll start showing a six minute video that shows some images generated through a few independent evolutionary processes:

A curious phenomenon, although logical, of the results of the programmed neuroevolution mimics what happens in natural evolution: when some pattern appears close to the beginning of the evolutionary run, and for some reason it benefits the genome, the pattern tends to persist for the rest of the evolution in some form or another (for example, the spinal cord).

The experiment works the following way: it generates a population of around 100 genomes that contains the nodes and connections of a neural network. When it gets activated, it will receive two inputs: the x coordinate divided by the width of the resolution the future image will have, and the y coordinate divided by the height of the future image. After the internal calculation, the neural network will produce the four components of a RGBA color: the value for red, for green, for blue, and for the transparency.

When I implemented this experiment for the first time in Java years ago, I programmed it so that each generation’s genome would produce a 32×32 pixels image, that it saved in the hard disk. I had to choose by hand which interested me and add them to a special folder, from which the program would sample to produce the next evolutionary run. However, even then I realized that I was sacrificing vital information so that seeded evolution would work entirely as expected: the genomes hold information about when its nodes and connections appeared for the first time, along with to what species the genomes belong. That information is vital when the genomes reproduce. This time I intended to solve the issue as soon as possible for the Python version, but I ended concluding that I shouldn’t only save the wanted genomes, but all the species involved in that run, along with the generation number. So it made sense to allow the user to save the entire evolutionary state at the chosen stage, all the genomes and the species they belong to. The equivalent to saving the game and reloading it.

The code draws on the screen a 32×32 version of the image each genome produces. In opposition to my previous implementation in Java, in which the genomes got promoted according to how novel they were, now the user has the responsibility to select the genomes he wants to promote. When he decides to move to the next generation, the algorithm scores the genomes in descending order of selection.

I’ve recorded 100 generations of the process in the following video:

The genomes start either completely disconnected or partially connected to the end nodes; I’ve configured it so a possibility of 10% exists so each connection is present at the beginning. That causes some genomes to output no color, or to come out completely black. However, even in the first generation different patterns are already present: vertical bars, diagonals with distorsions, and gradients. It takes just five generations for three genomes to connect with the green output node. However, curiously, it’s only in the 26th generation when a genome connects with the blue output node. A mix of both dominates the evolutionary run, and there’s a complete, or almost complete absence of connections to the red output.

The neural network that the genome converts to must be executed 32 * 32 times (1024 times) only to generate the texture that I’ll display on screen, so it wasn’t feasible during the recording of the video to generate the full images that I include separately in other videos, because the resolution of 1080×1080 implies executing the neural network for each of the selected genomes 1,166,400 times, which takes a while, and for now I haven’t managed to parallelize it (the overhead kills it).

Although the images generated during the recorded evolutionary run didn’t interest me that much, I’ve gathered some of them in the following video:

UPDATE: I’ve managed to parallelize both generating the pixels for all 100 pictures that get displayed on screen for each generation, as well as saving in the background the selected genomes in full. During the last few months I’ve searched for the right parallelization library written in Python, and after considering Pathos for a while, I’ve settled on the brilliant Dask (, which makes it very transparent.

This is all it takes to map the generation of the pixels for a population and gather the results:


For saving the full pictures, I love the “fire and forget” feature, that allows you to keep advancing the generations while the other cores handle saving the full pictures for the previously selected genomes:


From here I’ll move on to parallelize certain tasks of my main “experiment”, that game thing: running the behavior trees as well as launching the pathfinding queries.

Generación de imágenes mediante un algoritmo neuroevolutivo

Gracias a mi recientemente adquirido conocimiento sobre cómo mostrar cosas en la pantalla mediante OpenGL, he vuelto a implementar en Python un experimento que hace años implementé en Java: un algoritmo que genera imágenes mediante el método de neuroevolución NEAT inventado a mediados de los 2000s. Cuando lo implementé en Java, tuve que programar el método NEAT desde cero tirando de los artículos científicos, porque las librerías de Java existentes en ese momento no me inspiraban mucha confianza. Por fortuna hoy en día y en Python existen un par de paquetes muy sólidos que me libran de esa responsabilidad.

Empiezo enseñando un vídeo de seis minutos que muestra imágenes generadas a lo largo de varios procesos evolutivos independientes:

Un fenómeno curioso, aunque lógico, de los resultados de la neuroevolución programada se asemeja a lo que pasa en la natural: cuando algún patrón surge cerca del comienzo de la evolución, y por un motivo u otro beneficia al genoma, tiende a perpetuarse durante el resto de la evolución en diferentes formas (por ejemplo, la columna vertebral en los seres vivos).

El experimento funciona de la siguiente manera: se genera una población de unos 100 genomas que contienen los nodos y las conexiones de una red neural. Cuando se necesite activarla, se le pasarán dos valores: la coordenada x dividida entre la anchura de la resolución que la imagen tendrá, y la coordenada y dividida entre la altura de la resolución que la imagen tendrá. Tras el cálculo interno, la red neural produce los cuatro componentes de un color RGBA: el valor para el rojo, para el verde, para el azul, y para la transparencia.

Cuando implementé este experimento por primera vez en Java hace años, yo programé que cada genoma de cada generación produjera una imagen de 32 por 32 píxeles que guardaba en el disco duro. Yo tendría que elegir a mano cuáles me interesaran y añadirlos a otra carpeta, de los que el programa leería al iniciarse la siguiente vez, y sólo consideraría esos genomas elegidos para comenzar otra evolución. Sin embargo, aun entonces yo sabía que estaba sacrificando información vital para que la segunda evolución con genomas anteriores funcionara de la manera adecuada: los genomas guardan información sobre cuándo surgieron por primera vez sus nodos y conexiones, además de a qué especie pertenecen. Ambas informaciones son vitales cuando los genomas se reproducen. Por aquel entonces a mí no se me ocurría cómo implementarlo adecuadamente. En esta ocasión me planteé solucionarlo lo antes posible para la nueva versión en Python, pero acabé llegando a la conclusión de que no sólo habría que guardar los genomas queridos, sino también todas las especies y la generación a la que pertenecen, así que he optado por permitir que el usuario salve una generación entera, todos los genomas y las especies a los que pertenecen. Es el equivalente de salvar la partida y volver a cargarla.

Además, el código dibuja en la pantalla la imagen en 32×32 píxeles que cada genoma produce. Al revés que en mi pasada implementación en Java, en la que los genomas se promovían dependiendo de lo novedosos que fueran, ahora se le da la responsabilidad al usuario de seleccionar los genomas que quiere promover en la evolución. Cuando decida pasar a la siguiente generación, el algoritmo puntua de manera descendiente dependiendo del orden en el que el usuario ha seleccionado los genomas.

He grabado 100 generaciones de este proceso en el siguiente vídeo:

Los genomas empiezan o completamente desconectados o parcialmente conectados a los nodos de salida; lo he configurado para que exista una posibilidad del 10% de que cada conexión esté presente nada más empezar. Eso hace que algunos genomas no produzcan ningún color, o que salgan completamente negros. Sin embargo, en la primera generación ya se presentan patrones diferentes: barras verticales, diagonales con distorsiones, y gradientes. Sólo transcurren cinco generaciones hasta que tres genomas conectan con el nodo de salida verde. Sin embargo, de manera curiosa, es sólo en la generación 26 cuando un genoma conecta con el nodo de salida azul. Una mezcla de ambos acaba dominando la evolución, y faltan por entero, o casi, genomas que contemplen la salida roja.

Dado que la red neural que un genoma forma debe ejecutarse 32 * 32 veces (1024 veces) sólo para generar la textura que luego plasmo en la pantalla, no era factible generar durante la grabación las imágenes grandes que incluyo en los otros vídeos, ya que la resolución de 1080 por 1080 píxeles implica ejecutar la red neural de cada genoma 1.166.400 veces, lo que tarda un buen rato, y de momento no he conseguido paralelizarlo.

Aunque las imágenes generadas durante esa evolución no me han interesado demasiado, he recogido unas cuántas de ellas en el siguiente vídeo: