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

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

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