Monday, November 8, 2010

Recursive Solution For obstacle avoidance program

Ha ha!

It's now 1:46am, but that is perfectly ok, because after only a few hours at work I've managed to combine my two functions, avoidLine, and avoidCluster into one function avoidObstacles! Alright so here's the breakdown!

when you call avoidObstacles() from your line instance, you're really calling a wrapper function that calls a recursive algorithm that takes the obstacle array as well as an array to hold the solution lines you're generating.
This allows for user friendliness, that way they client doesn't have to pass in an array holding a reference to the object calling the function.
Figure 1- Partial solution

You can see the 2 Lines used
to find the other 3 in this picture
See figure 2 if you can't see which
are the partial solutions.
So heres how it works:

Base Case = length of the obstacle array is 0
     return lines array
otherwise
     if last object in lines array intersects first object in obstacle array:
          is obstacle a cluster?
               YES > avoidCluster call
                           replace last object in lines with first line from 
                           Cluster
               append second line from avoidCluster call to lines array
               remove obstacles from obstacle array
         else is obstacle a line?
               YES > avoidLine call
               replace last object in lines with first line from avoidLine
               append second line from avoidLine call to lines array
               remove obstacle from obstacle array
     return (recursive call to function)

So, to make this as clean as possible, I wrote a isCluster function to check if the Line was linked to any other, also there still is a small bug in the program that I'll have to be careful of.

If the obstacle array does not hold all the obstacle clusters parts, then the function will crash. Because python will report an error if it cannot remove the object from the array, and it can't do that if it's not in there. Doing a check to see if the obstacles parts are in the array is possible using the 'in' keyword. But even with that fix, when calling the drawLines function, or any other function, you might try to pass the array of obstacles in and forget it won't draw that particle line.

Technically the drawLines won't draw any of them if you pass in the obstacle array you used in the recursive call because the removal function of python is not only operating a local scope. Anyway though. Besides that bug, the program works very nicely.

Figure 2
Recursive Solution to
an array of obstacles
I did run into an amusing problem thought took up my time for a good hour or so. Which was the 2nd Line seemingly ignoring the obstacle that's not part of the cluster. So instead of the full solution to the left, it was a hybrid between figure 1 and 2. I did have an image saved, however it was written over during the 2 hour process. Anyway, the problem was, that I wasn't passing in the correct array to my drawLines function, and my recursive solution was working the whole time. I figured this out by printing off the starting and ending points of all the lines returned by my function.

 I feel very accomplished after managing to work around all the issues I had when I was attempting this problem before. This was a definite positive increase in my day's overall situation. Instead of attending a review session for an upcoming test in my Discrete Mathematics and Structures class, I read a little bit of A Brief History of Time, and took a nap. Or at least tried, I cried a little and was trying to figure out what I really want from life in general, and who I want to be. Lucky for me I was attempting to take a nap so when my roommate mentioned my eyes looking like I'd been crying for an hour, I could wave it off as being sleepy. I prefer to keep my friends away from my issues. I don't the pity, I have plenty enough for myself.

Going back to happy thoughts, my recursive solution is even more elegant than I had originally thought it would be. Being exactly 18 lines long. Although it might increase maybe 2 lines if I add the code to check for obstacle cluster pieces not being in the array and just forcing the function to return at that point and yell at the client.
Good times,
I think I'll finish listening to Я твоя не первая and then go to bed.

No comments:

Post a Comment