Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

up vote 10 down vote accepted

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
share|improve this answer
    
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. –  Jonathan Hobbs May 11 '11 at 14:07
    
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? –  Jonathan Hobbs May 11 '11 at 14:11
2  
@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. –  LumpN May 11 '11 at 20:23
    
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. –  Jonathan Hobbs May 11 '11 at 21:39
    
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.) –  user744 Oct 16 '11 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.

share|improve this answer
    
You've got a pointer to a native array and a size? Fail- use a self-owning self-sizing pointer. –  DeadMG May 11 '11 at 10:46
    
Whoops... C/C++ mixup and an error. I have updated my answer. Thanks for the heads-up. –  ghost May 11 '11 at 12:58
    
@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? –  Kylotan May 11 '11 at 13:36
    
A Boost ptr_vector might be even better. –  Zan Lynx May 11 '11 at 16:05
5  
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. –  user744 Oct 16 '11 at 15:52

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

share|improve this answer

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"};
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.