Research Trees: What is the best way to do them?

[Tdata]

I my last thread, which I locked as it was going no where, I asked about research trees. (*Note: You really should have a forums for Game Programming not related to Utilities)

I figured I would try again.

What I really need, is guidance. I have never set up a game that uses a research tree before, so I am lost about the best method to use for one.

This time, I have a Diagram, so I hope it helps:

Spoiler: Picture

Now, for the question. How do I program that? I have tried to use for loops and such, but it takes forever to search through one tree...

Any help will be nice... ^_^

 

[silver wind]

The image link is broken. Sorry I can't help, it's been a while since I worked with trees.

 

[Sgt. Cookie]

Whats a research tree?

 

[Tdata]

The best way to describe a research tree... Well, to put it simply, it is when you need a previous bit of research to research the next thing... For Example: To research SRM-4, you need to have SRM-2 Researched. To research LRM-20, you need LRM-15, LRM-10, and LRM-5 researched...

 

[Sgt. Cookie]

Thanks. How are you doing the tree right now?

 

[Tdata]

FlatFiles converted into massive Lists...

Right now I am using a Struct as the base. The attributes are ID, Name, Cost and another Struct called Requirements...

 

[Tdata]

I feel I must ask, Is there no one who has tried to create a game that uses a research tree?

 

[e]

There is a general game making forum; it's not strictly for programming, but I don't think there's any restrictions either about it. viewforum.php?f=215

Anyhow...I gave you a possible solution last time. What you want is not necessarily a tree structure, but might be more general. You'd then look for different types of graph. Yours would be a directed, weighted graph.

First you need to map out each node's attributes and restrictions. Here's what I gathered from your diagram.

A node: has a name, an id, can have any number of dependencies (parents, if you will), and does not need to know if another node is dependent on it.

Now, I think it's safe to assume that you won't have nodes in your graph which have, say, more than 10 direct dependencies. Most likely, 3 or 4 will be the direct cost. These nodes only need to know of their respective direct dependencies, and if they have been fulfilled (or paid for, or however it works in your game). That can be represented with a simple boolean switch IS_ENABLED true/false or whatever.

So a basic node structure would be:

<div class="c" id="{CB}" style="font-family: monospace;"><ol><span style="color: #993333;">struct _node_T {

   <span style="color: #993333;">struct _node_T atDeps[MAX_NUMBER_OF_DEPS]; // The node's direct dependencies

   <span style="color: #993333;">unsigned <span style="color: #993333;">int ui8Id; // The node ID

   <span style="color: #993333;">char kstr8Name[MAX_NAME_LENGTH]; // The maximum length of node's name

   <span style="color: #993333;">unsigned <span style="color: #993333;">int bEnabled; // Has the node been enabled yet? Did the user get it?

}

Now, when you want to know if a node can be bought, you simply iterate through its parent dependencies and check if their bEnabled is TRUE or FALSE.

You'll need to make up functions to initialize your nodes, destroy them, link them together, etc., but I'm sure you can work that out.