The most important mathematical idea for understanding projectiles is being able to imagine the movement in just one direction, to ignore all the other motion.

In particular imagining just how the height changes is important, but it's also the most difficult. It's also quite hard to deal with the idea of projectiles that can go north-south and east-west.

So lets just fix our boss facing north, and think about the horizontal movement of the projectile first. It turns out that the northwards movement of the projectile is exactly the same for MOVETYPE_MISSILE and MOVETYPE_BOUNCE. We fire it with some speed to the north, and it keeps going at a constant speed. Most importantly it takes the same amount of time to come in line with the player.

Now we can think about how the height changes. The MOVETYPE_BOUNCE has exactly the same behaviour as a falling player. Measure the amount of time the MOVETYPE_MISSILE takes to hit the player. If a player could fall from the height the projectile is thrown at down to the height of the target player in that time then the MOVETYPE_BOUNCE will score a hit, otherwise the shot will sail over his head.

So what can we do if it does sail over his head? Well, one trick is to start the projectile with a negative velocity_z, so it is already moving downwards. This will make it fall further during the flight and hopefully hit the player. Alternatively we can reduce the speed it travels north at. This will give a longer flight time and so longer for it to fall. We could combine these two ideas if needed.

Calculating exactly how much adjustment is needed is where you have an unavoidable level of fairly grizzly maths. I'm sure I wrote something about this particular problems but I can't remember if I finished it and ever posted it. You can probably get a good enough function by just measuring the threshold at which projectiles start going overhead, and applying one of the two above fixes when the player is that close(using trial and improvment to get values that work well). 

So, with a zero velocity_z, does the projectile fall from the horizontal at a predetermined and constant rate i.e. no acceleration? And if so, do we (you) know what that rate is?

I'm just thinking that a series of If Thens could adjust the velocity_z and velocity to get to the target in the given time. (Not sure what the player would think of that?) 

z is a parabolic function, depending of initial velocity, the initial direction/angle and the weight of the projectile, so to say gravity...
x and y can be linear it eases calculation, unless you want to add some wind effects, etc..

Wikipedia gives some mathematics clue for this: http://en.wikipedia.org/wiki/Trajectory

Experiment ! 

JPL is right that it's not a constant rate, it's an acceleration, and the easiest way to understand it is to experience it in-game. Because gravity affects players in the same way as bouncing missile, you can see exactly how it changes just by falling. In particular if you go on ziggurat vertigo then you can see the change in speed happen in slow motion, which makes it easier to gauge. The next paragraph is optional mathematical detail:

Standard quake gravity is 800 units per second per second. What that means is that after 1 second of falling (from rest) a projectile will be travelling down at a velocity of 800. After 2 seconds that speed has reached 1600 and so on until it reaches the maximum speed the engine allows (which defaults to 2000 units per second I believe). The speed increases smoothly, after 0.5 seconds the projectile has velocity 400 and so on, but this constantly increasing speed means that position changes irregularly.

Despite that, we can use approximations here. The trick is to restrict ourselves to a controlled case. Work out the distance at which the shots are missing the player, and only apply this approximation within that range.

Since we know that the shots we are correcting are close range, we can assume the flight time will be 1 second or less. We can then approximate the falling motion of the projectile as a constant speed of 400 units per second*. Based on that we can do some fairly simple calculations based on the relative height of the player and the projectile's start location. If these differ by more than 400 units then add the difference to the velocity.

The important thing is to get that typical flight time right for the shots we want to correct, detect when we're in that case and then issue appropriate corrections. If my guess at the timescale is wrong please let me know and I'll recrunch the numbers.


*This certainly looks like I just averaged the starting speed of 0 with the final speed (at 1 second) of 800. I will be belligerent and claim I actually performed an integral of the accelerated motion to discover the exact distance a projectile covers in 1 seconds, the answer being 400. 

Well, the first thing I did was to manipulate velocity_z, with so-so results. However, by just thinking a little less, and velocitising a bit more, I found a figure for velocity that covers the distance perfectly, whilst still providing an obvious 'lob' effect. The only downside is that if you get too close, you do not really have time to get out of the way.

Still, given that the player starts off x distance from the Lavaman, which IS a dodgeable distance, and given that he does not HAVE to get closer if he does not want to, I may just reduce velocity a bit according to the distance to target, and settle with what I have.

