I can't get collision detection to work

[VideroBoy]

Kind of a followup to my other project.

There was a remaining bug in my collision detection code that allowed an actor penetrate a corner no matter what I did. I was able to gloss over this when I just had one actor moving through a level. However, I thought it was something I'd need to fix in order to make collisions between multiple actors work better. Except I. Can't. Fix. The. Damn. Thing.

Having no way to tell where the bug could be coming from I'm just dumping my code here in the vague hope that someone else will bother to read it.

So you know what you're getting into:

• I use a predictive approach to collision detection
  • I test if and when a collision will occur before moving an actor
• The player-controlled actor is a circle
• Walls are represented by edge line segments and corner points
• When moving an actor, I get the line segments and corner points the actor will likely hit
• I test the actor against each of these lines and points, getting the minimum time of impact if any
• If a collision will occur, I return a new velocity for the actor along with the time of impact
  • The new velocity is meant to make the actor slide along the obstacle
• The time of impact is (supposed to be) a value between zero and one
• The time of impact is a time within the current frame
  • The frame is a time period of one
  • I regulate the frame rate
• If a collision occurs within the frame time I move the actor by the collision time and subtract that time from the frame time
  • I keep testing and moving the actor until no more time is left in the frame
  • This is how sliding is able to work
• In the attached code, I've removed any coordinate rounding I used previously, in case they were messing with my results
  • You will see several graphical artifacts when the player actor has floating-point coordinates

What the actual problem is:

• Negative time values for collisions can occur
• These always come from the corner collision tests
  • I'm convinced the circle-corner collision test is still allowing penetrations
• I'm convinced I ought to fix this to make simulating a level full of actors easier
• Also, the negative time values cause the main actor movement code to go into an infinite loop, since it's largely assuming things go forward in time
  • Previously, when I was rounding things, I got around this by checking for a zero (rounded) response vector
    • Not possible without rounding
    • I kind of want to know what the real problem is
  • Be ready to kill the program when testing it
• To find the bug, you sort of have to move against a corner and, while sliding around it, move into the wall edge beyond it
  • e.g. Move south, against a north-west corner, while trying to move into the west side of the corner's tile
  • Before
  • After
  • The game will probably freeze shortly after this

Relevant code:

• main.lua
  • Line 245, function moveActor - Where collision detection and actor movement occurs
• collision.lua
  • All of it, really
  • Line 272, function checkCorner - Test actor against corner
  • Line 341, function actorVSTile - Test actor against line segments and corners of a tile
  • Line 384, function actorVSLevel - Main function that gets tiles actor will likely hit and test actor against those
  • Line 179, function checkWall - Get line segments and corners actor will likely hit for a single tile
• levels.lua
  • Has some stuff about getting tiles
  • Line 69, function tilesInRect

Some web links that I used as reference

• http://twobitcoder.blogspot.com/2010/04 ... ction.html - Circle-circle collision detection
• http://local.wasp.uwa.edu.au/~pbourke/g ... ineline2d/ - Line intersection
• http://www.physicsforums.com/showthread.php?t=202263 - Vector projection

I know that this is a lot to ask for, but I've been beating my head on this forever. I've tried asking elsewhere (without posting my full source code) and have had zero responses. I honestly don't know where else to go.

In conclusion, help on this will be appreciated. I'll also accept hugs.

[kikito]

This is so much code to browse...!

Let me see.

I don't like the 'north','south','east','west' in functions and structures. Too much "copy-paste". If you really need to make multiple functions with directions, consider using something like this:

Code: Select all

for direction, coords in pairs({ north = {x=0, y=1}, east = {x=1, y=0}, south = {x=0, y=-1}, west = {x=-1, y=0} }) do
  _G['go_' .. direction] = function()
    x = x + coords.x
    y = y + coords.y
  end
end 

Instead of defining go_north, go_east, etc. individually by copy pasting.

Also, why you use north,south,east and west in some cases and 'up', 'down', 'left' and 'right' in others? One single mistake in 'translating' (using 'north' when you meant 'up') is all it takes for a member to become nil instead of {your_table_full_of_members}.

You can return multiple values without creating a table:

Code: Select all

function foo()
  return 1,2,3
end
local a,b,c = foo()

