Programming: a skill tree

[TCAtect]

Here's something that's been bothering me for a while. In many modern (heck, even old) RPG, tactical RPG, or strategy games, there is a wealth of skills available to players. However, some skills must be earned while other skills are given near the beginning. The player spends time (either by leveling up, or repeating/doing certain tasks) to populate his/her character with skills. I love to think about the countless possibilities one can create with a skill-tree, but I have run into a practical issue. How to program a skill tree?

Suppose a skill requires that the player's character have a strength of 50 points or above. That's simple to understand. My first reaction would be to use an if statement. All's well, until one sees that if there were hundreds of skills available, and many of them having different (and multiple) pre-requisites, the code would be a mess. Obviously, it's not quite practical to have hundreds of stacked if statements.

So, how would I go and approach it? I searched over the horizons of the interweb, but found no practical answers (one person suggested looking up Decorator Patterns, which led to me reading tens of other web pages and the wiki page, but still not understanding the concept). Would anyone be kind enough to provide some tips on how to approach this dilemma?

tl;dr: How to program skill tree system without millions of if statements?

[eiefai]

maybe a skill tree is programmed a little bit different, one way i would use to make a skill tree is that in the DB I would make a table with a self referring column "parent" and a query to extract the tree itself.

i.e. one skill has the id of 1 and a null value at the "parent" column, the child skill of this first skill would have a distinct id and in the "parent" column of this new skill should have a 1 and then I would use a query to get the tree that is generated with the user data

[Gundark]

Hmmm, many different was you could do this. Personally I would think about using a tree data structure. Each node of the tree could have an attribute along with a required value (or list of attributes and value pairs). This would allow easy access and traversal of your skill tree. Your character class or whatever could have a pointer to the current skill node , then when changing skills you just move the pointer to the next node (as long as the character meets the perquisites). You could also save this data structure to a database or file or whatever you'd like.

There are all kinds of possibilities here, this is just the first idea that popped into my head.

[bluemagica]

hmm nice question!

"IF you cannot use if on the code, The use if on the pattern."

Does your skill tree has a pattern in it? If yes, then the pattern can be used to create the skill tree.
for example: in a skill tree, all skills become available when conditions in thier parent branch has been met, and this is a pretty usable pattern!


Also if you are defining a hundred skills in code, then i dont think using a few if statements will be that much tough! But i would suggest making a XML out of your skill tree, this will help you find more ways of reducing code!

[TCAtect]

First of all, thanks to everyone who responded!


...make a table with a self referring column "parent" and a query to extract the tree itself...

This is very interesting, an ingenious method for storing the data. I like the simplicity in its recursive element. Now, combine this with...


..in a skill tree, all skills become available when conditions in thier parent branch has been met, and this is a pretty usable pattern!...

And we have a very robust skill tree! I love the (again) simple, recursive element in this. I am pretty pumped, as this is a very elegant solution to my problem at hand. However, being the cynic I am, I'm pretty sure in a couple of days, I'll have some more questions as I run into more problems regarding the skill tree (Always happens :D). But for now, thanks a lot for answering my questions, I gotta go pseudocoding :D!

Ooh, one last thing,


...Each node of the tree could have an attribute along with a required value (or list of attributes and value pairs). This would allow easy access and traversal of your skill tree. Your character class or whatever could have a pointer to the current skill node , then when changing skills you just move the pointer to the next node...

Because I'm not too well versed in Java or C++, do you mind explaining the pointer idea? I read a couple of columns on it, but the authors seemed to like explaining an abstract term with even more abstract terms! If you don't mind, is a pointer the same as a reference? Does it have to do with direct memory management, even in Flash/Flex? Just somewhat confused about its concept, and I couldn't understand why at one point people hailed it as being the end all and be all of the C++ language.

Greatly appreciated!
TCA

[bluemagica]

instead of ranting about the definition of pointers, just assume it to be a reference variable.

[TCAtect]

Done. :D

[Gundark]

Yeah, there are no "pointers" only references in Actionscript. Sorry for the confusion.