Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm developing a Roleplaying character viewer/manager programme for a locap LARP system. The Characters have access to skills that are layed out in a tree-like structure. There are a lot of skills, and potentially a lot per character.

I know I can just import the Java swing library to get access to a tree, but I feel like this may bog me down, when all that needs to be done is access to a tree-like database, and the character needs only know that they have access to a subset of the skills.

I'm not sure if the tree design pattern is the best choice for this (i.e. instantiate a tree for the skills known per character, and add to/delete parts as needed) or 'do the clever stuff' and use a list per character to see which parts (skills) of database (external tree) are 'owned'.

My skills are broken down roughly as so:
Course catogory -> Weapon Type -> Actual Weapon -> Proficiency-->Special Skill, which goes quite deep. Further to this there is little need to know what is at each level, just that it's children, until you hit the leaf, and the one up.

My database effectively already exists on the LARP website, so if I don't have to reproduce it, that would be good. Here is a sample

Weapons and Shields     Warrior Priest Scout Mage 
1H Weapon Proficiency     3        6     6     9 
1H Weapon Specialisation  6        12    12    18 
1H Weapon Expertise       12       24    24    36 
1H Weapon Mastery         24       48    48    72 

And later on:

Magic           Warrior       Priest        Scout         Mage 
Learn Spell     9 x (l + 1)   9 x (l + 1)   6 x (l + 1)   3 x (l + 1) 
l = spell level,  
...
Create Talisman 9 + l         9 + l         6 + l         3 + l 
l = level, 
share|improve this question
    
Maybe strategy design pattern will fit here. –  superM Jul 13 '12 at 8:47
    
@superM I'm sorry but I'm not aware of that term. –  Pureferret Jul 13 '12 at 8:59
    
Take a look at en.wikipedia.org/wiki/Strategy_pattern. –  superM Jul 13 '12 at 9:08
    
Tree structures are very well represented with Composite Pattern. –  m3th0dman Jul 13 '12 at 9:17
1  
@Pureferret: it's not a pattern but I recently bumped into this technology. Maybe you could borrow some ideas from there. –  JohnDoDo Jul 13 '12 at 10:07
show 2 more comments

2 Answers

up vote 1 down vote accepted

Using a tree in a normal (relational) database is difficult. Properly stored, each skill references only its parent skill, and trying to find children and siblings takes forever, even with a small table. This can be solved somewhat by de-normalizing the database (adding columns to provide a complete ancestry for each skill) but then you have to know the maximum number of levels in your tree and hard-wire it into your DB design.

Given that a human had to invent your data, there can't be too much of it, so I'd just put it in your own tree structure in memory. Each node would reference its parent and have a list of its children, so you can rocket around the thing as needed. You'd need only a simple Skill class, with parent, child list, name, and associated data, so it's real simple to do and use.

Use a Map (java.util.HashMap might be best, since you'll know the size of the tree) to locate each entry. Drop each Skill object into it, keyed, most likely, by name. So if you want to know about a "Long Sword", you find it in the Map by name, and now you have all the information, plus its parent and all its children.

(One thing not quite so simple: when reading the DB you are likely to get the name of a parent that's not in your tree (and Map). You have to create it on the fly. This means that when reading a new skill from the DB it may already be in the tree. So instead of adding it, you just need to fill in the information and parent. (And if the parent's not in the tree, you have to create it on the fly.))

Try to get by with displaying just a parent and its child list. Displaying everything as a simple table may work too. But once you start collapsing parts of the tree in the display it gets tricky. Doing a good tree/outline/explorer/table/list is a lot more work than everything else here.

I did use the swing library JTree years ago. It's probably your best bet if you must display the full tree as a tree. Unfortunately, I needed to make it part of a table, and it proved easier to skip the JTree and expand and collapse rows in the JTable directly. It was a massive effort. So don't, for instance, let anyone talk you into adding the cost to each row, where all the costs are aligned in their own column.

share|improve this answer
    
I've lost the thrust of your point here. Are you saying hardcode the tree aspect into a brand new class, or make Skill part of an existing Tree class? I don't follow your fourth paragraph, why is there a parent that's not in your tree (and Map)? The set of tables I want to make the tree out of/read from to make a sub-tree of skills known has about 4800 elements. Each skill has different number of levels, sometimes with the leaf just having an int that increases when bought so hard wiring that will be hard. –  Pureferret Jul 13 '12 at 14:48
    
@Pureferret: I'm using Skill as a node in a tree. A Tree class then needs only a pointer to the top level Skill, which has children, which have children, which... Real simple. I was thinking your database would contain such a structure with "Long Sword" having "Sword" as a parent. (And "Sword" having "Weapon" as a parent.) If you read in "Long Sword" before "Sword", you'd have trouble setting up your in-memory tree. You've got something more complicated, which at least gets you around this problem. –  RalphChapin Jul 13 '12 at 15:16
    
@Pureferret: it does look like your tree structure will be complicated. You might want different Classes for different parts, but you might get by with extentions (subclasses) for my Skill class. Random thoughts: I suspect you may be adding children in cases where you just want to add another field to your leaf node (Skill extension). You may want a master tree and then plain lists for each player. 4800 elements is nothing; you could get by with a simple list and linear scans to find the row/object you want. All classes in tree should carefully implement toString() method. –  RalphChapin Jul 13 '12 at 15:27
add comment

The canonical design pattern used for tree-like data structures is the Visitor. You start at the root (or the current node) and visit each node in order (preorder, postorder, whatever order you need), performing the required task at each node.

It's not clear from your description, but I get the impression that a Visitor that returned the information required to display the information about all primary children of the current node (that is, all the child nodes of the current node but not their descendants) would work. This assumes you have skills broken down into progressively finer categories (Fighting -> weapons -> close combat -> edged weapons -> short blade -> dagger). Players would be able to drill down into any category and see what their capabilities are. You could also collapse categories that only have single children (e.g. if a person only has one skill, just go directly to it and don't make them select a bunch of single links).

share|improve this answer
    
The example on wikipedia seems to be a bit rubbish. My skills are broken down roughly as so: Course skill catogory -> Weapon Type -> Actual Weapon -> Level of proficiency-->Special Skill, which goes much deeper. Further to this there is little need to know what is at each level, just that it's children, until you hit the leaf, and the one up. Also the example seems to have each part of the car be an object, but I just want to draw from a tree-like database... –  Pureferret Jul 13 '12 at 14:38
add comment

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.