Is lookup table here necessary at all?

[dzhuzha]

Sorry, but I try understand - what the profit from usage here lookup table (with additional memory allocations) instead of just simple foreach search through all existing nodes and creation of list of child nodes?

or in a such way if we want look only through parentNode children.

[Brian_Trotter]

The NodeLookup’s purpose is to quickly translate the identifier of the node to the actual node itself. Nothing will be faster for this than a Dictionary. It also does this with far less overhead than a Linq expression… (don’t get me wrong, I use a Linq expressions all the time, being mindful of when the overhead is not worth it).
Every time a Linq expression is called, a new temporary copy of the collection it’s acting on is created…
Imagine you have 100 DialogueNodes…
You have a parent node with 3 children…
Each iteration of the first foreach you mention

foreach (var node in _nodes)
{
    if(parentNode.Children.Contains(node.Id))
    {
          childNodes.Add(node);
    }
}

will require 100 iterations over the foreach loop. As you’re in the Editor drawing nodes, this will be noticed as the number of Dialogue nodes increases.

In the second case, with the Linq expression and targetted to only work on the parentNode.Children, The linq expression will be evaluating all 100 nodes * the number of children in the collection. It will actually be less performant than the previous for loop and it will leave garbage in the heap (overhead) that the Garbage collector will have to deal with at some point or another.

Here’s a mildly better Linq expression, but it does require that aforementioned lookup to have been created:

        public IEnumerable<DialogueNode> GetAllChildren(DialogueNode node)
        {
            {
                return from child in node.GetChildren() where nodeLookup.ContainsKey(child) select nodeLookup[child];
            }
        }

Now in this case, it is making two copies of the collection, but the collection is already restricted to the children of the parent node. It would be leaving less garbage in the heap, and it’s still relatively fast. If you had some form of transactionally enforced validation (like in a strong database), you could even leave out the where clause (because you’ve ensured that no children in the DialogueNode are not in the lookup).

[dzhuzha]

Brian, Thanks for for the detailed answer.