TAGS :Viewed: 9 - Published at: a few seconds ago

[ Abstract Collision Detection ]

I've been struggling conceptually with how to implement simple square collision detection within a game I am writing while avoiding Pygame; I want to learn how to do it without cheating. The structure of the program as intended looks is this: The game loads a text file containing a level. Each level consists of 25 rows of 25 digits (for a total of 625 digits). It is extracted into a 2D array to emulate a cartesian grid which will correspond with the screen. From there the program draws a 32x32 block at the proper place on the screen. For example, if the digit at location [2][5] is a 1, it will draw a white square at pixel coordinate (96,192) (the counting of the squares starts at zero since it is an array). It also generates a collision array consisting of True or False for each location corresponding to the original array.

I have a player object that moves freely along the grid, not confined to the 32x32 squares. My question is this: how would I implement square collision detection? I've tried a number of methods but I'm not quite sure where I'm getting stuck. I'll post my latest incarnation and the relevant code below.

Collision code:

def checkPlayerEnvCollision(self,player):
    p = player
    c = self.cLayer #this is the collision grid generated when loading the level
    for row in range(25):
        for col in range (25):
            print("checkEnvCollision")
            if c[row][col] != False:
                tileleftx = row*32
                tilerightx = tileleftx + 32
                tilelefty = col*32
                tilerighty = tilelefty+32
                if (abs(tileleftx - p.x) * 2 < (tilerightx + (p.x + 32))) and (abs(tilelefty - p.y) * 2 < (tilerighty + (p.y + 32))):
                    print("OH NO, COLLISION")

The code that loads the tiles from the text file into the array:

def loadLevel(self, level):
    print("Loading Level")
    levelFile = open(level)
    count=0
    for line in levelFile:
        tempArray = []
        if line.startswith("|"):
            dirs = line.split('|')
            self.north = dirs[1]
            self.south = dirs[2]
            self.east = dirs[3]
            self.west = dirs[4]
            continue

        for item in line:
            if item in self.tileValues:
                tempArray.append(int(item))
        self.tileLayer[count] = tempArray
        count+=1
    for items in self.tileLayer:
        if len(items) > 25:
            print("Error: Loaded Level Too Large")

    count = 0
    for line in self.tileLayer:
        tempArray = []
        for item in line:
            if self.tilePassableValues[item] == False:
                tempArray.append(False)
            else:
                tempArray.append(True)
        self.collisionLayer[count] = tempArray
        count += 1

Not sure if this is useful, but here is a simple demonstration of the drawing method:

def levelTiles(self, level):
    row = 0
    for t in level:
        col = 0
        for r in t:
            color = "white"
            if r == 0:
                col+=1
                continue
            elif r == 1:
                color = "red"
            elif r == 2:
                color = "white"
            elif r == 3:
                color = "green"
            self.Canvas.create_rectangle(row*32, col*32, row*32+32, col*32+32, fill=color, width=1,tags='block')
            col += 1
        row += 1

Lastly, here is the text file I have been testing it with:

1111111111111111111111111
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1222233332222222222222221
1222233332222222222222221
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1222222222233332222222221
1222222222333332332222221
1222222222222222332222221
1222222222222222332222221
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1222222222222222222222221
1111111111111111111111111
|onescreen2|onescreen2|onescreen2|onescreen2

(The last line is what will load the map to the north, south, east and west when reaching the edge of the level; you can ignore it.)

Thanks for the help. It's a lot to ask, but I'm stuck on this one!

Answer 1


If the player is tied to the grid, why not just test the grid positions:

if grid[player.x][player.y] == some_collidable_thing:
    # there was a collision

If not,
I also provided an answer to something almost identical in This question

def check_col(self, rect):
    for row in self.cLayer:
        for column in row:
            grid_position = (row*element_size, column*element_width)
            collide_x = False
            collide_y = False

            # check x axis for collision
            if self.rect.x + self.rect.w > grid_position[0]:
                collide_x = True
            elif self.rect.x < grid_position[0] + element_width:
                collide_x = True

            # check y axis for collision
            if self.rect.y < grid_position[1] + element_height:
                collide_y = True
            elif self.rect.y + self.rect.h > grid_position[1]:
                collide_y = True

            # act on a collision on both axis
            if collide_x and collide_y:
                # act on the collision
                return True
            else:
                # act on no collision
                return False

Answer 2


An easier way to do this would be to define vectors for the player's movement, and lines for the boundaries of the objects. Then you check to see if the vector collides with any line (there should not be many lines to check) as follows (I'm assuming that the player/object can be on the boundary of the other object):

Take the determinant of the triangle formed by the movement vector and endpoint of the line you're checking for a collision, and take its area via determinant. Compare its area to the area of the triangle formed with the other endpoint. If they are both positive/negative, then there is no intersection. If their signs are different, then there MIGHT be an intersection.

If their signs are different, do the same thing as above, except using the endpoints of the movement vector instead of the endpoints of the line. (And using the whole line instead of the movement vector).

If their signs are different, then there is definitely an intersection, and if they are the same, then there is no intersection.

I hope this helps (and just comment if it does not make sense).