CODEWITHSUNDEEP
c#algorithmrecursionunity-game-engine
Miron Alex
Miron Alex

Reputation: 258

Recursive algorithm for adding items into a list

I am having some problems writing a recursive algorithm.

I have an item that affects other items. Each of the affected items might affect other items...etc. With a limited number of steps I might write:

var tempAffected = new List<Item>();
foreach(var item2 in item1.affectedItems)
{
    if(item2.affectedItems > 0)
    {
        foreach(var item3 in item2.affectedItems)
        {
            if(item3.affectedItems > 0)
            {
                ...
                tempAffected.AddRange(item3.affectedItems)
                tempAffected.Add(item3);
            }
            else
                tempAffected.AddItem(item3);
        }  
     }
     else
         tempAffected.AddItem(item2);
 }

But I would like something recursive. Any help would be appreciated.

EDIT

The final code ended up looking like this, after a few modifications in my code.

var tempAffected = new List<HSGameItem>();
    var stack = new Stack<HSGameItem>(affected);

    Func<HSGameItem, List<HSGameItem>> affectedForItem = item => {
        if (item.booster.accounted)
            return new List<HSGameItem> ();
        item.booster.accounted = true;
        return item.booster.affected;
    };

    while(stack.Count > 0)
    {
        var childrenParent = stack.Pop();
        foreach (var child in affectedForItem(childrenParent))
        {
            tempAffected.AddUnique(child);
            stack.Push(child);
        }
    }
    tempAffected.ForEach(x => x.state.Matched(mType, length));

I had to mark every item that i already affected as "accounted" to make sure i wouldn't check it again.

Upvotes: 1

Views: 2651

Answers (2)

Peter Duniho
Peter Duniho

Reputation: 70681

IMHO, the simplest implementation might look something like this:

IEnumerable<Item> GetAffectedItems(Item item)
{
    foreach (Item affectedItem in item.affectedItems)
    {
        foreach (Item subItem in GetAffectedItems(affectedItem))
        {
            yield return subItem;
        }
    }

    yield return item;
}

That said, note that the above will instantiate a large number of iterators (but at least that's better than creating a lot of copies of the data itself!). It's simple to write, but may not be as efficient as some other mechanism for enumerating all of the affected items.

As an example, an alternative would be to just build a List<Item> as you recurse (more similar to your original example):

List<Item> GetAffectedItems(Item item)
{
    List<Item> list = new List<Item>();

    GetAffectedItems(item, list);
    return list;
}

void GetAffectedItems(Item item, List<Item> list)
{
    foreach (Item affectedItem in item.affectedItems)
    {
        GetAffectedItems(affectedItem, list);
    }

    list.Add(item);
}

Upvotes: 1

Roy Dictus
Roy Dictus

Reputation: 33139

So basically you want to collect all affected items into a temporary list called TempAffected, right?

Then you could do:

public List<Item> tempAffected = new List<Item>();

AddAffectedToDerived(item1, tempAffected);


private AddAffectedToDerived(Item root, List<Item> derived)
{
    if (root.AffectedItems != null)
    {
        foreach(Item itemX in root.AffectedItems)
        {
           AddAffectedToDerived(itemX);
        }
    }

    derived.Add(root);
}

That should do the trick for you.

Mind you, if your data structures are very large, you may want to use an iterative approach rather than a recursive instead because of the risk of stack overflow.

Upvotes: 2

Related Questions