Tag: Dwarf Fortress

Map manipulation

On By Jon UreñaIn Inteligencia artificial, ProgramaciónLeave a comment

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.

Implementation of pathfinding with Z levels

On By Jon UreñaIn Inteligencia artificial, ProgramaciónLeave a comment

The following video shows an actor moving through the different levels of depth of a simple map, and then going for a while to random coordinates on the first level:

Although the actor reaches the objective, for now I haven’t managed to prevent that in two particular moments the actor decides to go through the roof as part of his route, although I had modified the code so it wouldn’t allow him to do so, at least in theory. But it’s a minor problem for what I intended implementing the pathfinding: that when I programmed new experiments in which the user moved his character, around him other actors would find their way and act according to their AI.

Movement in three dimensions tends to divide these kinds of games. Dwarf Fortress is famous in part for how it handles the different layers, allowing the user to strike the earth for a couple dozen levels to build his fortress, or raise it several levels above sea level if he wants to. On the other hand, Rimworld, programmed with Unity, sacrifices that verticality to offer better graphics and effects and a complexity limited in comparison. I was convinced that simple sprites were enough in exchange of a complex simulation and an artificial intelligence that would, hopefully, surprise often. And behave reasonably to begin with.

I programmed this experiment a few days ago, but I recall spending a couple hours trying to solve a problem. When the actor had to find his route to the inside of the house, which should force him to pass through the doorway, the actor went straight to the western wall of the house, his image passed through and stopped in the final coordinates. I was making sure that the pathfinding algorithm identified the wall as impassable, but the actor was still going through it. In the end, after a lot of testing, I revised my assumptions. Were the actor sprites being displayed according to the level they were in? Turns out I had let that for later, and the pathfinding was doing its job: instead of going through the wall, the actor jumped it and “crashed” through the roof to reach his objective. The function that had to draw the actor showed him indistinctly going through a wall that in reality existed a level below.

After that, to make sure the pathfinding algorithm worked better in three dimensions, I had to add more booleans to the tiles. Apart from whether or not they blocked the straight path, they should mark whether they blocked going upwards or downwards (days later I wrote a couple of booleans more: whether the tile blocked the path straight up and down). Otherwise the actor would go through several layers of underground tiles to reach a basement. The changes worked for the most part, shown in the video where the actor goes down the stairs to reach the basement.

To draw the different layers of depth I paid attention to how Dwarf Fortress did it. When the user went up a z level, if any tile was defined as “empty”, the program should draw the closest “real” tile below, but tinted blue to show the user that he was seeing tiles belonging to another z level. On my first try, the code copied each of those sprites and modified its RGB component according to how close they were to the current z level. That’s shown in the video. However, copying all those sprites every frame hurt the framerate too much. A couple of days later I opted for something simpler and that even works better: I draw the first “real” tile normally, but over it I draw translucent tiles for each z level in between. The translucent tiles stack up, darkening the tile below.

This experiment worked for what I intended, so I moved on to new ones.

Implementación de búsqueda de ruta con niveles de profundidad

On By Jon UreñaIn Inteligencia artificial, ProgramaciónLeave a comment

El siguiente vídeo muestra a un actor moviéndose por los diferentes niveles de profundidad de un mapa simple, y luego dirigiéndose por un rato a puntos aleatorios del primer nivel:

Aunque el actor alcanza su objetivo, no conseguí de momento evitar que en dos puntos concretos decidiera atravesar el techo como parte de su ruta, a pesar de que yo había modificado el código para que en teoría lo evitara. Pero se trata de un problema menor para lo que pretendía implementando la búsqueda de ruta: que en otros experimentos en el que el usuario moviera a su personaje, a su alrededor hubiera actores moviéndose y actuando en base a su inteligencia artificial.

