Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Writing for android, but this is an abstract question for any OO language. Is there a "best-practice" for implementing a TechTree?

Here is an example:

    Vegetation  ->v     Strawberries        ->      BioDome
    Livestock   ->      Biomass

In this example, both Vegetation and Livestock are required for Biomass, but only Vegetation is required for Strawberries.

I have brainstormed a handful of implementations, but I'm not very confident with any of them. I will probably be loading the techs from XML, if that matters.

Is there a "best-practice"for implementing tech trees?

share|improve this question
2  
Probably a duplicate of What data structure should I use for a Diablo/WoW-style talent tree?, which already has an answer. –  Jonathan Hobbs Mar 16 '12 at 5:22

3 Answers 3

up vote 6 down vote accepted

Tech trees are basically DAGs. Representing it in xml in a way that won't set your hair on fire is pretty simple:

<tech name="Biomass">
    <depends>Vegetation</depends>
    <depends>Lifestock</depends>
    <!-- more stuff: description, bonuses, etc... -->
</tech>

Simply read the XML, turning it into an object graph, and use standard techniques for getting the available techs.

This is mostly metadata, and it really, really, really shouldn't reside in your code. You can use search and replace for XML too!

share|improve this answer
    
If you use this XML representation, you also need to check for cycles after loading the graph. Likewise, as a DAG, you can't load it into an object tree. –  user744 Mar 16 '12 at 12:43
    
this is what I was looking for! Thanks, now I can find any algorithm that applies to a DAG and make use of it. Thanks! –  edthethird Mar 16 '12 at 15:32
    
Joe: yes, you're right that's a pretty stupid way of putting it! I'll edit my answer for clarity –  brice Mar 17 '12 at 8:57

It's a pretty simple nested loop: to find available technologies you loop through all the possible technologies, and for each possible tech you loop through all the unlocked technologies to see if the requirements are fulfilled.

In your XML you just define what the requirements are for each tech, and then loop through that XML data when doing the looping I described above.

share|improve this answer
    
my concern with this approach is with identification. I don't want to do string compares on the name, and am hesitant to start assigning arbitrary IDs (which I must then manage) –  edthethird Mar 16 '12 at 3:25
    
What's wrong with comparing the names? –  jhocking Mar 16 '12 at 3:26
    
Because I only have a handful of techs fully designed. I need to be able to change, move, add, and remove techs as I go, and don't want to have to make changes in multiple places. It's a good solution, don't get me wrong, I just don't know if it'll work for what I need. –  edthethird Mar 16 '12 at 3:32
1  
I would rather change a few names in an XML file than have to change a bunch of classes and all the boilerplate code, but hey whatever. –  jhocking Mar 16 '12 at 3:38
1  
@edthethird: Each tech has to have a unique identifier that can identify it unambiguously - it could be an ID, a name or something else. Pick something. Since they already all have names, and no two techs will have the same name (unless you're doing something odd), you might as well just pick the name as the identifier. Bear in mind: regardless of what you pick for an identifier, you have to manage it anyway, changing all references to it whenever it gets changed, etc. –  Jonathan Hobbs Mar 16 '12 at 5:39

One solution is to simulate bit fields using EnumSets. An EnumSet uses bit-wise arithmetic for operations that involve the whole set, which means it is very fast. If you are using a language that does not have these features, you could implement something like this using regular bit fields.


Implementation 1

First, have an enum like this:

public enum TechType { NONE, VEGETATION, STRAWBERRIES, BIODOME, LIVESTOCK, BIOMASS; }

Then you can implement the individual Tech classes:

public class VegetationTech implements Tech {
    public TechType type = TechType.VEGETATION;
    public static Set<TechType> prerequisites = EnumSet.of(TechType.NONE);

    @Override
    public Set getPrerequisites() {
        return prerequisites;
    }

    @Override
    public TechType getType() {
        return type;
    }
}

public class BiomassTech implements Tech {
    public TechType type = TechType.BIOMASS;
    public static Set<TechType> prerequisites = EnumSet.of(TechType.VEGETATION,
                                                           TechType.LIVESTOCK);

    @Override
    public Set getPrerequisites() {
        return prerequisites;
    }

    @Override
    public TechType getType() {
        return type;
    }
}

Then set up your Player class to check the tech tree for prerequisites before adding a tech or whatever you want:

public class Player {
    public Set<TechType> currentTechs;

    public Player() {
        currentTechs = EnumSet.of(TechType.NONE);
    }

    public boolean addTech(Tech tech) {
        if (currentTechs.containsAll(tech.getPrerequisites())) {
            currentTechs.add(tech.getType());
            return true;
        }
        return false;
    }
}

Implementation 2

Use case: when techs do not have to be dynamic class objects.

public enum Tech {
    NONE            (null,                      0),
    VEGETATION      (EnumSet.of(NONE),          1),
    LIVESTOCK       (EnumSet.of(NONE),          1),
    STRAWBERRIES    (EnumSet.of(VEGETATION),    3),
    BIODOME         (EnumSet.of(STRAWBERRIES),  5),
    BIOMASS         (EnumSet.of(VEGETATION,
                                LIVESTOCK),     4);

    private final Set<Tech> prerequisites;
    private final int turnsRequired;

    Tech(Set<Tech> prerequisites, int turnsRequired) {
        this.prerequisites = prerequisites;
        this.turnsRequired = turnsRequired;
    }
    public Set<Tech> prerequisites() {
        return prerequisites;
    }

    public int turnsRequired() {
        return turnsRequired;
    }
}

Here you can add as many parameters as you want, such as a thumbnail icon and description string or whatever.

Then you could schedule research jobs through the Player class:

public class Player {
    private Set<Tech> techsKnown;

    public Player() {
        techsKnown = EnumSet.of(Tech.NONE);
    }

    public boolean researchTech(Tech tech) {
        if (techsKnown.containsAll(tech.prerequisites())) {
            addResearchJob(tech, tech.turnsRequired());
            return true;
        }
        return false;
    }

    ...

    public void researchJobDone(Tech tech) {
        techsKnown.add(tech);
    }
}

A benefit to this is you could easily combine the methods into a generic "Constructable/Researchable" interface and have the Tech enum and Building class implement it. Then the player could "startWorkOn" either polymorphically.

share|improve this answer
    
thanks! This looks the most promising so far, as I can easily add/modify techs as I go. –  edthethird Mar 16 '12 at 3:24
    
I edited in another (somewhat nicer) implementation. There is still lots more you can do with enums, like implement abstract functions for each instance. –  Matt Eckert Mar 16 '12 at 4:55

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.