c++ - sistema - manual programacion android

Manera eficiente de hacer coincidir las entidades con los sistemas en un sistema de componente de entidad

Question

Estoy trabajando en un sistema de componentes de entidades orientado a los datos donde se conocen los tipos de componentes y las firmas del sistema en tiempo de compilación.

Una entidad es un agregado de componentes. Los componentes se pueden agregar / eliminar de las entidades en tiempo de ejecución.

Un componente es una clase pequeña sin lógica.

Una firma es una lista en tiempo de compilación de tipos de componentes. Se dice que una entidad coincide con una firma si contiene todos los tipos de componentes requeridos por la firma.

Un ejemplo de código corto le mostrará cómo se ve la sintaxis del usuario y cuál es el uso previsto:

// User-defined component types.
struct Comp0 : ecs::Component { /*...*/ };
struct Comp1 : ecs::Component { /*...*/ };
struct Comp2 : ecs::Component { /*...*/ };
struct Comp3 : ecs::Component { /*...*/ };
// User-defined system signatures.
using Sig0 = ecs::Requires<Comp0>;
using Sig1 = ecs::Requires<Comp1, Comp3>;
using Sig2 = ecs::Requires<Comp1, Comp2, Comp3>;
// Store all components in a compile-time type list.
using MyComps = ecs::ComponentList
<
Comp0, Comp1, Comp2, Comp3
>;
// Store all signatures in a compile-time type list.
using MySigs = ecs::SignatureList
<
Sig0, Sig1, Sig2
>;
// Final type of the entity manager.
using MyManager = ecs::Manager<MyComps, MySigs>;
void example()
{
MyManager m;
// Create an entity and add components to it at runtime.
auto e0 = m.createEntity();
m.add<Comp0>(e0);
m.add<Comp1>(e0);
m.add<Comp3>(e0);
// Matches.
assert(m.matches<Sig0>(e0));
// Matches.
assert(m.matches<Sig1>(e0));
// Doesn''t match. (`Comp2` missing)
assert(!m.matches<Sig2>(e0));
// Do something with all entities matching `Sig0`.
m.forEntitiesMatching<Sig0>([](/*...*/){/*...*/});
}

Actualmente estoy comprobando si las entidades coinciden con las firmas utilizando las operaciones std::bitset . Sin embargo, el rendimiento se degrada rápidamente tan pronto como aumenta el número de firmas y el número de entidades.

Pseudocódigo

// m.forEntitiesMatching<Sig0>
// ...gets transformed into...
for(auto& e : entities)
if((e.bitset & getBitset<Sig0>()) == getBitset<Sig0>())
callUserFunction(e);

Esto funciona, pero si el usuario llama a las forEntitiesMatching con la misma firma varias veces, todas las entidades deberán coincidir nuevamente.

También puede haber una mejor manera de almacenar en antememoria las entidades en contenedores amigables con el caché.

He intentado usar algún tipo de caché que crea un mapa en tiempo de compilación (implementado como std::tuple<std::vector<EntityIndex>, std::vector<EntityIndex>, ...> ), donde están las claves los tipos de firma (cada tipo de firma tiene un índice incremental único gracias a SignatureList ), y los valores son vectores de índices de entidad.

Llené la tupla de caché con algo como:

// Compile-time list iterations a-la `boost::hana`.
forEveryType<SignatureList>([](auto t)
{
using Type = decltype(t)::Type;
for(auto entityIndex : entities)
if(matchesSignature<Type>(e))
std::get<idx<Type>()>(cache).emplace_back(e);
});

Y lo borró después de cada ciclo de actualización del administrador.

Desafortunadamente, funcionó más lentamente que el bucle "raw" que se muestra arriba en todas mis pruebas. También tendría un problema mayor : ¿qué forEntitiesMatching si una llamada a forEntitiesMatching elimina o agrega un componente a una entidad? La memoria caché tendría que ser invalidada y recalculada para las forEntitiesMatching llamadas de forEntitiesMatching .

¿Hay alguna forma más rápida de hacer coincidir las entidades con las firmas?

Se conocen muchas cosas en tiempo de compilación (lista de tipos de componentes, lista de tipos de firmas, ...) : ¿existe alguna estructura de datos auxiliar que pueda generarse en tiempo de compilación que ayude con la concordancia "similar a un conjunto de bits"? ?

Answer 1

¿Has considerado la siguiente solución? Cada firma tendrá un contenedor de entidades que coinciden con esa firma.

Cuando se agrega o elimina un componente, debe actualizar el contenedor de firmas correspondiente.

Ahora la función puede simplemente ir al contenedor de la entidad de la firma y ejecutar la función para cada entidad.

Answer 2