It's not that I don't want to do the maths, it's just that this is just one monster in one scenario for my final Quake map.

Thanks Preach and JPL for the guidance. 

wow thanks to everyone for pointing me towards those other data structures.
looking around, it seems like LinkedHashSet is the way to go as it is supposed to be only slightly slower than a HashSet (but not as slow as a TreeSet) and preserves the order based on when they were added.

I don't think the Map interface is what i need, since i'm storing more than just a relation between a key.
FGD has many extra bits for key/vals including data type (Target/TargetName/Integer/String/Choice) along with (if a choice) the individual choices as well as a default value (if any), so all that has to be in there, but i'm only interested in the key's name when building the list (as that's how i want to determine if it's a duplicate or not)

anyway, i'll throw some more code at the problem and see what happens! 

One of the interesting things about projectiles is that for a fixed launch speed there are two angles you can fire them to land at a given range*.
http://en.wikipedia.org/wiki/File:Ideal_projectile_motion_for_different_angles.svg
The above illustrates how that works, but the reason I raise it is because the high lobbed shot, which I think of as the less obvious of the two paths, has a longer flight time. The difference is greatest on the shortest ranges.

This would be a great solution to giving the player enough reaction time. It also would be good at lobbing over any cover between the player and monster, which might make the combat more interesting.

There is however a price to pay, and that price is the need for greater computation. Essentially when you fire on a low trajectory you can land a lot of hits even without getting the range very accurate, because the horizontal line of the attack will usually intersect with the player somewhere. When you go for the tall lob shot your attacking line is much more vertical, and so you need to get the horizontal spot on.

How that would go would be:
� Calculate the vertical range to target h.
� Compute the time to drop to height h:
http://chart.googleapis.com/chart?cht=tx&chl=t=\frac{600%2B\sqrt{600^2%2B2\times800h}}{800}
(here 800 is gravity and 600 is our intended upwards velocity)
� Calculate the horizontal range to our target x
� Divide x by t to get the horizontal velocity v

We now need to make a vector with length v moving towards our target in the horizontal plane:
d = self.origin - self.enemy.origin;
d_z = 0;
d = normalize(d)*v;
Finally we set d_z = 600 and off we go!


*except for maximum range where the two solutions converge on 45� 

I seriously doubt that you need to worry about performance in your app. Or am I wrong? Also, if you have more data, you can store an object that represents that data in the hashmap with the name as the key. That's the usual approach anyway. 

re 707: in doom3, you can see that happen sometimes with hellknights. they usually use the more horizontal trajectory when throwing their fire balls, but occasionally, they'll toss one way up into the air.

re 708: yeah, you're probably right about performance. anyway, managed to get it working in a quick hacked up way. i store keyval lists as arraylists on the entity definitions, but when i call the get method for a keyval index, i build the linkedhashset each time out of all those arrays.
works well for now even though it feels like this is wrong... like i should be storing all the keyval lists as linkedhashsets and using .addall. 

I guess the main problem is not to obtain the parabolic curve, that can be even coded very simply like an exponential code (i.e x = x/2 or x = 2x). no I guess the challenge is rather to be able to obtain the projectile to perform direct hit to the player (if not moving). in order to achieve this, a reverse calculation is required: you know player position, monster position, projectile weight, hence it is possible to determine velocity and angle to apply... that could be very interesting as more realistic ;) 

did this a while ago.. it was supposed to be for a leaping monsters and would trace the parabolic course in increments via a while look and tracelines so check if the leap parabola was clear...

traceFraction = 0;
while(traceProjection <= 1)
{
traceProjection = traceFraction + 0.25; //project the trace. will make for 4 traces.

local vector trace_pos0, trace_pos1;

trace_pos0 = self.origin + ( (dir * (hdist * traceFraction)) + ( '0 0 1' * ( ((vtime * 400)*(vtime * traceFraction)) + (0.5 * (vtime * traceFraction) * (vtime * traceFraction) * -800) )));
trace_pos1 = self.origin + ( (dir * (hdist * traceProjection)) + ( '0 0 1' * ( ((vtime * 400)*(vtime * traceProjection)) + (0.5 * (vtime * traceProjection) * (vtime * traceProjection) * -800) )));

traceline(trace_pos0, trace_pos1, 0, self);
bprint (vtos(trace_endpos));
bprint (" -> ");

if (trace_fraction < 1)
traceProjection = 1000000; //cause a break

traceFraction = traceProjection;
}

