Collision detection problem.

ID:162464
 
Jan 5 2008, 6:21 am
Okay I am making a pixel projectile system. I've gotten the projection part done, and part of the collision detection done. I have a problem, though.

When a projectile is moving fast enough, it starts to skip over whole tiles. These tiles may have dense objects in them. How do I check to see if there is a dense object between points A and B?

Note, please don't direct me to Shadowdarke's PixelProjectiles library. It does not suit my needs.
Jan 5 2008, 9:33 am
The same way you check for hits when it's not going as fast? Is it feasible to just record the turfs between points A and B and check for a hit using t.Enter()?
Jan 5 2008, 9:34 am
In response to CaptFalcon33035
That's inaccurate. It needs to be as accurate as possible.
Jan 5 2008, 9:34 am
In response to Koil
What's inaccurate about it? 0.o
Jan 5 2008, 9:43 am
In response to CaptFalcon33035


Maybe that helps.

Cyan dot is the initial position, red dot is the next step, and the blue dot is something that needs to be checked for a collision.

That obviously wouldn't collide, but if I did it per tile it would. That's not accurate enough.


However, now that I think about it, in the particular game I'm using this in, there shouldn't be any collisions that aren't whole icon sized. So nevermind. ;)
Jan 5 2008, 1:57 pm
In response to Koil
BYOND games aren't "accurate" enough to be able to shoot a marble in between two rectangles with space in the middle.

o Marble
|
P
_ A _
| |T| |
|_|H|_|
|
x Start
Jan 5 2008, 11:52 pm
Koil wrote:
Okay I am making a pixel projectile system. I've gotten the projection part done, and part of the collision detection done. I have a problem, though.

When a projectile is moving fast enough, it starts to skip over whole tiles. These tiles may have dense objects in them. How do I check to see if there is a dense object between points A and B?

What you need to do is account for the edges of the tiles. This will tell you which spots to look out for.

Let's say we start with some simple vars: O,opx,opy for origin turf and pixel_x/pixel_y. For convention's sake, a pixel offset of 0,0 is at the lower left corner of its tile. Now you need a direction, so that's dpx and dpy: Pixels moved per unit of time. These can be fractional since your calculation doesn't rely on integers.

On any given tick, your projectile is on a specific turf and has a specific pixel offset. Now this gives you what you need to calculate a turf impact. The turf impact will be turf I, with Ipx and Ipy representing where the impact happens. If you hit on the right side of this turf for instance, Ipx would be 32, but Ipy would be anywhere from 0 to 32 depending on where it hit. (Note: It's possible to impact a corner precisely, so when that happens you'll have to figure out how the turfs are set up in relation to each other if you use this info to bounce stuff around.)

// Itime is time remaining in this tick
proc/CalculateImpact(Itime=1)
    var/t
    I = null
    if(dpx>0)
        while(opx >= 32)
            T = get_step(O, EAST)
            opx -= 32
        if(opx + dpx >= 32)
            O = (32-opx) / dpx
            if(t < Itime)
                I = get_step(O, EAST)
                Ipx = 0
                Ipy = opy + t*dpy
                Itime = t
    else if(dpx<0)
        while(opx <= 0)
            O = get_step(O, WEST)
            opx += 32
        if(opx > 0 && opx + dpx <= 0)
            t = -opx / dpx
            if(t < Itime)
                I = get_step(O, WEST)
                Ipx = 32
                Ipy = opy + t*dpy
                Itime = t
    if(dpy>0)
        while(opy >= 32)
            O = get_step(O, NORTH)
            opy -= 32
        if(opy < 32 && opy + dpy >= 32)
            t = (32-opy) / dpy
            if(t < Itime)
                I = get_step(O, NORTH)
                Ipx = opx + t*dpx
                Ipy = 0
                Itime = t
    else if(dpy<0)
        while(opy <= 0)
            O = get_step(O, SOUTH)
            opy += 32
        if(opy > 0 && opy + dpy <= 0)
            t = -opy / dpy
            if(t < Itime)
                I = get_step(O, SOUTH)
                Ipx = opx + t*dpx
                Ipy = 32
                Itime = t
    if(I)
        O = I
        opx = Ipx
        opy = Ipy
    else
        opx += Itime * dpx
        opy += Itime * dpy
    // return the amount of time elapsed
    return Itime


The thing you'd want to do is to repeatedly call this, keeping note of its return value as you went along. A simple loop would look like so:
var/time = 1
while(time > 0)
    time -= CalculateOffset(time)
    if(I)
        // consider hit, change of direction, etc.


This gets slightly more complicated if you're in an environment where the hit can cause damage and destroy the wall/etc. it its, because different shots might both hit the wall within the same tick. In a case like that, you'd want to calculate the minimum hit time for any projectile into any turf boundary, and step the calculations forward.

If your projectile has a radius, this also complicates the issue because then it's possible to impact a turf on a corner.

Lummox JR