Discussion :

[r0d]

Bonjour,

dans le cadre du développement d'une variante du jeu de la vie, je me pose tout un tas de questions existentielles.

Voici une brève description de ce que je voudrais implémenter:
Je voudrais un nombre N d'entités, chacune indépendante. Chaque entité aurait un comportement qui serait défini par des suites d'états. Par exemple, une entité donnée pourrait passer de l'état "se déplacer", puis à l'état "attendre", puis à l'état "se téléporter", puis encore à "attendre", puis à "clignoter", etc. L'entité ne peut être dans qu'un seul état à la fois.

Nous ne nous préoccuperons ici que de l'aspect "data", ou "modèle", c'est à dire que l'on ne s'occupera pas de l'affichage. Mais déjà, nous voyons deux mot importants: entité et état.

A première vue, mes entités doivent être des instances uniques. Il s'agira donc d'une classe à sémantique d'entité. Êtes-vous d'accord sur ce point?

Ensuite, puisque ces entités vont avoir des états, il va me falloir une machine à état. La question que je me pose à ce sujet, c'est qu'à première vue, il faudrait une machine à état par entité. Ce qui peut poser des problèmes de performances si on atteint un grand nombre d'entité. Or je ne vois pas comment une seule machine à état peut gérer les états d'entités indépendantes. Avez-vous des idées sur ce point?

[therwald]

Si les états en eux-mêmes sont stateless, peut-être peux-tu avoir en réalité une instance de machine à état par état de la machine (suis-je clair? ) et n'avoir pour tes entités qu'une référence à l'état approprié?

[r0d]

Je ne suis pas certain d'avoir bien compris, en particulier ça:

peut-être peux-tu avoir en réalité une instance de machine à état par état de la machine

Mais j'ai oublié de spécifier une chose: mes états ont des données. Par exemple, l'état "se déplacer" aura des valeurs concernant la direction et la vitesse, valeurs qui seront différentes selon les entités et qui peuvent même, pour la même entité, varier dans le temps (par exemple, une même entité pourra changer de direction ou de vitesse tout en restant dans le même état).

[ternel]

Une machine à état se code de deux manières:
soit par une classe de machine, soit par une variante de la liste chainée.

Considérons la machine à état explicite.

Dans les cours théoriques, la machine à état avance pas à pas, généralement avec une entrée à chaque itération.
L'interface d'utilisation est alors la suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T, typename Id=int>
struct machine {
    typedef Id (*selecteur)(T const&);
    void avancer(T const& t) const {
        courant = (etats.find(courant)->second)(t);
    }
    machine(){}
    ~machine(){}
    etat(Id id, selecteur f) {etats.insert(id, f);}
private:
    map<Id, selecteur> etats;
    mutable Id courant;
};

Cela dit, la plupart du temps, tu as aussi besoin de savoir si la machine est ou non dans un etat terminal.

Par ailleurs, si une machine lit des caracteres à chaque pas, elle peut servir à coder des grammaires régulières

Voici un exemple (simpliste) d'usage:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <algorithm>
#include <list>
#include <map>
 
struct machine_error{};
 
template <typename T, typename Id=int>
class machine {
public:
	typedef Id (*selecteur)(T const&);
private:
	typedef std::map<Id, selecteur> etats_t;
 
public:
	machine(Id id, selecteur initialstate, bool final = false) : courant(id) {
		etat(id, initialstate, final);
	}
	~machine(){}
 
	void etat(Id id, selecteur f, bool final = false) {
		etats.insert( typename etats_t::value_type(id, f) );
		if(final) finaux.push_back(id);
	}
 
	void avancer(T const& t) const {
		typename etats_t::const_iterator it = etats.find(courant);
		if (it==etats.end()) throw machine_error();
		courant = (it->second)(t);
	}
 
	bool final() const {
		return std::count(finaux.begin(), finaux.end(), courant) != 0;
	}
 
private:
	std::map<Id, selecteur> etats;
	std::list<Id> finaux;
	mutable Id courant;
};
 
template <typename Id>
class machine<void, Id> {
public:
	typedef Id (*selecteur)();
private:
	typedef std::map<Id, selecteur> etats_t;
 
public:
	machine(Id id, selecteur initialstate, bool final = false) : courant(id) {
		etat(id, initialstate, final);
	}
	~machine(){}
 
