this is java, but it's more of a conceptual thing...

finally started working on the inheritance aspect of fgd files for my fgd<>def converter thingy...

essentially, i have multiple lists of objects which represent key/val pairs. these lists can have duplicate entries from base classes that an entity inherits from.

eg: you have 'monster_army' which inherits target/targetname fields from the base 'monster' class.

what i'd need to do is, on demand, collapse the multiple lists into a single one.
ie: when i 'get' a list element, i should iterate through a single apparent list:

monster_army has the fields: (inherits from 'monster')
0: B
1: C
2: D

monster has the fields:
0: E
1: C
2: A

should look like:
0: B
1: C
2: D
3: E
4: A

(duplicate C in 'monster' is ignored because 'monster_army' already had that field)

i can work through the logic of building a new list myself, but the problem is that there are many times where i need to iterate through the (final) list, so every time i .get(i), i'll have to rebuild this list which feels wrong.

is there maybe some more complex data structure that would work better for this? i'm thinking maybe trees due to their non-linear nature?
unfortunately, i've never really learnt data structures more complex than a simple linked list. :S

or maybe there's some absurdly easy solution and i'm just not seeing it. 

you should be able to get away without building the final list. I'd store the key/value pairs in a hash table instead of a list of key/value pair objects, and have an object for each "quakec class". then set up a recursive get() function which first checks the object-being-called's key/value pair mapping (e.g. Grunt), and if the requested key wasn't found, call the get() method on the superclass (e.g. Monster) (or return null if there is no superclass - so for a key requested that isn't in either Grunt or Monster).

something like this:

class EntityClass {
EntityClass superclass;
HashMap<String, Object> fields;

Object get(String key){
if (fields.containsKey(key)) {
// the requested key is stored directly in our class
return fields.get(key);
} else {
// the requested key is not in our class, try searching
// our superclass.
if (superclass != null) {
return superclass.get(key);
} else {
return null;
}
}
}

}

hope that helps..

btw here's the javadoc for HashMap.
http://docs.oracle.com/javase/1.5.0/docs/api/java/util/HashMap.html 

If you're only storing the keys and no value with them, I'd recommend using a Set instead of a Map. You should read up on the Java collections framework, as in most cases it already solves a problem for you. 

I have a Lavaman in my map (FMB_BDG) and he does a good job except I notice that there is a point where I can stand and the missiles go over my head. If I move closer, they hit me and if I move further away they hit me up to a point where they drop in front of me.

I can see that MOVETYPE_BOUNCE seems to affect the 'lobiness', and velocity_z seems to affect the height of the lob. What is affecting the gap between the hit range and the no-hit range? I am not too worried about the far distance as the missile falling short is not an issue because I can contain the player, but the over-me-'ead-john lob is not good.

If I change to MOVETYPE_MISSILE and ignore velocity_z I get a straight line missile a la roquette, but this is not good where the player is higher or lower than the Lavaman as dodging becomes too easy.

Are there any good web-sites that explain weapon behaviour (in short sentences with no long words, and mathematics that any four year old can understand)? 

This is also how I would do it. Note though that the keys will be unordered. If you need them to be sorted in some way, consider a SortedHashMap, e.g. TreeMap. 

I think everyone is right on Necros' problem that using sets/maps is the way to go, but I think that the implimentations so far have been backwards: So far we've had how to check if a specific element is a member of one or more sets, but what necros is looking for is the ability to list all the unique elements in a collection of sets, omitting duplicates.

The key to doing this is set union. Have a set of properties for the monster, a set of properties for the grunt. When it comes time to output the combined list, use the addAll method to create combined lists which omit duplicates. 

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*