Exploración y análisis de rendimiento y extensibilidad de diferentes implementaciones de simuladores de partículas

Trabajo de Fin de Grado Grado en Desarrollo de Videojuegos Exploración y análisis de rendimiento y extensibilidad de diferentes implementaciones de simuladores de partículas Exploration and analysis of performance and extensibility of different implementations of particle simulators. Universidad Complutense de Madrid Alumnos Nicolás Rosa Caballero Jonathan Andrade Gordillo Dirección Pedro Pablo Gómez Martin 7 de mayo de 2024 1 Agradecimientos Nicolás Quiero dar las gracias a mis padres, por su paciencia y comprensión cuando estaba agobiado, y a mi hermano, por su apoyo y ánimos. A mis amigos, por su apoyo y por estar siempre ahí cuando los necesito. A mi compañero de proyecto, por su colaboración y esfuerzo. A mi tutor, por su ayuda y orientación. A todos ellos, gracias. Jonathan Quiero dar las gracias, de igual manera, a mis padres por su incondicional apoyo, a mis amigos, por estar ahí para lo bueno y lo malo, a Marta, por haberme dado fuerzas incluso cuando no las tenía ella, a mi compañero de proyecto por ser una inspiración como desarrollador de software y por su gran trabajo y, por último y no menos importante, a mi tutor por su orientación y por todas los momentos y reuniones que hemos tenido durante el TFG y durante la carrera. 2 Resumen Los simuladores de arena, subgénero de autómatas celulares, han experimentado un resurgimiento en popularidad recientemente. Sin embargo, hemos identificado un obstáculo significativo que dificulta su adopción más generalizada tanto entre usuarios como desarrolladores, y este es la escasez de antecedentes o ejemplos disponibles. Por lo tanto, el objetivo de este proyecto es investigar diversas implementaciones de estos simuladores, evaluando sus ventajas e inconvenientes, así como su capacidad para ser ampliados por cualquier usuario, con el fin de aumentar la visibilidad y comprensión de este subgénero. Para lograr este objetivo, el proyecto examinará varias implementaciones, tanto en términos de su ejecución en la CPU como de una versión que ejecute la lógica en la GPU. Además, se llevará a cabo un estudio con usuarios reales para identificar posibles problemas con las implementaciones y evaluar el interés general en el proyecto. Los resultados de estos análisis se utilizarán para extraer conclusiones y proponer posibles mejoras para el proyecto. Palabras clave • Simuladores de arena • Automatas celulares • Programación paralela • Multihilo • GPU • Lua • Rust • WebAssembly • Blockly • Compute shader 3 Abstract Sand simulators, a subgenre of cellular automata, have experienced a resurgence in popularity in recent years.However, we have identified a significant barrier that hinders its broader adoption among both users and developers, and this is the scarcity of background or available examples. Therefore, the aim of this project is to investigate various implementations of these simulators, evaluating their advantages and disadvantages, as well as their ability to be extended by any user, in order to increase the visibility and understanding of this subgenre. To achieve this goal, the project will examine several implementations, both in terms of their execution on the CPU and a version that runs the logic on the GPU. Additionally, a study will be conducted with real users to identify potential issues with the implementations and assess the overall interest in the project. The results of these analyses will be used to draw conclusions and propose possible improvements for the project. Key Words • Sand simulators • Cellular automata • Parallel programming • Multithreading • GPU • Lua • Rust • WebAssembly • Blockly • Compute shader 4 Índice 1. Introducción ........................................................................................................................ 7 1.1. Motivación ................................................................................................................... 7 1.2. Objetivos ...................................................................................................................... 7 1.3. Plan de trabajo ............................................................................................................ 8 1.4. Enlaces de interés ......................................................................................................... 9 1. Introduction ...................................................................................................................... 10 1.1. Motivation .................................................................................................................. 10 1.2. Objectives ................................................................................................................... 10 1.3. Work plan ................................................................................................................... 10 1.4. Relevant links ............................................................................................................. 11 2. Autómatas celulares y simuladores de arena ..................................................................... 12 2.1. Autómatas celulares ................................................................................................... 12 2.1.1. Historia ............................................................................................................. 13 2.1.2. Ejemplos ........................................................................................................... 14 2.1.2.1. Juego de la vida ................................................................................... 14 2.1.2.2. Autómatas de Wolfram ........................................................................ 16 2.1.2.3. Hormiga de Langton ............................................................................. 17 2.1.2.4. Autómata de Contacto ......................................................................... 18 2.1.2.5. Autómata de Greenberg-Hastings ........................................................ 18 2.2. Simuladores de arena .................................................................................................. 19 2.2.1. Introducción ...................................................................................................... 19 2.2.2. Simuladores de arena dentro de los videojuegos ............................................... 20 3. Programación paralela ...................................................................................................... 22 3.1. Programación paralela en GPU .................................................................................. 22 3.1.1. Hardware .......................................................................................................... 23 3.1.2. Software ............................................................................................................ 25 3.2. Programación paralela en CPU .................................................................................. 26 4. Estrategias para definir comportamiento en motores de videojuegos ................................ 28 4.1. Ficheros de definición de datos ................................................................................... 28 4.2. Librerías dinámicas .................................................................................................... 29 4.3. Lenguajes de scripting ................................................................................................ 30 4.4. Blockly ....................................................................................................................... 31 5. Simuladores de arena en CPU ........................................................................................... 33 5.1. Generalidades ............................................................................................................. 33 5.2. Simulador en C++ ..................................................................................................... 33 5.3. Simulador en Lua con LÖVE ..................................................................................... 34 5.4. Simulador en la web ................................................................................................... 37 6. Simulador de arena en GPU ............................................................................................. 40 7. Comparación y pruebas ..................................................................................................... 42 7.1. Comparación de rendimiento ...................................................................................... 42 7.2. Comparación de usabilidad ........................................................................................ 43 8. Conclusiones y trabajo futuro ........................................................................................... 48 8. Conclusions and future work ............................................................................................. 49 5 9. Contribuciones .................................................................................................................. 50 9.1. Nicolás Rosa Caballero ............................................................................................... 50 9.2. Jonathan Andrade Gordillo ........................................................................................ 51 Bibliografía ............................................................................................................................ 53 Índice de Figuras Figura1: Ejemplo de autómata celular sencillo .................................................................... 13 Figura2: Ejemplo del Juego de la Vida ................................................................................ 15 Figura3: Estructuras estáticas en el juego de la vida ........................................................... 15 Figura4: Blinker, estructura oscilatoria del juego de la vida ................................................ 15 Figura5: Planeador, estructura moviente del juego de la vida ............................................. 15 Figura6: Ejemplo autómata de Wolfram .............................................................................. 16 Figura7: Ejemplo simple de la hormiga de Langton ............................................................ 17 Figura8: Ejemplo completo de la hormiga de Langton ........................................................ 18 Figura9: Ejemplo de autómata de contacto determinista .................................................... 18 Figura10: Ejemplo de simulador de arena ............................................................................ 20 Figura11: Ejemplo de simulador de arena, diferente orden .................................................. 20 Figura12: Imagen gameplay de Noita ................................................................................. 21 Figura13: Comparativa arquitectura de un chip de CPU y de GPU [1] ............................. 24 Figura14: Streaming Multiprocessor [1] .............................................................................. 25 Figura15: Jerarquía de ejecución [2] ................................................................................... 26 Figura16: estructura básica de Blockly ............................................................................... 32 Figura17: Interacción entre partículas en el simulador de C++ .......................................... 34 Figura18: Patrón de ajedrez de actualización ...................................................................... 35 Figura19: Problema de multithreading ................................................................................ 36 Figura20: Diferencia entre variar y no el orden de actualización al procesar partículas ...... 37 Figura21: Interfaz de la simulación en la web ..................................................................... 38 Figura22: Artefactos visuales ............................................................................................... 40 Figura23: Ejemplo problema movimiento diagonal .............................................................. 41 Figura24: Resultados de las pruebas de rendimiento con GPU ........................................... 42 Figura25: Resultados de las pruebas de rendimiento con GPU ........................................... 43 Figura26: Resultados de las pruebas con usuarios para la prueba de Lua .......................... 45 Figura27: Resultados de las pruebas con usuarios .............................................................. 46 6 1. Introducción 1.1. Motivación Los simuladores de arena fueron un subgénero emergente durante la década de los noventa, y continuaron siendo populares hasta principios de los años 2000. Durante ese tiempo, surgieron muchos programas y juegos que permitían a la gente interactuar con mundos virtuales llenos de partículas simuladas. Esto atrajo tanto a amantes de la simulación como a desarrolladores de videojuegos. Sin embargo, tras un período de relativa tranquilidad, estamos presenciando un nuevo auge del género de la mano de videojuegos como Noita o simuladores sandbox como Sandspiel. Este proyecto nace del deseo de sumergirnos en el mundo de los simuladores de arena. Queremos explorar sus diferentes aspectos y características así como entender mejor las ventajas y desventajas de diferentes enfoques de desarrollo de cara al usuario, para así poder contribuir a su evolución y expansión, ya que consideremos que es un subgénero que puede dar muy buenas experiencias de juego y de uso. En resumen, queremos entender y ayudar a mejorar los simuladores de arena para hacerlos más útiles y efectivos para los usuarios. 1.2. Objetivos El principal objetivo de este TFG es estudiar el comportamiento y aprendizaje de usuarios haciendo uso de diferentes implementaciones de simuladores de arena. Se valorará la funcionalidad de cada implementación haciendo uso de los siguientes parámetros: • Comparación de rendimiento: se compararán bajo las mismas condiciones, tanto a nivel de hardware como en uso de partículas midiendo el rendimiento final conseguido. Este rendimiento se comparará haciendo uso de razón nº partículas / frames por segundo conseguidos. Idealmente se averiguará la mayor cantidad de partículas que cada simulador puede soportar manteniendo 60 fps. • Comparación de usabilidad: se estudiará el comportamiento de un grupo de usuarios para valorar la facilidad de uso y de entendimiento de sistemas de ampliación de los sistemas que permitan expansión por parte del usuario. Se valorará la rapidez para realizar un set de tareas asi como los posibles desentendimientos que puedan tener a la hora de usar el sistema. Con estos análisis, se pretende explorar las características que contribuyen a una experiencia de usuario óptima en un simulador de arena, tanto en términos de facilidad de uso como de rendimiento esperado por parte del sistema. Al comprender mejor estas características, se podrán identificar áreas de mejora y desarrollar recomendaciones para optimizar la experiencia general del usuario con los simuladores de arena. Nuestro objetivo es encontrar un balance entre rendimiento y facilidad de extensión que proporcione tanto un entorno lúdico a usuarios casuales como una base sólida de desarrollo para desarrolladores interesados en los simuladores de arena. 7 1.3. Plan de trabajo La metodología de trabajo a usar será una variante de scrum ajustada a nuestras necesidades. Se elaborará un tablero de tareas en el que se reflejarán las tareas a realizar, el estado de cada tarea y el tiempo estimado para su realización. No habrá reuniones diarias pero se fijarán tareas a realizar cada semana, así como reuniones semanales para revisar el estado del proyecto y ajustar el tablero de tareas en consecuencia. Por otro lado, se planean reuniones cada dos semanas con el tutor para revisar el estado del proyecto y recibir feedback sobre el trabajo realizado, así como orientación al respecto de las tareas a realizar en el futuro. Respecto al trabajo, lo primero será realizar una investigación preliminar sobre los conceptos fundamentales de los autómatas celulares y los simuladores de arena, así como de sistemas ya existentes para entender cómo se han abordado problemas en el pasado. Se espera que esta investigación dure aproximadamente dos meses. Tras esto se planea la realización de 4 implementaciones: • Simulación nativa base: Esta será la simulación usada de base para comparar las demás. Debe ser eficiente y sentar las bases de como se realiza el procesado de partículas. Esta implementación será difícil de ampliar debido a esto. Se espera realizar esta implementación en C o C++ debido a la familiaridad con el lenguaje. Se espera que esta implementación sea realizada entre un mes y un mes y medio. • Simulación en GPU: Esta implementación se realizará en un lenguaje de programación que permita la ejecución de código en GPU, como CUDA u OpenCL. El objetivo de esta implementación es explorar la viabilidad de realizar la simulación de partículas en GPU, así como comparar el rendimiento con las demás implementaciones. Se espera que esta implementación también sea difícil de ampliar. Se espera realizar esta implementación en un mes. • Simulación nativa ampliada con un lenguaje de script: Será necesario investigar y elegir un lenguaje de script que permita la ampliación de la simulación base de manera sencilla manteniendo el mayor rendimiento posible. Se espera realizar esta implementación entre uno y dos meses. • Simulación accesible mediante lenguaje de programación visual: Se investigarán librerías y frameworks que permitan definir código o datos mediante programación visual. Se espera que esta implementación sea la más sencilla de ampliar y la más accesible para usuarios no técnicos. Se investigará la posibilidad de ejecutar esta simulación en la web para mayor accesibilidad. Se espera realizar esta implementación entre uno y dos meses. Se considera la posibilidad de que se realicen más simuladores si la investigación da a conocer una posibilidad alternativa que aporte valor a la comparativa. Tras realizar las distintas implementaciones, se realizarán pruebas de usuario para comparar los resultados obtenidos por cada una de ellas. Se analizarán los datos obtenidos y se compararán los resultados para extraer conclusiones sobre las ventajas y desventajas de cada implementación. Se espera realizar estas pruebas en un periodo de dos a tres semanas. 8 1.4. Enlaces de interés Repositorio del proyecto: https://github.com/Nrosa01/TFG-2023-2024-UCM Simulación base en C++: https://youtu.be/Z-1gW8dN7lM Simulación en GPU: https://youtu.be/XyaOdjyOXFU Simulación con Lua: https://youtu.be/ZlvuIUjA7Ug Simulación web con Blockly: https://youtu.be/obA7wZbHb9M 9 El Juego de la Vida ha sido objeto de considerable estudio en el campo de la teoría de la complejidad. Ha demostrado ser un modelo útil para explorar conceptos como la autoorganización, la emergencia de la complejidad en sistemas dinámicos, y la computación universal (la capacidad de simular una máquina de Turing) [4], [3]. A pesar de su aparente simplicidad, el Juego de la Vida esconde una riqueza de comportamientos complejos y sorprendentes, y continúa siendo un área activa de investigación y experimentación. 2.1.2.2. Autómatas de Wolfram Los Autómatas de Wolfram [5], ideados por el físico y matemático Stephen Wolfram, son un conjunto de reglas que rigen el comportamiento de autómatas celulares unidimensionales con estados binarios. Estos autómatas consisten en una línea de celdas, cada una de las cuales puede estar en uno de dos estados: 0 o 1. Cada regla en el conjunto de autómatas de Wolfram determina cómo cambia el estado de una celda en función de su estado actual y los estados de sus vecinos inmediatos (la celda a la izquierda y la celda a la derecha). Dado que cada celda y sus dos vecinos pueden estar en uno de dos estados, hay 23= 8 configuraciones posibles para una celda y sus vecinos. Cada regla se puede representar como un número binario de 8 bits, donde cada bit corresponde a una de las 8 configuraciones posibles de una celda y sus vecinos. Por lo tanto, hay 28 = 256 reglas posibles, numeradas del 0 al 255. Aunque los autómatas de Wolfram son unidimensionales, a menudo se visualizan en dos dimensiones para mostrar cómo evolucionan con el tiempo. En esta visualización, cada generación (o iteración) del autómata se representa como una nueva fila debajo de la fila anterior. Esto permite ver cómo los estados de las celdas cambian con el tiempo y cómo emergen patrones a partir de las reglas simples del autómata. A continuación se muestra la regla 30 [10] de Wolfram tras ejecutar 15 iteraciones de este: Regla 30 de Wolfram 00011110 Figura6: Ejemplo autómata de Wolfram 16 2.1.2.3. Hormiga de Langton La «hormiga de Langton» [5], [11], es una máquina de Turing bidimensional de 4 estados, se describe de manera sencilla de la siguiente manera. Se considera un tablero cuadriculado donde cada casilla puede ser negra o blanca, y también puede contener una hormiga. Esta hormiga tiene cuatro direcciones posibles: norte, este, oeste y sur. Su movimiento sigue reglas simples: gira 90 grados a la derecha cuando está sobre una casilla negra, y 90 grados a la izquierda cuando está sobre una casilla blanca, tras lo cual “avanza” en dicha dirección. Además, al “dejar” una casilla, ésta cambia de color. El proceso comienza con una sola hormiga en una casilla blanca. Al principio, su movimiento parece caótico, pero después de un cierto número de pasos, se vuelve predecible, repitiendo un patrón cada cierto tiempo. En este punto, la parte del rastro de la hormiga que está en casillas negras crece de manera periódica, extendiéndose infinitamente por el tablero. En el autómata celular de la hormiga de Langton, se tienen 10 estados posibles. Estos se derivan de 2 colores de celda (blanco y negro), y la presencia de la hormiga. Cuando la hormiga está ausente, se consideran los 2 estados de color. Cuando la hormiga está presente, se consideran 4 direcciones posibles (norte, este, oeste y sur) para cada color de ceSlda. Por lo tanto, se tienen 2 estados (colores) cuando la hormiga está ausente, y 2 (colores) * 4 (direcciones) = 8 estados cuando la hormiga está presente. En total, se tienen 2 + 8 = 10 estados. Cabe destacar que la hormiga no se mueve en sí misma, sino que cambia el estado de las celdas en las que se encuentra [5]. Cuando la hormiga está en una celda, esa celda cambia de color y la hormiga desaparece. Sin embargo, una de las celdas adyacentes notará que la celda vecina tenía una hormiga orientada en su dirección, lo que provocará que su estado cambie para incluir la hormiga en la siguiente iteración. Para una mejor comprensión, se pueden considerar dos celdas adyacentes: una celda blanca sin hormiga y, a su derecha, otra celda blanca con una hormiga orientada hacia arriba. En un autómata celular, el estado de una celda es dependiente de sus vecinos. En este escenario, la celda vacía detecta que su celda vecina contiene una hormiga orientada hacia arriba y es de color blanco. De acuerdo con las reglas de la hormiga de Langton, la hormiga debería girar a la izquierda, que es la ubicación de la celda vacía. Como resultado, el estado de la celda vacía cambiará a ser blanca pero ahora con una hormiga orientada hacia la izquierda. Simultáneamente, la celda que originalmente contenía la hormiga cambiará su estado a estar vacía y se tornará de color negro. 1ª Generación ⬆⟶ 2ª Generación ⬅⟶ 3ª Generación ⬇⟶ 4ª Generación ➡⟶ 5ª Generación ⬆⟶ 6ª Generación ➡ Figura7: Ejemplo simple de la hormiga de Langton A partir de las 10.000 generaciones aproximadamente, la hormiga de Langton muestra un comportamiento periódico que se repite en un ciclo de 104 generaciones. Este es el resultado en la generación 11.000: 17 Figura8: Ejemplo completo de la hormiga de Langton 2.1.2.4. Autómata de Contacto Un autómata de contacto [5] puede es uno de los modelos más simples de la propagación de una enfermedad infecciosa. Este autómata está compuesto por 2 estados: celda infectada (negra) y celda no infectada (blanca). Las reglas son las siguiente: Una celda infectada nunca cambia, una celda no infectada se vuelve una celda infectada si cualquiera de las 8 celdas adyacente es una infectada. Existe una versión no determinista en la que la una celda no infectada se infecta pero con una probabilidad P. Este modelo es muy útil en la investigación de la propagación de enfermedades infecciosas, ya que en una situación real existen variables aleatorias como se mencionó anteriormente. Estado inicial ⟶ 2ª Generación ⟶ 3ª Generación Figura9: Ejemplo de autómata de contacto determinista 2.1.2.5. Autómata de Greenberg-Hastings Los autómatas de Greenberg-Hastings [5] son modelos bidimensionales compuestos por células que pueden estar en uno de tres estados: reposo, excitado y refractario. Estos autómatas son particularmente útiles para simular patrones de propagación de la actividad eléctrica en tejidos cardiacos, así como otros fenómenos de propagación y ondas. 18 La evolución de las células en un autómata de Greenberg-Hastings se rige por reglas locales que determinan la activación y desactivación de las células en función de su estado actual y el estado de sus vecinos. Estas reglas son las siguientes: • Reposo: una célula en estado de reposo se mantendrá en reposo a menos que al menos uno de sus vecinos esté en estado excitado. En ese caso, la célula pasará al estado excitado en el siguiente paso de tiempo. • Excitado: una célula en estado excitado se moverá al estado refractario en el siguiente paso de tiempo, independientemente del estado de sus vecinos. • Refractario: una célula en estado refractario se moverá al estado de reposo en el siguiente paso de tiempo, independientemente del estado de sus vecinos. Estas reglas simples permiten la propagación de la excitación a través del autómata, creando patrones de propagación que pueden ser analizados y estudiados. Los automátas celulares han sido una influencia en el mundo del videojuego. Existen diversos juegos y hasta géneros basados en autómatas celulares. El siguiente apartado tratará sobre los simuladores de arena y su relación con los autómatas celulares. 2.2. Simuladores de arena En esta sección, se hablará de manera resumida acerca de qué son los simuladores de arena y su funcionamiento. Más tarde, se presentan una serie de antecedentes que se han tomado de base para el desarrollo del proyecto. 2.2.1. Introducción Los simuladores de arena son simuladores cuyo objetivo es representar con precisión interacciones dinámicas entre elementos físicos como granos de arena u otros materiales granulares presentes en el mundo real. Estos comparten muchas similitudes estructurales y conceptuales con los autómatas celulares. El «mapa» de la simulación está formado por un conjunto de celdas dentro de un número finito de dimensiones, representado como una matriz. Cada una de estas celdas se encuentra, en cada paso discreto de la simulación, en un estado concreto dentro de un número finito de estados en los que puede encontrarse. Cada uno de estos estados representa el tipo de la partícula que se encuentra en la celda. Sin embargo, a diferencia de los autómatas celulares, donde la evolución de cada celda está estrictamente determinada por reglas locales con sus celdas vecinas y pueden procesarse todas las partículas sin seguir un orden específico, un simulador de arena funciona de manera secuencial y no determinista. El estado futuro de una celda no solo es influenciado por el estado de sus celdas vecinas, sino también por el orden en que las partículas son procesadas. Además, el procesar una celda, no necesariamente se limita a afectar solo a esa celda. Por ejemplo, el simular fenómenos físicos como la gravedad, implica mover partículas por la matriz de celdas, fenómeno no contemplado en los autómatas celulares. En este sistema, «mover» una partícula consiste en cambiar el estado de una celda a otra. Sin embargo, existen casos en los que este comportamiento no es deseado. Es posible simular el comportamiento de un autómata celular en un simulador de arena aún procesando de forma 19 secuencial mediante una técnica conocida como «doble buffer». En esta técnica, se tienen dos matrices, una que representa el estado actual de la simulación y otra que representa el estado futuro. En cada paso de la simulación, se procesa el estado actual y se guarda el resultado en el estado futuro. Una vez se ha procesado toda la matriz, se intercambian los estados de las matrices. De esta forma, se consigue que el estado futuro de una celda no se vea afectado por el estado futuro de otra celda, es decir, que una celda cambie su estado o el de su vecina no afecta a dicha celda en el mismo paso de simulación. En un simulador de arena, pueden existir multitud de tipos de partículas, cada una con unas reglas distintas de evolución e interacción con otras celdas de la matriz, lo que puede dar lugar a ejecuciones con dinámicas muy complejas. Para explicar el funcionamiento de los simuladores de arena, se tomará un ejemplo básico de un simulador que contenga solo un tipo de partícula, la de arena. Esta partícula tiene el siguiente comportamiento: • Si la celda de abajo esta vacía, me muevo a ella. • En caso de que la celda de abajo esté ocupada por otra partícula, intento moverme en dirección abajo izquierda y abajo derecha, si las celdas están vacías. • En caso de que no se cumpla ninguna de estas condiciones, la partícula no se mueve. ⟶⟶⟶ Figura10: Ejemplo de simulador de arena Esta ejecución toma como base un orden de ejecución de abajo a arriba y de derecha a izquierda. Para un orden de ejecución de arriba a abajo y de izquierda a derecha el resultado sería el siguiente. ⟶⟶⟶ Figura11: Ejemplo de simulador de arena, diferente orden Como puede verse, el orden en el que se procesan las celdas de la matriz afecta al resultado final. 2.2.2. Simuladores de arena dentro de los videojuegos Dentro de la industria de los videojuegos, se han utilizado simuladores de arena con diferentes fines, como pueden ser mejorar la calidad visual o aportarle variabilidad al diseño y jugabilidad del propio videojuego. Este proyecto toma como principal referencia a «Noita», un videojuego indie roguelike que utiliza la simulación de partículas como núcleo principal de su jugabilidad. En «Noita», cada píxel en pantalla representa un material y está simulado siguiendo unas reglas físicas y químicas específicas de ese material. Esto permite que los diferentes materiales sólidos, líquidos y gaseosos se comporten de manera realista de acuerdo a sus propiedades. El jugador tiene la capacidad 20 de provocar reacciones en este entorno, por ejemplo destruyéndolo o haciendo que interactúen entre sí. Figura12: Imagen gameplay de Noita Noita no es el primer videojuego que hace uso de los simuladores de partículas. A continuación, se enumeran algunos de los títulos, tanto videojuegos como sandbox, más notables de simuladores de los cuales el proyecto ha tomado inspiración durante el desarrollo. • Falling Sand Game [12] Probablemente el primer videojuego comercial de este subgénero. A diferencia de Noita, este videojuego busca proporcionarle al jugador la capacidad de experimentar con diferentes partículas físicas así como fluidos y gases, ofreciendo la posibilidad de ver como interaccionan tanto en un apartado físico como químicas. Este videojuego estableció una base que luego tomaron otros videojuegos más adelante. • Powder Toy [13] Actualmente el sandbox basado en partículas más completo y complejo del mercado. Este no solo proporciona interacciones ya existentes en sus predecesores, como Falling Sand Game, sino que añade otros elementos físicos de gran complejidad como pueden ser temperatura, presión, gravedad, fricción, conductividad, densidad, viento etc. • Sandspiel [14] Este proyecto utiliza la misma base que sus predecesores, proporcionando al jugador libertad de hacer interaccionar partículas a su gusto. Además, añade elementos presentes en Powder Toy como el viento, aunque la escala de este proyecto es más limitada que la de proyectos anteriores. De Sandspiel, nace otro proyecto llamado Sandspiel Club [15], el cual utiliza como base Sandspiel, pero, en esta versión, el creador porporciona a cualquier usuario de este proyecto la capacidad de crear partículas propias mediante un sistema de scripting visual haciendo uso de la librería Blockly [16] de Google. Además, similar a otros títulos menos relevantes como Powder Game (no confundir con Powder Toy), es posible guardar el estado de la simulación y compartirla con otros usuarios. 21 3. Programación paralela En esta sección se hablará sobre qué es la programación paralela, su funcionamiento y usos tanto en CPU como en GPU. La programación paralela es una técnica de programación que consiste en dividir un problema en tareas más pequeñas y ejecutarlas simultáneamente en múltiples procesadores o núcleos de procesamiento. Esto permite aprovechar el poder de cómputo del hardware y acelerar la ejecución de programas. Sin embargo, debido a las particularidades de cada tipo de hardware, la forma en que funciona y se aplica varía en función de si se quiere usar la CPU o la GPU. Cabe destacar que independientemente del hardware utilizado, la paralelización de un problema no incrementa el rendimiento de manera lineal con el número de núcleos utilizados, el incremento de rendimiento tiene un límite. La ley de Amdahl [17] es un principio importante en la programación paralela que establece que el rendimiento máximo que se puede lograr al paralelizar un programa está limitado por la fracción secuencial del código. En otras palabras, aunque se pueda paralelizar una parte del código, siempre habrá una porción que debe ejecutarse de forma secuencial y que limitará el rendimiento general del programa. La ley de Amdahl se expresa mediante la siguiente fórmula: Mejora Total = 1 (1 − 𝑃) + (𝑃 𝑁) Donde: •Mejora Total es la mejora en el rendimiento del programa al paralelizarlo. •P es la fracción del código que se puede paralelizar. •N es el número de núcleos de procesamiento (hilos) disponibles. Esta fórmula muestra que, a medida que aumenta el número de procesadores o hilos (N), el rendimiento total mejora, pero solo hasta cierto punto. La fracción secuencial del código (1 - P) siempre limitará el rendimiento máximo que se puede lograr. 3.1. Programación paralela en GPU La GPU (graphics processing unit) es un procesador originalmente diseñado para manejar y acelerar el procesamiento de tareas gráficas, como puede ser el mostrar imágenes o vídeos en pantalla. Para facilitar la aceleración de estas tareas, se crearon los shaders, pequeños programas gráficos destinados a ejecutarse en la GPU como parte del pipeline gráfico. El pipeline gráfico es el conjunto de operaciones secuenciales que finalmente formarán la imagen a mostrar en pantalla. La denominación pipeline hace referencia a que las operaciones que lo componen se ejecutan de manera secuencial y cada operación recibe una entrada de la fase anterior y devuelve una salida que recibirá la siguiente fase como entrada, hasta completar la imagen. [18] El pipeline gráfico comienza con la representación de objetos mediante vértices. Cada vértice contiene información como su posición, normal, color y coordenadas de textura. 22 Luego, las coordenadas de los vértices se transforman en coordenadas normalizadas mediante matrices de transformación, pasando por etapas de escena, vista y proyección. Después, se ensamblan los vértices para formar primitivas, se descartan o recortan las que están fuera del campo visual y se mapean a coordenadas de pantalla. La rasterización determina qué píxeles formarán parte de la imagen final, utilizando un buffer de profundidad para determinar qué fragmentos se dibujan. Se interpola entre los atributos de los vértices para determinar los atributos de cada fragmento y se decide el color de cada píxel, considerando la iluminación, la textura y la transparencia. Finalmente, los fragmentos dibujados se muestran en la pantalla del dispositivo. Aunque la funcionalidad inicial de la GPU se limitaba al apartado gráfico, los fabricantes de este tipo de chips se dieron cuenta de que los desarrolladores buscaban formas de mapear datos no relacionados con imágenes a texturas, para así ejecutar operaciones sobre estos datos mediante shaders [19]. Esto significaba que se podía aprovechar las características de este hardware para la resolución de tareas que no tengan que ver con imágenes, por lo que extendieron su uso más allá de la generación de gráficos. Una de estas extensiones fue la creación de «compute shaders» [20] que son programas diseñados para ejecutarse en la GPU, pero, a diferencia de los shaders, no están directamente relacionados con el proceso de renderizado de imágenes, por lo que se ejecutan fuera del pipeline gráfico. Los «compute shaders» se emplean para realizar cálculos destinados a propósitos que se benefician de la ejecución masivamente paralela ofrecida por la GPU. Son ideales para tareas como simulaciones físicas, procesamiento de datos masivos o aprendizaje automático. Para lograr el procesamiento de shaders de la manera más eficiente, la GPU se diseñó con una arquitectura hardware y software que permite la paralelización de cálculos en el procesamiento de vértices y píxeles independientes entre sí. Este apartado se centra en explicar las diferencias de arquitectura entre una CPU y una GPU a nivel de hardware, así como en explicar cómo este hardware interactúa con el software destinado a la programación de GPUs. 3.1.1. Hardware La tarea de renderizado requería de un hardware diferente al presente en la CPU debido a la gran cantidad de cálculos matemáticos que requiere. Desde transformaciones geométricas hasta el cálculo de la iluminación y la aplicación de texturas, todas estas tareas se basan en manipulaciones matemáticas haciendo uso de vectores y matrices. Para optimizar el proceso de renderizado, es esencial reducir el tiempo necesario para llevar a cabo estas operaciones [21]. Por lo tanto, surge la GPU como co-procesador con una arquitectura SIMD (single instruction multiple data) cuya función es la de facilitar a la CPU el procesado de tareas relacionadas con lo gráfico, como renderizar imágenes, vídeos, animaciones, etc [17]. Al ser el objetivo de la GPU el procesar tareas de manera paralela, se puede observar una gran diferencia en cuanto a la distribución de espacio físico (recuento de transistores) dentro del chip con respecto a la CPU, que esta diseñada para procesar las instrucciones secuencialmente [1]. 23 Figura13: Comparativa arquitectura de un chip de CPU y de GPU [1] Una GPU dedica la mayor cantidad de espacio a alojar núcleos para tener la mayor capacidad de paralelización posible, mientras que la CPU dedica, la mayoria de su espacio en chip a diferentes niveles de caché y circuitos dedicados a la logica de control [1]. La CPU necesita estos niveles de caché para intentar minimizar al máximo los accesos a memoria principal, los cuales ralentizan mucho la ejecución. De igual manera, al estar diseñados los núcleos CPU para ser capaces de ejecutar cualquier tipo de instruccion, requieren lógica de control para gestionar los flujos de datos, controlar el flujo de instrucciones, entre otras funciones. Sin embargo, la GPU al estar dedicada principalmente a operaciones matemáticas y por lo tanto tener un set de instrucciones mucho más reducido en comparación con la CPU, puede prescindir de dedicarle espacio a la logica de control. Al acceder a memoria, a pesar de que los cores tengan registros para guardar datos, la capacidad de estos es muy limitada, por lo que es común que se acceda a la VRAM (Video RAM). La GPU consigue camuflar los tiempos de latencia manejando la ejecucion de hilos sobre los datos. Cuando un hilo esta realizando acceso a datos, otro hilo está ejecutandose [1]. La gran cantidad de cores presentes en una GPU, están agrupados en estructuras de hardware llamados SM (Streaming Multiprocessors) en NVIDIA y CP (Compute Units) en AMD. NVIDIA y AMD son dos de los principales fabricantes de tarjetas gráficas, cada uno con su propia arquitectura y tecnologías específicas. Además de núcleos de procesamiento, estas agrupaciones incluyen normalmente una jerarquía básica de memoria con una cache L1, una memoria compartida entre núcleos, una caché de texturas, un programador de tareas y registros para almacenar datos. Su tarea principal es ejecutar programas SIMT (singleinstruction multiple-thread) correspondientes a un kernel, asi como manejar los hilos de ejecución, liberándolos una vez que han terminado y ejecutando nuevos hilos para reemplazar los finalizados. [21] 24 Figura14: Streaming Multiprocessor [1] 3.1.2. Software Debido a que la implementacion de CUDA fue un punto de inflexión en el desarrollo de GPUs y asentó las bases de lo que hoy es la computación de propósito general en unidades de procesamiento gráfico, se explicará cómo se enlaza el software al hardware ya explicado haciendo uso de CUDA. Todos los conceptos son extrapolables a otras APIs de desarrollo como pueden ser SYCL o OpenMP. Un programa CUDA puede ser dividido en 3 secciones [1]: • Código destino a procesarse en el Host (CPU). • Código destinado a ser procesado en el Dispositivo (GPU). • Código que maneja la transferencia de datos entre el Host y el dispositivo. El código destinado a ser procesado por la GPU se conoce como kernel. Un kernel está diseñado para contener la menor cantidad de código condicional posible. Esto se debe a que la GPU está optimizada para ejecutar un mismo conjunto de instrucciones en múltiples datos de manera simultánea. Cuando hay muchas ramificaciones condicionales (como if-else), puede haber una divergencia en la ejecución de los hilos, lo que disminuye la eficiencia del paralelismo y puede resultar en un rendimiento inferior. A cada instancia de ejecución del kernel se le conoce como hilo. El desarrollador define cual es el número de hilos sobre los que quiere ejecutar el kernel, idealmente maximizando la paralelización de los cálculos. Estos hilos pueden ser agrupados uniformemente en bloques, y a su vez estos bloques son agrupados en un grid de bloques. El número de bloques totales que se crean viene dictado por el volumen de datos a procesar. Tanto los bloques como los grids pueden tener de 1 a 3 dimensiones, y no necesariamente tienen que coincidir. 25 Figura16: estructura básica de Blockly La Figura16 muestra la estructura de un proyecto de Blockly. Esta se divide en 2 partes básicas, la toolbox o caja de herramientas y el workspace o espacio de trabajo. La toolbox alberga todos los bloques que haya creado el desarrollador o que haya incluido por defecto. Estos bloques los puede arrastrar al workspace para generar lógica que haya sido definida por el desarrollador. Por defecto, todos los bloques son instanciables las veces que sean necesarias. Para que el usuario pueda usar un bloque correctamente, son necesarios tres pasos desde el punto de vista del desarrollador [36]: • Definir cómo es su apariencia visual. Esto puede ser realizado tanto usando código JavaScript como mediante JSON. Es recomendable usar JSON, aunque por características particulares puede ser necesario definirlos mediante JavaScript. • Especificar el código que será generado una vez haya sido arrastrado el bloque al workspace. Debe haber una definición del código a generar por cada bloque y lenguaje que se quiera soportar. • Incluirlo en la toolbox para que pueda ser utilizado. Esto puede ser realizado mediante XML o JSON, aunque Google recomienda el uso de JSON. La definición de la apariencia y la inclusión en la toolbox son tareas bastante directas. Sin embargo, la generacion de código requiere la presencia de un intérprete que genere código a partir del texto que devuelve la función. En caso de querer generar código para un lenguaje no soportado por defecto, el desarrollador necesitará crear este intérprete. 32 5. Simuladores de arena en CPU Este trabajo trata sobre simuladores de arena y, como se mencionó en la Sección2.2, los simuladores de arena no son paralelizables debido a que cada celda puede modificar el estado de las demás. En este capítulo se muestran distintas implementaciones de simuladores de arena que se ejecutan en la CPU para poder compararlos. Para poder realizar la comparativa, se han realizado 3 simuladores diferentes basados en explotar la CPU. Cada uno de ellos tiene sus propias ventajas y desventajas, además de distintos propósitos. A continuación se detalla cada implementación, profundizando en sus rasgos particulares. 5.1. Generalidades En todas las implementaciones, una partícula es una estructura de datos con al menos dos propiedades: id y clock. La propiedad id es un valor que indica el tipo de partícula, mientras que clock es un valor que alterna entre 0 y 1 en cada iteración. Esto permite que una partícula no sea procesada dos veces en la misma generación. Es decir, si una partícula de arena se mueve «hacia abajo» y la actualización del simulador procesa las partículas de arriba a abajo, la partícula de arena que se movió hacia abajo volverá a ser procesada dentro de la misma generación. Para evitar este problema, se usa el valor clock para marcar si una partícula fue procesada en la generación actual. Para evitar tener que resetear el valor de clock de todas las partículas en cada generación, se alterna entre 0 y 1 en cada iteración y se compara con el valor clock del sistema, que también alterna entre 0 y 1 en cada iteración. 5.2. Simulador en C++ El primer simulador fue desarrollado en C++ con OpenGL y GLFW. Este simulador sirve como base comparativa de las siguientes implementaciones. Este sistema posee 6 partículas: Arena, Agua, Aire, Gas, Roca y Ácido. En este sistema las partículas están programadas en el sistema y no son modificables de forma externa. Cada partícula tiene una serie de propiedades: color, densidad, granularidad, id y movimiento. El color es el color de la partícula, la densidad es un valor númerico que indica la pesadez relativa respecto otras partículas, la granularidad es un valor que modifica ligeramente el color de la partícula, la id es un valor que indica el tipo de partícula y el movimiento es una serie de valores que describe el movimiento de la partícula. Estos rasgos son particulares de esta implementación y no se repiten en las siguientes a excepción del identificador de la particula, que es común a todas las implementaciones. Este sistema es limitado, pues los comportamientos de las partículas dependen de estos parámetros y el sistema que las procesa. Con todo, esto permite generar variaciones de partículas con facilidad. El valor del movimiento permite crear los tipos de movimientos más comunes (arena, agua, lava, gas, etc). La densidad permite controlar que partícula puede intercambiarse por otra sin tener que controlarlo manualmente para cada partícula… Al ser un sistema cerrado, se da lugar a un sistema más rápido y eficiente que los siguientes ya que el compilador puede optimizar el código de forma más eficiente. La Figura17 muestra la interacción entre partículas en este simulador en un mundo de 100 ∗ 100 celdas. 33 (a) Antes de que la arena llegue al agua (b) Arena hundiéndose en el agua Figura17: Interacción entre partículas en el simulador de C++ Esta implementación ejecuta una lógica directa en un solo hilo. Debido a esto es la base para comparar el rendimiento de las siguientes implementaciones. Para poder mostrar el estado de la simulación de forma visual, se escribe en un buffer el color de cada partícula después de cada paso de simulación. Este buffer se envía a la GPU para ser renderizado en pantalla. Se puede ver un video de esta simulación haciendo click en el siguiente enlace 5.3. Simulador en Lua con LÖVE LÖVE [37] es un framework de desarrollo de videojuegos en Lua orientado a juegos 2D. Permite dibujar gráficos en pantalla y gestionar la entrada del usuario sin tener que preocuparase de la plataforma en la que se ejecuta. LÖVE usa LuaJIT, por lo que es posible alcanzar un rendimiento muy alto sin sacrificar flexibilidad. Para mejorar aún más el rendimiento, esta implementación se basa de la librería FFI de LuaJit. Esta permite a Lua interactuar con código de C de forma nativa. Además, al poder declarar structs en C, es posible acceder a los datos de forma más rápida que con las tablas de Lua y consumir menos memoria. En este sistema, una particula es un struct en C que contiene su id y su clock. Para facilitar la extensión y usabilidad de esta versión, se creó un API que permite definir partículas en Lua de forma externa. Una particula está definida por su nombre, su color y una función a ejecutar. Una vez hecho esto, el usuario solo debe arrastrar su archivo a la ventana de juego para cargar su «mod». La función que ejecuta cada partícula recibe un solo parámetro: un objeto API. Este define las funciones necesarias para definir las reglas que modelan el comportamiento de una partícula. Además, para facilitar el desarrollo, las direcciones que consume el API son relativas a la 34 posición de la partícula que se está procesando. Obtener el tipo de una partícula a la derecha de la actual es tan sencillo como llamar a api:get(1, 0). Además de esto, el sistema registra automáticamente los tipos de partículas en una tabla global que actúa como un enum. Esto permite que el usuario pueda comprobar con facilidad si un tipo de partícula está definido en el sistema para poder interactuar con este. Por ejemplo, una particula de lava puede comprobar si hay agua debajo de ella y convertirla en roca. Sin embargo, simular tantas partículas es un proceso costoso. Debido a esto, se optimizó mediante la implementación de multihilo. Si bien Lua es un lenguaje muy sencillo y ligero, tiene ciertas carencias, una de ellas es el multithreading. Lua no soporta multithreading de forma nativa. La alternativa a esto es instanciar una máquina virtual de Lua para cada hilo, esto es exactamente lo que love.threads hace. LÖVE permite crear hilos en Lua, pero además de esto, permite compartir datos entre hilos mediante love.bytedata, una tabla especial que puede ser enviada entre hilos por referencia, en resumen, un recurso compartido. Además de esto, LÖVE provee canales de comunicación entre hilos, que permiten enviar mensajes de un hilo a otro y sincronizarlos. Esto permitió enviar trabajo a los hilos bajo demanda. La implementación del multihilo dio lugar a problemas que no se tenían antes: escritura simultánea y condiciones de carrera. Esto supuso un desafío que fue resuelto implementando la actualización por bloques. En lugar de simular todas las particulas posible a la vez, se ejecutarían subregiones específicas de la simulación en 4 lotes. Se dividió la matriz en un «patron de ajedrez» [38]. Esto consiste en procesar primero las columnas y filas pares, luego columnas pares y filas impares… Y así hasta completar las 4 combinaciones posibles. Esto nos permite dividir la actualización de la simulación en 4 «pases», donde en cada uno de estos pases se procesan varias partículas a la vez. La figura Figura18 muestra como serían estos pases. ⟶⟶⟶ Figura18: Patrón de ajedrez de actualización Cada uno de los cuadrados de la imagen representa una «submatriz» de partículas, esto se denomina un «chunk». El sistema dividirá la matriz en chunks siguiendo el siguiente criterio: El tamaño mínimo de una chunk es de 16 píxeles, el número de chunks debe ser igual o superior al cuadrado de hilos disponibles. Estos requisitos garantizan que se puedan utilizar todos los hilos a la vez. El requisito de tamaño es para evitar que una partícula trate de modificar a otra lejana que esté siendo procesada por otro hilo. El orden en que se procesan las regiones coincide con el mostrado en la Figura18. Primero filas y columnas pares, a continuación, filas impares y columnas impares, tras esto, filas pares y columnas impares y finalmente filas impares y columnas pares. Sin embargo, esto da lugar a problemas. Surgen artefactos visuales cuando una partícula se mueve fuera de la región que se estaba procesando. A continuación se muestra un ejemplo de este problema. Cada imagen es una generación de la simulación. 35 ⟶ ⟶ Figura19: Problema de multithreading En la Figura19 se muestran tres generaciones procesando con el sistema multithread descrito. Se ilumina el borde de cara región para mayor claridad. Cada subregión procesa las particulas de arriba a abajo y de izquierda a derecha. El comportamiento de la partícula es el siguiente: Si el vecino superior es vacío, se «mueve» hacia arriba. En tercera generación se puede observar como las partículas se separan. Al haberse procesado primero la región roja, la partícula no puede moverse porque en la región morada había una partícula encima. Acto seguido, la partícula morada se mueve hacia arriba. En ejecución este efecto es notorio y afecta al comportamiento esperado de la simulación. Cambiar el orden en que se actualizan las partículaas resolvería el problema para partículas que se muevan en una dirección determinada, pero el problema siempre se presentará en una dirección. Para evitar este problema se requirió modificar la actualización de la simulación. En primer lugar, se introdujo un doble buffer, esto permite que el procesamiento de las partículas sea consistente por lo mencionado en la Sección2.2. Con todo, esto no es suficiente y existen casos específicos en los que el problema persiste. Por ello, además de añadir doble buffer, el orden en que se actualizan las particulas cambia en un ciclo de 2 fotogramas. Primero se actualiza la matriz de derecha a izquierda y de arriba a abajo, y luego de izquierda a derecha y de abajo a arriba. Esto se debe a que si siempre se actualizan las partículas de izquierda a derecha o viceversa, el sistema presentará un sesgo en la dirección en la que se actualizan las partículas que provoca que el resultado tras varias iteraciones no sea el esperado. 36 (a) Sin variar el orden de actualización (b) Variando el orden de actualización Figura20: Diferencia entre variar y no el orden de actualización al procesar partículas Con estas mejoras el sistema funciona correctamente en casi todos los casos, pero aún existen casos muy específicos resultados de procesar chunks en un patrón de ajedrez. La solución para esto fue variar el orden de actualización de dichos «chunks» o trozos. En cada generación se invierte el orden de actualización de los chunks de una manera simlar a la que se invierte del orden de actualización de las partículas dentro de dichos chunks. Esto permite que el sistema sea más estable y no presente sesgos en la dirección en la que se actualizan las partículas. Finalmente, para gestionar el procesamiento de los chunks se implementó la técnica del work stealing. El hilo principal va asignando chunks a los hilos libros hasta que todos han sido procesados, lo cual deja a los hilos esperando para la siguiente generación. El procesamiento de una partícula tiene una segunda fase. Una vez todos los chunks han sido procesados, se actualizan los buffers y se actualiza la textura que posteriormente se renderiza en pantalla. La actualización de los buffers consiste en copiar el buffer de la generación actual al buffer de la generación anterior. Esto se hace debido a que hay partículas que podrían no realizar ninguna acción y por tanto no modifican el buffer de la generación actual, por lo que intercambiarlos no es suficiente. Se puede ver un video de esta simulación haciendo click en el siguiente enlace 5.4. Simulador en la web La siguiente implementación es distinta a las demás en dos aspectos. Esta se ejecuta en el navegador y además permite a los usuarios definir las reglas de las partículas mediante Blockly. Se profundizará de esto más adelante. Blockly puede usarse para generar código en cualquier lenguaje, incluido JavaScript, el lenguaje usado en programar elementos interactivos en las webs. No obstante, JavaScript es un lenguaje interpretado que aún siendo JIT, es lento. Debido a esto, desde hace varios años los navegadores tienen soporte para WebAssembly [39], un lenguaje de bajo nivel que es más rápido que 37 JavaScript. Las mayores diferencias entre WebAssembly y JavaScript, es que WebAssembly es un lenguaje de tipado estático y además, no posee gestión automática de memoria, esta debe ser manejada manualmente. WebAssembly no está pensado para ser usado directamente, sino que es un destino de compilación para otros lenguajes. En este caso, se usó Rust, un lenguaje de programación de propósito general con características de lenguajes funcionales y orientados a objetos. Es un lenguaje con características de bajo y alto nivel. Rust y WebAssembly por si solo no son suficientes. Para poder visualizar el estado de la simulación en la web se usó Macroquad, una librería de Rust que permite renderizar gráficos en la web, además de gestionar la entrada del usuario. Ejecutar la simulación en la web incurre en un problema no resoluble, no es posible controlar el número de generaciones que se ejecutan por segundo, ya que esto es controlado por la función requestAnimationFrame del navegador. Además, el entorno web impide el uso de multihilo, por lo que la simulación se ejecuta en un solo hilo. Finalmente, para agrupar todos estos elementos, se creó una página web usando Vue y estilizando con TailwidCSS para crear la interfaz de usuario e implementar BLockly. La Figura21 muestra la interfaz de la simulación en la web. Figura21: Interfaz de la simulación en la web A continuación se explica la lógica y funcionamiento interno de la simulación. Esta es una simulación secuencial que no usa doble buffer, pero sí altera el orden de actualización de las partículas para evitar el problema del sesgo visto en la Sección5.3. Las partículas en esta implementación son más complejas y ofrecen más posibilidades. Existen dos tipos de datos: los que posee cada partícula y los que son comunes a todas. Existe un registro asociado a cada tipo de partícula que contiene los siguiente datos: nombre, primer color, segundo color. El nombre sirve para identificar a la partícula en Blockly. Para poder hablar de los dos colores primero es necesario describir la información que tiene cada partícula individualmentea a parte de los 38 parámetros básicos de clock e id, poseen otros 6 datos: opacity, color_fade, hue_shift, extra, extra2, extra3. Todos estos campos son números restringidos a un intervarlo entre 0 y 100. Cuando una partícula se crea en este sistema, se le asigna un color fade aleatorio entre 0 y 100. Este valor controla la interpolación entre el primer y segundo color, opacity controla la transparencia de la partícula y siempre se inicializa a 100, hue shift altera el tono de la partícula y siempre se inicializa a 0, todos los campos extra son valores que se inicializan a 0 y el usuario puede usar para representar cualquier cosa. Al igual que en la implementación anterior, cada tipo de partícula tiene una función asociada cuyo único parámetro de entrada es un objeto API que contiene las funciones necesarias para interactuar con la simulación. Esta función es generada en tiempo de ejecución. Nuestra implementación de Blockly no genera código, sino que genera datos en formato JSON. Este JSON se envía de JavaScript a WebAssembly (Rust) para ser procesado. Cada bloque de Blockly está asociado a una variante de un enum en Rust, además, estas variantes son tuplas que pueden contener parámetros. El fichero JSON se deserializa en dicha estructura para poder ser procesado mejor. Con esta estructura puede generarse una función. Para ello se define una función que devuelve una función anónima. Se usa pattern matching para que cada variante devuelva una función distinta. Algunas variantes contienen instancias de otras variantes, por lo que en estas se llama de nuevo a la función que devuelve una función anónima en una suerte de recursión. Finalmente la función obtenida se guarda para ser usada posteriormente. Este procesamiento no es directo, sino que en función de los datos de las tuplas se toman unas u otras decisiones. Existen dos tipos de datos: constantes y dinámicos. Los datos constantes son aquellos que nunca cambian, mientras que los datos dinámicos dependen del estado de la simulación. Al «convertir» las variantes del enum a funciones, esto se tiene en cuenta. Los datos estáticos son capturados por la función anónima que se devuelve, mientras que los datos dinámicos son recalculados dentro de la función que se devuelve. Un ejemplo sería la dirección. La dirección es un enum que tiene dos variantes: CONSTANT([i32; 2]) y RANDOM. Es evidente que la dirección constante no cambia y puede capturarse en la función anónima, mientras que la dirección aleatoria debe ser recalculada en cada iteración. Esta optimización se aplica en cada variante que tenga una dirección como dato. Se puede ver un video de esta simulación haciendo click en el siguiente enlace 39 6. Simulador de arena en GPU Ejecutar una simulación de partículas en la GPU supone un desafío. Como se explicó en la Sección2.2, y se mencionó en la Sección5, los simuladores de arena de por sí no son paralelizables, ya que son dependientes del orden de ejecución y cada celda puede potencialmente modificar al resto de celdas de la matriz. Sin embargo, es posible, reescribiendo las condiciones de evolución de las partículas, transformar un simulador de arena en un autómata celular. Para ello, hay que volver del concepto de partícula al de celda. Esto supone que cada celda tiene que poder conocer su próximo estado mediante reglas locales con sus vecinas, y cada celda solo se modificará a sí misma. Tomando de nuevo el ejemplo de la Sección2.2 de simulador básico con un solo tipo de partícula, la de arena, se va a mostrar como se puede convertir este simulador en un autómata celular con un comportamiento similar. Cada celda de este autómata celular solo tiene dos estados, vacío y arena. La partícula de arena necesita tener el siguiente comportamiento: • Si la celda de abajo esta vacía, me muevo a ella. • En caso de que la celda de abajo esté ocupada por una partícula de arena, intento moverme en dirección abajo izquierda y abajo derecha si las celdas están vacías. • En caso de que no se cumpla ninguna de estas condiciones, la partícula no se mueve. Ahora, tomando cada celda como entidad aislada, se puede lograr un comportamiento similar de la siguiente forma: • Si la celda es una partícula vacía, comprueba si encima suyo hay una partícla de arena, en cuyo caso, la celda se convierte en una partícula de arena. • Si la celda es una partícula de arena, solo existen dos opciones: ‣La celda inmediatamente inferior es vacía, por lo tanto puede caer. La celda actual se convierte en vacía. ‣La celda inferior es arena. En este caso, no es posible saber en el mismo paso de la simulación si la celda inferior también puede caer, por lo que la celda no se mueve y se queda como partícula de arena. Nótese que esto provoca que se produzcan artefactos visuales entre partículas al caer, de manera similar a lo que sucedía en la simulación de Lua con multithreading cuando una partícula se movía fuera de la región en la que se estaba ejecutando. Solo que en este caso, se producen entre todas las partículas en todo momento, ya que cada celda es un hilo de ejecución separado. Se puede observar que caen en líneas horizontales con espacios entre ellas. ⟶ ⟶ Figura22: Artefactos visuales 40 Para realizar movimientos diagonales, se llevan a cabo las mismas comprobaciones que para el movimiento de caída vertical. Sin embargo, en lugar de verificar las celdas ubicadas arriba y abajo, se realizan comprobaciones en las direcciones arriba derecha, abajo izquierda y arriba izquierda, abajo derecha respectivamente. Desde el punto de vista de desarrollo, para poder ejecutar estas instrucciones de movimiento en la GPU, es necesario programar las reglas de movimiento dentro de un compute shader. Éste recibe como input el estado de la simulación actual y devuelve como output el estado de la simulación tras realizar uno de los tres movimientos. Cada comprobación de movimiento se realiza de manera separada, es decir, se ejecuta el compute shader de movimiento hacia abajo, y el output de éste lo procesa el compute shader de movimiento diagonal. Es necesario, a su vez, separar la lógica de movimiento abajo derecha y abajo izquierda ya que no sería posible realizar el movimiento hacia ambas diagonales en un solo paso de simulación. Dado el siguiente estado de la matriz: Figura23: Ejemplo problema movimiento diagonal Tanto la partícula de arriba a la izquierda como la de arriba a la derecha pueden moverse a la celda central, sin embargo, la celda central, que es la que tiene que decidir si en el siguiente paso de la simulación existe materia o no en esa posición, no puede saber si alguna de esas partículas se va a mover a esa posición, ninguna de ellas, o ambas. Esta implementación, a cambio de ser la más rápida en ejecución, como ya se verá en la Sección7.1, no aporta flexibilidad de ampliación alguna al usuario, ya que el código de lógica de movimiento se ejecuta mediante compute shaders escritos en .GLSL, lo cual es una tarea que puede ser complicada incluso para programadores que no tengan muchos conocimientos de informática gráfica y programacion de GPUs. A su vez, otro problema que presenta esta implementación es que el añadir partículas e interacciones entre ellas requiere mucho más trabajo que sus contrapartes en CPU, ya que requiere transformar las normas de movimiento y de interacciones entre partículas a reglas locales de celdas. La dificultad que presenta ampliar este sistema ha hecho que actualmente solo tenga implementada la partícula de arena. Se utilizó Vulkano [40], una librería hecha en Rust que actúa como wrapper de Vulkan [41], como librería gráfica para renderizar partículas debido a la flexibilidad y rendimiento que aporta el tener control sobre el pipeline gráfico a la hora del renderizado. Se hizo uso de Bevy [42], motor de videojuegos hecho en Rust, para implementar mecánicas básicas como el bucle principal de juego o procesamiento de input y de Egui [43] para crear la interfaz. Se puede ver un video de esta simulación haciendo click en el siguiente enlace 41 8. Conclusiones y trabajo futuro La implementación realizada en Lua resulta ser muy versátil dado su rendimiento y facilidad de uso considerando un perfil técnico. Para su uso en videojuegos esta opción puede llegar a ser viable con un poco más de trabajo para simular solamente grupos de partículas activas y no la totalidad de las partículas en memoria. La simulación web es idónea para simulaciones de un tamaño reducido. Debido a su interfaz amigable esta implementación puede ser usada para enseñar conceptos básicos de programación y simulación, así como de introducción a los simuladores de arenas y autómatas celulares. Desarrollar simuladores en GPU resulta ser una buena opción cuando se requiere una gran potencia de cómputo o cuando el tamaño de la simulación es muy grande, pero implementar nuevos comportamientos es complicado. Como trabajo a futuro existen diversas tareas y ampliaciones. En primer lugar, en la simulación web se podría añadir cálculo vectorial, esto permitiría realizar operaciones con partículas que estén alejadas y no solo con las vecinas inmediatas. También sería interesante replicar la simulación web con código nativo para lograr un rendimiento mayor. Además, esto permitiría explorar la posibilidad de generar código GLSL de la interfaz de bloques para poder ejecutar la simulación en GPU. Realizar esto implicaría crear una interfaz de programación visual similar a Blockly de cero. La simulación web podría ser modificada para que su procesamiendo sea similar al de un autómata celular como en la implementación realizada en Lua, esto permitiría crear el juego de la vida, ya que en el estado actual no es posible. La implementación de Lua podría ser mejorada añadiendo más datos para las particulas, ya que actualmente solo tienen clock e id. De realizarse esta ampliación, sería posible crear la ya mencionada interfaz de programación visual nativa para poder generar código Lua. 48 8. Conclusions and future work The Lua implementation turns out to be very versatile given its performance and ease of use considering a technical profile. For use in video games this option can be viable with a little more work to simulate only groups of active particles and not all the particles in memory. The web simulation is suitable for small sized simulations. Due to its user-friendly interface this implementation can be used to teach basic programming and simulation concepts, as well as an introduction to sand and cellular automata simulators. Developing GPU simulators turns out to be a good option when high computational power is required or when the size of the simulation is very large, but implementing new behaviors is complicated. As future work there are several tasks and extensions that can be done. Firstly, in the web simulation, vector calculation could be added, this would allow to perform operations with particles that are far away and not only within the immediate neighbors. It would also be interesting to replicate the web simulation with native code to achieve higher performance. In addition, this would allow exploring the possibility of generating GLSL code from the block interface to be able to run the simulation on GPU. Accomplishing this would involve creating a Blockly-like visual programming interface from scratch. The web simulation could be modified so that its processing is similar to that of a cellular automaton as in the Lua implementation, this would allow to create the game of life, since in the current state it is not possible. The Lua implementation could be improved by adding more data for the particles, since currently they only have the clock and id variables. If this extension were realized, it would be possible to create the aforementioned native visual programming interface to be able to generate Lua code. 49 9. Contribuciones En este capítulo se detalla la aportación de cada uno de los alumnos en el desarrollo del proyecto. 9.1. Nicolás Rosa Caballero Existen 3 aportaciones principales de Nicolás al proyecto: • Simulador en C++ ‣Maquetación inicial del proyecto, implementación de OpenGL, GLFW y IMGUI. ‣Implementación de la lógica inicial de la simulación de arena y la interacción con el usuario. ‣Refactorización de las partículas básicas para este modelo: Arena, Agua, Ácido, Roca, Aire y Gas para generalizar su comportamiento y facilitar el desarrollo de nuevas partículas. ‣Investigación e implementación de un sistema de interacciones entre partículas. ‣Optimizaciones y revisiones del código pertinentes para asegurar que la implementación sea un buen referente comparativo para el resto de implementaciones. • Simulador en Lua con Love2D ‣Diseño de la arquitectura del proyecto y la implementación de toda la lógica de la simulación de arena. ‣Implementación de un sistema de partículas programables en Lua. ‣Diseño e implementación del API para la creación de partículas y sus interacciones. ‣Sistema de eventos implementado con Beholder para disminuir la dependencias entre componentes. ‣Implementación de un sistema de multithreading para mejorar el rendimiento del simulador. ‣Implementación de un algoritmo para encontrar el mayor número de hilos y tamaño de chunk en función del tamaño de la matriz de la simulación y la cantidad de núcleos de la CPU que permita aprovechar la mayor cantidad de hilos simultáneos sin incurrir en condiciones de carrera. ‣Sincronización del trabajo entre los hilos aplicando una implementación propia de la técnica «work stealing» en base al uso de canales. ‣Implementación de un sistema de doble buffer para evitar condiciones de carrera y asegurar la consistencia de los datos. ‣Elaboración de la documentación del API del sistema de partículas. • Simulador en Rust con Macroquad ‣Creación del proyecto y configuración de las dependencias. ‣Configuración del proyecto para soportar WebAssembly, aplicando características distintas según el destino de compilación mediante flags de compilación condicional. ‣Diseño de la arquitectura del proyecto y la implementación de la lógica de la simulación de arena. 50 ‣Implementación de un sistema de comunicación con WebAssembly mediante una cola de comandos global. ‣Implementación de un sistema de plugins para facilitar la creación de nuevas partículas. ‣Extensión del sistema de plugins mediante la creación de un tipo de plugin que toma como datos un fichero JSON y genera una función a ejecutar para la partícula. ‣Diseño e implementación del formato de JSON para definir partículas y sus interacciones. • Web Vue3 envoltorio del ejecutable de Rust ‣Creación de la web usando Vue, Vite y TailwindCSS. ‣Diseño en Canva y posterior implementación de la interfaz gráfica de la web. ‣Implementación del código JavaScript pegamento que permite comunicar la web y el ejecutable WebAssembly. ‣Implementación de un sistema de guardado y cargado de plugins en formato JSON. ‣Implementación de un menú de ayuda y un sistema de gestos para facilitar la interacción con la web. ‣Implementación de integración continua en GitHub mediante GitHub Actions para automatizar la generación de la web. ‣Interactividad de los botones, gestos y otros elementos de la web mediante JavaScript y Vue (variables reactivas, watchers). ‣Implementación de Pinia para gestionar un estado global reactivo y minimizar la interdependencia entre componentes. ‣Colaboración con Jonathan para integrar Blockly en la web. ‣Edición de algunos generadores y definiciones de bloques creados por Jonathan para adaptarlos a las necesidades del proyecto. ‣Diseño del logo de la web. • Otros ‣Elaboración del plan de pruebas con usuario. ‣Realización de parte de las pruebas de usabilidad con usuario. ‣Elaboración de pruebas de rendimiento entre distintos simuladores. ‣Elaboración de figuras para la memoria mediante scripting en Typst y Canva. 9.2. Jonathan Andrade Gordillo • Simulador en C++ ‣Configuración inicial del proyecto así como configurado de solución, proyecto y biblicotecas ‣Implementación de partículas iniciales como agua, roca y gas ‣Asistido en la interaccion con el usuario añadiendo pincel ajustable ‣Añadido propiedades físicas a las particulas como la densidad 51 ‣Movimiento que se ajuste a estos parámetros físicos ‣Añadido de granularidad a las partículas ‣Investigación de sistema alternativo de interaccion entre partículas mediante funciones anónimas ‣Solución de bugs a lo largo del desarrollo relacionados con rendimiento e interacciones • Simulador en Rust con Vulkan haciendo uso de GPU ‣Investigación de posibles formas de hacer uso de la GPU para el cálculo de la lógica, entre ella añadir OpenMP o SYCL al proyecto principal ‣Desarrollo de pipeline gráfico básico haciendo uso de Vulkan ‣Desarrollo de sistema de interacción básico para colocar partículas ‣Implementacion de interfaz mediante ImGUI ‣Implementación de partícula de arena ‣Investigación y desarrollo de compute shaders que permitan delegar el movimiento a la GPU ‣Exploración de diferentes tamaños de work group que den lugar a un mayor rendimiento de ejecución • Blockly para simulador de Rust ‣Investigación sobre las necesidades del proyecto y los requisitos del módulo de Blockly. ‣Creación de todos los bloques presentes en el proyecto, así como de los posibles mutadores que necesiten a excepcion de uno ‣Ajuste del toolbox para incluir los bloques desarrollados ‣Implementación de los generadores para cada bloque creado, aunque algunos de ellos tuvieron que ser corregidos más tarde junto a Nicolás de ‣Colaboración con mi compañero para incluir Blockly en la página web • Otros ‣Realización de parte de las pruebas de usabilidad con usuario. ‣Elaboración de pruebas de rendimiento entre distintos simuladores. 52 Bibliografía [1] W. Stallings, Computer Organization and Architecture Designing for Performance. [2] «Cuda C++ Programming Guide». [En línea]. Disponible en: https://docs.nvidia.com/ cuda/cuda-c-programming-guide/ [3] T. M. Li, Cellular automata. Nova Science Pub Incorporated, 2011. [4] A. Adamatzky, Game of Life Cellular Automata. 2010. doi: 10.1007/978-1-84996-217-9. [5] K.-P. Hadeler y J. Müller, Cellular Automata: Analysis and Applications. Springer, 2017. [6] C. Petzold, The annotated turing. John Wiley & Sons, 2008. [7] J. T. Schwartz, J. Von Neumann, y A. W. Burks, «Theory of Self-Reproducing Automata», Mathematics of computation, vol. 21, n.º 100, p. 745-746, oct. 1967, doi: 10.2307/2005041. [8] W. Buckley, Systems Research for Behavioral Science. Routledge, 2017, pp. 97-107. doi: 10.4324/9781315130569. [9] M. Gardner, «Conway's Game of Life: Scientific American, October 1970», pp. 120-123, [En línea]. Disponible en: https://www.ibiblio.org/lifepatterns/october1970.html [10] S. Wolfram, A New Kind of Science. 2002. [11] Weisstein, Eric W, «Langton's Ant – from Wolfram MathWorld». [En línea]. Disponible en: https://mathworld.wolfram.com/LangtonsAnt.html [12] W. Archive, «Falling Sand Game». [En línea]. Disponible en: https://web.archive.org/ web/20090423105358/http://fallingsandgame.com/overview/index.html [13] P. Toy, «Powder Toy». [En línea]. Disponible en: https://powdertoy.co.uk/ [14] M. Bittker, «Sandspiel». [En línea]. Disponible en: https://maxbittker.com/makingsandspiel [15] M. Bittker, «Sandspiel Club». [En línea]. Disponible en: https://sandspiel.club/ [16] Google, «Blockly». [En línea]. Disponible en: https://developers.google.com/blockly [17] D. A. Patterson y J. L. Hennessy, Computer Organization and Design. Morgan Kaufmann, 2013. [18] T. Möller, E. Haines, y N. Hoffman, Real-time renderiNg. A K PETERS, 2018. [19] J. Krüger y R. Westermann, «Linear algebra operators for GPU implementation of numerical algorithms», 2003. [20] «Compute Shaders Introduction». [En línea]. Disponible en: https://learnopengl.com/ Guest-Articles/2022/Compute-Shaders/Introduction [21] T. M. Aamodt, W. W. L. Fung, y T. G. Rogers, General-Purpose Graphics Processor Architectures. Springer Nature, 2022. [22] S. Chen et al., «Scheduling threads for constructive cache sharing on CMPs», en Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures, en SPAA '07. San Diego, California, USA: Association for Computing Machinery, 2007, pp. 105-115. doi: 10.1145/1248377.1248396. 53 [23] J. Gregory, Game Engine Architecture, Third Edition. CRC Press, 2018. [24] Y. Sharvit, Data-Oriented programming. Simon, Schuster, 2022. [25] J. R. Levine, Linkers and Loaders. Morgan Kaufmann, 1999. [26] D. Barron, The World of Scripting Languages. John Wiley & Sons, 2000. [27] R. Ierusalimschy, Programming in Lua. Roberto Ierusalimschy, 2006. [28] C. Ltd, Mastering lua. Cybellium Ltd, 2023. [29] L. H. De Figueiredo, W. Celes, y R. Ierusalimschy, LUA Programming Gems. Lua.Org, 2008. [30] MIT, «App Inventor». [En línea]. Disponible en: https://appinventor.mit.edu/ [31] MIT Corporation, «MIT». [En línea]. Disponible en: https://www.mit.edu/ [32] Google, «Blockly Games». [En línea]. Disponible en: https://code.org/ [33] MIT, «Scratch». [En línea]. Disponible en: https://scratch.mit.edu/ [34] «code.org». [En línea]. Disponible en: https://code.org/ [35] «Blockly Visual». [En línea]. Disponible en: https://developers.google.com/blockly/ guides/get-started/workspace-anatomy [36] «Blockly Block Creation». [En línea]. Disponible en: https://developers.google.com/ blockly/guides/create-custom-blocks/define-blocks [37] D. D. Akinlaja, LÖVE2d for Lua Game Programming. Packt Publishing Ltd, 2013. [38] G. Vault, «https://www.gdcvault.com/play/1025695/Exploring-the-Tech-and-Design». [En línea]. Disponible en: https://www.gdcvault.com/play/1025695/Exploring-the-Techand-Design [39] A. Haas etal., «Bringing the web up to speed with WebAssembly», SIGPLAN Not., vol. 52, n.º 6, pp. 185-200, jun. 2017, doi: 10.1145/3140587.3062363. [40] «Vulkano». [En línea]. Disponible en: https://vulkano.rs/01-introduction/01-introduction. html [41] «Vulkan». [En línea]. Disponible en: https://www.vulkan.org/ [42] «Bevy». [En línea]. Disponible en: https://bevyengine.org/ [43] «egui». [En línea]. Disponible en: https://github.com/emilk/egui 54