Appart from these things, are you sure your mathematical model is 'solid' ? I mean, if you are detecting collisions against *segments* ... well, they are very easy to miss, because they are so ... unidimensional. They have tricky properties on their vertices, too. I've never attempted a collision detection system myself, but using solids (as in, 2-D objects) seems like a much less 'tricky' way to do things.

That is all for now.

Oh, I send you a hug too

[VideroBoy]

This is so much code to browse...!

Yeah, sorry about that. I was desperate.

why you use north,south,east and west in some cases and 'up', 'down', 'left' and 'right' in others? One single mistake in 'translating' (using 'north' when you meant 'up') is all it takes for a member to become nil instead of {your_table_full_of_members}.

Yeah, I'll admit that's confusing. I think it resulted from me trying to distinguish between the cardinal directions for movement and usage of the arrow keys, which will be used for things besides movement like menus. I suppose it might be unnecessary

You can return multiple values without creating a table:

Code: Select all

function foo()
  return 1,2,3
end
local a,b,c = foo()

I'm aware of that. Are you by any chance referencing the functions that return collision data (time of impact and new velocity)? I pack them into a table because the returned collision data may be nil, which represents there being no collision in the given time period. I used to have three return values (time of impact, new dx, new dy) where all three would be nil if no collision happened, but then decided to put them in a table to make the possible "nil-ness" explicit.

Appart from these things, are you sure your mathematical model is 'solid' ? I mean, if you are detecting collisions against *segments* ... well, they are very easy to miss, because they are so ... unidimensional. They have tricky properties on their vertices, too. I've never attempted a collision detection system myself, but using solids (as in, 2-D objects) seems like a much less 'tricky' way to do things.

I haven't seen algorithms for testing swept circles against axis-aligned squares directly. All the theory I've seen is treat the target square as four lines and four vertices, filter out the lines and vertices not likely to take part in a collision, and find which object the circle will hit first.

As far as I can tell, the line testing hasn't been giving me any problems. All issues (negative times of impact, etc.) always seem to derive from those pesky corner tests.

Oh, I send you a hug too

P.S. Since it looks like you've browsed my code, have you been able to replicate the bug I was talking about?

[VideroBoy]

If anyone cares, the problem is not negative time values like I thought at first. I actually had an assertion statement to catch this which I forgot about.

Instead, it seems to get stuck in some loop when calculating the slide vector when hitting corners; the circle is already at the wall (collision time of zero) but is somehow jiggling in place.

Code: Select all

// Time, slide vector x, slide vector y
0.035754985720033	3.6691873485476	-0.28337767253879
0.39292656646808	3.6563932470098	0.1168764220075
0.16375731772327	3.6542055491465	-0.04837621768946
0.067901929471502	3.6538304173066	0.020035558309996
0.028130979124569	3.6537660612652	-0.0082988204018282
0.011652594065061	3.6537550197027	0.0034374712010096
0.0048266881671539	3.6537531252756	-0.0014238462801908
0.0019992815239068	3.6537528002435	0.00058977637078279
0.00082812960527906	3.6537527444768	-0.0002442933816113
0.00034302256123967	3.6537527349087	0.00010118963028082
0.00014208440762571	3.6537527332671	-4.1914195265627e-05
5.8854323402909e-05	3.6537527329854	1.736107451575e-05
2.4375154935889e-05	3.6537527329371	-7.1921338614068e-06
1.0095239702078e-05	3.6537527329288	2.9805547467786e-06
4.1945260950642e-06	3.6537527329274	-1.2306628153445e-06
1.7303614401934e-06	3.6537527329271	5.0878256917785e-07
7.5612160363337e-07	3.6537527329271	-1.9334024191515e-07
1.2832337417555e-07	3.6537527329271	1.398056951826e-07
9.5785853645422e-08	3.6537527329271	-9.984530016955e-08
5.6735706596047e-08	3.6537527329271	7.6176029041556e-08
5.007077435508e-08	3.6537527329271	-5.5287270788266e-08
3.435624417236e-08	3.6537527329271	4.0954369011335e-08
4.9652459002072e-08	3.6537527329271	-2.0240123790485e-08
0	3.6537527329271	2.0240123790485e-08
0	3.6537527329271	-2.0240123790485e-08
0	3.6537527329271	2.0240123790485e-08
0	3.6537527329271	-2.0240123790485e-08
0	3.6537527329271	2.0240123790485e-08
0	3.6537527329271	-2.0240123790485e-08
0	3.6537527329271	2.0240123790485e-08
0	3.6537527329271	-2.0240123790485e-08