El movimiento en tres dimensiones suele dividir este tipo de juegos. Dwarf Fortress es famoso en parte por cómo gestiona las diferentes capas, permitiendo profundizar en la tierra durante un par de decenas de niveles para construir tu fortaleza, o elevándola varios niveles sobre el nivel del mar si se quiere. En contra, Rimworld, programado con Unity, sacrifica esa verticalidad para ofrecer mejores gráficos y una complejidad muy limitada en comparación con Dwarf Fortress. Yo tenía claro que los sprites en dos dimensiones bastaban a cambio de ofrecer un juego con una simulación compleja y una inteligencia artificial que, con suerte, sorprenda a menudo. Y que actúe de una manera razonable en un primer lugar.

Programé este experimento hace unos pocos días, pero recuerdo que dediqué un par de horas intentando solucionar un problema. Cuando el actor debía encontrar su ruta hasta el interior de la casa, lo que debería obligarlo a pasar por la puerta, dado que se trata de una única entrada despejada, el actor se dirigía al muro occidental de la casa, su imagen pasaba a través del muro y acababa la ruta en su objetivo. Yo me aseguraba de que el algoritmo de búsqueda de ruta identificaba el muro como impasable, pero a pesar de ello lo pasaba. Al final, después de mucho probar, revisé lo que yo había asumido sobre la escena: ¿de verdad los gráficos dibujaban al actor en el nivel de altitud en el que está de verdad? Resultó que había dejado eso para otro momento, y la búsqueda de ruta hacía su trabajo: en vez de atravesar el muro, lo subía y luego atravesaba el techo para llegar a su objetivo. La función que dibuja la escena reflejaba al actor de manera indistinta atravesando el muro que en realidad se encontraba en un nivel por debajo.

A raíz de eso, y de manera previsible, para que el algoritmo de búsqueda de ruta funcionara mejor en tres dimensiones tuve que añadir otros booleanos a cada terreno. Aparte de si bloqueaban el paso a través, debían marcar si bloqueaban subir a un nivel superior, para que a un actor no le diera por elevarse por el cielo, y también debían marcar si bloqueaban lo contrario, bajar a un nivel inferior, para que no atravesaran varias capas de tierra subterránea para llegar a un sótano. La modificación acabó funcionando en su mayor parte, lo que se ve en el vídeo cuando el actor baja por la escalera para alcanzar el sótano.

Para dibujar las diferentes capas de altitud me fijé en cómo lo hacía Dwarf Fortress. Cuando el usuario sube la vista a un nivel superior, si alguna casilla está vacía, el programa debería dibujar lo que está por debajo, pero tintado de otra manera para que no le parezca al usuario que está viendo elementos en la misma dimensión. En un primer lugar el código copiaba cada una de esas casillas inferiores y las tintaba con más o menos azul en función de lo lejos del nivel actual que se encontraban. Eso se ve en el vídeo. Sin embargo, reducía los fotogramas por segundo de una manera bestial. Un par de días después opté por algo más simple y que además funciona mejor: dibujo la casilla original de manera normal, pero luego voy dibujando casillas traslúcidas por cada nivel de altitud que lo separe de la vista. Las transparencias se acumulan y oscurecen la casilla inferior.

El algoritmo me sirve de momento como ha quedado, así que paso a otros experimentos.

Simple experiment about neuroevolution (NEAT-Python)

On By Jon UreñaIn Inteligencia artificial, ProgramaciónLeave a comment

The next video, that shows about 166 generations of the evolving neural networks, clarifies the situation enough so I can explain myself later:

I’m interested in programming above all because of artificial intelligence and videogames. Although I consider myself a writer first, another one of my dreams, shared with many programmers of modern videogames, consists on making a game with the best of Dwarf Fortress, but with the more immediate and exploratory aspects of games like Cataclysm: Dark Days Ahead. Rimworld’s ambience comes somewhat close to what I would want, but I’d prefer a complexity closer to that of Dwarf Fortress, with most of its elements depending on procedural generation, and supported with an artificial intelligence based on neural networks that would offer constants surprises.

To prove to myself that I could program the visual aspect of a similar game and set the basis for developing the intelligence of its actors, I intended to develop the prototype shown in the video. For now I’ve failed in generating the behaviors that I wanted for the involved neural networks, but having reached this point allows me to progress quickly.