	void etat(Id id, selecteur f, bool final = false) {
		etats.insert( typename etats_t::value_type(id, f) );
		if(final) finaux.push_back(id);
	}
 
	void avancer() const {
		typename etats_t::const_iterator it = etats.find(courant);
		if (it==etats.end()) throw machine_error();
		courant = (it->second)();
	}
 
	bool final() const {
		return std::count(finaux.begin(), finaux.end(), courant) != 0;
	}
 
 
private:
	std::map<Id, selecteur> etats;
	std::list<Id> finaux;
	mutable Id courant;
};
 
#include <iostream>
using namespace std;
 
namespace states {
	int todo;
	int begin() {
		todo = 10;
		cout<<"start"<<endl;
		return 1;
	}
	int etat1() {
		cout<<"exercise"<<endl;
		return 2;
	}
	int etat2() {
		cout<<"done"<<endl;
		return --todo ? 1 : 3;
	}
	int close() {
		cout<<"finish"<<endl;
		return 3;
	}
}
 
int main() {
	machine<void> m(0, states::begin);
	m.etat(1, states::etat1);
	m.etat(2, states::etat2);
	m.etat(3, states::close, true);
	try {
		while (!m.final()) {
			m.avancer();
		}
	} catch (machine_error& e) {
		cerr << "machine error" << endl;
	}
}

[therwald]

Si les états ont des données internes, spécifiques...alors ce que je disais ne tient pas. Il faut effectivement que chaque entité ait sa propre machine à états.
Par contre si tu as beaucoup de cellules, plutôt que de représenter chaque cellule par une entité, est-ce que tu ne pourrais pas appliquer tes règles à des matrices de paramètres? Ça élimine le côté entité+machine à état, mais sur traitement massif ça devrait être plus performant,non?

[r0d]

@leternel: En fait, j'ai déjà commencé une implémentation à titre de poc (proof of concept), et j'utilise la machine à état de boost

[ternel]

Vu que j'ai été doublé dans la publication, j'ai un commentaire à faire.

Les états de mon exemple sont simplistes (juste des pointeurs de fonctions), mais on peut aisément améliorer le processus avec des foncteurs (classes définissant operator())

[Klaim]

Bonjour,

dans le cadre du développement d'une variante du jeu de la vie, je me pose tout un tas de questions existentielles.

...


A première vue, mes entités doivent être des instances uniques. Il s'agira donc d'une classe à sémantique d'entité. Êtes-vous d'accord sur ce point?

Non.

Mais alors pas du tout.

Ton entitee peut etre identifiee par un identifiant unique ou un index, mais son etat, lui, a besoin d'avoir une semantique de valeur.
Tu peut utiliser une machine etat si tu veux, mais tu as mieux fait d'avoir un tableau d'etats, qui est parcouru par un algorithm qui ne fais qu'updater.
De ce fait, tu aurais deux tableaux: celui resultant du dernier cycle, et celui qui est une copie du premier, mais qu'on va modifier lors du prochain cycle. (double buffering, swap a la fin de l'update).

Que ce soit pour du jeu video ou du jeu de la vie, c'est quasimment toujours la methode la plus flexible (mais pas forcement la plus evidente a comprendre sans pas mal d'experience et/ou de lecture).

Donc moi je conseille:

1. Sauf si ton algorithm est trop complexe pour extre ecris uniquement en "fonction", oublie la machine etat. OU ALORS fais en une qui ait une semantique de valeur (comme Boost.MSM par exemple): tu fais ta classe MachineEtat avec tous les etats dedans qui manipulent la meme donnee, et tout copiable.

2. T'as mieu fait d'utiliser un identifiant pour sympoliser un objet, et d'avoir tes differents types d'etats dans des tableaux associes a leur type. De cette maniere, il est beaucoup plus facile d'ecrire des algorithms de mise a jour de ces types d'etats pour un cycle unique, ainsi que de potentiellement pouvoir paralleliser certains algos.

Il y a pas mal de documentation sur ce genre d'organization dans les communaute de dev de jeux, cherche "entity component system" par exemple.

[r0d]

Merci Klaim!

Je n'avais pas pensé à regarder du côté des jeux vidéos, mais là c'est bon, rien que sur gamedev.net j'ai trouvé tellement de matière que je vais rapidement trouver toutes les réponses à mes questions.

