Quelle structure de données dois-je utiliser pour un arbre de talents de style Diablo / WoW?

J'envisage d'implémenter un système d'arborescence de talents pour un RPG en ligne, similaire à celui de World of Warcraft, où l'acquisition d'une compétence déverrouille le "niveau" suivant en dessous dans l'arborescence.

Quelqu'un connaît-il la meilleure façon de mettre cela en œuvre structurellement dans la base de données / le code?

Utilisez une structure comme celle-ci pour représenter un arbre dans une base de données:

#Talent
id  parent  description
1   0       Tackle
2   1       Kick
3   1       Punch
4   3       Fire Punch

Et une autre table pour représenter les talents acquis par utilisateur

#UserTalent
id  user  talent
1   4     1
2   4     3
3   4     4

Vous pouvez vérifier les dépendances des talents par programmation en interrogeant la table complète des talents et en créant une arborescence liée. Vous pouvez également le faire avec SQL mais cela nécessitera soit des sous-sélections récursives, soit de nombreuses requêtes. Mieux vaut le faire dans votre code.

S'il y a plusieurs dépendances, comme par exemple Fire Punchdépend de PunchET Immolationutilisez deux tables pour représenter le graphique de dépendance:

#Talent
id  description
1   Tackle
2   Kick
3   Punch
4   Fire Punch
5   Immolation

#Depedency
id  parent  child
1   0       1
2   0       5
3   1       2
4   1       3
5   3       4
6   5       4

Je recommanderais d'utiliser un arbre où chaque nœud représente un talent / compétence spécifique. Selon que le joueur a gagné ou non un talent, ses talents d'enfant peuvent être gagnés. Par exemple, la structure de données suivante

class Talent {
    std::vector<Talent*> children;
    bool earned;
};

Pour déterminer les talents d'un joueur, vous prenez le talent racine et parcourez le graphique jusqu'à ce que vous atteigniez les nœuds de talent où il est faux. Cela révèlera également quels talents sont disponibles pour l'obtention: le premier talent dans chaque branche en dessous du talent racine où il est gagné est faux.

Dans mon jeu, je le fais comme ceci:

Base de données:

reference_talent : contient un identifiant unique, un nom, un effet, etc.

talent : id, playerid <- contient tous les talents que les joueurs ont "appris".

Ingame: (sur le serveur)

Je charge tous les reference_talents dans une std :: map 'statique' (en lecture seule) afin que je puisse y accéder facilement par leur identifiant.

Lorsqu'un client vérifie un joueur, j'obtiens tous les talents de la base de données et les stocke dans un vecteur std :: afin que lorsque j'ai besoin de calculer des caractéristiques, etc., je les ai dans la RAM. J'envoie également les talents au client.

C'est à peu près tout (sauf sauver de nouveaux talents bien sûr qui n'est qu'un 'INSERT' dans le tableau 'talent' + un message au client).

Approche relationnelle

Vous le décrivez comme une relation entre les déverrouilleurs et déverrouillés similaires comme dans ce tutoriel . Je suggère d'en savoir plus sur l'algèbre relationnelle et les bases de données. Ils sont une bonne façon de modéliser les données. Si vous apprenez à interroger les informations de la base de données, vous pouvez modéliser les données assez facilement.

Je ne sais pas ce que vous savez sur la modélisation des relations. Ce didacticiel devrait vous y aider.

Une solution

Je suppose que WoW fonctionne comme dans la réalité (ehm), qu'il est

• le talent débloque plusieurs (autres) talents
• le talent est débloqué par plusieurs (autres) talents.

C'est la relation N: N, ce qui implique que vous avez besoin de "l'homme du milieu" une nouvelle relation entre les deux talents:

(talent who unlocks id, talent who is unlocked)

De cette façon, vous pouvez avoir le talent A déverrouillant B, C et D ((A, B), (A, C), (A, D)) et le talent Y déverrouillé par X, Z et W ((X, Y), ( Z, Y), (W, Y)). Dans un langage impératif / procédural / orienté objet, vous le feriez en tant que liste / tableau de paires comme ici:

var unlocks_unlocked = [[A, B],[A,C],[A,D],[X,Y],[Z,Y],[W,Y]];

Donc, pour l'exemple "du monde réel" Vous pouvez avoir:

... ["running fast", "jumping superhigh"], ["antigravity's child", "jumping superhigh"]

et cela signifie que "sauter très haut" est obtenu après que vous ayez des talents de "courir vite" et "d'enfant d'antigravité".

Autre solution

Je n'ai pas joué à Diablo récemment mais il se peut qu'il n'ait que:

• le talent débloque plusieurs autres talents
• le talent est débloqué par un seul talent.

C'est une relation 1: N:

 You put "is unlocked by this talent's id" variable into talent's structure

comme:

 var Talent[8] = { "name": "superpower", "unlocked by": "being Clark Kent"};