Lets say that you have a reasonably small graph. Each node in the graph has either no ''requirement'', or a single ''requirement''. For instance: Requirements: None Open Doors Jump Nodes: n0 = None. n1 = Open Doors. n2 = jump. n3 = None. Edges: n0 <-> n1 n0 <-> n2 n1 <-> n3 n2 <-> n3 From n0 to n3, I would like to be able to extract: -- To get from n0 to n3, AI must be able to either open doors or jump. -- Now, as an additional layer of complexity, over larger graphs, requirements may look more like: -- To get from n0 to n3, AI must be able to open doors and crawl or open doors and jump. -- Any keywords, whitepapers or algorithm names to check out would be appreciated. I spent a while this weekend looking around the net and various books, but couldn''t find anything. Thanks!

I''d have each type of movement as a different edge "colouring". Just check which colours are possible for the AI as it navigates the graph.