For reference, here's what the update code looks like:

Code: Select all

local function moveActor(act)
    local frameTime = 1

    local moving = true

    local stoppedByWall = false

    print('start move')

    while moving do
        local cData = collision.actorVSLevel(currentLevel, act,
          frameTime)

        if cData then
            print('\t', cData.time, cData.newDX, cData.newDY)

            assert(cData.time < frameTime)
            assert(cData.time >= 0)

            if cData.time > 0 then
                actor.move(act, cData.time)
                frameTime = frameTime - cData.time
            end

            if frameTime > 0 then
                actor.setVelocity(act, cData.newDX, cData.newDY)
            else
                -- Stopped completely
                stoppedByWall = true
                moving = false
            end
        else
            print('\t', 'done')
            -- No collision
            actor.move(act, frameTime)
            moving = false
        end
    end

    if stoppedByWall and act.ai then
        ai.wallHit(act.ai)
    end
end

I don't know how to handle this generally, so for now I'm just rounding the actor's coordinates when moving like I was before kind of.

Code: Select all

function utility.floor2(n)
    -- Rounds the absolute value of n to the lowest integer
    return math.floor(math.abs(n)) * utility.sign(n)
end

...

function actor.move(act, time)
    local time = time or 1

    act.x = act.x + utility.floor2(act.dx * time)
    act.y = act.y + utility.floor2(act.dy * time)
end

This takes care of the loop, but not the fact that the. Damn. Thing. Still. Lets. The. Circle. Penetrate. Walls. Through. The. Corners. God. Dammit.

[kikito]

Really, if you have reached this point and are hitting a wall, you might want to consider just dumping it.

Writing a collision system isn't supposed to be easy, but it's not supposed to take more than 1 or 2 weeks. If you are stuck, just erase it and try a different way.

Try doing a different algorithm. Perhaps a tile-based one instead of a segment-based one.

The best that can happen is that you implement a simple system that does what you really need in 2 days. The worst, that you spend two days doing a creative thing instead of bashing your head against a wall.

[VideroBoy]

I guess I might as well start over.

I don't know what other algorithms I can use though. Remember that I was trying to implement a continuous collision detection system, where I check for future collisions before moving my objects. This was to avoid things like tunnelling, where collisions are missed for things like bullets because they go fast enough to simply skip over obstacles. I made the player a circle to be able to slide around corners. And I was testing against segments and points because, as far as I can tell, algorithms that test when a circle will hit a square which do not involve treating the square as a bunch of points and lines simply do not exist.

[TechnoCat]

http://www.metanetsoftware.com/technique/tutorialA.html

[VideroBoy]

That article talks about static collision detection (where objects have already moved and you're looking for existing intersections). I'm talking about continuous collision detection.

So, is everyone suggesting that I simply abandon my idea of using continuous collision detection?

(Sorry if I sound harsh)

[kikito]

Just to clarify: I'm not saying that you abandon "Continuous collision detection". I'm saying you abandon your current implementation of it. Just save it on a "failed_collision" file, and start again.

You did not sound harsh; only desesperate - which is completely understandable. I've had my share of algorithms that were either too complicated / long or just plain painful to debug. I've found that the best thing to do is set a time limit: Something "If I'm not able to make any advancement in two days, I scrap it". And I started again. Sometimes I'd try implementing exactly the same thing. Other times I tried doing a slightly different one (I've already mentioned using something other than segments).

When I just re-write the whole thing, I do it incredibly faster than the first time. It's like building a second Ikea armchair; on the first one you had to follow the instructions step by step, while on the second one you already know more or less where all the pieces go. Also, you might end up fixing the error that was lurking on the first implementation (a < instead of a <= in some condition check - that sort of thing).

When I do different things, I normally end up liking the second solution more than the first one.

Independently of whether you go the 'reimplement the same' or 'do a new thing' route, it is also possible that while you are writing you suddently go "Ah! this is what wasn't working before!" and you try that little change on failed_collision and it suddenly works.

In any case, good luck!