Modéliser un arbre de compétences

[Sephi-Chan]

Salut à tous,

Depuis quelque temps, je me pose à nouveau des questions sur la modélisation d'arbres de compétences et de talents qui gèrent des dépendances, des branches, etc.

Imaginons par exemple que je veuille reproduire un arbre comme ceux de World of Warcraft (Cf. http://fr.wowhead.com/?talent=L).

Comment modéliseriez vous ces arbres commun à tous les personnages du jeu, proposant toutefois des restrictions (il faut être de telle ou telle signe pour activer ce point, il faut avoir mis 5/5 points dans cette compétence pour pouvoir activer celle-ci, il faut avoir dépensé N points dans des compétences de type Corps à Corps pour pouvoir activer celle-ci, etc.

J'ai naturellement pensé à un document XML (ou JSON :p) avec des propriétés pour chaque noeud (le type de compétence, les dépendance, etc.), mais ensuite, pour stocker les points choisis en telle capacité pour tel personnage, ça se corse un peu et il y a surtout plein de méthodes pour aborder ce problème ! Voici ce à quoi pourrait ressembler ma représentation de l'arbre.

Qu'est ce que vous feriez, vous, si vous deviez modéliser complètement ça ?

Au plaisir de vous lire,


Sephi-Chan

[phenix]

Perso, c'est peut être pas la meilleur solution mais je ferais une table qui contient les données des compétences et une autre qui contient les compétence et les points aquit:

id_comp | point

id | nom | max_point | need | min_point

Sa parle tout seule, pour débloquer la compétence il faut posséder "need" et avoir suffisamment de point dedans.

Moi c'est la piste que j'explorerais, maintenant, il y a sûrement d'autres solutions

[gottferdom]

Je pensais justement faire un truc dans ce genre pour pouvoir débloquer des compétences en attaque / défense selon le style de jeu préfèré par le joueur, et effectivement j'avais commencé à reflechir au système de table donné par phenix

[Roworll]

Dans la 3e Edition de D&D, les auteurs ont intégré la notion de Feats/Dons.
Ces capacités sont souvent interdépendantes les unes des autres et s'organisent plus ou moins à la manière d'un arbre.

De nombreux générateurs de personnages existent et l'un d'entre eux, PCGen, est en open source. Il peut être intéressant de se pencher sur leur manière d'envisager ce problème.

Ce programme n'utilise pas de bases de données mais de simples fichiers au format texte (pas de XML ni de YAML). Je suppose que les lignes de données sont simplement parsées et découpées selon des mots clefs.

Je prends l'exemple du don Improved Precise Shot. Voici comment il est codé dans le fichier

Code PHP :

<?php 

Improved Precise Shot

TYPE:General.Fighter

PREATT:11

PREFEAT:2,Point Blank Shot,Precise Shot

PRESTAT:1,DEX=19 

[Eluox]

Même si j'aurais du mal, je ferais sa par document JSON perso

Mais c'est sur que le fichier risque de devenir bien corsé et compliqué :q

[Stargate63]

Justement je tombe sur ce sujet.

Pour BSG, nous avions pensé à un arbre, nous aussi inspiré de WoW, et nous avons travaillé sur la méthode de phoenix.

Nous n'avions pas de max_point toutefois. Les "max_point" étaient définis lorsqu'on touchait à la base de donnée. C'est à dire que si max_point valait 5, alors pour chaque "case", on avait définis son max_point dans une variable. Ainsi, le membre pourrait seulement augmenter la compétence si les points de cette compétence étaient inférieur à ses max_point.

Notre table se présentait ainsi :

id_joueur ; id_compétence ; points_requis ; active ;

Pour le nom, il était déjà implanté dans le tableau avec des balises <p>. Nous avons fait un tableau pour savoir quelle id correspondait à quelle compétence.

En espérant t'avoir aidé un peu.

[Ter Rowan]

perso, je ferais (en bleu une table, en gras la clef parfois multiple)

une table des "talents"

id talent / nom talent / id famille / niveau général/ valeur max

le niveau général correspondant à une contrainte du personnage (genre tu ne peux pas accèder à ce talent si tu n'as pas tel niveau de personnage, si tu n as pas le statut vip, etc...)

la famille (avec sa table éventuellement id famille / nom famille) correspond à une famile de talent (dans wow je crois qu'on appelle ça une branche, exemple : branche feu du mage)

la valeur max correspondant au nombre de points possibles à engranger

une table des contraintes de familles
id talent / id famille / niveau famille
permettant de faire comme wow :
talent duchmol de la branche feu nécessite 10 points dans la branche feu (la valeur de niveau famille)

mais aussi de croiser (ce que ne fait pas wow)
talent duchmol de la branche feu (cf table talents) nécessite 5 points dans la branche arcane

une table des contraintes de talent
id talent / id pere / niveau

permettant de faire comme dans wow
talent super nécessite 10 points dans talent truc

niveau = 10points
id talent = id talent super
id pere = id talent truc

mais aussi mieux que wow dans le sens où

talent super nécessite aussi 5 points dans talent bidule

[Sephi-Chan]

Pour modéliser l'arbre en lui même, j'opterai plus pour une représentation intervallaire.

Mon problème est plus de stocker l'arbre de chaque joueur. La première idée qui me vient est d'utiliser une table de relation joueur_a_talent qui associe chaque talent à un personnage, avec le nombre de points investis dans ce talent.


Sephi-Chan

[Lanwin]

Je ne m'en tiens personnellement avec une seule table joueur_competences (id_joueur | id_competence | points).

Dans l'idée où je n'ajouterai des compétences que très rarement (mon arbre de base étant déjà très "touffu" ^^), je me suis "limité" à les répertorier et les coder directement dans un fichier PHP. Je ne me voyais pas les rajouter dans la base de données alors qu'elles allaient n'être que très rarement modifiées. De plus cela me permettait, à mon goût, de coder plus facilement les dépendances qui sont assez complexes dans mon projet.

Sinon, j'ai il y a un petit moment été m'intéresser à Mangos, un émulateur de serveur WoW. Si j'ai tout désinstallé maintenant, j'ai tout de même gardé les tables MySQL du serveur. Si je n'ai vu aucune table parlant des talents et de leur dépendances, je n'ai pas trouvé grand chose non plus côté stockage de l'arbre pour chaque joueur. M'est avis donc que ce stockage est compris dans le champ "data" de la table "character", et dont voici son contenu pour l'un de mes persos que j'avais créé à l'époque (entier, le champ étant de type "longtext") :

2 0 25 0 1065353216 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4819 4442 0 0 100 0 4819 4442 1000 0 100 0 70 35 513 0 0 0 0 0 0 0 0 0 4104 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967040 4294901760 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 1140457472 1157234688 1155097645 1065353216 1069547520 49 49 0 1125802405 1130317835 1107633298 1107633298 0 0 0 0 0 0 0 1065353216 0 0 0 0 138 77 162 118 97 0 0 1100480512 1095761920 0 0 0 0 0 0 169 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3917 4399 10240 466 0 0 0 0 0 1065353216 1073741824 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 84214273 33554432 0 0 0 7 0 0 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 45 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 367 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 43 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 25049 0 0 0 0 0 0 2803 2803 2804 2824 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12790 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7725 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1073741824 0 0 0 0 0 0 4 1073741824 0 0 0 0 99 1073741824 0 0 0 0 0 0 0 0 237 1073741824 0 0 0 0 26 1073741824 43 1073741824 0 0 0 0 0 0 6 1073741824 7 1073741824 87 1073741824 5 1073741824 36 1073741824 10 1073741824 89 1073741824 3 1073741824 97 1073741824 353 1073741824 12 1073741824 91 1073741824 28 1073741824 14 1073741824 105 1073741824 233 1073741824 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 235 1073741824 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 785800 98 24576375 0 55 22937950 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 183 22937950 0 594 22937950 0 754 22937950 0 0 0 0 0 0 0 0 0 0 473 22937950 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 762 19661100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 673 24576375 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 1079264324 1092616192 0 1094432326 1087859851 1087859851 1083830174 1095563215 1096611791 1090121630 1090121630 1090121630 1090121630 0 1703967 16942016 58721299 4152561690 2231288346 204999556 3427008624 1073741930 139340 1181483168 802619392 2147483648 436207628 134880 201326592 72 17301536 45136 3221225609 2993171968 9430529 1645443 2097156 1728382976 71304193 1073741824 1838090 536897544 1679294464 1611137216 2147484160 0 0 0 51904545 42467328 445456 32 0 131072 844288 32770 0 8192 100732928 0 4736 393216 0 90112 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2151529767 0 15 38 15 15 15 15 0 0 0 0 0 0 0 1065353216 1065353216 1065353216 1065353216 1065353216 1065353216 1065353216 15 0 262144 33803 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1099536794 0 70 0 0 0 0 0 0 0 0 0 0 0

Quelques petites précisions sur ce champ : il ne contient pas la race, la position, la classe, ni l'id du pet, ni encore les sorts qu'il possède, ni les quêtes faites/en cours, ni le contenu de l'inventaire, ni les infos de guilde, ni les id des amis, ni les kills effectués, ni les infos d'instance, ni les infos de groupe, ni les réputations, et j'en oublie encore plein. En gros il y a tellement d'infos qui ne sont à priori pas contenu dans ce champ que je pense fortement que l'arbre des talents est stocké ici (sans doute parmi d'autres choses).

A titre de comparaison, les tables relatives à l'émulateur sont au nombre de 126 (seulement, je dirai, pour un jeu comme WoW).

Amicalement,

PS : Je vous encourage à télécharger au moins une version d'une DB de Mangos (ou Ascent), juste pour voir comment l'émulateur se charge de stocker tout ça (ce qui n'est sans doute pas la façon qu'utilise Blizzard pour stocker ses infos, mais c'est déjà ça ^^)

[Ter Rowan]

Pour modéliser l'arbre en lui même, j'opterai plus pour une représentation intervallaire.

je ne connaissais pas ces méthodes, elles me semblent très intéressantes mais.. sont elles adaptées à un arbre de compétences / talents ?

je pense que ce système n'apporte une valeur ajoutée que si la fréquence des requêtes sur ce modèle est importante.

Dans quel cas as tu besoin de regarder l'arbre des compétences ?

si c'est une fois de temps en temps (ex wow, on va pas modifier son arbre toutes les cinq minutes), c'est peut être un peu sophistiqué pour le besoin (enfin, dans l'hypothèse où on est pas habitué à cette modélisation, évidemment si tu nages dedans comme un poisson dans l'eau, mon argument ne tient pas)

si c'est plus fréquent que cela, alors pourquoi pas

de même si l'arbre bouge souvent, cela ne me parait pas très performant (une modification fonctionnelle = beaucoup de mise à jour)

dans tous les cas ces techniques sont très enrichissantes, ça devrait même me permettre de briller en société donc merci :good:

par contre je me demande si cet arbre permet à un fils d'avoir plusieurs pères (si on veut plusieurs contraintes à remplir)

quand au stockage des compétences d'un joueur, ça doit rester du standard (soit matrice si le système est fermé, soit table avec un enregistrement par couple utilisateur/compétence si le système est ouvert), même en utilisant ce modèle d'intervalle :

si on teste la présence d'une compétence pour un joueur, on n'a pas besoin de l'arbre des talents
si on teste les contraintes des talents du système, on n'a pas besoin des compétences du joueur.

la seule nuance étant (je me pose la question sur mon projet) :
je veux laisser la possibilité au joueur de réaliser une action alors qu'il n'a pas la compétence mais qu'il a une compétence avoisinante qui permettrait de le faire avec un malus

là on croise système et personnage, ça nécessite de pousser l'analyse