Talk:Bullet Shadow

Cut from Talk:Diamond/Version_History#1.6.0

Very nice score increase indeed. As a heads up, Chase-san has made "cs.Nene MC58k7" the second robot in the rumble to do passive bullet shadow surfing, haha. Also... hmm... it seems bullet shadows will now go on the looooong list of things for me to include on my next surfer. --Rednaxela 06:23, 22 August 2011 (UTC)

Oh, a question about implementations: are you calculating where bullet shadows will be before the bullets pass through the waves, or are you only updating shadows once the bullet actually hits the wave? Currently I'm doing the latter, but I suspect the former may improve scores a bit. Also, precalculating hits may be nasty once actual bullet hits start happening - keeping track of which bullets (which may now be gone) improved which waves (which may now be gone) and in what order is a bit of a nasty. (this question goes for you too, Chase) --Skilgannon 07:33, 22 August 2011 (UTC)

At the moment I only add the bullets once they actually pass the wave, as this was much simpler to add. — Chase-san 10:21, 22 August 2011 (UTC)

Why would order matter? The shadows exist for every pair of bullet/enemy wave until/unless there is a BulletHitBullet, then you can recalculate them all. I still say it's not nasty, despite the fact that I moronically forgot to remove the destroyed bullet before recalculating in 1.6.1. --Voidious 16:03, 22 August 2011 (UTC)

Yeah, but the destroyed bullet might have created shadows by passing through waves before it was destroyed. If you remove it entirely then you'll lose out on those shadows. --Skilgannon 06:48, 23 August 2011 (UTC)

Yeah the new Nene version takes this into consideration. Only waves that it has yet to pass through is it removed from. Since the older ones have been already been proved to be safe. — Chase-san 06:53, 23 August 2011 (UTC)

Lol @ "death blow". =) Yes, I calculate as soon as a bullet or wave is added. And as of 1.6.1 (which sadly seems to be exploding somehow on Darkcanuck's client) I recalculate all bullet shadows from onBulletHitBullet. It's not really that nasty. I have my lists of active bullets and active enemy waves - when I add one, I loop through the other, and onBulletHitBullet I loop through both, clearing the old shadows first. --Voidious 09:26, 22 August 2011 (UTC)

Congrats. Looking at your debug graphics are the dangers of the dots the actual dangers you use to calculate movement or do you just use those for painting and not use bins for you surfing? I don't use bins in Gilgalad to make the botwidth more precise, but this makes it difficult to mark an area on a wave as safe.--AW 13:37, 22 August 2011 (UTC)

I don't use bins - indeed I do just calculate the danger at 51 specific points for the debug graphics. --Voidious 13:44, 22 August 2011 (UTC)

Well for marking areas as safe without bins, I believe there are two ways:

1. The simple way: Just scale the risk depending on the proportion of the botwidth that is covered by the shadow. (Potential trap of getting caught by bullets near but outside shadows, but Nene MC58 shows this simple method is better than no bullet shadows)
2. The accurate way: Ensure you have a risk function that works with the guessfactors ranges rather than just the center. Then ensure your risk function satisfies the criteria "risk(A to B) + risk(B to C) = risk(A to C)". If your risk function is defined that way, you can subtract the risk of the overlap with the shadow (be sure to not double-count multiple overlapping shadows on the same wave)

--Rednaxela 14:16, 22 August 2011 (UTC)

Rednaxela's #2 is clearly the most accurate way, but seemed really hard. My two approaches were his #1, and since you're dealing with raw firing angles already when you don't use bins, just ignore any angles that fall within a bullet shadow when doing kernel density to calculate danger. Both of those options performed about the same, but somewhat shockingly, doing both was almost twice as good in my test beds. --Voidious 14:26, 22 August 2011 (UTC)

Exactly what I was thinking (re: accurate but difficult), but I have an idea on how to approximate it. The reason it is hard is that we want the danger to push us as far as possible from the firing angles, and to do this, you can use bins (less accurate) or as we do, some smoothed kernel density estimation. So basically we want to approximate the integral of the kernel density estimation across the bot width and use that for our danger. To mark an area as safe, we need to find the danger on the intersection of the interval we will mark as safe and the interval the bot will cover and subtract that from the danger of this movement option as calculated without bullet shadows. So the question is now: "how do you approximate the integral?" Because the danger function is smoothed relative to our bot width, we previously used the center of the bot to approximate danger, but we can do it differently without using much more CPU time. We can approximate the danger by taking the Riemann sum (average the upper and lower for more accuracy) of the kernel density estimation on the interval the bot will cover (for more accurate calculations use more points.) Approximate the danger on the intersection using the same method, subtract this from the movement option's danger, and use this new value. I hope that was clear enough.--AW 15:13, 22 August 2011 (UTC)

Also, if anyone can understand / clarify the algorithm above, should it be added to Bullet Shadow--AW 15:17, 22 August 2011 (UTC)

I think that is very similar to using bins =) The difference being using bins only for the bullet shadow, not the danger function... --Skilgannon 15:37, 22 August 2011 (UTC)

My view is... why bother with the mess of doing a approximations of integrals? Using the exact formula is not hard. Just design a risk function for "probability they fire at a given angle", do a proper integral of that, and just start using it. No need for the extra coding complexity of iterative approximations. It's really not difficult at all, so long as you have a well defined risk function in the first place. If your kernel density function for "probability of where they fire" is the sum of gaussian curves, the integral over a botwidth is made up sums of the "error function". It seems to me, that doing it in an accurate way is only difficult if your risk function is not well-founded in the first place. --Rednaxela 15:56, 22 August 2011 (UTC)

Agreed, I didn't realize how easy it would be to get the actual value.--AW 21:21, 22 August 2011 (UTC)

Actually Rednaxela's full method is more or less precisely what Nene did originally, however it required changing my risk function, the new risk function did not perform as well as the older one did, meaning it gained an overall drop in score. I have attached a little doodle I drew detailing about how it works.— Chase-san 15:23, 22 August 2011 (UTC)

http://img189.imageshack.us/img189/4650/bulletshadowintegrals.th.png

Even with bins it's a complicated story. Because of the finite number of bins, there are obviously cases where bins are only partially covered. So what do you do? Round it at 0.5, take the risk and act like they're empty? Act conservatively by using floor and ceil and not take advantage of that extra half bin that could have been safe? Obviously, the larger the number of bins the better, but isn't it always like that... right now I'm weighting the bin by the portion that was covered, but I don't really like it. According to MC2K7 it worked just a smidgeon better when rounding, but not against the weak bots - I lost 0.3 on average compared to partial bins. The possibility for tweaking is endless...--Skilgannon 14:58, 22 August 2011 (UTC) s

Funny you should say that about endless tweaking. This struck me as a super straightforward feature that you'd implement, collect your 0.8 APS, and move on. :-) Well, before considering more strategic applications where you modify when/where you fire. I may try doing the integral thing to subtract the exact danger in the shadowed region, but I don't expect much gain from that, if any. And it seems non-debatable that that's the most accurate way of modeling the impact on surfing dangers, right? The approximation of 171 bins can't be too far off. (Btw, we should prolly cut/paste all this to Talk:Bullet Shadow sometime...) --Voidious 18:07, 22 August 2011 (UTC)