From: tehom@REMOVEpanNOSPAMix.com   
      
   steve.breslin@gmail.com writes:   
      
   > I want to resolve a shortest path between two nodes (vertices) in a   
   > graph; some arcs (edges) are "locked"; the locked arc can be traversed   
   > only if we have already visited one of its key-nodes (and a lock can   
   > have more than one key-node); the key-nodes are dispersed throughout   
   > the graph.   
   >   
   > I think this is closely similar to a SOP, but of course it is not   
   > technically a SOP: we want the shortest path to the goal node, not the   
   > shortest path through all the locked arcs and key-nodes.   
   > I'd greatly appreciate any suggestions.   
      
   Sounds like you could basically use A* and carry some extra   
   information along.  Like, each boundary node would retain not just one   
   shortest path, but the shortest path relative to each combination of   
   keys.   
      
   Eg, if node A can be reached by path (B C D), and that path acquired   
   key K1, (we don't care which node was the key-node), we associate node   
   A with the list of 1 element:   
      
       lengthBCD, (K1)   
      
   If later we find that a shorter path (B D) reaches A but acquires no   
   key, we now have a list of 2 elements:   
      
       lengthBCD, (K1)   
       lengthBD, ()   
      
   And if later we find that path (B E) is shorter than both (B C D) and   
   (B D) and acquires K2, it doesn't replace the path with K1, but   
   replaces the path with no key, and we have:   
      
       lengthBCD, (K1)   
       lengthBE, (K2)   
      
   And if path (F) is still shorter and acquires K1 and K2, it replaces   
   both, and we have 1 element again:   
      
       lengthF, (K1 K2)   
      
      
   Obviously for a node containing key K, all paths proceeding from it   
   would acquire key K, and a lock node rejects any path that has not   
   acquired the key that it needs.  Aside from that, we just propagate as   
   usual except that we carry a keyset along too.   
      
   This allows you to have duplicate keys in distinct nodes, if you want   
   to.   
      
   Implementationwise, for a reasonably small set of keys, it probably   
   makes sense to represent them as bits in a bitvector; comparison is   
   extremely cheap.   
      
   May I ask what this is for?  Sounds like a game level designer's   
   helper, but maybe that's just me.   
      
   --   
   Tom Breton, the calm-eyed visionary   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)