Creating a tree of required items

Question

As I am developing my small game, I have made a lot of progress yet frustrated about a lot of things. The latest thing was creating a list of required items and for you to understand that I will provide you with both Explanation as well as Code which I created but obviously doesn't work...

I - Explanation

In order for the player to build a building he must have done some required researches with each research requires more researches for it to be researched... It is like a tree of researches that the player will go through them by exploring the game and doing some tasks...

So to imagine it more accurately you can look at my small code here

II - Code

    //Available Main Elements
    var carbon = new Element {Name = "Carbon"};
    var hydrogen = new Element {Name = "Hydrogen"};
    var oxygen = new Element {Name = "Oxygen"};
    var nitrogen = new Element {Name = "Nitrogen"};

        //Example Research
var steam = new Research(name : "Steam", requiredElements: null, requiredResearches: /*Fire*/ & /*Water*/ & /*Iron*/);

So from the last snippet of code [which is just to explain] the player want to research the Steam that for instance needs 3 more researches in order to be researched... one of which the Iron also needs 1 more research to be researched and so on [maybe less maybe more or maybe no requirements at all]...

Concluding that the Question is : How could I create such nesting so that when a player tries to do a research the system quickly looks at the researches he have done and the research he wants to do [including it's nested ones] and If the player did not meet the requirements it just returns a tree with what things he want's to achieve ?

After all, I just want to thank you in advance and I am waiting for your very valuable support...

Answer 1

I would remove the requirement logic out of the Research objects themselves. For simplicity say it was this:

public class Research
{
    public string Name { get; set; }
}

Then, I would keep a list of the requirements in a Dictonary where each Research contains a bucket of other Researches:

Dictionary<Research, List<Research>> requiredResearches = 
    new Dictionary<Research, List<Research>>();

// the list of Researches the player has completed
List<Research> playersResearched = new List<Research>;

For example, "Steam" would contain "Fire", "Water" and "Iron". And maybe "Iron" contains "Tin".

Next, given a Research, we could look at all of it's requierements including requirements of requirements:

// e.g. research is "Steam" and returns "Fire", "Water", "Iron", "Tin"
var chainOfRequirements = GetReq(requiredResearches, research);

That calls a recursive function like this:

public IList<Research> GetReq(Dictionary<Research, List<Research>> reqs, 
                              Research target)
{
    var chain = new List<Research>();
    if(reqs.ContainsKey(target))
    {
        foreach(var item in reqs[target])
        {
            chain.Add(item);
            chain.AddRange(GetReq(reqs, item));
        }
    }
    return chain;
}

What you are returned is a flat list of requirements (including requirements of requirements). At that point, a little query against the players list of Researches can return to you which ones that are missing:

var missing = chainOfRequirements.Where (c => 
                  playerResearches.Where (r => r == c).Any () == false).Distinct();

TO ENABLE COMPARING DICTIONARY USING "NAME"

public sealed class NameEqualityComparer : IEqualityComparer<Research>
{
    public bool Equals(Research x, Research y)
    {
        if (ReferenceEquals(x, y)) return true;
        if (ReferenceEquals(x, null)) return false;
        if (ReferenceEquals(y, null)) return false;
        if (x.GetType() != y.GetType()) return false;
        return string.Equals(x.Name, y.Name);
    }

    public int GetHashCode(Research obj)
    {
        return (obj.Name != null ? obj.Name.GetHashCode() : 0);
    }
}

Here is proof of concept.

Answer 2

I don't know C# well enough to provide code, but you could make each Research have an Array of type Research, that would hold the Research that must be done to be able to make the actual Research, then you only need to iterate the Array checking if all of them are completed.

You don't even need to check the requirements of the requirements, as if they are completed, they already have all requirements completed.

If the Research don't have any requirements you just let the Array empty.

Answer 3

I suggest that you make your own requirementsTree class, which would need to be a linked list with at least the following members:

• a requirementsTree[] prerequisiteResearch property, containing all of the research required for that particular item.
• a bool isResearched property, indicating if the player has in fact researched the item.
• a method, say, bool isEligibleToResearch(), which loops through all of the items in prerequisiteResearch to check if the player has already researched them.

With this I think you'd have a well-structured and extensible requirements class.

Answer 4

I can't think of any specific things that would prevent this from happening, but I can see why you'd be hesitant to just jump into coding it without having thought through the cases. To try to give some pointers, here are some functions I would imagine you having by the end:

// Having a function to retrieve a unique variable by its name (backed by a Dictionary<string, Research>)
// is often handy for me, especially if you decide to script the requirements tree in a text file.
// If you have enough references passed around that you can do this without a static method, all
// the better.
Research.getResearchByName(string name)

// A recursive function. If this research has not been completed, it adds itself to the set, as well
// as any prerequisites (by calling this function on its prerequisites). The top-level, public
// version of this function would create the set, and then return it after performing this check. If
// the Set is empty, then the player can start the research.
Research.addUnresearched_Internal(Set<Research> unresearched)

I think the main issue with my approach here is that I only thought to use a Set, rather than a Tree; but with some bit of variation, you might be able to do better than me.