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

23

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?

RSH1
la source

Réponses:

13

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
Jonas Bötel
la source
Votre UserTalenttable n'a pas besoin d'une colonne autokey. useret talentpeut être les deux seules colonnes et une clé composite: ce ne seront jamais des doublons et vous ne demanderez jamais de idtoute façon.
doppelgreener
Je ne suis pas un concepteur de base de données et je serais intéressé d'entendre son opinion à ce sujet: si chaque talent avait un nom unique, ne pourriez-vous pas également supprimer tous les autres champs d'identification numérique dans cette conception de table et utiliser des noms comme clés (avec des modifications en cascade)? Y aurait-il des coûts ou des avantages importants à le faire?
doppelgreener
3
@Jonathan Hobbs: Un identifiant principal d'auto-incrémentation est toujours agréable pour les opérations de suppression / mise à jour. Ce n'est jamais plus lent mais souvent plus rapide. La taille des lignes n'est pas non plus un problème ici. Il en va de même pour le cas des noms de talents uniques. Pour de bonnes performances, vous souhaiterez joindre vos tables uniquement sur des entiers uniques. Voir en.wikipedia.org/wiki/Database_normalization etc.
Jonas Bötel
Merci. Un concepteur de base de données que je connaissais a déclaré une fois que les autokeys étaient mauvais et devaient être évités, mais je n'ai jamais été clair sur le cas ou sur la raison. Je suppose que non.
doppelgreener
Il n'y a aucune raison réelle d'utiliser une base de données pour stocker ces données, sauf si vous avez besoin d'une base de données pour les concepteurs, car vous prenez en charge l'édition multi-utilisateurs ou quelque chose. Sinon, cela ne fera qu'empêcher. (Je n'utiliserais jamais non plus de clé d'auto-incrémentation principale pour cela, car vous voulez presque certainement vous associer à des noms logiques décidés par un concepteur plutôt qu'à une clé fournie par la base de données.)
5

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.

fantôme
la source
Vous avez un pointeur vers un tableau natif et une taille? Échec: utilisez un pointeur à dimensionnement automatique.
DeadMG
Oups ... Mélange C / C ++ et une erreur. J'ai mis à jour ma réponse. Merci pour l'information.
fantôme
@DeadMG: qu'entendez-vous exactement par «auto-dimensionnement auto-propriétaire»? Faites-vous référence à quelque chose comme le vecteur ci-dessus, ou pensiez-vous à autre chose?
Kylotan
Un coup de pouce ptr_vector pourrait être encore mieux.
Zan Lynx
5
La structure arborescente doit être entièrement distincte de savoir si le joueur l'a gagnée, la première est des données statiques faites par les concepteurs et la seconde est des données par joueur stockées dans une sauvegarde ou une base de données.
1

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).

Valmond
la source
0

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"};
user712092
la source