What data structure should I use for a Diablo/WoW-style talent tree?

Question

I'm considering implementing a talent-tree system for an online RPG, similar to that seen in World of Warcraft, where acquiring a skill unlocks the next "tier" beneath it in the tree.

Does anyone know of the best way of implementing this structurally in the database/code?

Answer 1

Use a structure like this to represent a tree in a database:

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

And another table to represent acquired talents per user

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

You can check for talent dependencies programatically by querying the complete talent table, and building a linked tree. You can also do that with SQL but it will require either recursive subselects or lots of queries. Better do it in your code.

If there are multiple dependencies, like for example Fire Punch depends on Punch AND Immolation use two tables to represent the dependency graph:

#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

Answer 2

I would recommend using a tree where each node represents a specific talent/skill. Based on whether or not the player has earned a talent, its child talents can be earned. For example the following data structure

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

To determine which talents a player has, you take the root talent and walk down the graph until you reach the talent nodes where earned is false. This will also reveal which talents are available for obtaining: the first talent in each branch down from the root talent where earned is false.

Answer 3

In my game I do it like this:

Database:

reference_talent : contains an unique ID, name, effect etc

talent : id, playerid <- contains all talents players have "learned".

Ingame: (on the server)

I load up all reference_talents in a 'static' (read only) std::map so I can access them easily by their id.

When a client checks out a player I get all the talents from the database and stocks them in a std::vector so that when I need to calculate characteristics etc. I have them in RAM. I also send away the talents to the client.

That's about it (except saving off new talents of course which is just an 'INSERT' in the table 'talent' + a message to the client).

Answer 4

Relational approach

You describe it as relation between unlockers and unlocked similar as in this tutorial. I suggest learning more about relational algebra and databases. They are nice way how to model data. If You learn how to query the information from database You can model data quite easily.

I don't know how much You know about modeling relations. That tutorial should help You with it.

One solution

I assume that WoW work as in reality (ehm), that it is

• talent unlocks several (other) talents
• talent is unlocked by several (other) talents.

It is N:N relation, which implies You need "middle man" a new relation between the two talents:

(talent who unlocks id, talent who is unlocked)

This way You can have talent A unlocking B, C and D ((A, B), (A,C),(A,D)) and talent Y unlocked by X,Z and W ((X,Y),(Z,Y), (W,Y)). In imperative/procedural/object-oriented language You would do it as list/array of pairs like there:

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

So for "real-world" example You can have:

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

and it means that "jumping superhigh" is obtained after You have "running fast" and "antigravity's child" talents.

Other solution

I have not played Diablo recently but it might be, that it had only:

• talent unlocks several other talents
• talent is unlocked just by one talent.

It is 1:N relation:

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

like:

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