dunno if that code is 100% correct... or even helpful. :P 

I guess what is interesting is not that much the result, but the logical reasoning you made to obtain it ;) 

oh sorry yeah, should have explained it a bit. :P

you'll notice there's two vars, traceFraction and traceProjection.

these should be only values of 0 to 1.

next is trace_pos0 and trace_pos1.
we determine these points by using that physics formula that describes position relative to time with an initial velocity and taking into account gravity. (i subbed 400 in to any 'g' variables, which, sorry to say preach, i figured out totally by guessing... ^_^;)

this is where traceFraction and traceProjection come in. if you look at the first line of the loop, traceProjection is always 25% ahead of traceFraction.
trace_pos0, then, is the origin of the traceline and trace_pos1 is 25% ahead through the trajectory.
incidentally, you could increase the 'resolution' of the trace by decreasing 0.25 to 0.1 or something to get 10 iterations instead of 4.

if you can imagine a typical parabolic trajectory, what you're doing in that code is tracing a line, first, from the starting point to 25% into that trajectory.
then, from there, tracing another 25% forward to the middle of the trajectory, etc etc.
if at any point the traceline fails (trace_fraction < 1, ie: something blocked the trace)
then we break out of the loop and notify the rest of the code what happened.

basically, i turned quake into a really crappy 3d graphing calculator. :P 

oops, there was additional information i forgot about (i wrote this years ago so i forgot how it works! :D)

this is the start of the code (before that loop):

epos = self.enemy.origin;
//epos = self.enemy.origin + dir;

zsep = epos_z - self.origin_z;
dist = vlen(epos - self.origin);
dir = epos - self.origin;
dir_z = 0;
dir = normalize(dir);

if (zsep > 64) //player is too high, forget it.
return;

temp1 = epos;
temp1_z = 0;
temp2 = self.origin;
temp2_z = 0;
hdist = vlen(temp2 - temp1);

if (hdist > 768) //player is too far, stop
return;


if (hdist < 440)
{
hspeed = hdist; //do a 1 second jump.
vtime = 1;
}
else
{
hspeed = 440; //max out at 440 horizontal speed and jump higher to compensate.
vtime = hdist / hspeed;
}

i guess the important things is noting that dir is a flattened normalized vector towards the target and that vtime is the amount of time we want to spend in the air. 

Oh, I see, you made it like a move forward, rotate, move forward, rotate, etc... like polar coordinates or (better) vectorized move: interesting, I was not thinking it was possible doing it this way actually ;)

And thanks for the explanations :) 

The sooner I can get my assignment finished, the sooner I can get back to mapping :)

This bloody search_array thing is kicking my ass. Trying to use php to search an array of info. Its a multi-dimensional array. I swear I have looked all over for a solution and have had no luck.

http://www.php-forum.com/phpforum/viewtopic.php?f=2&t=17353 

But the search_array func probably isn't built for multi dimensional arrays. Seems to be versions of that in the comments of the search array in the php docs:

http://php.net/manual/en/function.array-search.php 

I dunno, it seems I'm just not getting something.
I think it's to do with the way I have my array. Which is awkward because It's just the way it comes from the XML file. Blerg. 

Xml...*shudders* 

Any sensible person would design a DB in MySQL, but we are not allowed to use MySQL (go figure?!) - which sucks because any real-world application would use MySQL or SQL or even .net + access or whatever, but 'noooooo', not my retarded course. php + XML is the recipe of the day. Fuck it, I guess I'll learn something at the end of the day ... 

ditch array_search and iterate through the arrays manually. It's pretty simple. 

I can handle a stupified approach, I just wanna get a fucking A. I don't care if I have to re-design my data structure completely, I have been thinking about this for far to long now and my brain hurts... 

Hey, XML can be fun and it is quite simple if you use a good parser. seriously! 

I enjoy the transition from, "Stupid class, can't use a database, have to use XML, *grumble*" to "can you show me an example of a loop?"

Walk before you run, Ricky. :) 

If you don't know what a loop looks like, how can you expect to get an A in a programming class?

Here is an explanation of the most important loop constructs in PHP:
http://nefariousdesigns.co.uk/loopy.html