For those who don’t know it, and according to the story as I remember it, neural networks were considered the Holy Grail of artificial intelligence in the eighties and early nineties, but they crashed against an unsolvable problem: no mathematical model could determine which was the best architecture to use for a network to solve a particular problem. They depended on trial and error, and eventually neural networks ended up relegated to obscurity for the most theory-minded and a minority of dedicated programmers.

But in 2002, Kenneth Stanley, from Texas university in Austin, wrote the following paper:

Evolving Neural Networks through Augmenting Topologies

The paper, and those that followed it, revealed the way to solve the main issue with neural networks: instead of designing its architecture, it should evolve through a genetic algorithm. A significant part of the revolution in artificial intelligence we are living in has its origin in papers like this one and others from that era.

The prototype I intended to build had to implement the the following elements:

  • The visual aspect of games like Dwarf Fortress (with tilesets) and Cataclysm: Dark Days Ahead.
  • A reusable architecture that would allow adding new features and programming other experiments easily
  • It would implement the neuroevolution using some library based on NEAT
  • The neural networks should evolve a behavior close to what I intended

Visual representation of a neural network:

neuralnetwork.jpeg

A neuroevolution tends to begin with only the input and output layers set. The inputs represent the sensorial information that a neural network would process, and the outputs the answers that the internal architecture generates through the interaction of all the nodes.

The success of this method depends mainly on the following factors: the inputs must feed the network with the relevant information that could end up producing the intended behavior, and the inputs should be normalized (should be scaled to a range of 0.0 to 1.0). For my experiment I settled on the following inputs:

  1. The normalized value of each turtle’s health
  2. A value of 1.0 if the animal detects a fruit close enough in the northwest, but 0.0 otherwise.
  3. Same but in the north
  4. Same but in the northeast
  5. Same but in the east
  6. Same but in the southeast
  7. Same but in the south
  8. Same but in the southwest
  9. Same but in the west

I decided that each actor would act depending on which output had produced the highest value, and according to its index, the actor would walk a tile over to one of the cardinal directions or it would stay in place.

I chose those inputs because I considered that an actor should learn to link his health deteriorating quickly to the need to search for food, and the actor should detect the fruits instead of stumbling in the dark.

Apart from the architecture of the network, the other key is the function that determines each neural network’s fitness. The fitness is a mathematical measure of how close the network has gotten to the goal. Usually it consists in reaching a high number. In my case I settled for the following function:

((Health ^ 2) + (AmountOfFruitsEaten * 50) + (TurnsSpentNearFood * 2)

I wanted to reward the actors that kept their health as high as possible, and as secundary measures I wanted to suggest that they should look for food and keep close. I’m terrible at math and I’m doing this alone, so suggestions are welcome.

For now the experiment hasn’t produced the behaviors I intended. I’ll leave it some night so it can reach a thousand or thousands of generations, but at least I’m happy that it’s built upon a platform that could allow me to move towards programming something close to an interesting videogame or simulation.

UPDATE: I’ve changed some aspects of the experiments and gotten results close enough to what I intended. I’ll write another post showing them.

Experimento simple sobre la neuroevolución (NEAT-Python)

On By Jon UreñaIn Inteligencia artificial, ProgramaciónLeave a comment

El siguiente vídeo, que recoge unas 166 generaciones de las redes neurales que evolucionaban, ilustra la situación lo suficiente como para que me explique después:

Me interesa la programación sobre todo por la inteligencia artificial y los videojuegos. Aunque me considero primero un escritor, otro de mis sueños, compartido con muchísimos programadores de videojuegos modernos, era crear un juego que recogiera lo mejor de Dwarf Fortress, pero con los aspectos más inmediatos y exploratorios de juegos como Cataclysm: Dark Days Ahead. La ambientación de Rimworld recoge parte de la idea, pero yo querría una complejidad mucho más cercana a Dwarf Fortress, con la mayor cantidad de elementos basados en la generación procedural, y una inteligencia artificial fundada en las redes neurales que ofreciera sorpresas constantes.

Para probar a mí mismo que podría programar el aspecto visual de un juego semejante y establecer la base para desarrollar las inteligencias de sus actores, pretendí desarrollar el prototipo que se muestra en el vídeo. De momento he fracasado en generar los comportamientos que pretendía para las redes neurales involucradas, pero haber llegado hasta este punto me permite progresar deprisa.

Para quienes lo desconozcan, y de acuerdo con la historia tal como la recuerdo, las redes neurales se consideraban el Santo Grial de la inteligencia artificial en los años ochenta y principios de los noventa, pero se toparon con un problema insalvable entonces: no existía ningún modelo matemático que determinara cuál era la mejor arquitectura de cada red neural para resolver los problemas concretos. Que dependieran del ensayo y error acabó relegando las redes neurales a los ámbitos más teóricos o a una minoría de programadores dedicados.

Pero en 2002, Kenneth Stanley, de la universidad de Texas en Austin, sacó este artículo académico:

Evolving Neural Networks through Augmenting Topologies

El artículo, y los que se sucedieron, revelaron la manera de solventar el problema principal de las redes neurales: en vez de diseñar su arquitectura, debería evolucionar mediante un algoritmo genético. Una parte significativa de la revolución en inteligencia artificial que vivimos durante estos días tiene su origen en este artículo y en otros de esa época.

El prototipo que yo pretendía construir debía implementar los siguientes elementos:

  • El aspecto visual de juegos como Dwarf Fortress (con tilesets) y Cataclysm: Dark Days Ahead
  • Una arquitectura reusable para que tanto añadir nuevos elementos como programar experimentos adicionales fuera razonablemente fácil
  • Implementar la neuroevolución con alguna librería de NEAT
  • Que las redes neurales evolucionaran un comportamiento cercano a lo que quería

Representación visual de una red neural:

neuralnetwork.jpeg

La neuroevolución suele empezar sólo con la capa de inputs y la de outputs. Los inputs representan la información sensorial que una red neural recogería, y el output la respuesta que la arquitectura interna genera mediante la interacción de todos los nodos.

Con respecto a la arquitectura, que una neuroevolución funcione bien depende en gran medida de los siguientes factores: que los inputs recojan la información relevante para generar los comportamientos queridos y que estén bien normalizados (reducirlos proporcionalmente a rangos como de 0.0 a 1.0). Para mi experimento decidí los siguientes inputs:

  1. El valor normalizado de la salud de esa tortuga.
  2. Valor de 1.0 si ve una fruta en el noroeste (en las cuatro casillas más cercanas), 0.0 en caso contrario
  3. Lo mismo pero en el norte
  4. Lo mismo pero en el noreste
  5. Lo mismo pero en el este
  6. Lo mismo pero en el sureste
  7. Lo mismo pero en el sur
  8. Lo mismo pero en el suroeste
  9. Lo mismo pero en el oeste

Decidí que cada actor actuaría en función de qué output había recibido el valor más alto, y dependiendo de cuál se tratara, avanzaría una casilla en una dirección cardinal o se quedaría quieto.

Opté por esos inputs porque consideré que un actor debería aprender a relacionar que su salud se deterioraba rápidamente con la necesidad de buscar comida, y necesitaba poder detectar las frutas para que topar con ellas no fuera una coincidencia.

Aparte de la arquitectura de la red neural, la otra pieza fundamental es la función que determina el fitness de cada red neural. El fitness consiste en un valor que calcula matemáticamente cuánto se ha acercado a cumplir la meta. Por lo general suele consistir en intentar alcanzar un valor alto. En mi caso me decidí por la siguiente función:

((Salud) ^ 2) + (CantidadDeFrutasComidas * 50) + (TurnosPasadosCercaDeFruta * 2)

Quería premiar a los actores que mantuvieran la salud lo más llena posible, pero también pretendía sugerir que debían buscar comida activamente y no alejarse demasiado de ella. Soy pésimo con las matemáticas y programo solo, así que se admiten sugerencias.

De momento el experimento no ha sacado los comportamientos que quería. Lo dejaré alguna noche para que cumpla mil o miles de generaciones, pero al menos me alegra que se sostenga sobre una plataforma que me permitirá avanzar hacia programar algo cercano a un videojuego interesante.