Runtime Analysis On Turret3D

Since I have yet to decide on another project, I decided to do some runtime analysis on my program. At first, I looked at just the complexity of the overall algorithm, and figured it to be O(n) where n is the max lookahead value for the targeting algorithm, but since that literally took 2 seconds of thinking to do, I decided to figure out the more specific runtime, so I started checking on the complexity of the mathematical operations used within my code. To save myself the effort of typing it all up, and because blogger doesn't support latex embedded math typescripting (I believe), here's a screenshot of part of my paper that I wrote up.

If you do the math, the numbers won't add up quite correctly, the reason for the addition complexity in the actual runtime (the first line in the picture) is because of the boolean checks used to test if the loop should terminate or not.

The runtime is dominated by it's multiplications, as well as it's loop of course. So instead of just O(n) it's O(n * multiplications * trig). But, the addition and boolean constant time operations are negligible really, but they're included for specificity's sake.

I really want to create something involving AI, or using some Genetic Algorithms. But I have yet to figure out exactly what I want to do

Finished and Completed

Well, my 3-dimensional turret program has been finished. And I've even written up an 8 page document detailing the... well, details. It's available in pdf form, and if anyone would like a copy, all you've got to do is send me an email or leave a comment on this blog.

The real question is, what should I make next?

Working

I got my turret working. Or at least, it certainly seems it is working. See here:

The x axis is the x axis from the 3d vectors and the y value are the z height of the objects. Red is an object falling straight down at some position and green is the projectile fired. It seems like what I've done worked. But it doesn't make sense to me yet why.

What I'm confused about is how I fixed my problems I've had before. I changed the z velocity of the projectile to be v*sin(theta) and when calling an update to the projectile, instead of adding the position to the equation of the height I add the velocity instead. Somehow this works, but I do want to look into the mathematics before I do this. I'll update this project one more time if it turns out that this solution is not a fluke. And then start on a new one. I'm thinking of possibly coding up Tic Tac Toe to get my feet wet in some artificial intelligence.

Math, a new plane to work on

Idea given to me by my Math friend Adam

So, as I think I mentioned, I was discussing how to do this with a friend. But until tonight I didn't have too much time to reflect on what he was telling me. He said, not exactly:  use the angle of elevation to make a connecting line between the target and the turret, then use that and the plane of the z axis to create a new axis. Since this is now a 2d problem solve it with newtons laws of motions that take gravity into effect. And kerpow.

