Beam Weapon Collision Detection

[Hearteater]

In response to this mantis issues I mentioned using a translation/rotation approach, instead of a line/circle intersection test.  I threw together a quick C# speed test at lunch and I was getting much better results with translation/rotation even with as few as 50 targets.  I realize you guys don't use doubles for this stuff, but just as a proof of concept I've included the speed test and a results screen shot.

Of course if you are already using translation/rotation then nevermind .

[x4000]

That's a really hefty improvement!  But you're not getting the exact same results, it looks like?  I am not familiar with the translation/rotation test, and don't really follow the premise of the math it uses (I see what it's doing, and why that's faster, but not what that represents in practical terms).

[Hearteater]

Basically you translate the attacker and target to the origin (simple subtraction of the attacker's x and y from the target).  The you rotate the target around the origin so that the beam attack is travelling along the x-axis in the positive direction.  You do this by finding the angle of the beam attack from the x-axis, and then rotate in the opposite direction that amount.  This gives the target a new x and y location.  The attacker doesn't move because he's at the origin.  The beam moves, but we don't need to do any math for that because we already know its width and length and those values translate directly to x and y easily.  Effectively you are now testing for intersection with the positive x-axis up to a point equal to the length of the beam.  Just don't forget to account for the target's radius.  See also the attached image.

The mis-matches appear to all be edge-cases.  The 4000 ship, 10k run matched 99.918% the same which is probably good enough that no human would be able to spot the difference.

[x4000]

Very clever!  Thanks for taking the time to explain that to me.

What an amazing thing to have code just handed to us like this. 

[Hearteater]

When I found this I was going to do it up using FInt instead of doubles, but to really get an accurate speed test I'd need to run it against your actual collision code anyway, so I figured I'd just do a clean proof of concept.  It still may not be better than what you are doing, but it does look promising.  Anyways, I figured you guys were busy enough with AVWW that fiddling with something like this isn't really something you have time for so I wanted to make it as easy as possible for you guys to take advantage of.

[x4000]

I appreciate it!

[Hearteater]

Oh, the code I provided did not cover beam width since I wasn't even positive you had any wide beam attacks.  But if you do, just pass in the width of the beam, cache half the width locally, and change line 71:

Code: [Select]

BEFORE:
71:           if (y <= t.radius)

AFTER:
71:           if (y <= t.radius + halfBeamWidth)


[keith.lamothe]

Beams have no width in that sense, you were right originally

I was really beat today from some other stuff going on so I cracked this problem open to relax a bit, and upon further investigation I found that we don't actually do line vs circle, we do line vs the circle's inscribed square, whose sidelength is precomputed to avoid any trig.  Way less complex than anything involving a curve or approximation thereof.

But it's still running really slowly.  Part of it is FInt: I created FInt equivalents of your Intersection and Rotate methods and they were roughly 10x slower than your double-based variants.  Then I tested our "cheat and use the square" method and it still came up really slow (faster than IntersectionFInt, but interestingly slower than RotateFInt... how could it possibly be slower than trig, right?).  After a bit of profiing it seems like most of the cost is in casting ints to FInts, but I'm still not entirely sure.

Anyway, thanks for kickstarting the investigation, significant gains seem likely in the end

[Hearteater]

Very interesting.  Glad to help.  I had fun throwing it together.  If nothing else works, maybe you could just unroll the FInts into their RawValue longs and do the operations manually in the collision test method.  Not pretty, but sometimes speed isn't .

I actually haven't forgetten this thread either.  Sadly Bit Tries just can't complete with the extremely fast C# Dictionary implementation.  In fact for AI Wars the Dictionary is nearly as good as an array.  But I've been messing with a custom Dictionary implementation that looks like it might shave 4 bytes per entry.  I don't think it will have any noticeable speed improvement, but it will be at least as fast.  It does handle memory allocation better when it gets really big.