16
Bugs in older version (2.3.1) / Re: crash in tactical mission, latest revision
« on: July 18, 2010, 05:10:57 pm »
31041 should've fixed that for 2.3. 31039 fixed just trunk.
News:
New board
Show Posts
This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.
17
Bugs prior to release 2.3 / Re: R31032 , firemode failed - game crash in battlescape
« on: July 18, 2010, 04:45:18 pm »
for 2.3, the fix patch was introduced as of 31041.
Sry for not mentioning that.
Sry for not mentioning that.
18
Coding / Re: the AI discussion
« on: July 17, 2010, 09:19:16 pm »
shaunc311: well, keep playing with it 
I was kinda afk the past 2 weeks, so I just came back to my old mess:
the CL_GetHitChance is most of the math I wanted to code, so I opted in copy/pasta'ing it while fixing the very annoying partial-occlusion bug it has (see last post).
Instead of multiplying the no-cover hitchance with the percentage of the 8 tracings that were succesfull, we're going to assign weights each 'hitbubble' that the tracing checks for. So missing the center bubble of the target is way more important than missing one on the edge.
My brother is out there fixing this atm, but we have one very important question we need answered before we can even start:
What point of the 'model' is the edict_t->origin?
Is it the center of the object, or some corner of it?
We kinda need that so we can extrapolate the center of the shooting surface and start creating the boxes.
I was kinda afk the past 2 weeks, so I just came back to my old mess:
the CL_GetHitChance is most of the math I wanted to code, so I opted in copy/pasta'ing it while fixing the very annoying partial-occlusion bug it has (see last post).
Instead of multiplying the no-cover hitchance with the percentage of the 8 tracings that were succesfull, we're going to assign weights each 'hitbubble' that the tracing checks for. So missing the center bubble of the target is way more important than missing one on the edge.
My brother is out there fixing this atm, but we have one very important question we need answered before we can even start:
What point of the 'model' is the edict_t->origin?
Is it the center of the object, or some corner of it?
We kinda need that so we can extrapolate the center of the shooting surface and start creating the boxes.
19
Bugs prior to release 2.3 / Re: R31032 , firemode failed - game crash in battlescape
« on: July 17, 2010, 07:05:53 pm »
check latest trunk and see if it's ok now. PM me directly if it's not.
20
Bugs in older version (2.3.1) / Re: crash in tactical mission, latest revision
« on: July 17, 2010, 06:48:29 pm »
my bad (again), on it
check latest trunk and see if it's ok now. PM me directly if it's not.
check latest trunk and see if it's ok now. PM me directly if it's not.
21
Bugs prior to release 2.3 / Re: 2.3 rev 31015 Win32bit Unable to play in Battlescape
« on: July 17, 2010, 06:42:32 pm »
Assert error:
my bad, will look into it shortly. I shifted some code around and this is what you got for it :/
check latest trunk and see if it's ok now. PM me directly if it's not.
my bad, will look into it shortly. I shifted some code around and this is what you got for it :/
check latest trunk and see if it's ok now. PM me directly if it's not.
22
Coding / Re: the AI discussion
« on: July 11, 2010, 08:58:13 pm »
So, here's the current plan with the hit % calculations, WITHOUT support for target occlusion from random things in the line of fire (more on it later):
Given the optimal shot point (the point which G_ShootSingle considers as the target point for a target entity), we really want to calculate the hit probability for every point in space the entity occupies.
We drop the calculation the 3rd dimension (which does lead to less accuracy but much greater performance) and essentially we calculate the hit % for each point in a slice of the target (perpendicular to the shot). In simpler terms, try shooting someone with only one of your eyes open.
So, in essence we have something like this:
----**----
---***---
---***---
--*---*---
legend:
*: points of the 'slice' we care about shooting
Because calculating for each point is a very expensive procedure, we scan line by line for each axis:
Calculate the chance a bullet will land in the first line's RANGE interesting points, and so on.
Then calculate the chances a bullet will land in the first row's interesting points, and so on.
Bear in mind that we calculate for a range, which in this example is for 2 points in the top line, and 3 for the 2nd. Now, we have to translate the range hit % to point hit chances. There proper way of doing that is employing the CDF cumulative distribution functions of a normal distribution. Now, this looks very expensive. Instead we use lookup tables, that are commonly used today to solve such problems by hand (yay, for saved cpu cycles). This is another loss of precision.
So what we really plan on doing is calculate the hit % on the series of the points we're considering and then assign individual hit % according to a weight defined in the lookup table. So, for example, the series of 3 points in the 2nd row end up having a chance of 12%, we give 12/3*lookup_weight on each on.
The reason for having to do this once in the x axis and once in the y is that we have 2 gauss vars in the shooting calculations. Once for each variables. The final hit % of each point is the multiplication of the values it was assigned on each scan.
Up to here we have 0 tracing calculations and quite the lightweight math (avoiding the erf function is a big plus), but we also have 0 idea if there is an actual Line Of Fire. We basically calculate with (an expectedly) very nice precision what would happen if there were no obstacles in the course.
We're pretty confident that up to here we're on a good road, and even though the equations we used were for non-gravity (bullet-based) weapons, the parabola of the grenade/launcher shouldn't be that difficult to implement.
Interesting observation: Ever noticed that many games can only predict up to 95-7% max shot chances? I believe this is a direct result from the gaussian randoms and the respective calculations (like the ones we use here).
The problem is now occlusion. Given our previous raster-like approach, we need to find out which 'points' are occluded by objects in the line of fire.
Tracing shots for each and every one of the points and then calculating intersections with objects is right out of the question, since that'd probably be more expensive that the sampling that swamps the AI atm.
In theory, we could try create a cone (or pyramid if that's expensive) originating from the gunpoint and having as it's base the 'slice' we're shooting at. Then, find all objects contained/intersecting this cone and project their shape on the slice. All points that are overshadowed get their hit % set to 0.
Unfortunately, not even my brother could think of an easy way to run the math, nor me think of any function I've seen in the code that could handle that kind of intersection calculations.
The simplest thing we've thought of is to trace the shot on the center of the 'slice' (the perfect shot) and depending onto whether that gets through:
a) Consider the shot impossible (even if the occlusion is light and any accuracy deviations would land us hits)
b) Project only that object to the slice and use it's shadow.
I believe (b) is what the gamer sees in the UI (hit % along with the red part of the line if the perfect shot is not possible), and what we'll probably end up with.
EDIT: the cl_battlescape.c/CL_GetHitProbability, but we couldn't grasp... Oh crap, I think that function does exactly what I've been talking about here. Will try to use that instead of reinventing the wheel.
RE-EDIT concerning CL_GetHitProbability:
Ok, so the difference (the ones I can grasp at least) in that function is that it considers the target (the actor for our considerations atm) to be box-shaped.
Is that true in game-terms, or do we actually have the actors have more complicated/non-convex hulls?
From the looks of it, the chance to hit that box is calculated just fine, it's the method of calculating occlusion from objects in the LOF (to the box-target) that drops the accuracy. If you take a look at the function you'll see that it takes 8 prefixed (in width/height percentages) points to the target and traces a line at them. After doing that, it multiplies the hit percentage with the percentage of traces that actually went through.
I don't think it even considers shooting the center of the target (need to double-check), which probably leads to the 1 or 2 occasions that bursts for 95+% chances all miss because they land on a protrusion. Apart from that, all traces are considered with equal weight (in terms of their ability to reduce hit %), which is true for uniform distribution but not for our gaussian: occlusions at the edge of the window have minimal hit % impact compared to something close to the 'perfect shot'.
Unless I copy/pasted something wrong in the AI code (which I probably did), I noticed serious deviations from the sampling code and the predictive code where there is partial occlusion in place (I think that happens a lot when there's that africa-map fence).
Obvious possible semi-solution is to reposition & weight those sampling points.
Since I did look a bit into bsp trees looking for a 'perfect' solution, I was told that it's probably possible to employ the bsp tree while trying to find occluding objects (as in possibly do it fast enough):
Our problem: if the gunpoint is a lightsource pointing at the target-box, find me the parts of the box that are shadowed from random objects in the map.
Now, the basic idea is to traverse the bsp tree and keep checking for objects intersecting the pyramid defined by the gunpoint and the target box. I'll bribe the graphics-geeks with coffee tomorrow and see what they really meant. If this works, it's all up to profiling to show us if the performance hit is worth it (at least we could use it in the UI if it's too heavy for the AI).
A notice on performance: we're already traversing the bsp tree for each sample-trace, so this might end up being faster (don't know how heavy the object intersection math is compared to the line intersections).
Question: what is the edict_t->origin point? Is it the center of the object, or some other predetermined point?
I know I need to at least release the code I'm currently working at, but it has so many leftovers from previous experiments, I'm ashamed to show XD. Will have to cleanup and post.
Given the optimal shot point (the point which G_ShootSingle considers as the target point for a target entity), we really want to calculate the hit probability for every point in space the entity occupies.
We drop the calculation the 3rd dimension (which does lead to less accuracy but much greater performance) and essentially we calculate the hit % for each point in a slice of the target (perpendicular to the shot). In simpler terms, try shooting someone with only one of your eyes open.
So, in essence we have something like this:
----**----
---***---
---***---
--*---*---
legend:
*: points of the 'slice' we care about shooting
Because calculating for each point is a very expensive procedure, we scan line by line for each axis:
Calculate the chance a bullet will land in the first line's RANGE interesting points, and so on.
Then calculate the chances a bullet will land in the first row's interesting points, and so on.
Bear in mind that we calculate for a range, which in this example is for 2 points in the top line, and 3 for the 2nd. Now, we have to translate the range hit % to point hit chances. There proper way of doing that is employing the CDF cumulative distribution functions of a normal distribution. Now, this looks very expensive. Instead we use lookup tables, that are commonly used today to solve such problems by hand (yay, for saved cpu cycles). This is another loss of precision.
So what we really plan on doing is calculate the hit % on the series of the points we're considering and then assign individual hit % according to a weight defined in the lookup table. So, for example, the series of 3 points in the 2nd row end up having a chance of 12%, we give 12/3*lookup_weight on each on.
The reason for having to do this once in the x axis and once in the y is that we have 2 gauss vars in the shooting calculations. Once for each variables. The final hit % of each point is the multiplication of the values it was assigned on each scan.
Up to here we have 0 tracing calculations and quite the lightweight math (avoiding the erf function is a big plus), but we also have 0 idea if there is an actual Line Of Fire. We basically calculate with (an expectedly) very nice precision what would happen if there were no obstacles in the course.
We're pretty confident that up to here we're on a good road, and even though the equations we used were for non-gravity (bullet-based) weapons, the parabola of the grenade/launcher shouldn't be that difficult to implement.
Interesting observation: Ever noticed that many games can only predict up to 95-7% max shot chances? I believe this is a direct result from the gaussian randoms and the respective calculations (like the ones we use here).
The problem is now occlusion. Given our previous raster-like approach, we need to find out which 'points' are occluded by objects in the line of fire.
Tracing shots for each and every one of the points and then calculating intersections with objects is right out of the question, since that'd probably be more expensive that the sampling that swamps the AI atm.
In theory, we could try create a cone (or pyramid if that's expensive) originating from the gunpoint and having as it's base the 'slice' we're shooting at. Then, find all objects contained/intersecting this cone and project their shape on the slice. All points that are overshadowed get their hit % set to 0.
Unfortunately, not even my brother could think of an easy way to run the math, nor me think of any function I've seen in the code that could handle that kind of intersection calculations.
The simplest thing we've thought of is to trace the shot on the center of the 'slice' (the perfect shot) and depending onto whether that gets through:
a) Consider the shot impossible (even if the occlusion is light and any accuracy deviations would land us hits)
b) Project only that object to the slice and use it's shadow.
I believe (b) is what the gamer sees in the UI (hit % along with the red part of the line if the perfect shot is not possible), and what we'll probably end up with.
EDIT: the cl_battlescape.c/CL_GetHitProbability, but we couldn't grasp... Oh crap, I think that function does exactly what I've been talking about here. Will try to use that instead of reinventing the wheel.
RE-EDIT concerning CL_GetHitProbability:
Ok, so the difference (the ones I can grasp at least) in that function is that it considers the target (the actor for our considerations atm) to be box-shaped.
Is that true in game-terms, or do we actually have the actors have more complicated/non-convex hulls?
From the looks of it, the chance to hit that box is calculated just fine, it's the method of calculating occlusion from objects in the LOF (to the box-target) that drops the accuracy. If you take a look at the function you'll see that it takes 8 prefixed (in width/height percentages) points to the target and traces a line at them. After doing that, it multiplies the hit percentage with the percentage of traces that actually went through.
I don't think it even considers shooting the center of the target (need to double-check), which probably leads to the 1 or 2 occasions that bursts for 95+% chances all miss because they land on a protrusion. Apart from that, all traces are considered with equal weight (in terms of their ability to reduce hit %), which is true for uniform distribution but not for our gaussian: occlusions at the edge of the window have minimal hit % impact compared to something close to the 'perfect shot'.
Unless I copy/pasted something wrong in the AI code (which I probably did), I noticed serious deviations from the sampling code and the predictive code where there is partial occlusion in place (I think that happens a lot when there's that africa-map fence).
Obvious possible semi-solution is to reposition & weight those sampling points.
Since I did look a bit into bsp trees looking for a 'perfect' solution, I was told that it's probably possible to employ the bsp tree while trying to find occluding objects (as in possibly do it fast enough):
Our problem: if the gunpoint is a lightsource pointing at the target-box, find me the parts of the box that are shadowed from random objects in the map.
Now, the basic idea is to traverse the bsp tree and keep checking for objects intersecting the pyramid defined by the gunpoint and the target box. I'll bribe the graphics-geeks with coffee tomorrow and see what they really meant. If this works, it's all up to profiling to show us if the performance hit is worth it (at least we could use it in the UI if it's too heavy for the AI).
A notice on performance: we're already traversing the bsp tree for each sample-trace, so this might end up being faster (don't know how heavy the object intersection math is compared to the line intersections).
Question: what is the edict_t->origin point? Is it the center of the object, or some other predetermined point?
I know I need to at least release the code I'm currently working at, but it has so many leftovers from previous experiments, I'm ashamed to show XD. Will have to cleanup and post.
23
Coding / Re: the AI discussion
« on: July 09, 2010, 01:11:59 pm »
I took some time and had a discussion with my brother (who just happens to be into the math we need because of engineering) and he could identify some of the maths we need, without having any compromises.
Let's hope that works out ok, otherwise it's cpu grinding time.
Interesting thing about the RF/nock there dodon. Maybe if we can conjure the math properly we could give a helping hand to that part of the code. 100's of calls to the shoot is probably quite painful to the cpu (albeit in a time when you don't really need the cpu). So the mockshot tries to do something similar like us? Hmmm
Shaunc311: Yes, that's pretty much the stuff we'd have to replicate for shotSingle. For the AoE equivalent, I really didn't look much into it since I did expect it to be more complicated.
Even if we replicate the needed functionality in the AI, the cpu expense will stay about the same (we still need to play with vectors). The gain by copying the code/calcs is ofc not to abuse a system that wasn't meant for our case. I'll go and take a look at the RF code dodon mentioned since it does look a lot like ours (I'd like to see how it handles the out-of-turn player_t struct).
Right, I believe we should wait a few days and see if we can solve it by maths. If not, we can bite the bullet and copy code into the AI (or augmenting mock shot code to fit our needs).
Here's the issue as I described it to my brother, relayed here to make sure I won't ask the wrong things from him:
The point is to accurately (eve semi-accurately if it's faster/easier) find the expected dmg and hit % to a target with the least possible resources. As it is right now, we take 10 shots to the target, avg the dmg, which gives us roughly a avg_dmg*hit_ratio that fits our needs. <Explaining the trace-rand-retrace mentioned in my last post>. The tracing/intersection math is what's really expensive, and we'd like to limit it down to one. Given that we know the gaussian generation values, can't we just estimate the hit% to the target by taking into account the fact that the rands apply to the equation of the vector?
Apparently this isn't something hard, BUT, we do have issue no.2:
Well yes, but we don't care just for the hit % to the exact target (a point), but to the body of the target itself. So it's many points. And to make matters worse, at any distance from our gun, there can be an object partially occluding the hit window. In this case we want to project the 'shadow' of the object to the target window and subtract the 'target' area by it's shape.
Suffice to say this isn't as simple as the first case scenario as he started foaming a bit.
So, am I missing/forgetting something from my description? It'd be a drag to make him run the math only to find out at the end that I missed an important point.
edit: ah, yeah, we ignore dmg from bullets (non-gravity weapons) since the avg damage is easy to calculate. In explosion/indirect weapons the window suddenly expands and lays on the floor, while projecting shadows now becomes something that I can't even describe with magic markers. Ergh, maybe we can just bite the cpu bullet when the weapon is gravity-based?
Let's hope that works out ok, otherwise it's cpu grinding time.
Interesting thing about the RF/nock there dodon. Maybe if we can conjure the math properly we could give a helping hand to that part of the code. 100's of calls to the shoot is probably quite painful to the cpu (albeit in a time when you don't really need the cpu). So the mockshot tries to do something similar like us? Hmmm
Shaunc311: Yes, that's pretty much the stuff we'd have to replicate for shotSingle. For the AoE equivalent, I really didn't look much into it since I did expect it to be more complicated.
Even if we replicate the needed functionality in the AI, the cpu expense will stay about the same (we still need to play with vectors). The gain by copying the code/calcs is ofc not to abuse a system that wasn't meant for our case. I'll go and take a look at the RF code dodon mentioned since it does look a lot like ours (I'd like to see how it handles the out-of-turn player_t struct).
Right, I believe we should wait a few days and see if we can solve it by maths. If not, we can bite the bullet and copy code into the AI (or augmenting mock shot code to fit our needs).
Here's the issue as I described it to my brother, relayed here to make sure I won't ask the wrong things from him:
The point is to accurately (eve semi-accurately if it's faster/easier) find the expected dmg and hit % to a target with the least possible resources. As it is right now, we take 10 shots to the target, avg the dmg, which gives us roughly a avg_dmg*hit_ratio that fits our needs. <Explaining the trace-rand-retrace mentioned in my last post>. The tracing/intersection math is what's really expensive, and we'd like to limit it down to one. Given that we know the gaussian generation values, can't we just estimate the hit% to the target by taking into account the fact that the rands apply to the equation of the vector?
Apparently this isn't something hard, BUT, we do have issue no.2:
Well yes, but we don't care just for the hit % to the exact target (a point), but to the body of the target itself. So it's many points. And to make matters worse, at any distance from our gun, there can be an object partially occluding the hit window. In this case we want to project the 'shadow' of the object to the target window and subtract the 'target' area by it's shape.
Suffice to say this isn't as simple as the first case scenario as he started foaming a bit.
So, am I missing/forgetting something from my description? It'd be a drag to make him run the math only to find out at the end that I missed an important point.
edit: ah, yeah, we ignore dmg from bullets (non-gravity weapons) since the avg damage is easy to calculate. In explosion/indirect weapons the window suddenly expands and lays on the floor, while projecting shadows now becomes something that I can't even describe with magic markers. Ergh, maybe we can just bite the cpu bullet when the weapon is gravity-based?
24
Coding / Re: the AI discussion
« on: July 08, 2010, 01:52:04 am »
Shawnc311:
I don't use the 10 shots to get an avg damage, that is going to be pretty stable because the rand variations on damage are pretty miniscule. I run it so it can take into consideration a good amount of the hit probability. This is especially true with low-accuracy explosive weapons. So essentially I'm taking back the old dmg*hit-% metric. The more I think about it, the more I'm convinced we just have to duplicate the hit mechanics employed in the G_Shot functions:
a)Calculate the shooting origin of the weapon
b)Calculate a line that intersects the point we want to shoot
c)Apply rand&accuracy deviations on each axis with some gaussian rands.
d) Trace the modified line and find the first object that it intersects.
That wouldn't be that difficult to replicate, and the damage calculations are even easier. The real problem is the explosive weapons.
Mattn/other people that work on g_combat.c: What's the real use of the mock shots? Can we ninja-in the mock structure (and the shooting code) values that would stop us from having to sample shots?
It's not so much as the base dmg (we could easily estimate that) nor the % to hit (we could use the UI estimation function). It's the LOF issue which we cannot substitute with LOS. And remember, we don't deal with only one LOF, we deal with a 'window' to the target, since we don't always hit spot on and that's where the partial cover really comes into play (I guess we could skip the window calculations in favor of speed without sacrificing a lot).
1. Filtering by vis before taking shots: That's a very logical thing to do, and doesn't seem to be that hard (UNLESS that ent-to-ent visibility function uses the visflags, then I'm fked).
2. Aborting on shot > maxDmg. Sheesh! I can't believe I made such a nubbish mistake. I'm moving the entire if statement inside the loop to constantly keep checking the total mock damage vs the dmg_avoid_factor
I scaled the sampling down to 5 checks and now 4x4 is quite playable (still weeding out a bug that makes aliens try to take more shots than they can).
I also have a confession to make: I think I was mistaken in my assumptions (at least partly) about god-o-vision and the vis flags. If I'm not mistaken what I thought as a 'bug' was actually what was holding the AI back in terms of unlimited vision (quite crafty too). So, I worked under the assumption of that and amptly handed out vision to the aliens in my current code. Nonetheless, I do believe we should first see the results of the pending changes, then contrast them vs the 2.3 AI behaviour (with the augmented dmg calcs included). We could also slap on bestAia re-calculation every time a visibility event is thrown (at which point visflags should get recalculated) for some extra spice (for the 2.3 because the current work sees all).
Also, there are no performance issues with multiple calls to the AI_ActorThink() as I thought there would be. Oh well, good ole optimization needed then.
I don't use the 10 shots to get an avg damage, that is going to be pretty stable because the rand variations on damage are pretty miniscule. I run it so it can take into consideration a good amount of the hit probability. This is especially true with low-accuracy explosive weapons. So essentially I'm taking back the old dmg*hit-% metric. The more I think about it, the more I'm convinced we just have to duplicate the hit mechanics employed in the G_Shot functions:
a)Calculate the shooting origin of the weapon
b)Calculate a line that intersects the point we want to shoot
c)Apply rand&accuracy deviations on each axis with some gaussian rands.
d) Trace the modified line and find the first object that it intersects.
That wouldn't be that difficult to replicate, and the damage calculations are even easier. The real problem is the explosive weapons.
Mattn/other people that work on g_combat.c: What's the real use of the mock shots? Can we ninja-in the mock structure (and the shooting code) values that would stop us from having to sample shots?
It's not so much as the base dmg (we could easily estimate that) nor the % to hit (we could use the UI estimation function). It's the LOF issue which we cannot substitute with LOS. And remember, we don't deal with only one LOF, we deal with a 'window' to the target, since we don't always hit spot on and that's where the partial cover really comes into play (I guess we could skip the window calculations in favor of speed without sacrificing a lot).
1. Filtering by vis before taking shots: That's a very logical thing to do, and doesn't seem to be that hard (UNLESS that ent-to-ent visibility function uses the visflags, then I'm fked).
2. Aborting on shot > maxDmg. Sheesh! I can't believe I made such a nubbish mistake. I'm moving the entire if statement inside the loop to constantly keep checking the total mock damage vs the dmg_avoid_factor
I scaled the sampling down to 5 checks and now 4x4 is quite playable (still weeding out a bug that makes aliens try to take more shots than they can).
I also have a confession to make: I think I was mistaken in my assumptions (at least partly) about god-o-vision and the vis flags. If I'm not mistaken what I thought as a 'bug' was actually what was holding the AI back in terms of unlimited vision (quite crafty too). So, I worked under the assumption of that and amptly handed out vision to the aliens in my current code. Nonetheless, I do believe we should first see the results of the pending changes, then contrast them vs the 2.3 AI behaviour (with the augmented dmg calcs included). We could also slap on bestAia re-calculation every time a visibility event is thrown (at which point visflags should get recalculated) for some extra spice (for the 2.3 because the current work sees all).
Also, there are no performance issues with multiple calls to the AI_ActorThink() as I thought there would be. Oh well, good ole optimization needed then.
25
Coding / Re: the AI discussion
« on: July 06, 2010, 05:51:20 pm »
mattn's edition on the original diff includes the removal of a NULL player_t * being passed into G_ClientShoot. This would happen when HideNeeded requested GetDamagePotential. The null was my solution to G_ClientShoot returning false because G_ActionCheck reports 'this is not your turn'. This is logical ofc because we are mock-shooting for the humans in the aliens' turn.
ActionCheck though returns default true if "!player". We also need to skip ActionCheck because the TU's left on the human soldiers is next to 0 (we simulate the shots by checking vs 30 TU's worth of shots with the appropriate GetDamagePotential param).
Now, I found what caused all of my crashes, it's a visibility check that uses the (NULL) player_t when we are considering the humans tossing grenades. I took the liberty of enclosing that check in a "if (!mock)" check that seems to be covering all other visChecks in the code. If that's not viable for some reason, do tell me.
Now, for optimization in search trees, the higher-up you optimize (see: prune) the tree, the greater the overall gain. I did notice that the AI_Run is called on ServerFrame events, and only 1/10 of them is utilized. ActorThink is called way more than 8 times in the aliens turn, so that's the first place to start.
What are serverframes, when is AI_Run really called and why do we have to call ActorThink more than once for any alien is the issues I will solve... tomorrow, because today nonickch is hitting the bars.
Shaunc311: Yes that's one of the things we should see more into. I do indeed depend on the fact that ClientShoot will quickly return false. I will debug a few to see if there is any chance of G_ClientShoot returning anything but false after returning it one (you should be right with this one, but I just wanna make sure).
Update, the returning qfalse is "typedef enum {qfalse, qtrue} qboolean;", so we can't really make between 0-dmg because of a miss and qfalse because we can't take the shot.
MCR: I do love the customized alien behaviour aswell. Up to now I've seen 2 possible ways of doing that:
a) Behaviour: Move/tie GUETE values (or some of them) to a race/weapon-outfit. That can parameterize the aliens. If it needs to be LUA, I guess we could make LUA alter the GUETE's, then call AI_ActorThink. But aren't the alien stats scriptable?
b) Intelligence: If we ever incompletely search trees, the ordering of the candidate nodes decides the apparent 'intelligence'. Divert from best-to-worst to dumb-down.
I don't believe we're currently in any position to consider the extent of infra-vision. Maybe if we play with the CLOSE_IN metric... not sure. But in overall, aliens have the same amount of god-o-vision because we really have 0 visibility considerations in the AI (The last few we had I snuffed because of the vis flags). Once this cheating AI is top notch, then we can go from there.
For anyone thinking on running tests like these: Get CDT-Eclipse or go mental with any of your debuggers. I was slowly inching through the code untill I got my trusty eclipse up and everything sped along nicely. dcom_printf's are NOT to be trusted when you spam 100's of em.
ActionCheck though returns default true if "!player". We also need to skip ActionCheck because the TU's left on the human soldiers is next to 0 (we simulate the shots by checking vs 30 TU's worth of shots with the appropriate GetDamagePotential param).
Now, I found what caused all of my crashes, it's a visibility check that uses the (NULL) player_t when we are considering the humans tossing grenades. I took the liberty of enclosing that check in a "if (!mock)" check that seems to be covering all other visChecks in the code. If that's not viable for some reason, do tell me.
Now, for optimization in search trees, the higher-up you optimize (see: prune) the tree, the greater the overall gain. I did notice that the AI_Run is called on ServerFrame events, and only 1/10 of them is utilized. ActorThink is called way more than 8 times in the aliens turn, so that's the first place to start.
What are serverframes, when is AI_Run really called and why do we have to call ActorThink more than once for any alien is the issues I will solve... tomorrow, because today nonickch is hitting the bars.
Shaunc311: Yes that's one of the things we should see more into. I do indeed depend on the fact that ClientShoot will quickly return false. I will debug a few to see if there is any chance of G_ClientShoot returning anything but false after returning it one (you should be right with this one, but I just wanna make sure).
Update, the returning qfalse is "typedef enum {qfalse, qtrue} qboolean;", so we can't really make between 0-dmg because of a miss and qfalse because we can't take the shot.
MCR: I do love the customized alien behaviour aswell. Up to now I've seen 2 possible ways of doing that:
a) Behaviour: Move/tie GUETE values (or some of them) to a race/weapon-outfit. That can parameterize the aliens. If it needs to be LUA, I guess we could make LUA alter the GUETE's, then call AI_ActorThink. But aren't the alien stats scriptable?
b) Intelligence: If we ever incompletely search trees, the ordering of the candidate nodes decides the apparent 'intelligence'. Divert from best-to-worst to dumb-down.
I don't believe we're currently in any position to consider the extent of infra-vision. Maybe if we play with the CLOSE_IN metric... not sure. But in overall, aliens have the same amount of god-o-vision because we really have 0 visibility considerations in the AI (The last few we had I snuffed because of the vis flags). Once this cheating AI is top notch, then we can go from there.
For anyone thinking on running tests like these: Get CDT-Eclipse or go mental with any of your debuggers. I was slowly inching through the code untill I got my trusty eclipse up and everything sped along nicely. dcom_printf's are NOT to be trusted when you spam 100's of em.
26
Coding / Re: the AI discussion
« on: July 06, 2010, 03:15:13 am »GOOD NEWS EVERYBODY
Futurama is back!
Errr, I mean I solved many AI shooting-related problems. I think... eh, what? Oooh, but I do have my jammies on.
Futurama is back!
Errr, I mean I solved many AI shooting-related problems. I think... eh, what? Oooh, but I do have my jammies on.
On related news the damage calculations have been fixed & the AI_HideNeeded was brought in line with the dodon patch (no more suicide, mkay?).
Kinda... I used proof-of-concept sampling of real shots via mock calls to G_ClientShoot, and, um, I broke my CPU (a turn takes 15 mins atm and crashes are frequent). I didn't check memory usage, but I expect that to skyrocket aswell.
Remember the fan-out term and tree size theorycrafting? Good, here's how it all ties into this post, along with the performance cost estimations & the necessary optimizations. We consider each function separately:
GAH, upon reviewing, my complexity calculations are WAY off. Too bothered to fix tm
AI_FighterCalcBestAction
All damage considerations for a given target are now moved to AI_GetDamagePotential. All notes on AI_GetDamagePotential are in reference to the code that existed i AI_FighterCalcBestAction
AI_GetDamagePotential now drops visibility checks against the target because:
* (fix) Visibility checks were counter-productive. G_VisTeam was used which incorrectly (yet efficiently) checks the vis flags. BUT, a few lines above we moved our critter to a new position which makes those flags obsolete (and G_Vis a terrible liar).
* (fix) We don't need to see someone if we yield an indirect-fire weapon like a grenade/grenadelauncher.
This removes the visibility cut-off and produces a possible fanout between 0(seeing all targets) to enemies+civilians(16?). So, worst case scenario is 16x more leafs.
Obvious performance optimizations are to re-introduce visibility checks for non-indirect weapons.
AI_GetDamagePotential now has all it's damage calculations replaced with the avg of 10 G_ClientShoot mock-up calls. This means that the damage expectation we have is the best there can be (even better from the UI estimations imho).
* (fix) Aliens properly pick shoot types and shooting spots. The difference in their dmg output is quite dramatic.
* (fix) Aliens no longer try and shoot through walls. LOF is properly calculated in G_ClientShoot.
* (fix) Aliens now know the destructive power of grenades & launchers. I did not test this, but it is most probable that they will strongly prefer crowded places for their splash weapons.
* (fix) Aliens properly evaluate friendly fire/self-harm chances (they currently subtract FF damage from damage to enemies in order to get to a final expected dmg).
The penalty we take on performance is quite significant. The fan-out may be only 10 (ontop of the previous one, for a total 160x number of leaves compared to 2.3 AI), but the tracing calculations needed here are a heavy factor.
Performance optimizations needed: An obvious proper bridge to the G_ClientShoot (no reason to try 10x, instead it can give us a base dmg+deviation), OR a complete copy of the damage calculations inside the AI code (bad, code replication&heavy maintenance). Best solution is a mathematical equation that can give us comparable results with minimal CPU.
For people wanting to try and extract the math equations, have a look at g_combat.c. Entry point is G_ClientShoot. HELP APPRECIATED, I SUCK AT MATH
AI_HideNeeded
This function became an issue as soon as the dodon patch fixed a hiding issue which moved quite some weight onto this function. Right, over here we need to perform a basic morale check (if morale < brave, then we need to hide), but most of all we evaluate what kind of damage we can expect in the next round (given the tile we stand on). The old style was very simplistic and quite mistaken in the damage expectations. So, we change these with a call to our new AI_GetDamagePotential for every enemy soldier out there. Simple isn't it? That should fix:
* (fix) Aliens now exactly know how much damage they can take the next round (not taking enemies moving into consideration). This means that they will not wander in range of large guns for no reason (reason enough is ofc slamming a grenade in your cluster of soldiers
)Now, this function is what cause the MAJOR fan-out disaster of doom. If you exclude the changes in this function, the AI is fast enough to play, but here we fan-out again, ontop of our 160x worst case scenario. For every of those leaves we check the damage possible for every enemy. Yes, that's another set of the same fan-outs we had up to this point (we just have num_enemies, not num_enemies+civilians). So that's a worst-case scenario of 8, bringing our fanout up to 8x10=80. Since this is in sequence with the damage calculations, this is multiplicative bringing the total amount of leaves to 160x80=12.800 for a worst case scenario. Yes, this is the point where the CPU just shrieks and tries to liftoff. And don't forget, the shooting calculations are a whole lot heavier than any other calculation we ever do.
Obviously, this would need to be another place were we need to improve quite a bit if we still intend to perform full-tree non-heuristic searches. Only checking only vs enemies that have a direct line of sight would be a first step (but that would make us oblivious to indirect-fire nades/launchers). Other than that, I can't see many ways to keep this functionality and still preserve a full-tree searching. The performance of this function is mainly influenced from the AI_GetDamagePotential function, so any performance gain (in fan-outs) there affects this function in a sqrt kinda of way (8x8 vs (8-Y)x(8-Y)).
So there it is, a nice step forward. Woah, the aliens in the background game are giving me a REALLY hard time :}
You may wanna test this out, if only for a turn or two to get a general idea of what's really changing. You may also want to skip the changes that happen in the AI_HideNeeded function if you only want to see the AI gains in the damage output department.
Oh and I did change the g_ai.h #def GUETE_CIV_FACTOR to 0.20 (from 0.25) because it seemed right (I liked 0.15, but babysteps...). I also created a "#def GUETE_DAMAGE_AVOID 0.5" which is the % of current HP that an alien considers 'acceptable losses' (if not, this tile does not get the GUETE_HIDE bonus). Obvious possible change to this is to flip it from a binary value (run | not_run) to a gradient of score penalty.
Here's the svn diff vs the latest-ish trunk. (DO NOT GET COMMIT-HAPPY WITH THIS)
P.S: Sweet jesus, my squad got mauled in the last turn, and I did position them nicely...
27
Coding / Re: the AI discussion
« on: July 03, 2010, 03:43:29 pm »
Right, todays work ended up being the AI_HideNeeded while trying to tone down suicidal tendencies introduced from fixing the hiding checks.
There's quite a few things wrong with this function:
a) Checking if we take too much damage is very poor. Only considers one shot (probably the simpled firetype) from an enemy and doesn't add up the damage when many enemies can see you (death by pistol firing squad, dmg expected from a flamer is 7!!). I kinda fixed the many-enemies issue in my working copy (by just adding up and having a % of HP threshold) but then I found the rest of the bugs:
b) Before we consider the damage we take from an enemy, we first check if our team can see him: "if (G_IsVisibleForTeam(from, ent->team)) {". BUT, this function doesn't take into account that we're actually considering going places where we still have no vision on. So aliens tend up to rush to a firing squad as long as they had no vision on them. Testing fix of thinking we're always visible still stumbles upon:
c) Damage expectation from: a rocketlauncher is always 0, 0-range shotgun is 11, grenade launcher 0. This essentially turns AI_HideNeeded into just a morale check as I have never seen it evaluate true because of the damage. This is where I'd need the function-ized damage calculations mentioned in the previous post.
EDIT: I'm rewriting the damage calcs and HideNeeded atm. No need for someone else to go at it at the same time
The current state is this: The basic damage calculations are so simplistic you can say they are totally wrong. Attempts to use the core server shooting algorithm is not going anywhere since the G_IsVisibleForTeam(ent) is used all over the place, and this function does not take into account that we are considering an alternate positioning of our alien.
Anyone got ideas how to fix this without messing up the server code? If not, I guess I'll have to start ripping large portions of the G_* code
There's quite a few things wrong with this function:
a) Checking if we take too much damage is very poor. Only considers one shot (probably the simpled firetype) from an enemy and doesn't add up the damage when many enemies can see you (death by pistol firing squad, dmg expected from a flamer is 7!!). I kinda fixed the many-enemies issue in my working copy (by just adding up and having a % of HP threshold) but then I found the rest of the bugs:
b) Before we consider the damage we take from an enemy, we first check if our team can see him: "if (G_IsVisibleForTeam(from, ent->team)) {". BUT, this function doesn't take into account that we're actually considering going places where we still have no vision on. So aliens tend up to rush to a firing squad as long as they had no vision on them. Testing fix of thinking we're always visible still stumbles upon:
c) Damage expectation from: a rocketlauncher is always 0, 0-range shotgun is 11, grenade launcher 0. This essentially turns AI_HideNeeded into just a morale check as I have never seen it evaluate true because of the damage. This is where I'd need the function-ized damage calculations mentioned in the previous post.
EDIT: I'm rewriting the damage calcs and HideNeeded atm. No need for someone else to go at it at the same time
The current state is this: The basic damage calculations are so simplistic you can say they are totally wrong. Attempts to use the core server shooting algorithm is not going anywhere since the G_IsVisibleForTeam(ent) is used all over the place, and this function does not take into account that we are considering an alternate positioning of our alien.
Anyone got ideas how to fix this without messing up the server code? If not, I guess I'll have to start ripping large portions of the G_* code
28
Coding / Re: the AI discussion
« on: July 02, 2010, 10:07:44 pm »
Right.
Regarding dodon's patch, I've had conflicting reports from 2 people on irc.
One says it's much more challenging now, the other one says they're just plain suicidal/silly. Probably need to finetune values there and augment HideNeeded because it only checks for threat from single individuals and doesn't care if it's surrounded by 1000 lemmings (only cares if one of them can 1-shot 1/3 of it's hp). Also checks for visibility ofr that specific actor instead of shoot-ability, so I guess that's why the AI now hides behind your back more than often.
Found a new bug today while spamming debug messages around the code:
in AI_FighterCalcBestAction, there are cases where there is a target added to the action and no maxDmg set:
Perpetrator is the ungodly large set of nested statements before it (we should really break em down asap) that calculate damage:
Also, dmg may end up having a value when a target is not even remotely shootable, that's because of the continue;'s, so the fix I got is:
Here's the .diff
Can someone refactor the entire set of firing calculations into nice little functions? It's kinda chaotic to read and bug such as this can creep up. I tried to, but I still don't feel comfortable enough with C code.
It'd be nice to especially have the calculations for the base damage as one function, as I can use this in the AI_HideNeeded in order for the aliens to properly evaluate the threat level (don't run headlong into my machine-gunner you idiotic tammie).
Dammit, maybe I'll finally manage to get to the part where I can test the pathing close_in metric tommorow.
Regarding dodon's patch, I've had conflicting reports from 2 people on irc.
One says it's much more challenging now, the other one says they're just plain suicidal/silly. Probably need to finetune values there and augment HideNeeded because it only checks for threat from single individuals and doesn't care if it's surrounded by 1000 lemmings (only cares if one of them can 1-shot 1/3 of it's hp). Also checks for visibility ofr that specific actor instead of shoot-ability, so I guess that's why the AI now hides behind your back more than often.
Found a new bug today while spamming debug messages around the code:
in AI_FighterCalcBestAction, there are cases where there is a target added to the action and no maxDmg set:
Code: [Select]
if (aia->target) {
bestActionPoints += maxDmg;
assert(maxDmg>0);
assert(bestTime > 0);
tu -= bestTime;
}The assert(maxDmg>0) is there to prove the point.Perpetrator is the ungodly large set of nested statements before it (we should really break em down asap) that calculate damage:
Code: [Select]
maxDmg = 0.0;
for (shootType = ST_RIGHT; shootType < ST_NUM_SHOOT_TYPES; shootType++) {
See the maxDmg being reset? That shouldn't be there as it holds the current max dmg. I commented that out.Also, dmg may end up having a value when a target is not even remotely shootable, that's because of the continue;'s, so the fix I got is:
Code: [Select]
for (fdIdx = 0; fdIdx < item->m->numFiredefs[fdArray->weapFdsIdx]; fdIdx++) {
dmg=0.0;
Here's the .diff
Can someone refactor the entire set of firing calculations into nice little functions? It's kinda chaotic to read and bug such as this can creep up. I tried to, but I still don't feel comfortable enough with C code.
It'd be nice to especially have the calculations for the base damage as one function, as I can use this in the AI_HideNeeded in order for the aliens to properly evaluate the threat level (don't run headlong into my machine-gunner you idiotic tammie).
console command "sv debug_showall"Many thnx for that one
Dammit, maybe I'll finally manage to get to the part where I can test the pathing close_in metric tommorow.
29
Coding / Re: the AI discussion
« on: July 02, 2010, 03:50:21 pm »
That would eat into the AI calculations. You could check and see if it's the player teams' vision, but then again the AI does exactly the same calc to see if it's being seen.
If there's no standard way to do that, no biggie, I can just kill the AI and walk around instead.
If there's no standard way to do that, no biggie, I can just kill the AI and walk around instead.
30
Coding / Re: the AI discussion
« on: July 02, 2010, 01:36:05 pm »
coding high-5 dodon 
So, now: we give the hiding bonus to spots that don't cause our aliens to shit_pants (according to the morale/brave comparison) and spots that have caused our actor to dissapear from enemy view. Try out a standoff landing, the results will be quite different than what you expected.
I tried a couple of skirmishes and oh boy does this slight change totally change the alien behavior. You guys need to check for yourselves, they're pretty much all over the place not always hiding (even with the original 60 GUETE value).
If this 'error'/'new behavior' was introduced into a patch, how come nobody went 'omg aliens are cowards now'?
Somehow the aliens think that hiding right behind a soldiers back (after stabbing him) is a good place to hide (when they actually dissapear it's ok, they also do it when they don't). Todo I guess.
Getting stabbed is now quite popular, aliens will not cower in a bungalow close to you never to come out again.
We should remember that whatever makes sense to us and looks logical in code does not directly lead to better alien behavior in the game. That's why we need of testing with even slight changes to see if we turned them into zombies.
I'm trying to figure out a way to visualise the search tree to a developer. Is it possible to:
a) Draw those 'move-to' lines (that appear if I click a soldier of mine to move during the aliens turn)
b) Freeze the execution of the ai until some external event somehow arrives from the console/client (I can smell the mutex&threaded client/ServerFrame being thrown here, is there something simpler?)
This way you can examine some debugging output as the alien examines each tile separately (and visualized by the move-to lines). Type something in the console to consider the next tile.
Once we start using performance cutoffs this will be sorely needed since we will actually be able to see them kick in without going through thousands of debug lines.
I was trying to switch the close-in bonus to pathing last night, not much of a success (working on it). This is to fix the hull-hugging behavior.
While fixing that, I spotted another quite influencing parameter for the AI: #def CLOSE_IN_DIST 1200. Now this one was very subtle and was overshadowed my the puzzling OR in the hiding calcs.
As it stands, this 1200 value is the vector distance at which the aliens will start gravitating towards your soldiers. As long as you're further away from that (to be precise: further away from a tile an alien is considering to move to), the CLOSE_IN bonus is effectively nullified. While trying out the pathing distance metric, I'll be using something similar, like 50 TU's. That'd make an alien start gravitating towards you when he can get next to you within the next ~2.7 moves.
Ahhh, that's why my tests failed and the aliens looked stupid. They needed a larger value to get out of the ship. This complicates things, as the needed 80+ values to get aliens out of the ship are very large when no obstacles are involved (they can gravitate from other side of the map). I'll also be testing a weighted average of both vector and pathing to see if it's better.
Hey, can I somehow remove the fog of war?
So, now: we give the hiding bonus to spots that don't cause our aliens to shit_pants (according to the morale/brave comparison) and spots that have caused our actor to dissapear from enemy view. Try out a standoff landing, the results will be quite different than what you expected.
I tried a couple of skirmishes and oh boy does this slight change totally change the alien behavior. You guys need to check for yourselves, they're pretty much all over the place not always hiding (even with the original 60 GUETE value).
If this 'error'/'new behavior' was introduced into a patch, how come nobody went 'omg aliens are cowards now'?
Somehow the aliens think that hiding right behind a soldiers back (after stabbing him) is a good place to hide (when they actually dissapear it's ok, they also do it when they don't). Todo I guess.
Getting stabbed is now quite popular, aliens will not cower in a bungalow close to you never to come out again.
We should remember that whatever makes sense to us and looks logical in code does not directly lead to better alien behavior in the game. That's why we need of testing with even slight changes to see if we turned them into zombies.
I'm trying to figure out a way to visualise the search tree to a developer. Is it possible to:
a) Draw those 'move-to' lines (that appear if I click a soldier of mine to move during the aliens turn)
b) Freeze the execution of the ai until some external event somehow arrives from the console/client (I can smell the mutex&threaded client/ServerFrame being thrown here, is there something simpler?)
This way you can examine some debugging output as the alien examines each tile separately (and visualized by the move-to lines). Type something in the console to consider the next tile.
Once we start using performance cutoffs this will be sorely needed since we will actually be able to see them kick in without going through thousands of debug lines.
I was trying to switch the close-in bonus to pathing last night, not much of a success (working on it). This is to fix the hull-hugging behavior.
While fixing that, I spotted another quite influencing parameter for the AI: #def CLOSE_IN_DIST 1200. Now this one was very subtle and was overshadowed my the puzzling OR in the hiding calcs.
As it stands, this 1200 value is the vector distance at which the aliens will start gravitating towards your soldiers. As long as you're further away from that (to be precise: further away from a tile an alien is considering to move to), the CLOSE_IN bonus is effectively nullified. While trying out the pathing distance metric, I'll be using something similar, like 50 TU's. That'd make an alien start gravitating towards you when he can get next to you within the next ~2.7 moves.
Ahhh, that's why my tests failed and the aliens looked stupid. They needed a larger value to get out of the ship. This complicates things, as the needed 80+ values to get aliens out of the ship are very large when no obstacles are involved (they can gravitate from other side of the map). I'll also be testing a weighted average of both vector and pathing to see if it's better.
Hey, can I somehow remove the fog of war?