Ok he didn't say kerpow. but I'd like to imagine that's what his brain said when it thought all of that up. He's basically a math genius. Anyway though, what I'm now encountering as a difficulty, is how to switch from my ox,oy axes to my original coordinate system. ox corresponds to the line connecting them, so it must be the magnitude of the position vector. As far as converting the y axis of my new axis back, I'm not entirely sure. Although, I have a feeling that the converstion isn't neccesary for going back, only to converting the targets coordinates into the new system. But after that, the angle of elevation + the new angle given to me by my equations should give me the 'real angle' to fire on. And that will give me my velocity vector's z component. (it's x and y are calculated by the angle the turret faces on the XY plane. Anyway, I believe, that the y component of my target will be 0 in the ox,oy axes. Because the line connects both turret and target. And if you look at the drawing above, it's abundantly clear.

now that the details are, once again, possibly worked out. Time to code!

Been a little while

It's been a while since I've updated the running blog on the status of the 3d turret. Right now, I'm still working out a few bugs. But, I should have it figured out as soon as I find the time to do it. I've been very busy with schoolwork unfortunately. Not to mention trying to read library books on computer science before I have to return them. I did think of something today which I thought was worth posting about.

A problem I was running into was that I was measuring the distance traveled by the objects by their magnitude at a given time. This, while telling me if one will get there or not, is nice, but it doesn't actually tell me the difference between the actual distances they're traveling. When the projectile is fired, it travels in an arc of sorts, but the magnitude of it's vector only tells me how far away from the turret it is. Which is not what I want, I can use that information to see if the object is in range or not, but not for the estimation and leading part.

so, this is what I came up with: I'll have a running total for the distance traveled by the objects as oppose to a straight calculation based on it's magnitude. Since this will only introduce 2 more variables, I don't think this will effect the complexity of the algorithm too much either. Which is nice.

My main mistake in not doing this first, was that I was thinking too 2D ish for this 3D problem. But now I should be able to make some more progress!

Turret 3D Estimation... still quite a work in progress

Been a bit since I've updated you guy's on my project.
Gravity has once again, proven to be the bane of my existence. Hopefully my math friend will get back to me on what he meant when we went off about some equations and such. Anyway though. I screwed up in an equation, one which I took from wikipedia, I accidently wrote a + where should have been a minus, and by the time I noticed, I had already moved and changed lines of code that I thought were wrong because of it. So yeah, it's kind of unfortunate. So, now I'm going to sit back, and think for a while on this problem.

Gosh, I wish I had noticed that + sooner...

Gravity: Thou art a _ _ _ _ _

I've made progress in my 3D Turret program. I've (unfortunately for my poor brain) decided to include gravity in my calculations. Mainly because I'd prefer for my calculations to not shoot off into the sky without ever coming down again. Gravity's good for that sort of thing. Unfortunately, it's also good at making you do a bunch of calculations for determining maximum distance, terminal velocity, and a few other things. I did have a model that was close to what it should be, but the calculations it was making wasn't quite right. (Specifically it was 2 seconds later in hitting the ground than it should have been)

So I decided to peruse Wikipedia a little, specifically the free fall, projectile motion, and trajectory pages. They're plenty of nice equations ready to use. And although I was slightly saddened that I had admitted defeat in a way and just looked up the answer. The equation's were very similar to the ones I had devised. I had a big comment written at the top of my code that GRAVITY IS M/S^2, but for some reason I didn't square the time in my calculation for figuring the new z position of the projectile. But besides that, my equation was correct.  My velocity updating line of code was correct though, so I was quite happy. From this figuring out the maximum distance was a matter of either running trials of different time increments or solving an equation. Or the third option not allowed by any homework ever done by a person. Look up a calculator on the internet that displays all the information when you enter the right numbers. I opted for the third approach and then tested it against my code by running the simulation to that time and making sure the z went to 0.

The only thing I'm still unsure of, is terminal velocity. Which is, unfortunately, rather annoying to figure out when you have no idea what the dimensions of your hypothetical projectile is. So I had to determine what I was actually firing (a small bullet with a mass of .04 kg is what I believe I decided on, with a cross section of 50mm^2, traveling through  standard sea level air density (1.5 kg/m^3) with a drag coefficient of (.1) (a small ball by the examples I found, although it had a bullet (.3)) it gave a ridiculous terminal velocity (small that is not large) so I decided to go with my turret firing perfectly round projectiles.

So, after all that and 1 and a half cramped notebook pages later, I have an update position function I feel like I can rely on for my calculations.

Tommorow, after doing some trivial work (required course work for a required class which pertains to my major in no way), I'll start working on the estimation process and how it leads it's target through 3 dimensions. But for now, more reading Gödel, Escher, Bach by Douglas Hoftstadter (I'm a little more than halfway through the book )

3Dimensional Turret Beginning

So I've just finished coding my 3d vector class. And now am trying to think of how I'm going to do this. I want to introduce gravity into the simulation, but this restricts the range of the turret, which is realistic, does make an infinite loop of checking for targets that are in range a strong probability. Also, I'm trying to think of how exactly to orientate and move the turret.

Heres some solutions I've come up with so far:
I could do all the calculations out like before,  OR, since I made my previous 2D turret able to accept console output I could feed the coordinates into that, but that would only orientate the XY plane correctly, and even then, how would I grab the output from the execution? So, while it sparked my brain as a good idea at first, I think I'll ignore it a bit.

I think the hardest thing will be checking for gravity and other things of that nature. I know that in some science fictions, long range projectile weapons have to account for the curvature of the earth, but I don't think that will be my problem. So, to start off, I think the angle the turret's Z will be at is 45, aka the optimal distance angle, this could change a when aiming obviously. And now, before I was just using an arbituary 2 units / s for my projectile, but with the inclusion of gravity I think I've going to have to bump it up a bit to make the projectile move fast enough to stay airborne. I mean, let's face it, waiting 10 seconds for a projectile to hit a target is unrealistic. So I'll probably beef it up to say, 50 units / s or so and then just put the target out 150 or so units.

Since I've figured out the calculations to aim and lead in a 2d plane so I have reasonable confidence in extending it to the next plane up. It's just gravity and maximum distance I'm concerned about right now. Hmm.

I'll keep you updated

Not Sure about my previous solutions for the vector problems

Hm, It missed.

XY Velocity for a projectile? Solved for

Alright, So last I left off I had coded how to deal with projectiles moving in a strictly horizontal or vertical way. And was waiting on making the code for dealing with both velocities. At first I thought I would have to deal with some type of equation of two variables and solve form both of them using some complex business, but it turns out the method I use is at least 3x simpler than that.
So, first off I use the same method I've been using to get the time interval I should be using in my estimates. since I've described that in previous blogs I won't bother redefining it here. From that I get my hBound variable which is the top of said time interval. From here, I can compute how far the projectile will travel in the time given that it travels at a constant speed of 2.0 units. I then figure out the heading of my turret to aim at so it points at the targets estimated position after hBound time. From here all I need is the vector to give to the projectile as its x movement and y movement. So, using the cos of the gun's theta times the distance of the projectile as the x component and the sin of the guns theta times the distance of the projectile as the y component, I make up my vector. From this I have a triangle that may or may not overshoot the position if fired at the wrong time. So how do I figure my delay time out?

Simple, I take the magnitude of that vector I just made and divide by hBound to get how many units of time it will take to traverse this hypotenuse I've created. If that number is equal to the time it takes for the projectile to get to the estimated position then hoorah fire right away, weapons free, danger close. If its less than that then set up delay which is as simple as Time of the target - Time of the projectile. And the other situation, where T(proj) > T(target) never occurs because that would violate the work above with the whole hBound thing, theres a reason it's called the hBound you know. From here things get pretty simple.

since I have my heading, my delay time (if there is one) all that is left to do is to fire. Which is done by created  anew object that has the position of the turret, the velocity vector is the heading vector of the turret(which has been normalized) multiplied by the velocitiy I know the projectile will travel (2.0 units), ahem. Tah-dah.

Now of course is where I fork myself, should I proceed to trying to create a 3d version of this? Or should I build up a simple library in DirectX to actually see whats going on instead of just numbers? Hmmm.

Horizontal Target Tracking

Woo!

Just finished coding the turret of my current project to lead a target thats moving only horizontally. It took me a while to wrap my head around alot of the numbers, and also I was accidentally using degrees to start off my turrets heading and not radians. Wups!

Anyway, so this is how I accomplish leading a target horizontally:


 first using vector arithmatic and dot products and arcCos, we get the heading we'll be firing on.
 then we account for possible time delays in order to account for differences in distance.

 Heres the code: there is some stuff missing that is declared a bit above, such as getting the hBound which is the time where the distance the projectile will travel becomes greater (or equal to) than the distance the target will travel in the same amount of time. This is used so that we can lead the target. But because we lead it, we need to make sure to fire at the correct time in order to score a direct hit. So thats why we do some subtraction between the amount of distance and time and all that. Anyway: Heres the code:



if(target.velocity.y == 0 && target.velocity.x != 0){ //target only moves horizontally
                //get the heading to fire on.
                estMagPos = estMagPos + estMagVel*hBound;
                Vector2D gt =  (estMagPos - gun.position ).Normalize();
                gun.theta -= acos(Dot(gt,gun.heading));
                gun.heading = gt;
                //now, account for leading and time delay
                //hBound * vel = how much distance the proj will travel. 
                //Use the gun.theta and this to resolve the vector into it's components
                //then the distance between the (hBound * vel) - x of target
                double projd = hBound * vel;
                projd = (cos(gun.theta ))*projd; // x distance of vector
                double deltax = projd - estMagPos.x;
                double waitT = deltax/vel;
                gun.countdown = -waitT; //negation to make positive. no neg times
                gun.locked = true;
                std::cout << "Target Locked. Countdown Til Firing: " << gun.countdown << std::endl;
                system("hal target lockd");


So, the calls to system and hal are just a speech program to say the string aloud. 

Getting a bit farther with my vectors

 So I've gotten a bit father with things, these two images show some of the thought process on what I'm working on right now.
Which is, targeting and leading when the object is moving horizontally only. I've already worked out the case for the stationary target, which is the easiest, so now I'm working on the next easiest (I think) which is just horizontal movement.

this image right here shows how I was trying to think about zones and ranges of the turret.

normally, I would go into detail on more stuff. But I'm pressed for time right now, but once I get back to the world of internets, then I will gladly post and describe all the difficulties I've been having and how I've been solving them.

coming close of vacation.

So, my vacation is starting to come to a close. And I'm looking at what I expected from this vacation, and what I actually got.

I expected that I would, maybe not get laid, but find someone here who might be a friend who I could share attraction with. And maybe have a brief fling. I did kiss one of my friends, but it's normal for her and I to kiss. We're close, and the kissing really doesn't mean much. I kiss a few of my female friends on the cheeks when I see or leave them, this one I kiss on either the cheek or the lips. It's not a romantic kiss though, it's kind of like an italian kiss I suppose because it's more friendly than anything else. Anyway, getting off topic here aren't I? I expected to maybe cuddle with a specific friend and to admit some feelings for her. That didn't happen, because even though I saw her twice... maybe three times, it was always with a group. And since she invited people to events that we had planned on doing. I'm taking her hint that she just wants to be friends who tell each other they love each other and act like boyfriend girlfirend without the actual physical affection and only the virtual. It's just fake. I'm not a fake person, most of the time, and I don't especially enjoy fake. I do put on my smile for a good amount of the day, and I tend to shrug off my insecurities and sweep all my problems under an apathetic bed. I don't want a fake relationship, and I don't want a fake love, because after pretending for so long, it starts to feel like it might actually be something. I'm tired of that illusion. ... cough. I expected to see lots of friends and catch up on old times. That kind of happened, with one of my friends. The weird thing is, it was a friend who I am close with, but she was the only one who actually gave a damn to ask about me. Most of my conversations go something like this:
Hi, hi, how are you, and then they go on for a while, when they stop, they don't ask about me, so I further the conversation by asking them how their lives are going. And then the topic is them, them, them. I wish that for once or twice, maybe I could be the topic.

I think I'm mainly annoyed at the level of drama that occured while I was home. As noted by my previous rather depressing blogpost, my friend screwed up his relationship with his girl, and happened to do it with the girl who I was falling for. It's the reason I took a walk yesterday. Loaded the playlist I talked about onto my mp3 player and went for a walk in the crappy overcast weather. It was good, I got a good amount of thinking done. I was trying to figure out if I actually really like the girl enough to go for it, or if I'm more attracted to her as a friend. I didn't really figure too much out. But, I do think I'm attracted to her based on our common fuck ups. A'la she has baggage. Much in the same way I do. She still thinks about her big ex, and mentions him a lot. He was a big part of her life, so its no wonder a lot of things still remind her of him. And I think I like that about her, because I feel the same way about my ex from a long time ago. Everything still reminds me of her. Maybe that's why coming back home is kind of painful sometimes.

I expected more from my vacation, maybe some sunshine. I know I can't control the weather, but I've seen the sun once this entire week. It's frustrating when you want to go out and do fun things with friends, but they dont want to because the weather is shitty. It's rather annoyying and difficult.

I guess, when it comes down to it, I am looking forward to go back to VT, when I've talked to people over SMS, I've had to erase a part of a text that said: I only have x days before I go back home, multiple times, I guess I consider VT more home than this place to some extent. Maybe it's just nice to have a freshstart and not have all the people who already know you and stuff. Start new, find someone new, who hopefully wont fuck up my mind like my ex did.

Turret Estimation

Workin on my program some more:

So I've come up with a bit more code, and a few more interesting problems. I think I've figured out how to use my vectors correctly. I can use velocity vectors and position vectors to estimate the locations of objects. It's great.

The problem I've come up with is how to figure out where to rotate my turret to in order to fire. Because I have a few variables I need to keep track of, and keep in mind.

1. The projectiles statistics: the bullet or shell to be fired by the turret has a velocity vector and position vector. Once I move into a 3d space I may include a mass in here. But besides that, velocity is a straight float, why? Because I don't know which x y components to give the vector because I don't know the theta. so, a straight number like 2.5 m/s or something, allows me to estimate where to shoot the bullet. This will make sense once I describe my idea for this.
2. The target objects estimated path using the pings. This gives me a velocity vector and a position vector for the target.
3. The current heading, or theta of the turret.

So, my method, is briefly describe in the picture below.

I ran atrial of it last night, and it appeared to be working, but I do need to iron out some kinks in the simulation

Radar Tracking Turret!

I came up with a new idea to code! It will probably take up a good chunk of my nights during spring break

I simple turret that tracks and fires at objects in its pinging field, in 2d space. Once I get that working, I'll think about working in 3d space.

Here are a couple of my sketches for ideas:

ok, so the first image is how the ping system will work. The second is how the pings data will be used to determine the vector of the object being targeted. and the last is how the turret will estimate where to fire.

So this is how I plan to do it. No code yet!
Have the turret object which will hold its own cordinates in its plane, its angle of firing and a pointer to its projectile loaded.
The projectile object will have a velocity and x,y cordinates. (once I move to 3d space it will have mass and other things)
The target will have an x,y and a velocity and theta for movement.
Then there is the collections object that will store all these things. this will be used by the pings sent out by the turret to let the turret know the location of the target object.

A few of the details still need to be worked out. But I've got enough that I can start a basic console prototype