Tuesday, November 16, 2010

Node Box Transformations

Well hello again everybody! So I got to Wikipedia browsing, ended up in Artificial intelligence, and found something called Scene Graphs. Which are basically giant linked list structures, much like what I used before in various programs. I had no idea they had a name! Where you basically have a grid of linked structures, and those nodes point to things that are instantiated. While I always had them stored in arrays. My ideas were similar. But to represent an entire graph as a bunch of linked nodes never occurred to me as something that would be efficient at all!

3x3 Node box
So I got to thinking how I could use this type of structure. And decided to have a box, that could take inputs and translate them into box movements. As you can see in the picture to the right. It's pretty simple looking. Now obviously, when you apply force to the middle node on any side, it should shift the entire box if the force is sufficient. But, when you apply force to any of the corners of the box. Then, as my friend pointed out, the box should rotate. Right?

A corner node
Unfortunately, this complicates my coding quite a bit. At first I thought to try to use the fact that the angle between corner nodes and their adjacent nodes should be 90 degrees, or 180,270,360. Whichever one was necessary for the corner. But, I couldn't find, or remember how to get the angle between two lines easily. Without using dot notation for vectors, which I didn't want to do at all. So it was back to the thinking board for a bit.



Translating rotation
 to adjacent nodes
Luckily for me, as I was drawing out right triangles and trying to find some relationship. My brain clicked and got the image to the right. The red lines are how much the node moves in x coordinates, and then on the bottom part of the image, that same amount is translated to it's adjacent nodes! I'm not sure if this identity is completely true. But eyeballing objects that I moved in experimentation, And drawing out triangles with a ruler seem to confirm it. Observations were good enough for old school physicists, so I'm going with them on this one!

So I've been coding this bad boy up, and have reached the point where I have my node's behavior coded in. Though I have yet to actually test it and create a node box. Once I do that, then hopefully, I won't have to rework too much code. The overall goal of this little project is to create swarm-like AI structures that will attempt to push a block from one location to another, but they have to have enough of themselves pushing in the right directions to move the box. Their mass and force, must be greater than the inertial mass of the box itself. If they're not enough swarm-creatures to push the box, they can breed to make more.

It's very very basic AI coding with an implementation of an odd node box. This should be interesting! Maybe if it's easier than I think it will be, I can rig up some directX code to display a box going through what the node box is having done to it.

Thursday, November 11, 2010

Imaging and Transformation

Well, I decided to get an easier interface with the imaging library I'm using. I was just calling a function I had made before that accepted two arrays and a name for a file to be saved too. But I decided I'd like to have my graphs plotted like they're graphs. So I created a class that would accept a size (x by y) for a pane to draw to, and a coordinate system to use. 'c' for Cartesian, 'a' for absolute. Cartesian is the coordinate system you normally use, where there are 4 quadrants and it's pretty simple to plot. Absolute is how the computer really plots pixels, from the top left. There is no negative positions, only positive going eastward from the top left as x, and southward from the top left as y.

It was really simple to figure out how to transform coordinates in absolute to Cartesian. You simply take the of your pane, divide it by 2, and those (x,y) points are your origin. So when you receive absolute positions from the user, you simple do originX + incomingX and originY - incomingY. It's really simple! I was pretty happy at how well it worked out.

So I also made a couple functions to draw a Grid to the pane so you can see your lines with the axes and graph paper like quality, or just the axes. It's great! And it makes seeing my recursive solutions from my other program really easy!

My next project is to make an ongoing simulation where you can give the program points to go after loading up a maze of obstacles, set a start point and ask it to go places. If I can get that working, then I can move on to try to get some image processing to process images of streets and other things, and allow a user to flag things as obstacles and the program suggest ways to go about getting around them.
My Ultimate goal is to make it completely automated, flagging obstacles by itself and coming up with the best strategy to attack the problem, or suggesting multiple strategies. And from there, having it compute how 2 objects could work together to outflank anything behind the obstacles. Basically, a very basic tactical advisory unit. Or as my project folder is called, TAU.
Solution plotted with Grid
Solution plotted without
grid but with axes
Just the grid being displayed
mission accomplished!

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.

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

Sunday, November 7, 2010

Ha! A new approach

figure 1
I started working on my path finding algorithms again. I have yet to do any coding, however I've come to an epiphany of how to solve my problem that I was running into before, this problem is shown in figure 1. In my previous recursive algorithm, I treated each obstacle line as that, a line. Instead of considering the entire object as one obstacle.

Of course this means reworking an obstacle class to be more like a system of equations instead of just using an array of lines to increment through the obstacles to bypass. By comparing obstacle endpoints and startpoints with each other. The ones that are shared will then be considered one object. Thus, a solution path around that object involves skirting the edges of the lines of the obstacle themselves, and then computing the shortest path. I don't know why I didn't think of doing something along these lines before in all honesty.

I'll set up the class to have a flag to be checked if the obstacle is more than a simple line or not. If it's not, then a simple startpoint to obstacle end or start point and then to destination will suffice. If it's flagged, than the line of the other obstacle parts will be copied and shifted by X closer to the start position, and a little bit longer than the obstacle line so it moves past it.

I'm so excited to code this and fix it!