Dependiendo de la proporción de adición / eliminación de componentes en comparación con la coincidencia de firmas, puede intentar crear un tipo de árbol de prefijos que almacene referencias a entidades.

El árbol en sí es estático, solo las hojas que contienen entidades son contenedores construidos en tiempo de ejecución.

De esta manera, al agregar (o eliminar) un componente, solo necesita mover la referencia de la entidad a la hoja correcta.

Al buscar entidades que coincidan con una firma, solo tiene que tomar toda la unión de las hojas que subsumen la firma e iterar sobre ellas. Y como el árbol es (casi) estático, ni siquiera necesita buscar estas hojas.

Otro punto interesante: su conjunto de bits se puede utilizar para representar la ruta en el árbol, por lo que mover una entidad es bastante fácil.

Si el número de componentes induce un número irrealista de hojas, y no se utiliza toda la combinación de componentes, puede reemplazar el árbol con una tabla hash donde el conjunto de bits es la clave y el valor es el conjunto de referencias de entidad.

Eso es más ideas algorítmicas que cosas concretas, pero parece más razonable que iterar sobre el conjunto de entidades.

Answer 3

Otra opción que está un poco influenciada por la idea de @Marwan Burelle.

Cada componente contendrá un contenedor ordenado de entidades que tienen ese componente.

Cuando busque entidades que coincidan con una firma, debe iterar sobre el contenedor de componentes de las entidades.

Agregar o eliminar es O (nlogn) ya que debe ordenarse. pero solo necesita agregarlo / eliminarlo a / desde un solo contenedor que también contendrá menos elementos.

Iterar sobre los elementos es un poco más pesado, ya que es un factor de la cantidad de componentes y el número de entidades en cada componente. Todavía tienes un elemento de multiplicación, pero el número de elementos es nuevamente más pequeño.

Escribí una versión simplificada como POC.

Edición: mi versión anterior tenía algunos errores, ahora espero que estén arreglados.

