Introducing strongforce: an infrastructure for game engines

The strongforce library is a light-weight framework to build game engines. It provides a backbone for a powerful game loop and helper classes for efficiently implement new game components such as models, renders and simulators. Main framework features include:

  •  Model oriented.
  •  Decoupled simulation and render loops.
  •  Real time simulation loop for integration with physics engines.
  •  Separated read and write stages during simulation to avoid expensive model copies.
  •  Versatile and dynamic visitor pattern to implement the Game Model Hierarchy.
  •  Use of JavaScript functors to quickly implement simple renders or simulators.
  •  Helper classes to ease implementation of Renders and Simulators.
  •  Events for Model to allow asynchronous programming.
  •  Fully control of the loop step and execution.
  •  Careful separation of responsibilities allowing the developer to focus on data model, business logic and rendering process separately.

Strongforce is not a graphic engine, not even a game engine. It is only a proposal for a game architecture and a main loop. You can read more about the framework internals and philosophy of design in the wiki pages of the repository or further in this post. Please feel free to provide any feedback by opening new issues on GitHub.

Seguir leyendo «Introducing strongforce: an infrastructure for game engines»

Hash tables, diccionarios o la memoria del futuro

El ordenador, siguiendo el modelo actual, posee una memoria dividida en celdas que puede referenciarse palabra a palabra para obtener contenido de manera inmediata.  Los ingenieros decimos que el acceso a una celda de memoria tiene coste en O(1) o constante. No hay que buscar nada tan sólo pedir lo que haya en la celda número 42 y ¡presto! ahí está.

Este esquema de memoria es muy versátil porque representa listas de elementos. Casi cualquier estructura de datos puede representarse en una lista y, utilizando punteros, las listas no tienen por qué ser homogeneas. Podemos guardar en ellas de todo e identificar cada objeto guardado por el índice dentro de la lista. En otras palabras, por su posición.

Traducir una lista de objetos a un segmento de la memoria es tan simple como conocer el número de elementos, el tamaño de los mismos y la posición del primero.

Sobra decir que al concepto de lista está unido, muy fuertemente, el concepto de orden y posición.

Si hablamos de colecciones de elementos sin orden, como por ejemplo un conjunto, dónde no nos interesa en qué posición está un objeto, tan sólo si está o no está, encontramos que las listas dejan de resolver el problema elegantemente. Sin duda añadir un objeto a una lista es tan sencillo como añadir un nuevo elemento a una lista… ¿o no? Es un conjunto y en los conjuntos, formalmente descritos, no hay dos elementos iguales por lo que nos convendría no tener repeticiones. Así que antes de insertar un objeto habrá que buscarlo en la lista lo que en el mejor de los casos, tiene una complejidad de O(log n) y en el caso medio, de O(n). En palabras sencillas, buscar es una tarea sencilla pero cara en colecciones muy grandes.

Además, encontrar un objeto del conjunto, al no tener un orden predeterminado (nadie nos asegura que siempre metamos A primero, B segundo,  C tercero…), requiere una búsqueda también. Y eliminarlo, por definición requiere primero encontrarlo, así que tres cuartos de lo mismo.

Con esto en mente, un pedazo de ingeniero eléctrico, Dudley Allen Buck, describió un nuevo tipo de memoria llamada asociativa o direccionada por contenido. Esta memoria toma un objeto entero y lo busca en su interior pero esta búsqueda está hecha de tal forma que el acceso sigue siendo constante. ¿Magia? Nop, ¡ingenio!

Seguir leyendo «Hash tables, diccionarios o la memoria del futuro»