Design pattern for access to tree-like database in Java?

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,

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.

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

Filed under: softwareengineering - @ 15:38

Thẻ: database, design-patterns, java, trees

Thiết kế website giá rẻ

Danh mục

Design pattern for access to tree-like database in Java?