// Example program
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <functional>
#include <memory>
#include <chrono>
struct ComponentBase
{
};
struct Entity
{
Entity(std::string&& name, uint id)
: _id(id),
_name(name)
{
}
uint _id;
std::string _name;
std::map<uint, std::shared_ptr<ComponentBase>> _components;
};
template <uint ID>
struct Component : public ComponentBase
{
static const uint _id;
static std::map<uint, Entity*> _entities;
};
template <uint ID>
std::map<uint, Entity*> Component<ID>::_entities;
template <uint ID>
const uint Component<ID>::_id = ID;
using Comp0 = Component<0>;
using Comp1 = Component<1>;
using Comp2 = Component<2>;
using Comp3 = Component<3>;
template <typename ...TComponents>
struct Enumerator
{
};
template <typename TComponent>
struct Enumerator<TComponent>
{
std::map<uint, Entity*>::iterator it;
Enumerator()
{
it = TComponent::_entities.begin();
}
bool AllMoveTo(Entity& entity)
{
while (HasNext() && Current()->_id < entity._id)
{
MoveNext();
}
if (!Current())
return false;
return Current()->_id == entity._id;
}
bool HasNext() const
{
auto it_next = it;
++it_next;
bool has_next = it_next != TComponent::_entities.end();
return has_next;
}
void MoveNext()
{
++it;
}
Entity* Current() const
{
return it != TComponent::_entities.end() ? it->second : nullptr;
}
};
template <typename TComponent, typename ...TComponents>
struct Enumerator<TComponent, TComponents...>
{
std::map<uint, Entity*>::iterator it;
Enumerator<TComponents...> rest;
Enumerator()
{
it = TComponent::_entities.begin();
}
bool AllMoveTo(Entity& entity)
{
if (!rest.AllMoveTo(entity))
return false;
while (HasNext() && Current()->_id < entity._id)
{
MoveNext();
}
if (!Current())
return false;
return Current()->_id == entity._id;
}
bool HasNext() const
{
auto it_next = it;
++it_next;
bool has_next = it_next != TComponent::_entities.end();
return has_next;
}
void MoveNext()
{
++it;
}
Entity* Current() const
{
return it != TComponent::_entities.end() ? it->second : nullptr;
}
};
template <typename ...TComponents>
struct Requires
{
};
template <typename TComponent>
struct Requires<TComponent>
{
static void run_on_matching_entries(const std::function<void(Entity&)>& fun)
{
for (Enumerator<TComponent> enumerator; enumerator.Current(); enumerator.MoveNext())
{
if (!enumerator.AllMoveTo(*enumerator.Current()))
continue;
fun(*enumerator.Current());
}
}
};
template <typename TComponent, typename ...TComponents>
struct Requires<TComponent, TComponents...>
{
static void run_on_matching_entries(const std::function<void(Entity&)>& fun)
{
for (Enumerator<TComponent, TComponents...> enumerator; enumerator.Current(); enumerator.MoveNext())
{
if (!enumerator.AllMoveTo(*enumerator.Current()))
continue;
fun(*enumerator.Current());
}
}
};
using Sig0 = Requires<Comp0>;
using Sig1 = Requires<Comp1, Comp3>;
using Sig2 = Requires<Comp1, Comp2, Comp3>;
struct Manager
{
uint _next_entity_id;
Manager()
{
_next_entity_id = 0;
}
Entity createEntity()
{
uint id = _next_entity_id++;
return Entity("entity " + std::to_string(id), id);
};
template <typename Component>
void add(Entity& e)
{
e._components[Component::_id] = std::make_shared<Component>();
Component::_entities.emplace(e._id, &e);
}
template <typename Component>
void remove(Entity& e)
{
e._components.erase(Component::_id);
Component::_entities.erase(e._id);
}
template <typename Signature>
void for_entities_with_signature(const std::function<void(Entity&)>& fun)
{
Signature::run_on_matching_entries(fun);
}
};
int main()
{
Manager m;
uint item_count = 100000;
std::vector<Entity> entities;
for (size_t item = 0; item < item_count; ++item)
{
entities.push_back(m.createEntity());
}
for (size_t item = 0; item < item_count; ++item)
{
//if (rand() % 2 == 0)
m.add<Comp0>(entities[item]);
//if (rand() % 2 == 0)
m.add<Comp1>(entities[item]);
//if (rand() % 2 == 0)
m.add<Comp2>(entities[item]);
//if (rand() % 2 == 0)
m.add<Comp3>(entities[item]);
}
size_t sig0_count = 0;
size_t sig1_count = 0;
size_t sig2_count = 0;
auto start = std::chrono::system_clock::now();
m.for_entities_with_signature<Sig0>([&](Entity& e) { ++sig0_count; });
m.for_entities_with_signature<Sig1>([&](Entity& e) { ++sig1_count; });
m.for_entities_with_signature<Sig2>([&](Entity& e) { ++sig2_count; });
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
std::cout << "first run took " << duration.count() << " milliseconds: " << sig0_count << " " << sig1_count << " " << sig2_count << std::endl;
for (size_t item = 0; item < item_count; ++item)
{
if (rand() % 2 == 0)
m.remove<Comp0>(entities[item]);
if (rand() % 2 == 0)
m.remove<Comp1>(entities[item]);
if (rand() % 2 == 0)
m.remove<Comp2>(entities[item]);
if (rand() % 2 == 0)
m.remove<Comp3>(entities[item]);
}
sig0_count = sig1_count = sig2_count = 0;
start = std::chrono::system_clock::now();
m.for_entities_with_signature<Sig0>([&](Entity& e) { ++sig0_count; });
m.for_entities_with_signature<Sig1>([&](Entity& e) { ++sig1_count; });
m.for_entities_with_signature<Sig2>([&](Entity& e) { ++sig2_count; });
duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
std::cout << "second run took " << duration.count() << " milliseconds: " << sig0_count << " " << sig1_count << " " << sig2_count << std::endl;
}

Answer 4

Para la coincidencia, ¿está comprobando cada tipo de componente un bit cada vez? Debería poder navegar a través de las entidades verificando si todos los componentes de una firma están disponibles en una instrucción contra una máscara de bits.

Por ejemplo, podríamos usar:

const uint64_t signature = 0xD; // 0b1101

... para verificar la presencia de los componentes 0, 1 y 3.

for(const auto& ent: entities)
{
if (ent.components & signature)
// the entity has components 0, 1, and 3.
}

Eso debería ser rápido si las entidades se almacenan de forma contigua en una matriz. No importa, en cuanto al rendimiento, si está comprobando 3 tipos de componentes o 50 tipos de componentes a la vez. No uso este tipo de representante para mi ECS, pero definitivamente esto no debería tomar mucho tiempo, incluso si tiene un millón de entidades. Eso debería completarse en un abrir y cerrar de ojos.

Es la forma práctica más rápida que se puede obtener para ver qué entidades proporcionan un conjunto dado de componentes mientras se almacena la cantidad mínima de estado. La única razón por la que no uso este representante es porque mi ECS gira en torno a una arquitectura de complementos donde la gente registra un nuevo componente. tipos y sistemas en tiempo de ejecución a través de complementos y scripts, por lo que no puedo anticipar efectivamente un límite superior sobre cuántos tipos de componentes habrá. Si tuviera un sistema de tiempo de compilación como el tuyo que está diseñado para anticipar todo esto de antemano, entonces definitivamente creo que este es el camino a seguir. Simplemente no marque un poco a la vez.

