Différences

Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.

--- ecs [2015/06/13 01:15]
gbdivers
+++ ecs [2025/02/01 04:33] (Version actuelle)
gbdivers
@@ Ligne 1: / Ligne 1: @@
+https://github.com/SanderMertens/ecs-faq
 ====== L'Entity Component System - Qu'est ce que c'est et comment bien s'en servir ? ======
@@ Ligne 12: / Ligne 14: @@
 Il ne faut pas se faire d'illusions, créer un jeu est une tâche très complexe et très longue. Les blogs relatant les mauvaises expériences sont nombreuses (lire en particulier la série d'articles [[http://conquerirlemonde.com/blog/index-des-articles/|Erreurs classiques des créateurs de jeux vidéo amateurs]].
-Un moteur de jeux est quelque chose de complexe en soi. La meilleure approche pour créer un jeu est d'utiliser un moteur de jeux existant, qui vous propose déjà une architecture prête à l'utilisation. Il existe plusieurs [[http://fr.wikipedia.org/wiki/Liste_de_moteurs_de_jeu|moteurs de jeux]] gratuits très bien pour débuter et pour aller plus loin. Si votre objectif est la création d'un jeu, c'est cette approche qu'il faut suivre. Ne rejeter surtout pas les moteurs de jeux existants pour de mauvaises raisons, comme "je veux tout créer moi même pour avoir plus de liberté". En pratique, si vous faites cela, vous passerez plus de temps à régler les problèmes d'implémentation de votre moteur de jeux plutôt que de réellement concevoir votre jeu.
+Un moteur de jeux est quelque chose de complexe en soi. La meilleure approche pour créer un jeu est d'utiliser un moteur de jeux existant, qui vous propose déjà une architecture prête à l'utilisation. Il en existe plusieurs [[http://fr.wikipedia.org/wiki/Liste_de_moteurs_de_jeu|moteurs de jeux]] gratuits, très bons pour débuter et pour aller plus loin. Si votre objectif est la création d'un jeu, c'est cette approche qu'il vous faut suivre. Ne rejetez surtout pas les moteurs de jeux existants pour de mauvaises raisons, comme "je veux tout créer moi même pour avoir plus de liberté". En pratique, si vous faites cela, vous passerez plus de temps à régler les problèmes d'implémentation de votre moteur de jeux plutôt que de réellement concevoir votre jeu.
-Cet article présente une approche possible pour concevoir un moteur de jeux, appelée "Entity-Component-System" ou ECS. Il n'est pas possible de présenter toutes les problématiques que l'on peut rencontrer avec l'ECS, ni aborder toutes les implémentations possibles de l'ECS pour tous les types de jeux possibles. Le but est avant tout de vous donner les bases de compréhension de cette architecture et des pistes de réflexion pour l'adapter selon vos besoins.
+Cet article présente une approche possible pour concevoir un moteur de jeux, appelée "Entity-Component-System" ou ECS. Il n'est pas possible de présenter toutes les problématiques que l'on peut rencontrer avec l'ECS, ni aborder toutes les implémentations possibles de l'ECS pour tous les types de jeux possibles. Le but est avant tout de vous donner les bases de compréhension de cette architecture et des pistes de réflexions pour l'adapter selon vos besoins.
-Ce tutoriel ce décompose en quatre parties :
+Ce tutoriel se décompose en quatre parties :
-  * la première partie décrit les approches classiques utilisées dans la conception des jeux ;
+  * les approches classiques utilisées dans la conception des jeux ;
-  * vous verrez ensuite la théorie de l'ECS et les problématiques de son implémentation ;
+  * la théorie de l'ECS et les problématiques de son implémentation ;
-  * la troisième partie aborde plus en détail certains besoins de jeux (moteur graphique, intelligence artificielle, gestion des entées, etc) dans le cadre d'un ECS ;
+  * les besoins détaillés de jeux (moteur graphique, intelligence artificielle, gestion des entées, etc) dans le cadre d'un ECS ;
-  * la dernière partie sera une réflexion plus large sur la possibilité d'utiliser l'approche ECS en dehors des jeux vidéos.
+  * une réflexion plus large sur la possibilité d'utiliser l'approche ECS en dehors des jeux vidéos.
 ===== Critères de qualités et approches historiques =====
-Avant de commencer a étudier le fonctionnement des ECS, il est important de rappeler les critères de qualités logiciel qui permettent d'orienter les choix de design des moteurs de jeux et de survoler les problèmes présentés par les approches classiques des moteurs de jeux.
+Avant de commencer à étudier le fonctionnement des ECS, il est important de rappeler les critères de qualités logicielles qui permettent d'orienter les choix de design des moteurs de jeux et de survoler les problèmes présentés par les approches classiques des moteurs de jeux.
 ==== Qualités d'un moteur de jeux ====
@@ Ligne 33: / Ligne 35: @@
 === Performances ===
-Ce point dépend fortement du type de jeux que l'on souhaite créer et les plateformes sur les quelles le jeu sera utilisé. Une attention particulière doit être portée si on souhaite créer un jeu complexe dans un univers 3D riche. La réalisation de rendus 3D réalistes consomme énormément de ressources de la carte graphique, tandis que des fonctionnalités comme l'intelligence artificielle ou la simulations physiques réalistes (mouvements des cheveux et des vêtements, environnements destructibles) consommeront plus le processeur central. Même un simple jeu 2D peut se révéler être un challenge en termes d'optimisation des performances si l'on souhaite le faire tourner sur un téléphone mobile ou une box connectée à une télévision.
+Ce point dépend fortement du type de jeux que l'on souhaite créer et les plateformes sur lesquelles le jeu sera utilisé. Une attention particulière doit être portée si on souhaite créer un jeu complexe dans un univers 3D riche. La réalisation de rendus 3D réalistes consomme énormément de ressources de la carte graphique, tandis que des fonctionnalités comme l'intelligence artificielle ou des simulations physiques réalistes (mouvements des cheveux et des vêtements, environnements destructibles) consommeront davantage le processeur central. Même un simple jeu 2D peut se révéler être un challenge en termes d'optimisation des performances si l'on souhaite le faire tourner sur un téléphone mobile ou une box connectée à une télévision.
 === Maintenabilité et évolutivité ===
-La maintenabilité désigne la facilité à corriger les problèmes existants et l'évolutivité à ajouter de nouvelles fonctionnalités. L'un des plus grosses erreurs que l'on rencontre dans les projets de jeux amateurs est probablement l'envie de créer un jeu complet et riche dès le départ. Les amateurs ont généralement une vision de ce qu'ils veulent obtenir (plus ou moins), mais pas de la démarche correcte pour y parvenir.
+La maintenabilité désigne la facilité à corriger les problèmes existants et l'évolutivité à ajouter de nouvelles fonctionnalités. L'une des plus grosses erreurs que l'on rencontre dans les projets de jeux amateurs est probablement l'envie de créer un jeu complet et riche dès le départ. Les amateurs ont généralement une vision de ce qu'ils veulent obtenir (plus ou moins), mais pas de la démarche correcte pour y parvenir.
-Dans le développement logiciel classique, la question en se pose généralement pas. Il est nécessaire de livrer des versions intermédiaires du logiciel, fonctionnelles mais ne contenant pas la totalité des fonctionnalités. Chaque nouvelle livraison corrigera les bugs de la version précédente et ajoutera de nouvelles fonctionnalités. Cette différence de démarche peut être résumée par la figure suivante :
+Dans le développement logiciel classique, la question ne se pose généralement pas. Il est nécessaire de livrer des versions intermédiaires du logiciel, fonctionnelles mais ne contenant pas la totalité des fonctionnalités. Chaque nouvelle livraison corrigera les bugs de la version précédente et ajoutera de nouvelles fonctionnalités. Cette différence de démarche peut être résumée par la figure suivante :
 {{ https://pbs.twimg.com/media/BylDyxyIcAAg30b.jpg }}
@@ Ligne 49: / Ligne 51: @@
 Ces critères de qualité logiciel ne sont pas rappelés sans raison. Lorsque l'on doit faire des choix sur la conception a adopter pour concevoir un moteur de jeux, il est nécessaire de conserver ces critères en tête. Dans un monde idéal, on pourrait choisir de respecter tous les critères de qualité et de les appliquer à 100%. Dans le monde réel, ce n'est pas possible.
-En particulier, le critère de performances s'oppose souvent au critère de maintenabilité. Une autre erreur classique est de recherche en premier lieu la performance maximale, quitte pour cela à sacrifier la lisibilité du code et d’augmenter les risques d'erreur. Ainsi, en C++, on rencontre souvent du code //old-school// (mélange de C++ et de C bas niveau), ce qui pose régulièrement des problèmes d'exécution (c'est probablement le pire type d'erreurs, puisque ces erreurs ne produisent pas de messages d'erreurs claires, produisent un comportement indéterminé non reproductible, il est parfois très difficile de trouver la source de l'erreur).
+En particulier, le critère de performances s'oppose souvent au critère de maintenabilité. Une autre erreur classique est de recherche en premier lieu la performance maximale, quitte à sacrifier la lisibilité du code et augmenter les risques d'erreur. Ainsi, en C++, on rencontre souvent du code //old-school// (mélange de C++ et de C bas niveau), ce qui pose régulièrement des problèmes d'exécution (c'est probablement le pire type d'erreurs, puisque ces erreurs ne produisent pas de messages d'erreurs claires, produisent un comportement indéterminé non reproductible, il est parfois très difficile de trouver la source de l'erreur).
 Ceux qui suivent cette approche font deux erreurs :
@@ Ligne 76: / Ligne 78: @@
 Les approches possibles pour créer un jeu sont nombreuses, en particulier à l'époque où l'on n'avait pas encore pensé à créer des moteurs de jeux réutilisables et où chaque jeu repartait de zéro. Le but de cette partie n'est pas d'être exhaustive, nous allons présenter que les approches objets les plus classiques.
-Remarque : ces approches ne sont pas forcement nommées de manière aussi formelle que ce que nous présentons ici. Ces noms ont été choisit pour faciliter la description.
+Remarque : ces approches ne sont pas forcément nommées de manière aussi formelle que ce que nous présentons ici. Ces noms ont été choisis pour faciliter la description.
 === Hiérarchie profonde d'héritages (Deep Inheritance Hierarchy Approach) ===
@@ Ligne 90: / Ligne 92: @@
 (Source : http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/)
-En termes d'implémentation, cette approche est relativement simple à concevoir. Il suffit de regrouper les méthodes et attributs communs dans une classe et de dériver de cette classe. Tous les objets sont parcouru par une boucle, qui appelle une fonction commune de mise à jour (classiquement, on appelle cette fonction ''update'').
+En termes d'implémentation, cette approche est relativement simple à concevoir. Il suffit de regrouper les méthodes et attributs communs dans une classe et de dériver de cette classe. Tous les objets sont parcourus par une boucle, qui appelle une fonction commune de mise à jour (classiquement, on appelle cette fonction ''update'').
 <code cpp>
@@ Ligne 156: / Ligne 158: @@
 </code>
-Cette approche peut sembler intéressante en termes de non répétition du code (si un code est commun à deux classe, il suffit de le déplacer dans la classe parente) et d'évolutivité (si on veut ajouter une nouvelle classe, il suffit de la faire hériter d'une classe existante).
+Cette approche peut sembler intéressante en termes de non répétition du code (si un code est commun à deux classes, il suffit de le déplacer dans la classe parente) et d'évolutivité (si on veut ajouter une nouvelle classe, il suffit de la faire hériter d'une classe existante).
 En pratique, ce n'est pas le cas. Pour pouvoir déplacer un code commun entre deux classes dans une classe parente, encore faut-il qu'il existe une classe parente. Il y a toujours la possibilité de remonter jusque la classe ''Object'', mais on se retrouve au final à avoir une super-classe (on parle de //god-object//) qui remplit tous les rôles. Ce type de classe entre en violation directement des principe de responsabilité unique (//SRP - Single Responsabilty Principle//) et ouvert-fermé (//OCP - Open-Close Principle//) :
@@ Ligne 426: / Ligne 428: @@
 Nous allons voir dans un premier temps a quoi correspond cette approche et ce qui la distingue de la programmation objet. Nous verrons ensuite comment implémenter concrètement un ECS en C++.
+==== Data-driven programming ====
+Importance du DDP? Exemple pour illustrer avec comparaison avec la complexité algo
+Vous avez peut etre vu la notation O(n) pour la complexité algo.
+. O(n) avec constante, depend de matos. Certains algo vont utiliser des fonctionnalités du CPU et donc etre plus performant, meme en ayant une O(n) plus mauvaise. En particulier vectorisation, mem cache, GPU, etc. qui fait que certains algos ont un moins bon O(n) mais sont plus performant en pratique (meilleur utilisation des caches, meilleur utilisation des threads, etc)
+. O(n) mesure un comportement asymptomatique, donc n->infini. Mais en pratique, ce n'est jamais infini, et dans dans un domaine particulier de n, un algo peut etre plus performant. Par exemple, algo plus performant sur petite taille de n. Un exemple concret, certains algo de tri utilisent un methode pour faire un premier tri en bloc de taille N, puis utilisent un autre algo pour trier chaque block (de petite taille).
+. O(n) est une mesure de la complexité. Autre : big-theta, big-omega, etc. https://en.wikipedia.org/wiki/Big_O_notation. Pour rappel, avec une liste spécifique de valeurs de taille n, il y aura un temps mesuré t. Chaque liste de valeurs va donner des temps différents. Pour chaque algo, il y a une donc un t_min et un t_max pour chaque valeur de n et l'ensemble des mesures de perfs d'un algo est un enveloppe. Les notations O, theto, omega, etc. mesure un parametre particulier de cette envoloppe : par exemple le plus mauvais cas, le cas moyen, etc.
+Du coup, pour des données reels dans un cas d'utilisation particulier, il est possible de ne pas être dans l'enveloppe complete, mais dans un sous groupe, et dans ce cas, la mesure de complexité peut etre mauvais.  Par exemple, certains algos de tris sont plus efficace quand la majorité des valeurs sont deja trié et qu'il y a peu de valeur a déplacer (ce qui arrive par exemple quand vous ajoutez de nouvelles données dans un tableau deja trié).
+Pour resumer, il y a donc des caractéristiques sur les donne2es dans un contexte et cas d'utilisation particulier, qui peu influencer le choix de l'algo, le choix des structures de données, etc. Le principe de data driven dev est d'optimiser le choix des algos par rapport aux donne2es.
+Note : c'est important ausi dans les tests. On test souvent en utilisant des valeurs particuliere ou des valeurs aleatoire, mais cela peut etre important aussi de faire des tests avec des données reelles.
 ==== Différentes approches pour concevoir les choses ====
@@ Ligne 827: / Ligne 848: @@
 </code>
-=== A trier ===
+=== À trier ===
-Eviter de parcourir tous les composants. Comment parcourir une sous-liste de composant ? D'entité ?
+  * Éviter de parcourir tous les composants. Comment parcourir une sous-liste de composants ? D'entité ;
+    * Exemple : collision. Quadtree, octree, bounding box, etc. (spatial partitioning) ;
+  * sauvegarder l'état du jeu ? (liste des entités, des composants) Passer les informations via réseau ? (sérialisation) ;
+  * hiérarchie d'entités : relation entre plusieurs entités liées
-Exemple : collision. Quadtree, octree, bounding box, etc. (spatial partitioning)
+Exemple: 3 persos A (marchent à côté du char), B (dans le char), C (dans la tourelle), 1 char avec tourelle.
+^  Entité    ^  Composant position relative  ^  Composant "Transporte quelque chose"  ^
+|  A         |  x_a, y_a                     |                                        |
+|  B         |  x_b, y_b                     |  char                                  |
+|  C         |  x_c, y_c                     |  tour                                  |
+|  char      |  x_char, y_char               |                                        |
+|  tourelle  |  x_tour, y_tour               |  char                                  |
-  * sauvegarder l'état du jeu ? (liste des entités, des composants) Passer les informations via réseau ? (sérialisation)
+Au final, la position absolue (X, Y) des objets dans le monde est calculée en fonction des positions relatives et des dépendances :
+  * X_char = x_char
+  * X_tour = x_tour + x_char
+  * X_A = x_a
+  * X_B = x_b + x_char
+  * X_C = x_c + X_tour = x_c + x_tour + x_char
+===== Proposition d'implémentation =====
+<code cpp main.cpp>
+#include <cassert>
+#include <iostream>
+#include <vector>
+#include <algorithm>
+/******* Entity *******/
+using Entity = size_t;
+/******* Entities *******/
+class Entities {
+public:
+    Entities(size_t size = 1000);
+    Entity create();
+    void remove(Entity entity);
+    void print() const;
+private:
+    std::vector<Entity> m_entities{};           // sorted array (use std::set?)
+};
+Entities::Entities(size_t size) {
+    m_entities.reserve(size);
+}
+Entity Entities::create() {
+    const auto it = std::adjacent_find(begin(m_entities), end(m_entities),
+        [](Entity lhs, Entity rhs){ return (lhs+1 != rhs); });
+    if (it == end(m_entities)) {
+        m_entities.push_back(m_entities.size());
+        return m_entities.back();
+    } else {
+        const auto result = m_entities.insert(it+1, (*it)+1);
+        return *result;
+    }
+}
+void Entities::remove(Entity entity) {
+    const auto it = std::find(begin(m_entities), end(m_entities), entity);
+    if (it != end(m_entities)) {
+        m_entities.erase(it);
+    }
+}
+void Entities::print() const {
+    for(auto i: m_entities) {
+        std::cout << i << ' ';
+    };
+    std::cout << std::endl;
+}
+/******* Component *******/
+class Component {
+protected:
+    Component(Entity entity);          // disable instanciation of base Component
+public:
+    Entity entity() const;
+private:
+    Entity m_entity{};
+};
+Component::Component(Entity entity) : m_entity(entity) {
+}
+Entity Component::entity() const {
+    return m_entity;
+}
+struct PositionComponent : public Component {
+    int x{};
+    int y{};
+};
+struct StateComponent : public Component {
+    enum class State { Waiting, Walking, Running, Dead };
+    State state { Waiting };
+};
+/******* Components *******/
+template<class ConcretComponent>
+class Components {
+public:
+    Components(size_t size = 1000);
+    ConcretComponent& create(Entity entity);
+    void remove(Entity entity);
+protected:                                          // can add algos in derived classes
+    std::vector<ConcretComponent> m_components{};   // not sorted array
+};
+template<class ConcretComponent>
+Components::Components(size_t size) {
+    m_components.reserve(size);
+}
+template<class ConcretComponent>
+ConcretComponent& Components::create(Entity entity) {
+    m_components.push_back(ConcretComponent(entity));
+}
+template<class ConcretComponent>
+void Components::remove(Entity entity) {
+    std::remove_if(begin(m_components), end(m_components),
+        [entity](const ConcretComponent &component){ return (component.entity() == entity); });
+}
+/******* System *******/
+class System {
+public:
+private:
+    Components<T> m_components;
+}
+class System2 {
+public:
+    System2(Components<T>& attachedComponents);
+private:
+    Components<T>& m_components;
+}
+/******* Main *******/
+int main() {
+    // entities
+    Entities entities;
+    auto me = entities.create();
+    auto you = entities.create();
+    entities.print();
+    std::vector<Entity> badGuys;
+    for(auto i=0; i<10; ++i) { badGuys.push_back(entities.create()); }
+    entities.print();
+    entities.remove(you); // you're killed!!!
+    entities.print();
+    you = entities.create(); // but you're a survivor
+    entities.print();
+}
+</code>
 ===== Éléments de jeux appliqués à l'ECS =====
@@ Ligne 938: / Ligne 1119: @@
   * https://www.youtube.com/watch?v=WpkDN78P884
   * http://www.drdobbs.com/cpp/building-your-own-plugin-framework-part/204202899
+  * http://gamedev.stackexchange.com/questions/58693/grouping-entities-of-the-same-component-set-into-linear-memory
+  * http://gamedev.stackexchange.com/questions/31473/what-is-the-role-of-systems-in-a-component-based-entity-architecture/31491#31491
+  * https://tsprojectsblog.wordpress.com/
+{{:ecs_cache.png?200|}}
+https://github.com/skypjack/entt
 ===== Conclusion =====

C++, Qt, OpenGL, CUDA

Outils d'utilisateurs

Outils du Site

Différences

Outils de la Page