[PilloBuenaGente]

Bonjour,

Ce principe de "entity component system" se rapproche t-il de la programmation orientée objet ? (Du fait que l'on définisse les objets par leurs comportements)

PS(désolé, ces concepts ne sont pas encore bien clair dans ma tête)

[Klaim]

Non c'est du data-oriented programming - on organise tout autour de "flux" de donnees de maniere a le mettre a jour en "cycles".

En gros, tes composants sont chacun des donnees quasi brutes, ou avec juste peu de fonctions de verifications.
Toutes les instances d'un type de composant sont dans un tableau ce qui fait qu'en memoire tout est ensemble pour ce type la. Par exemple un composant peut etre responsable de tout ce qui est spatial (position + orientation + hitbox) et du coup toutes les instances peuvent etre mises a jour ensemble (mais independamment) en appliquant une fonction qui parcourt le tableau et update chaque instance a la fois, ou bien encore de maniere concurrente puisque chaque composant contiens toutes les donnees dont il a besoin.

En fait c'est plus proche de comment marchent les bases de donnees.

Bref, une fois que tu as des composants pour chaque "role", tu peux composer une entitee en associant des instances de composant a un identifiant unique. Du coup, par exemple, un personnage peut avoir les composants PlayerControl, PhysicalMovingEntity, HealthState, tandis qu'un rocher aura juste PhysicalStaticEntity et qu'un monstre aura PhysicalMovingEntity, HealthState, AIBrain etc.
Le tout est qu'une fois les composants definis, le designer du jeu peut alors constituer son monde d'entitees qui sont donc composees de divers briques, uniquement associees par le meme identifiant.

Le seul souci avec cette technique est que les communications entre composants sont necessairement plus lentes, mais du coup cela conviens tout a fait si elles sont plutot rare (ce qui est le cas de quasimment tous les jeux, en pratique).

Dans le cas du jeu de la vie, si une cellule est definie par sa position et son etat, alors on n'a pas besoin d'avoir une entitee par cellule, mais juste d'un tableau d'etats. Les regles du jeu de la vie sont alors une simple fonction de mise a jour a chaque cycle: on a l'etat du monde avant la mise a jour, (le tableau des etats des cellules) et un autre tableau de meme taille qui contiendra le resultat de la mise a jour. On lance donc une fonction qui parcours chaque cellule, compute l'etat resultant et ecrit le nouvel etat dans le tableau de resultat. Une fois toutes les cellules a jour, on a bien applique les regles pour un cycle. On a plus qu'a recommencer.

Dans les jeux (interactifs) plus compliques, on utilises les memes methodes pour simuler le temps: on a un "timestep" bien precis qui definis le temps reel entre chaque resultat de cycle. De cette maniere, on peut calculer la physique correctement ou avoir un framerate fixe (si la machine est suffisamment puissante pour suivre la cadence demandee - ou que les efforts sont suffisamment reduit pour que ce soit le cas).

Si on veut faire un truc qui ressemble au jeu de la vie, pour un mix de performance et de code correct et simple, on est oblige de passer par la. C'est une forme de simulation, donc il faut organiser les choses de maniere a ce que constituer les cause -> effets soit facile.

La programmation orientee objet est different dans le sens ou on irait vers une logique de composition par heritage, ce qui est tout a fais absurde. Si on fait un type d'entitee par type d'objet dans le monde aussi ca deviens difficile parceque ca cree des hierarchies (ou meme a plat) qui sont difficiles a modifier au fur et a mesure qu'on decouvres ses propres besoins.

D'ou l'utilitee d'avoir un systeme tres flexible et performant.

Peut etre que c'est pas necessaire pour un simple exercice, mais si c'es tpour inventer un truc similaire au jeu de la vie mais un poil plus complexe, c'est tout benef.

Pour clarifier, un peu de code d'exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
template< class ComponentType > 
class ComponentIndex  // ou un autre nom, peut importe
{
public:
 
    ComponentType& find( Id id ); // pour acceder a une instance specifique
 
    template< class TaskType >
    void transform( TaskType&& task )
    {
         for( ComponentType& component : m_components;
              task( component );
    }
 
private:
 
    std::vector<ComponentType> m_components;
};
 
 
class PhysicalMovingObject // un type de composant
{
 // note que ca aurait pu etre juste un struct mais perso je prefere
 // considerer l'interface comme etant la valeur, pas les donnees
public:
    ID id() const; 
    Vector3 position() const;
    Vector3 velocity() const;
    Vector3 orientation() const;
    HitBox hitbox() const;
 
    void move_to( const Vector2& new_pos ); 
    // etc.
 
private:
    //... des donnees
};
 
 
ComponentIndex<PhysicalMovingObject> physical_moving_objects;
 
// acces a l'etat physique du joueur dans le cas d'un jeu ou on veut faire
// un truc particulier unique a une seule instance de composant
auto& player_physical_state = physical_moving_objects.find( player_id );
 
// "appliquer la loi" de deplacement des objets
physical_moving_objects.transform( []( PhysicalMovingObject& object){
    object.move_to( object.position() + object.velocity() );
});
// puis collectionner les collisions
physical_moving_objects.transform( &detect_collisions ); 
 
etc.

C'est pas super complet comme code mais ca peut te donner des indications et surtout va lire des articles sur data-oriented programming et entity-component-systems pour mieu comprendre l'idee.

Note que data-oriented-programming ne veut pas dire qu'on refuse d'utiliser des class....

[r0d]

Et que penses-tu de l'approche "design pattern state"?
C'est à dire, que les états des cellules seraient des classes Etat1, Etat2, ... , qui héritent de EtatBase, et la classe Cellule possède un pointeur vers un état courant qui serait un EtatBase* et que l'on passerait de Etat1 à Etat2, etc...

[Klaim]

Et que penses-tu de l'approche "design pattern state"?
C'est à dire, que les états des cellules seraient des classes Etat1, Etat2, ... , qui héritent de EtatBase, et la classe Cellule possède un pointeur vers un état courant qui serait un EtatBase* et que l'on passerait de Etat1 à Etat2, etc...

Ca depends vraiment de ce que tu veux faire et si les performances sont importantes ou pas.

Si tu peux faire en sorte d'avoir un id qui identifie les differents composants (mix etat+fonction) qui constituent une entitee, alors tu gagnes en parallelization et en coherence du cache, mais tu perds en rapidite si tu dois recuperer souvent (dans la boucle principale) differents composants pour un objets avant de pouvoir faire quelque chose (parceque tu dois faire une recherche par type de composant utilise).

Si tu veux un equilibre plus simple, fais en sortes que tes tableaux de composants aient une taille fixe maximale, ce qui permet alors de ne pas bouger les instances de composants, et par la meme tu peux alors utiliser un pointeur au lieu d'un id. Dans ce cas les acces sont plus rapide, c'est juste moins flexible mais ca peut etre un tres bon compromis si la quantitee de contenu dans le jeu est connue a l'avance. Ce cas peut ressembler a ce que tu decris, je suis pas sur. Globalement une cellule aurait des pointeurs vers ses differents types d'etats. Mais par contre la mise a jour de ces etats doit se passer separement de la mise a jour de la cellule elle-meme, c'est le point le plus important: d'abord tu fais une passe de mise a jour de tous les etats/composants, puis tu fais l'update specifique a une entitee. Comme dis c'est moins flexible (parceque drive par le code, plutot que par les donnees) mais selon les cas ca peut mieu coller. Par contre je comprends pas en quoi l'heritage aurait un quelconque interet.

Note qu'ici quand je parle d'etat, je parle de different types d'etats qui constituent l'etat complet. Par exemple, PhysicalMovingObject contiens des infos de deplacement, positionnement, hitbox, ainsi que des fonctions pour manipuler tout ca. C'est pas une FSM parce l'etat est pas forcemment mis dans des "cases" d'etats, mais c'est la meme idee a haut niveau. Si un des composant est de l'IA, peut etre que ce composant sera implemente avec une machine etat.

Le tout est de separer un max comment tu geres tes composants (constituant une entitee) et les entitees specifiques (qu'elles soient des id ou des types). Si l'entitee est un identifiant (et donc tous les composants qui ont cet identifiant) c'est beaucoup plus facile de composer de nouvelles entitees a partir de donnees externe (des fichiers script, du xml, whatever). Si tes entitees ont un type C++, alors tu ne pourras les changer qu'avec du code, ce qui peut ou pas etre un probleme.

Dans tous les cas, le mix etat-comportement, c'est a dire le composant, doit etre contenu dans un tableau qui detiens tous le scomposants du meme type, pour pouvoir tous les mettre a jour en serie (ou en parallel). Il doit etre au maximum independant on avoir un systemes pour communiquer avec si besoin.

Pour ce genre de systeme, evite l'eritage au niveau des composants ou des entitees. Generalement tu auras besoin d'heritage uniquement pour le systeme qui gere ces deux la.

[PilloBuenaGente]

Merci pour le détail de cette technique que tu vantes bien souvent.
Elle semble en effet séduire tout les programmeurs de jeux vidéo avec de l’expérience.

Je vais me lancer dans un jeu histoire d'être confronté au problème !
(Ce bouquin que tu avais conseillé que je vais finir par acheter (je ne pensais pas me diriger vers le jeux vidéo tout de suite, mais ça m'a l'air bien passionnant(aussi )))

Aussi, peut être aussi que l'apprentissage d'une plateforme tel SQL aiderais ?!

[Klaim]

Merci pour le détail de cette technique que tu vantes bien souvent.
Elle semble en effet séduire tout les programmeurs de jeux vidéo avec de l’expérience.

Pour etre clair, c'est efficace pour un moteur de jeu, dans le cas ou tu sais pas exactement quel sera le contenu final. C'est un moyen de generaliser pour que le contenu du jeu sois 100% decris par des donnees externes fournis par les designers, independant des programmeurs.

Par exemple si tu fais un jeu qui est une legere variante du jeu d'echec ou du jeu de go, tu sais a l'avance ce dont tu as besoin et tu n'as donc pas besoin de faire une generalization de ce qu'il pourrait y avoir dans le jeu.

Mais si je fais un rpg, un fps ou n'importe quoi qui necessite de mettre differents contenus dont je ne suis pas sur du resultat final, mieu vaut avoir un systeme comme celui ci pour facilement ajouter de nouveaux elements.

Je dis ca parceque par exemple dans le jeu que je fais actuellement, je n'ai pas besoin de cette generalization. Mais si demain je me lance dans un jeu disons un tout petit rpg solo, la ouai je pense ca me ferait gagner du temps sur le long terme.

Enfin, si tu utilises un moteur deja fait, par exemple Unity3D, ils ont deja ce system en place (peut etre implemente differement de ce que j'ecris) donc tu as juste a l'utilser.

Je vais me lancer dans un jeu histoire d'être confronté au problème !
(Ce bouquin que tu avais conseillé que je vais finir par acheter (je ne pensais pas me diriger vers le jeux vidéo tout de suite, mais ça m'a l'air bien passionnant(aussi )))

Oui Game Engine Architecture est excellent parcequ'il survole les differentes techniques pour faire des moteurs de jeu generiques. Il a tout un chapitre qui explique comment organiser ses entitees de jeux, et qui montre pourquoi on a tendance aujourd'hui a faire des systemes de composants.

Par contre garde constamment a l'esprit qu'il faut faire un jeu avant de faire un moteur. Fais un jeu, sans chercher a generaliser pour d'autres jeux potentiels, puis a la fin, extrait ce qui est reutilisable et fait un autre jeu. Tout ce qui auras survecu au second jeux est reutilisable, du coup tu peux le mettre dans une lib. A lire: http://scientificninja.com/blog/write-games-not-engines

Aussi, peut être aussi que l'apprentissage d'une plateforme tel SQL aiderais ?!

Seulement si tu veux faire de la persistance de donnees, mais ce n'est necessaire que dans certaines categories de jeu. Franchement tu peux aprendre le SQL au moment ou tu verras que tu en as besoin, ce n'est pas important pour les jeux au debut.

[PilloBuenaGente]

Merci encore !

J’essayais de trouver LA bonne méthode de programmation, mais apparemment, elle va à chaque fois dépendre de ce qu'on cherche à créer..

( J'ai l'impression qu'on ne peut résoudre un problème que lorsque qu'on y ai confronté.
Mon manque d’expérience est sans doute la cause de beaucoup de mes soucis ! )

#Edit Puis-je traduire la page que tu m'as donné et la poster sur le forum ? Je ne suis pas très bon en Anglais, je la traduirais pour moi de toute façon. #

[ternel]

J'imagine que pour la traduction, il faut demander directement au propriétaire du blog…