Debería poder procesar fácilmente un millón de componentes varios cientos de veces por segundo con la solución anterior. Hay personas que logran tasas similares al aplicar filtros de imagen de la CPU que procesan muchos píxeles multiplicados por tantos por segundo, y esos filtros tienen mucho más trabajo que hacer que un solo bitwise and y una sola rama por iteración.

Tampoco me molestaría en almacenar este bucle secuencial súper barato a menos que tenga algunos sistemas que solo quieran procesar, por ejemplo, una docena de un millón de entidades. Pero en ese momento puede potencialmente almacenar en caché esos escenarios de casos raros en los que un sistema apenas procesa las entidades locales en lugar de tratar de almacenar en caché las cosas de forma centralizada. Solo asegúrese de que los sistemas que estén interesados ​​puedan averiguar cuándo se agregan o eliminan entidades del sistema para que puedan invalidar su caché local.

Además, no necesariamente necesita una metaprogramación sofisticada para estas firmas. Al final del día, realmente no está guardando nada utilizando la metaprogramación de plantillas, ya que no puede evitar recorrer las entidades que comprueban algo, ya que la lista de entidades solo se conoce en tiempo de ejecución. No hay realmente nada teórico que valga la pena optimizar en tiempo de compilación aquí. Usted puede simplemente hacer como

static const uint64_t motion_id = 1 << 0;
static const uint64_t sprite_id = 1 << 1;
static const uint64_t sound_id = 1 << 2;
static const uint64_t particle_id = 1 << 3;
...
// Signature to check for entities with motion, sprite, and
// particle components.
static const uint64_t sig = motion_id | sprite_id | particle_id;

Si usa bits asociados a la entidad para indicar qué componentes tiene una entidad, recomiendo establecer un límite superior en el número total de tipos de componentes que su sistema puede manejar (por ejemplo, 64 es probablemente suficiente, 128 es un barco) para que pueda compruebe los componentes contra las máscaras de bits como estas de una sola vez.

¿qué sucede si una llamada a forEntitiesMatching elimina o agrega un componente a una entidad?

Si, por ejemplo, tiene un sistema que agrega / elimina componentes a cada fotograma, en primer lugar no me molestaría en almacenar en caché. La versión anterior debería ser capaz de recorrer entidades súper rápido.

El peor de los casos de realizar un bucle en todas las entidades de forma secuencial es si tiene un sistema que, digamos, solo va a procesar el 3% de esas entidades. Si el diseño de su motor tiene sistemas como ese, entonces es un poco incómodo, pero puede notificarles cuando se agreguen / eliminen componentes en los que estén específicamente interesados, en qué momento pueden invalidar su caché de entidades y luego volver a almacenar en caché la próxima vez que el sistema comienza. Esperamos que no tenga un sistema que agregue / elimine componentes en cada fotograma de los tipos que son ese 3% de minoría de componentes. Sin embargo, si tiene el peor de los casos, probablemente sea mejor no molestarse en almacenar en caché. No hay ningún uso para un caché que simplemente se va a descartar en cada fotograma, y ​​tratar de actualizarlo de una manera elegante probablemente no le reduzca mucho.

Otros sistemas que, digamos, procesan el 50% o más de las entidades probablemente ni siquiera deberían molestar en el almacenamiento en caché, ya que el nivel de direccionamiento indirecto probablemente no valga la pena solo en arar a través de todas las entidades de forma secuencial y hacer una gran cantidad de bitwise and sobre cada .

Answer 5

Respecto al pseudo código:

for(auto& e : entities)
for(const auto& s : signatures)
if((e.bitset & s.bitset) == s.bitset)
callUserFunction(e);

No estoy seguro de por qué necesita el bucle interno.

Si tiene la firma solicitada en la función, puede obtener el conjunto de bits de esa firma y no hay necesidad de iterar sobre todas las firmas.

template <typename T>
void forEntitiesMatching(const std::function<void(Entity& e)>& fun)
{
for(auto& e : entities)
if((e.bitset & T::get_bitset()) == T::get_bitset())
fun(e);
}

Answer 6

Tener un conjunto de enteros dispersos por tipo de firma es la mejor solución teórica (en términos de complejidad de tiempo) .

La estructura de datos del conjunto de enteros dispersos permite una iteración contigua eficiente de O(N) sobre los enteros almacenados, la inserción / eliminación de enteros de O(1) consulta de O(1) para un entero específico.

El conjunto entero disperso por firma almacenaría todos los ID de entidad asociados con esa firma específica.

Ejemplo: Diana , una biblioteca de código abierto de C y C ++ ECS, utiliza un conjunto de enteros dispersos para realizar un seguimiento de las entidades en los sistemas. Cada sistema tiene su propia instancia de conjunto de enteros dispersos .