0
\$\begingroup\$

I'm making a game (shocker) in pygame and had issues with tile-based collision detection. There are 5 different non-empty tile types (pictured below) which can be rotated in increments of 90 degrees and flipped on both the x and y axis.

The tiles in question

Simply put, adjusting for deltatime was allowing the player to phase through objects they really shouldn't have. So, I developed an algorithm to convert the set of tiles to a map of vectors, which can then be collided with using math--by creating a second vector from the position on the last frame and the position on the current frame, a comparison can be run to see if the two lines collide, right?

Well, yes but actually no. Floating point errors cause collision under certain circumstances to simply not register. For context, I have provided the collision algorithm below:

    def vectorcollide(self,vector,line):
    #calculate the slopes of both lines
    #get offset of function. If it is a vertical line, offset behaves slightly different: it is the x value.
    try:
        moveslope = (vector[0][1]-vector[1][1])/(vector[0][0]-vector[1][0])
        moveoffset = vector[0][1]-moveslope*vector[0][0]
    except ZeroDivisionError:
        moveslope = "cringe"
        moveoffset = vector[0][0]
    try:
        lineslope = (line[0][1]-line[1][1])/(line[0][0]-line[1][0])
        lineoffset = line[0][1]-lineslope*line[0][0]
    except ZeroDivisionError:
        lineslope = "cringe"
        lineoffset = line[0][0]
    text = pygame.font.SysFont("Comic Sans MS", 100)
    state.display.blit(text.render(f"{lineslope}", 0, (255,0,0)),(line[0][0],line[0][1]))
        
    #find point that would lie on both lines if they were infinite
    if lineslope == "cringe":
        if moveslope == "cringe":
            #special contingency if both lines are vertical
            if lineoffset == moveoffset:
                if line[0][1]>=vector[0][1] and line[0][1]<=vector[1][1]:
                    return (lineoffset,line[0][1])
                elif line[1][1]>=vector[0][1] and line[1][1]<=vector[1][1]:
                    return (lineoffset,line[0][1])
                else:
                    return None
            else:
                return None
        else:
            y = lineoffset*moveslope+moveoffset
            point = (lineoffset,y)
            #if point is actually in both lines:
            if (point[1] <= line[0][1] and point[1] >= line[1][1]) or (point[1] >= line[0][1] and point[1] <= line[1][1]):
                if (point[1] <= vector[0][1] and point[1] >= vector[1][1]) or (point[1] >= vector[0][1] and point[1] <= vector[1][1]):
                    if (point[0] <= line[0][0] and point[0] >= line[1][0]) or (point[0] >= line[0][0] and point[0] <= line[1][0]):
                        if (point[0] <= vector[0][0] and point[0] >= vector[1][0]) or (point[0] >= vector[0][0] and point[0] <= vector[1][0]):
                            #return that point
                            return point
            return None

    else:
        if moveslope == "cringe":
            #special contingency for vertical moveslope
            if moveoffset <= line[0][0] and moveoffset >= line [1][0] or moveoffset >= line[0][0] and moveoffset <= line [1][0]:
                y = moveoffset*lineslope+lineoffset
                if (y <= vector[0][1] and y >= vector[1][1]) or (y >= vector[0][1] and y <= vector[1][1]):
                    return (moveoffset,y)
                else:
                    return None
            else:
                return None
        else:
            if moveslope == lineslope:
                #special contingency for two lines with the same slope
                if moveoffset == lineoffset:
                    xtru,ytru = False,False
                    if (line[0][1]>=vector[0][1] and line[0][1]>=vector[1][1])or(line[1][1]>=vector[0][1] and line[1][1]>=vector[1][1]):
                        ytru = True
                    if (line[0][0]>=vector[0][0] and line[0][0]>=vector[1][0])or(line[1][0]>=vector[0][0] and line[1][0]>=vector[1][0]):
                        xtru = True
                    if xtru and ytru:
                        return (vector[1])
                    else:
                        return None
                else:
                    return None
            else:
                x = (lineoffset-moveoffset)/(moveslope-lineslope)
                #contingency plan for horizontal lines
                if lineslope == 0:
                    y = line[0][1]
                else:
                    y = moveslope*x+moveoffset
                point = (x,y)
                #pygame.draw.rect(state.display,(0,255,0), [point[0]-8,point[1]-8,16,16])
                #if point is actually in both lines:
                if (point[1] <= line[0][1] and point[1] >= line[1][1]) or (point[1] >= line[0][1] and point[1] <= line[1][1]):
                    if (point[1] <= vector[0][1] and point[1] >= vector[1][1]) or (point[1] >= vector[0][1] and point[1] <= vector[1][1]):
                        if (point[0] <= line[0][0] and point[0] >= line[1][0]) or (point[0] >= line[0][0] and point[0] <= line[1][0]):
                            if (point[0] <= vector[0][0] and point[0] >= vector[1][0]) or (point[0] >= vector[0][0] and point[0] <= vector[1][0]):
                                #return that point
                                return point
                #by default, return nothing
                return None

