La hormiga de Langton
Introducción
La Hormiga de Langton es un autómata celular fascinante, debido a la simplicidad de sus reglas (solo tiene 2) y a que su universalidad quedó demostrada años más tarde, convirtiendo este experimento en una máquina de Turing bidimensional funcional.
Sobre el mundo de los autómatas celulares, el más conocido es el juego de la vida de John Conway, pero la hormiga de Langton me ha resultado muy llamativa ya que utiliza únicamente 2 reglas (en lugar de 4, como el juego de la vida) y da lugar a comportamientos simétricos, caóticos y emergentes. De forma simultánea.
Algoritmo
Imaginamos un tablero cuadriculado. Cada cuadrado del entramado se colorea o bien blanco o bien negro. Se identifica arbitrariamente un cuadrado como la "hormiga". La hormiga siempre está mirando en una de las cuatro direcciones cardinales y se mueve un cuadrado cada vez, de acuerdo con las siguientes reglas:
- Si está sobre un cuadrado blanco, cambia el color del cuadrado, gira noventa grados a la izquierda y avanza un cuadrado.
- Si está sobre un cuadrado negro, cambia el color del cuadrado, gira noventa grados a la derecha y avanza un cuadrado.
A simple vista, estas 2 reglas aparentemente opuestas, nos hacen pensar que la hormiga dibujará un patrón simétrico. En el momento que la ponemos a prueba se puede observar lo siguiente:
- Simplicidad: En los primeros 500 pasos, la hormiga crea un patrón sencillo con bastante simetría.
- Caos: Después aparece un patrón grande, irregular y caótico. Continua así hasta los 10000 pasos.
- Orden emergente: Finalmente la hormiga encuentra un "orden", creando una avenida que se extiende hasta el infinito.
Hormiga en orden emergente
Esta avenida es en realidad una suerte de atractor. Hay conjeturas que defienden que cualquier disposición inicial del tablero, hará que una hormiga termine generando ese atractor en un tiempo dado. A continuación os dejo una animación mostrando los primeros 2000 pasos de la hormiga:
Extensión en múltiples colores
Greg Turk y Jim Propp (computación gráfica y matemático) propusieron que las reglas de la versión clásica fueran generalizadas para permitir que los cuadrados tomen más de dos colores, en donde cada color está asociado a un sentido de giro (90° a la derecha 'R' o 90° a la izquierda 'L'). Así, por ejemplo, la hormiga "RRLL" se mueve en una rejilla cuyas celdas se alternan entre 4 colores, los dos primeros indican un giro a la derecha y los dos siguientes un giro a la izquierda, mientras que la versión clásica sería bajo esta nomenclatura la hormiga "RL".
La introducción de nuevos colores da lugar a comportamientos distintos a los observados en la versión clásica, por ejemplo, algunas hormigas como la "RRLL" genera siempre patrones simétricos, mientras que otras, como la hormiga "RLR" crece de forma caótica. Os dejo ejemplos de hormigas conocidos que generan patrones curiosos:
Fuente: wikipedia
Proyecto en Godot
Simulador de hormigas de Langton
Debido a la simplicidad de las 2 reglas, es muy sencillo llevar a cabo un simulador de hormigas. En mi caso he desarrollado uno en Godot, con la implementación de los colores, diferentes patrones y la posibilidad de generar hormigas random o custom.
Os dejo el código fuente por aquí: https://github.com/aikoncwd/langton-ant
Espero que os guste! Si encontráis algún patrón que genere una imagen curiosa, compartidlo en el hilo 
