0

Context:

For a video game, I need to load an arbitrary amount of resources which when combined would form a complete level of the game. These resources would be 3D models, textures, sound, etc.

Some resources depend on others,

e.g. a track needs its textures to be loaded first before it can be loaded.

What I've done so far:

The interface that defines a resource that has dependencies:

public interface IResource
{
    IList<IResource> Dependencies { get; }

    bool IsLoaded { get; }

    string Name { get; set; }

    void Load();
}

public abstract class Resource : IResource
{
    public IList<IResource> Dependencies { get; } = new List<IResource>();

    public bool IsLoaded { get; protected set; }

    public string Name { get; set; }

    public abstract void Load();

    public override string ToString()
    {
        return Name;
    }
}

Few examples of resources:

public class Level : Resource
{
    public override void Load()
    {
    }
}

public class Track : Resource
{
    public override void Load()
    {
    }
}

public class TrackTextures : Resource
{
    public override void Load()
    {
    }
}

public class Scene : Resource
{
    public override void Load()
    {
    }
}

public class SceneTextures : Resource
{
    public override void Load()
    {
    }
}

An example of resources to load:

private static IResource CreateLevel()
{
    var sceneTextures = new SceneTextures
    {
        Name = "scene textures"
    };

    var trackTextures = new TrackTextures
    {
        Name = "track textures"
    };

    var scene = new Scene
    {
        Name = "scene",
        Dependencies =
        {
            new Scene
            {
                Name = "scene 9",
                Dependencies =
                {
                    sceneTextures
                }
            },
            new Scene
            {
                Name = "scene 10",
                Dependencies =
                {
                    sceneTextures
                }
            }
        }
    };

    var track = new Track
    {
        Name = "track",
        Dependencies =
        {
            trackTextures
        }
    };

    var level = new Level
    {
        Name = "level",
        Dependencies =
        {
            scene,
            track
        }
    };

    return level;
}

Finally, read the resources, sort them descending according dependency tree first:

private static void ReadLevel([NotNull] IResource resource)
{
    if (resource == null)
        throw new ArgumentNullException(nameof(resource));

    var queue = new Queue<IResource>(new[] {resource});
    var stack = new Stack<IResource>();

    while (queue.Any())
    {
        var dequeue = queue.Dequeue();

        var dependencies = dequeue.Dependencies;

        foreach (var dependency in dependencies)
        {
            queue.Enqueue(dependency);
        }

        stack.Push(dequeue);
    }

    while (stack.Any())
    {
        var pop = stack.Pop();
        pop.Load();
    }
}

Right now this skeleton works as expected, resources are loaded in the right order so that parents can get their dependencies first to load themselves (not shown).

Issues:

1#

A single resource can be in the stack many times when it's used more than once, I have been looking for a mix of a stack and hash set but I feel this is probably wrong since it's quite weird.

I can solve this problem relatively easily using some bool IsLoaded property to check first but this won't be right as I first plan to traverse that tree to count the total items for reporting loading progress, like the following:

enter image description here

2#

I feel I am re-inventing the wheel but so far I couldn't find any relevant stuff about this problem on the web, probably by the lack of typing the right words in a search engine.

3#

Right now circular dependencies are not checked out for, it would be nice to be able to do so for reporting an error instead of the program being caught in an infinite loop.

Question:

How such system could be designed and/or is there already a framework that would do so ?

1

I'm going to start with detecting cyclical dependencies. This can be done by checking if a dependency is part of the chain leading to that dependency, i.e. something like this:

private static bool IsCyclic(IResource resource)
    {
        var stack = new Stack<IResource>();
        stack.Push(resource);
        while (stack.Any())
        {
            var current = stack.Pop();
            foreach(var dependency in current.Dependencies)
            {
                if (stack.Contains(dependency))
                    return true; // this should ideally contain more information about what caused the cycle.
                stack.Push(dependency);
            }
        }
        return false;
    }

to avoid duplicate resources we can simply only include the first of each resource. Unfortunately Linq.Distinct() results are unordered. You could simply convert the stack to a list, iterate over it and remove all but the first of each item. Another way would be to do it inline while traversing the tree, this has the benefit of being a bit faster if there are lots of duplicates since you can skip traversing that part of the tree.

/// <summary>
/// Traverses the tree depth first, the results are ordered in reverse depth first order, only including the first instance of each resource. 
/// </summary>
private static void GetUniqueDependencies(IResource current, HashSet<IResource> visited, IList<IResource> results)
{
    // ensure only the first occurrence of a resource is included
    if (visited.Contains(current))
        return;

    var dependencies = current.Dependencies;
    foreach (var dependency in dependencies)
    {
        // Recurse
        GetUniqueDependencies(dependency, visited, results);
    }

    // Adding the items after doing the recursion ensures the dependencies of a resource is placed before the resource itself.
    results.Add(current);
    visited.Add(current);
}

private static void ReadLevel(IResource resource)
{
    if (resource == null)
        throw new ArgumentNullException(nameof(resource));

    if (IsCyclic(resource))
    {
        throw new InvalidOperationException("Cyclical dependencies detected");
    }

    var dependencies = new List<IResource>();
    GetUniqueDependencies(resource, new HashSet<IResource>(), dependencies);
    foreach (var dependency in dependencies)
    {
        dependency.Load();
    }
}

Please note that the code is not tested, and is provided for illustrative purposes only.

This kind of graph is called a "Directed acyclic graph" or DAG, and occurs in all kinds of circumstances. There is plenty of literature on this concept and how to do traversal etc. There probably are existing solutions that could be used for this kind of thing, build systems come to mind, but the effort to use such a system might be larger than just doing it yourself.

Also consider making a generic interface for a tree to make the code for the tree traversal reusable.

  • I'll improvise from here, thank you! – Aybe Aug 13 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.