How to iterate through members of lists of members of lists within members of previous lists?

Question

I'm sorry for the clumsy title, and for what will be the continuation of further clumsiness in my question - I'm not even sure how to properly ask this, so please allow me to illustrate:

I'm writing a game using XNA and C#.

I have 'nodes' in 2d space, and I'm trying to create a network of nodes representing traverse-able world-space.

The nodes themselves store a list of their 'neighbors', and an associated dictionary that refer to how an AI might travel from one node to a node's neighbor, either by walking, or jumping.

I'm trying to find a way that I may iterate from the list of one node's neighbors, to its neighbor's neighbors, to its neighbor's neighbor's neighbors, etc. etc. etc., to test each for contiguous neighboring connections based on whether or not they are all reachable to each other by 'Walk' (so I can find whole walkable platform segments).

Answer 1

I'd make it a bit simpler. Each Node will contain a single List of NodeTransitions.

A NodeTransition is something simple like:

public class NodeTransition {
    public Node node; //neighbor node
    public Action action; //how to get to neighbor node
}

You can then perform a breadth first search, of Nodes. Perhaps choosing a recursive algorithm. Once you find your target node, you can step back up to your starting node, keeping track of each NodeTransition along the way. You've just created a list that gives you each Node and the action required to get to that Node, to take you from point A to B.

If possible, you may want to structure things so you can at least get a direction for your neighbor nodes. This would allow for a A* search, which would be much faster for the average path. (Technically this is available, but you'd have to look at each node to determine this).

Answer 2

This is just a recursive search through all the connected nodes.

For each node, iterate through all its immediate neighbors, adding it to your currently known connected set. Then recurse for any previously unseen nodes.

class Node {
    Dictionary<Node, Action> neighbors;

    public IEnumerable<Node> getNeighbors(Action actionType) {
        return from pair in neighbors
               where pair.Value == actionType
               select pair.Key;
    }
    public IEnumerable<Node> getAllConnected(Action actionType, HashSet<Node> currentlyKnown = null) {
        if (currentlyKnown == null)
            currentlyKnown = new HashSet<Node>();

        currentlyKnown.Add(this);
        foreach(var x in getNeighbors(actionType))
            if (!currentlyKnown.Contains(x))
                x.getAllConnected(actionType, currentlyKnown);

        return currentlyKnown;
    }

}