   Linear algebra and grenade trajectory testing
  I'm working on a piece of software with some semi-autonomous military units. I need to implement some sort of system to check if it would be possible for such units to throw grenades from a given point A to a given point B. From what I know in physics, grenades have a parabolic trajectory, so my solution is to see if I can fit a parabola between two points in my world which does not collide with any terrain or entities.The solution I'm trying to devise right now is to take the two points and plug them into a matrix in parabolic normal form.ie: (examples are in 2d for simplicity because I haven't devised a good way of doing it in 3d yet)Source = (0, 0)Target = (2, 0)For thse points ax^2+bx+c = y yields the matrix:[0 0 1 04 2 1 0]I've written something to reduce this to row echelon form through matrix operations, and I now have a matrix representing a system of possible parabolas (because you need 3 points to get just one parabola). So I'll produce a reduced matrix that's like this:[1 .5 0 0 0  0 1 0]Which which means that a=-.5b, and c=0I'm not really sure of the best way to go from here... I basically need to devise a way to generate different parabolas so that I can test them against the existing stuff. (i'm going to break them up into lines parametrically and test each line for interesections)Note: I know this may seem grossly inefficient, but the units are not searching for smart ways to use grenades. They receive a command to throw the grenade at a certain point and they just need to make sure that it is possible to do. Mapping the actual course of the grenade for physical collisions is outside the scope of the problem. I hope this was clear; if something needs further explanation please let me know. Thanks guys.[Edited by - kbirger on May 15, 2009 8:33:16 AM]
  One thing to keep in mind is that there are an infinite number of parabolas that pass between 2 points. For example if want to hit a target and you throw a baseball, the angle you aim at will depend on how fast you throw it.Even if you launch it at a single speed, there are still 2 different solutions, one corresponding to a high "fly ball" and the other corresponding to a low "line drive"A common way to resolve the issue (because it is easy not necessairily because it is realistic) is to assume it is always thrown at a constant initial speed, and always choose the lower of the 2 possible paths. Then you can solve the 3d parabola equations on paper, and then have the program plugin in the values for x0,y0,z0,xf,yf,zf,v0 into your solved equations.   ;  Like Maze Master said, you have an infinite number of solutions. You can see this from your matrix, since the rank of your rref matrix is only 2 and you have 3 variables. So you'll need 1 parameter (which you've made b in this case).Pick any real value for b, and it'll solve your equations. So if you want to brute-force this, you can just pick a starting value for b, increment it, test to see if it intersects, increment b again, and so on until you find a value for b that does not intersect.   ;  It doesn't make sense to test every parabolas, because units usually can't throw a granade at any speed and distance. You should probably set some constraints (maximal velocity or angle for example). To find a possible trajectory you can test some parabolas at random. If after some tests you haven't found a possible trajectory you can assume it's impossible (or at least quite hard to launch a granade to that position).   ;  Ok, so I was thinking about this problem, and I think I figured out a way to solve it for a range of velocities. By no means do I recommend you do this (implementing the coding would be a challenge), I just think its pretty cool and want to share.For simplicity lets restrict to 2D projectile motion. If you take the velocity and add it on as third dimension, then the possible trajectories of the grenade form two surfaces in 3D space:Figuring out for what grenade velocities an object is blocking the path is equivalent to finding out where the trajectory surface intersects the object, (extruded along the 3rd direction):You can pick a set of angles, a set of grenade travel times, and construct a series of points on the trajectory surface. Then triangulate that to approximate the trajectory surface, and do collision detection to find out where it intersects the extruded object.This is the example of solving it in 2D by adding another dimension and extending it to 3D. For 3D, you will have to add another dimension and do collision detection in 4D.   ;  Thanks for your replies guys. I've been away all weekend but I finally got a chance to read them. For my purposes, an consistent initial velocity is acceptable, and I know there are infinite parabolas in the system, sorry for not making that clear initially. My intent was to pick them at a certain interval until the free variables throw the parabola "out of range" (ie past a straight line, or pushing the vertex past the right "leg") That's an interesting way to approach the problem Maze Master, but yeah, would surely be quite something to implement :).My issue is really that I don't have a good idea on how to represent / solve the matrix I get into a form that would allow me to build out different parabolas. I know it's kind of a brute-force method, but due to the structure of the software, I'd pretty much have to test a series of possible paths regardless of what I do. Also, I can set the different between parabolas that it tries relatively high, because it would be acceptable for a window that is 6x6 inches to not provide a valid path for a grenade toss because of the high risk of missing and blowing yourself up. Maze, is it actually necessary to approach the problem in 3d? It seems like any grenade toss is really a projection onto a 2d plane because the AI doesn't try to (nor does the engine currently support) grenades bouncing off walls. I was thinking of solving it in 2d for efficiency and then adjusting the points.   ;  The trajectory of a grenade is really a 2D one (if you don't consider bouncing, wind...). The plane is defined by the starting force you apply to the grenade and gravity. So your 2D model can be easily generalized to 3D simply replacing the first base of the plane with (P1 - P0). Note that you have to represent your parabola in parametric form. The implicit equation you have written only works in 2D.I think your matrix approach isn't ideal. If you only have one initial velocity (with varying starting direction) you only have one possible trajectory (or maybe zero) from a starting position to the destination. The gravity is in fact constant and you have the following equation for the trajectory:x = x_0 + v_x ty = y_0 + v_y t - .5 g t^2So if you constraint something about this velocity (for example the length or direction) you can solve it and get the trajectory.   ;  That's a good point. Thinking about it more, I don't know if the initial velocity can be constant then, since by the objective (which is to determine if a human AI can hit a given point B while standing from point A (A will be the point of release for the grenade).I guess I wasn't really thinking earlier when I said that about Vi, because if the target is closer he wouldn't have to throw it as far. The constraints on throwing are outside my control and are actually just a maximum throwing distance as well as a minimum safe distance, which I was going to use to cull out invalid trajectories too.   