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.
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.
try...catch
for testable conditions in games will usually result in slower code than checking for the condition first. I use thetry
construct for filesystem access. \$\endgroup\$