Right now, I've sort of made the system limp along by running the old tile-based system after the vector-based one, thus picking up any slack (there are still some buggy collisions, but it's better than nothing(tm)).

Which brings me to my question: How do other people, specifically those in the industry, solve these problems? I've seen suggestions about adding a margin of error to the collisions, but the number of multiplications and divisions at play would likely mean the margin would have to be quite big.

Others in the industry must have ways to beat this--they've been using vectors to collide for years. So, what's the trick?

EDIT: As per @DMGregory's request, I've added some extra context. Also, he's given me some good ground to go off of for this project...but not every game uses a tile system--especially not 3D ones! So, I'm still open to whatever advice people can give me on how such a thing is usually done, which I can use in later endeavors.

\$\endgroup\$
6
  • \$\begingroup\$ If you need to collide a travelling point against a grid of cells that can be fully occupied or empty, have you tried using A Fast Voxel Traversal Algorithm for Ray Tracing? This is a bit like fusing your line-edge collision and tile-based check into a more efficient single pass, ensuring you always get the first collision along the line. It can also be adapted to work for a travelling box or disc rather than just a point. \$\endgroup\$
    – DMGregory
    Commented Oct 4, 2024 at 11:01
  • \$\begingroup\$ @DMGregory If I understand correctly, you are suggesting that I raycast thru the tilegrid, then perform a standard collision check on the tiles that intersect the ray? I had actually thought about this, but didn't implement it because I wasn't sure how to go about it. If this is the suggestion, I'll examine this concept further. \$\endgroup\$
    – Sad Robot
    Commented Oct 4, 2024 at 22:56
  • \$\begingroup\$ Yep, with those 5 tile types, you'd only need to check if the entry/exit point from a tile yoi get from the ray are both on the "above" side of the slope line. If either is not, it's a real collision (hitting the slope if the answers are "yes, no"). \$\endgroup\$
    – DMGregory
    Commented Oct 5, 2024 at 6:34
  • \$\begingroup\$ "How 3D games do collisions" is a different question that should be asked separately, since we try to stick to a one-question-per-post model here. But to help with the curiosity, 3D games usually aren't using point collisions, but larger shapes. Sometimes, using discrete collision detection, a shape will overshoot a collision, but since it has some thickness, we still detect an overlap and can backtrack it to a non-overlapping position. Cases where a shape jumps all the way over an obstacle in a single step are rare, but they happen — search "tunnelling" for Q&A on approaches to mitigate it. \$\endgroup\$
    – DMGregory
    Commented Oct 5, 2024 at 12:31
  • \$\begingroup\$ Please note that using try...catch for testable conditions in games will usually result in slower code than checking for the condition first. I use the try construct for filesystem access. \$\endgroup\$
    – agone
    Commented Oct 9, 2024 at 23:46

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.