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?


4 Answers 4


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

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

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:

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

id  parent  child
1   0       1
2   0       5
3   1       2
4   1       3
5   3       4
6   5       4
  • \$\begingroup\$ Your UserTalent table has no need of an autokey column. user and talent can be the only two columns and a composite key: they will never be duplicates and you will never query id anyway. \$\endgroup\$ Commented May 11, 2011 at 14:07
  • \$\begingroup\$ I am not a database designer and I would be interested to hear one's say on this: If every talent had a unique name, could you not also do away with every other numeric ID field in this table design, and use names as keys (with any edits cascaded)? Would there be any significant costs or benefits in doing so? \$\endgroup\$ Commented May 11, 2011 at 14:11
  • 3
    \$\begingroup\$ @Jonathan Hobbs: An autoincrement primary id is always nice for delete/update operations. It's never slower but often faster. Also row size is not of concern here. The same is also true for the case of unique talent names. For good performance you'll want to join your tables on unique integers only. See en.wikipedia.org/wiki/Database_normalization etc. \$\endgroup\$ Commented May 11, 2011 at 20:23
  • \$\begingroup\$ Thanks. A DB designer I knew once stated that autokeys were evil and should be avoided, but I've never been clear on whether that's the case or why. I suppose it isn't. \$\endgroup\$ Commented May 11, 2011 at 21:39
  • \$\begingroup\$ There is no real reason to use a database to store this data unless you need a database for designers because you support multi-user editing or something. Otherwise it will just get in the way. (I would also never use a primary autoincrement key for this, because you almost certainly want to join on logical names decided by a designer rather than a DB-provided key.) \$\endgroup\$
    – user744
    Commented Oct 16, 2011 at 15:56

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.

  • \$\begingroup\$ You've got a pointer to a native array and a size? Fail- use a self-owning self-sizing pointer. \$\endgroup\$
    – DeadMG
    Commented May 11, 2011 at 10:46
  • \$\begingroup\$ Whoops... C/C++ mixup and an error. I have updated my answer. Thanks for the heads-up. \$\endgroup\$
    – ghost
    Commented May 11, 2011 at 12:58
  • \$\begingroup\$ @DeadMG: what exactly do you mean by 'self-owning self-sizing'? Are you referring to something like the vector above, or were you thinking of something else? \$\endgroup\$
    – Kylotan
    Commented May 11, 2011 at 13:36
  • \$\begingroup\$ A Boost ptr_vector might be even better. \$\endgroup\$
    – Zan Lynx
    Commented May 11, 2011 at 16:05
  • 5
    \$\begingroup\$ The tree structure should be entirely separate from whether the player has earned it, the former is static data made by designers and the latter is per-player data stored in a save game or DB. \$\endgroup\$
    – user744
    Commented Oct 16, 2011 at 15:52

In my game I do it like this:


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


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


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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .