Fantastic!

An interesting solution

Hello again!
I've continued working on my obstacle aversion program, and after a little more editing and head scratching I got my program to come up with this, correct, albeit silly solution. This weird little guy resulted from giving the function to compute the X to plug into the obstacle the wrong obstacle to use for it's functions and what not. (Once you see the pseudo code you'll understand)

figure 1

So I put in a check to see if the lines being computed by the first part of my algorithm were correct. And as you can see in figure 1, the lines were going to each end point of the obstacle cluster. Those two lines were then compared by length to decide which would be the best path to tread.
The little vertical line is part of the cluster that got accidentally thrown in by mistake.

figure 2

So since I knew that my lines were correct, I figured out what the problem was and fixed it, and lo and behold, I arrived at the correct solution! Which is shown in figure 2.

The function that avoids the Cluster is only 31 lines long. Granted it uses a helper function and classes previously defined in the file, but still. Pretty good compared to my old function that had 63 lines and used a whole other class for piece wise classes.

So Let me explain my 'Cluster' before I state my algorithm, my Cluster is really just an extra part of my Line class that might not be apparent to anyone not reading the documentation I might write for it one day. Basically, my Line's also have the ability to link them to other Line's via nodes. Like a linked list. Each line has a next and prev variable that holds a pointer to another line. And of course it has function to check if the line has a next or prev. This way, if you try to call a getNext function, it can make sure that doesn't happen.

Ok, now for the algorithm.

Function takes itself (the line) and a cluster
if the line intersects the cluster
     >go to head end of the cluster, save pointer to head
     >go to tail end of cluster, save pointer to tail
      create Lines AB and AC that go from the lines start point
      - to the heads start point, tail end points, see figure 1
      compare AB and AC's length choosing the shorter one, assign a new pointer to hold this shorter
      at the same time, whichever obstacle the shorter line points to assign a pointer to that
      use the helper function to choose an x to plot with the obstacles line function
     create the two new lines using the original start points and endpoints and the new start and endpoints from
     your new x and y from the helper function and obstacle functions.
     return the two lines in an array.

It's pretty simple really.


def avoidCluster(self,clust):
        if(self.intersectL(clust)):
            c = clust.hasPrev()
            d = clust
            while(c):
                if(d.hasPrev()):
                    d = clust.prev
                    print -1
                    c = d.hasPrev()
            head = d
            c = clust.hasNext()
            d = clust
            while(c):
                if(d.hasNext()):
                    d = clust.next
                    print +1
                    c = d.hasNext()
            tail = d
            AB= Line(self.sx,self.sy,head.sx,head.sy)
            AC= Line(self.sx,self.sy,tail.ex,tail.ey)
            #drawLines([AB,AC],clust.getAll(),'check.jpg')
            if(AB < AC):
                LOne = AB
                line = head
            else:
                LOne = AC
                line = tail
            x = self.helperChooseX(line,LOne.ex)
            y = line.func(x)
            newLine1 = Line(self.sx,self.sy,x,y)
            newLine2 = Line(x,y,self.ex,self.ey)
            return [newLine1,newLine2]



that's the code in case my algorithm wasnt very clear.
Woo!

Now I'm going to combine my avoidCluster and avoidLine functions to create a function that can avoid all obstacles!
  

Note:
     the line AB < AC is really comparing AB.length and AC.length but I overrided the python __lt__ function of my Line object so I could make the comparison directly. which worked very well.
     Also, the two print -1 and +1 was making sure my clusters were cycled back to their head and tail ends correctly.
     The commented out line drawLines, is what made Figure 2
     the helper function is only 11 lines lone so if you want to get technical my new function takes up 43? lines. But that's still significantly better than my other function which took 60 something as well as using other helper functions! Hooray for elegant solutions