line segment square collision detection

[FloooD]

here's what i got for line segment square collisions... stole it straight from lua lag comp :D

https://gist.github.com/876568

any way to making it faster?

[leegao]

looks good (AKA lee's too lazy to read code today :P)

I remember doing line collision detection using bits and pieces of linear algebra to find the projection of the bullet trail onto each side of the rectangle/polygon and finding the parameters of the new ray/line for the begin/ending points of the projection (onto an infinitely extended vector for each side in the direction of the unit vector of the side) and testing to see whether this projection overlaps with the side of the polygon. If I remember correctly, the algorithm for testing this runs in O(1) amortized time per square, with just one line of calculation :P (albeit I haven't tested it so I have no idea whether it works or not)

[leegao]

PS: collision detection for players should be easy, theoretically, assuming 32px circle of hitbox, just test whether the shooter's angle falls within

atan( delta y/ delta x) +- atan(16/ sqrt (dydy + dx \ dx))

I totally dare you to use

float inv_sqrt( float n ) { // from wikipedia
    long i = 0x5f3759df - ((*(long*)&n)>>1);  // what the fucking fuck?
    float y = *(float*)&i;
    return y*(1.5-(0.5*n*y*y));   // 1st iteration of newton's approximation
}

and atan(dy/dx) + (float epsilon = atan(16._inv_sqrt(dy_dy+dx*dx)));

[FloooD]

in standard cs2d player hitboxes are 24x24 squares

I would rather avoid using arctan :p

[leegao]

y no u use arctan? <_<

I gotta finish the rest of my CS hw before spring break sets in

[FloooD]

idk a circular 'hitbox' could feel weird... and it isn't consistent with the squares used to detect wall collisions

[leegao]

o_O the arctan is only for the players, the tiles would obviously need to use your square collision detection.

[FloooD]

i meant that player-wall collisions use squares

still wouldnt square hitboxes be less computationally expensive than circles? with circles you still have to do all the start-point end-point checks since we are dealing with line segments and not rays. and then you can convert shit into angles and do some crap... whatever it's not very important for now and you can add triangular hitboxes later if you want rofl

[FloooD]

btw the current thing takes like 0.2 - 0.3 seconds per 1000000 calculations on my intel atom which underclocks itself to 800mhz worst case scenario:

32 players all shoot during the same frame 31 bullet - player collisions per bullet plus about 60 tile collisions so maximum is about 3000 calls to this functions every frame 3000 * 300ns = 0.9ms = 45% of a frame's time

of course that's not gonna ever happen in practice

[FloooD]

hm for circles it's actually pretty simple..
under polar coordinates with the starting point as origin

oh and I think it's arcsin(16/whatever)

edit: redoing the function with origin defined as starting point

new version: 100-240 nanoseconds. note: it's only > 120 ns when the collision is with a horizontal edge.

[FloooD]

k the stuff is getting so stripped down i barely know how it works now from reading the code...

[leegao]

shit, I wrote arctan for the margin too didn't I? T_T

[leegao]

still trying to finish my CS hw, I almost hate CS now <_< (note to posterity, never take the hardest undergrad CS course as a freshman)

[leegao]

oh wait, shouldn't it be arctan? o_O I have the denominator as the distance between the player and the center of the circle, so arctan should work

[FloooD]

no it's arcsin
get a piece of paper and draw it :P

if the point is in the edge of the sphere... lol cs homework... :P how many hours u spend a week? for physics i usually just do the homework the day it's due in ~3 hours

[leegao]

it used to take only around an hour or two to finish a problem set, we had to write a scheme interpreter with a full AST and everything (that only took me 5 hours) and then 7 stupidass proofs via natural deduction that is for all extensive purposes the most fucking waste of time ever. 3 effing days to finish, but I am now done :D (looks around for the party-hat emoticons)

btw, arcsin if we're using a line to the rim of the circle, arctan if to the center, I'll do a little bit of coding tonight for lua integration, but we're driving out tomorrow morning so I probably won't get anything in substantial. (You sure you don't want a quadtree? Those are inexpensive to instantiate and are fast, and I'm pretty sure I can get the implementation right)

[FloooD]

lol ouch :P

uh... no it's arctan (16/origin_to_rim) or arcsin(16/origin_to_circle_center) since the line from the origin to the rim is perpendicular to a radius line

[leegao]

oO shouldn't the origin->center line be perpendicular to the radius since we're going for a low/high bound on the angle? |/

[FloooD]

http://i.imgur.com/puI0g.png

red lines are max/min angles
sin(theta) = (R / sqrt((ex^2)+(ey^2)))

edit: k line-square is now always <200ns. still figuring out some stuff btw i calculated wrong previously. old version was 160-300ns

[leegao]

oh, I thought you meant the player-shooting-player circle, nevermind then, turns out packing just ate away the last few hours, probably won't be able to help for a while

[FloooD]

o.O that is what I meant lol

[FloooD]

current times (plus/minus 10ns) 40ns with end point and origin both inside box 160ns with origin inside box and end point outside. apparently sqhlen *= -1 takes 20ns -.- 55ns end point at origin 140ns collision but origin not inside box 100ns no collision

[FloooD]

k 2 less ns for the stuff above

[FloooD]

https://gist.github.com/880563 ya that's how simple it is yet it takes 290ns :P