10 Replies Latest reply on Jul 2, 2007 12:40 PM by kglad

    Finding unique paths

    Level 7
      Ok, here is the situation. I have several "Shapes" which are MovieClips
      that consist of "Nodes" (MovieClips) at the vertices. What I need to do
      (during runtime) is determine whether there is a path from any given Node
      to Shape_0 (the anchor shape).

      Here is the data I am able to generate and store in an Object...

      Key Value
      Shape_5.Node_3 ==> Shape_3.Node_1, Shape_0.Node_5
      Shape_5.Node_0 ==> Shape_1.Node_2, Shape_0.Node_0
      Shape_4.Node_1 ==> Shape_3.Node_2
      Shape_4.Node_0 ==> Shape_3.Node_3
      Shape_3.Node_3 ==> Shape_4.Node_0
      Shape_3.Node_2 ==> Shape_4.Node_1
      Shape_3.Node_1 ==> Shape_5.Node_3, Shape_0.Node_5
      Shape_3.Node_0 ==> Shape_0.Node_4
      Shape_2.Node_3 ==> Shape_1.Node_0
      Shape_2.Node_2 ==> Shape_1.Node_1
      Shape_1.Node_3 ==> Shape_0.Node_1
      Shape_1.Node_2 ==> Shape_5.Node_0, Shape_0.Node_0
      Shape_1.Node_1 ==> Shape_2.Node_2
      Shape_1.Node_0 ==> Shape_2.Node_3
      Shape_0.Node_5 ==> Shape_5.Node_3, Shape_3.Node_1
      Shape_0.Node_4 ==> Shape_3.Node_0
      Shape_0.Node_1 ==> Shape_1.Node_3
      Shape_0.Node_0 ==> Shape_5.Node_0, Shape_1.Node_2

      This translates to:
      Starting Node ==> Possible Destination Nodes

      So, taking the first piece of data (for example) I can see that Shape_
      5.Node_3 is connected to Shape_0.Node_5, so Shape_5 has a path to Shape_
      0.

      Alternately it can be found that Shape_4.Node_1 is connected to Shape_3
      and Shape_3.Node_0 is connected to Shape_0, so Shape_4 has a path to
      Shape_0.

      Ultimately my function will determine whether there are at least 2 unique
      paths to Shape_0, but for now I just need to determine whether any path
      exists.

      Thanks!!!




        • 1. Re: Finding unique paths
          kglad Adobe Community Professional & MVP
          each node should have an object property, say obj. the object property of Shape_5.Node_3, should have keys of Shape_3 (with value Node_1) and Shape_0 (with value Node_5). etc for the other shapes and nodes

          if you want to determine if Shape_n has a path to Shape_m, loop through all node objects of Shape_n to see if any has a key of Shape_m.
          • 2. Re: Finding unique paths
            crazyjoemilan Level 2
            on an almost related note,

            for($i in someMC) {
            if ($i instanceOf TextField) {
            trace("howdydoody")
            }
            }

            I have a stage designed page with a bunch of input fields. I thought rather than define everything, I could just loop through the whole of the file to collect the values, but I can't (and quit early) find a quick way to do it.

            Any ideas?
            • 3. Re: Finding unique paths
              Level 7
              "kglad" <webforumsuser@macromedia.com> wrote in
              news:f63vrg$4go$1@forums.macromedia.com:

              > each node should have an object property, say obj. the object
              > property of Shape_5.Node_3, should have keys of Shape_3 (with value
              > Node_1) and Shape_0 (with value Node_5). etc for the other shapes and
              > nodes
              >
              > if you want to determine if Shape_n has a path to Shape_m, loop
              > through all
              > node objects of Shape_n to see if any has a key of Shape_m.
              >


              Thanks for the response kglad. This would work for Shape_n to Shape_m if
              they are touching, however sometimes there are several Shapes in between
              the two. So, I think I need to do something recursively to determine if a
              path exists.

              Thanks.
              • 4. Re: Finding unique paths
                kglad Adobe Community Professional & MVP
                use nested for-loops to loop through intermediate shapes to see if there's a path.
                • 5. Re: Finding unique paths
                  Level 7
                  "kglad" <webforumsuser@macromedia.com> wrote in
                  news:f643m5$8nq$1@forums.macromedia.com:

                  > use nested for-loops to loop through intermediate shapes to see if
                  > there's a path.

                  Understood... the problem is two fold. First, the shapes are mutable and
                  their arrangement changes througout. Second, their is not a set number of
                  shapes between the one in questions (Shape_n) and the anchor shape
                  (Shape_m). There could be anywhere from 0 to 10 shapes between them.

                  But the number of possible shapes on the Stage will change depending on the
                  level of the game so it should not be something like hardcoded nested for
                  loops.

                  Thanks again.
                  • 7. Re: Finding unique paths
                    Level 7
                    kglad wrote:
                    > :
                    >
                    >
                    >
                    > function pathExists(shapeStart, shapeEnd):Boolean {
                    > for (var node in shapeStart) {
                    > for (var key in shapeStart[node].obj) {
                    > if (key == shapeEnd) {
                    > return true;
                    > } else {
                    > pathExists(key,shapeEnd);
                    > }
                    > }
                    > }
                    > return false;
                    > }
                    >

                    kglad... you da bomb! Really, I do appreciate the help. I can tell
                    just reading it that it will work... but I'll probably have to wait till
                    Monday to find out.
                    • 8. Re: Finding unique paths
                      kglad Adobe Community Professional & MVP
                      you're welcome.
                      • 9. Re: Finding unique paths
                        Level 7
                        "kglad" <webforumsuser@macromedia.com> wrote in news:f648rg$e8m$1
                        @forums.macromedia.com:

                        > function pathExists(shapeStart, shapeEnd):Boolean {
                        > for (var node in shapeStart) {
                        > for (var key in shapeStart[node].obj) {
                        > if (key == shapeEnd) {
                        > return true;
                        > } else {
                        > pathExists(key,shapeEnd);
                        > }
                        > }
                        > }
                        > return false;
                        > }

                        kglad...

                        I implemented your solution this morning but came up with the same type
                        of problem I was having before with my own recursive function.

                        Here is the code (modified from what you posted) that I am using:
                        function pathExists(shapeStart, shapeEnd):Boolean {
                        for (var i:Number = 0; i < allConnections[shapeStart].length; i++) {
                        if (allConnections[shapeStart] ._parent == shapeEnd) {
                        trace("shapeEnd found in list");
                        return true;
                        } else if (checkedParents.indexOf(allConnections[shapeStart]
                        .
                        _parent) == -1) {
                        checkedParents.push(allConnections[shapeStart] ._parent)
                        pathExists(allConnections[shapeStart]
                        ._parent,shapeEnd);
                        }
                        }
                        return false;
                        }

                        The problem is this... once the condition is met which returns true (I
                        know this condition is met because my trace works) it does not actually
                        return true to the initial caller. So, I end up with false being
                        returned. It is as if the true is being returned to the recursive call
                        and not to the original function call. Does that make sense?

                        Thanks...


                        • 10. Re: Finding unique paths
                          kglad Adobe Community Professional & MVP
                          instead of using returns assign a boolean to a variable to indicate if a path exists and check that variable's value.