[Python] DDA algorithm returning incorrect collision data for specific cases

I'm using my DDA algorithm for tile based collision detection so that high speed objects don't clip through collisions. The issue is the DDA algorithm I've written is returning invalid responses in specific cases.

The DDA algorithm can have floating point coordinates!

For example a DDA line going from (1.0, 1.0) -> (1.0, 2.0) incorrectly returns the result:



Collision Position: (1.0, 1)
Tile Exited: (1, 1)
Tile Exited Side: 2
Tile Entered: (0, 0)
Tile Entered Side: 0


which should be:

Collision Position: (1.0, 1)
Tile Exited: (1, 1)
Tile Exited Side: 2
Tile Entered: (1, 2)
Tile Entered Side: 0


This seems to happen in each direction.

Even when I increase the distance I still get incorrect results



Collision Position: (1, 1.0)
Tile Exited: (1, 1)
Tile Exited Side: 1

Tile Entered: (0, 0)
Tile Entered Side: 3

Collision Position: (2, 1.0)
Tile Exited: (2, 1)
Tile Exited Side: 1

Tile Entered: (1, 0)
Tile Entered Side: 3


Going from (2, 2) -> (3, 3) partly works as expected and returns the 2 tiles it passes through, however it should be the tiles near (3, 3) not (2, 2)



Collision Position: (2.0, 2)
Tile Exited: (1, 1)
Tile Exited Side: 2
Tile Entered: (2, 2)
Tile Entered Side: 0

Collision Position: (2, 2.0)
Tile Exited: (1, 1)
Tile Exited Side: 1
Tile Entered: (2, 2)
Tile Entered Side: 3


note that the algorithm works as expected when not on tile boundaries and just passing through edges



the code is as follows:

class RayCast:
def __init__(self, point1, point2):
self.point1 = point1
self.point2 = point2
self.collision_data = []

self.dx = point2[0] - point1[0]
self.dy = point2[1] - point1[1]

if self.dx == 0 and self.dy == 0:
return

self.x_step = 1 if self.dx > 0 else -1
self.y_step = 1 if self.dy > 0 else -1

self.next_vertical = ceil(point1[0]) if self.dx > 0 else floor(point1[0])
self.next_horizontal = ceil(point1[1]) if self.dy > 0 else floor(point1[1])

self.t_max_x = (self.next_vertical - point1[0]) / self.dx if self.dx != 0 else float('inf')
self.t_max_y = (self.next_horizontal - point1[1]) / self.dy if self.dy != 0 else float('inf')
self.t_delta_x = abs(1 / self.dx) if self.dx != 0 else float('inf')
self.t_delta_y = abs(1 / self.dy) if self.dy != 0 else float('inf')

self.x, self.y = point1

while (self.x_step > 0 and self.x < point2[0]) or (self.x_step < 0 and self.x > point2[0]) or (
self.y_step > 0 and self.y < point2[1]) or (self.y_step < 0 and self.y > point2[1]):
if self.t_max_x < self.t_max_y:
self.x = self.next_vertical
self.y = point1[1] + self.t_max_x * self.dy
self.t_max_x += self.t_delta_x
self.next_vertical += self.x_step
tile_exited_side = 3 if self.x_step < 0 else 1 # Left = 3, Right = 1
else:
self.y = self.next_horizontal
self.x = point1[0] + self.t_max_y * self.dx
self.t_max_y += self.t_delta_y
self.next_horizontal += self.y_step
tile_exited_side = 0 if self.y_step < 0 else 2 # Up = 0, Down = 2

collision_x, collision_y = round(self.x, 10), round(self.y, 10) # Avoid floating point precision issues

if collision_x == int(collision_x) and collision_y == int(collision_y): # Corner case
if self.dx > 0 and self.dy > 0:
tile_exited = (int(collision_x) - 1, int(collision_y) - 1)
tile_entered = (tile_exited[0] + 1, tile_exited[1] + 1)
elif self.dx < 0 and self.dy > 0:
tile_exited = (int(collision_x), int(collision_y) - 1)
tile_entered = (tile_exited[0] - 1, tile_exited[1] + 1)
elif self.dx > 0 and self.dy < 0:
tile_exited = (int(collision_x) - 1, int(collision_y))
tile_entered = (tile_exited[0] + 1, tile_exited[1] - 1)
else:
tile_exited = (int(collision_x), int(collision_y))
tile_entered = (tile_exited[0] - 1, tile_exited[1] - 1)

elif collision_x == int(collision_x): # Hit a vertical grid line
tile_exited = (int(collision_x) - (1 if self.dx > 0 else 0), int(floor(self.y)))
tile_entered = (tile_exited[0] + (1 if self.dx > 0 else -1), tile_exited[1])
else: # Hit a horizontal grid line
tile_exited = (int(floor(self.x)), int(collision_y) - (1 if self.dy > 0 else 0))
tile_entered = (tile_exited[0], tile_exited[1] + (1 if self.dy > 0 else -1))

tile_entered_side = (tile_exited_side + 2) % 4 # Opposite side

collision_data = RayCollisionData(
collision_position=(self.x, self.y),
tile_exited=tile_exited,
tile_exited_side=tile_exited_side,
tile_entered=tile_entered,
tile_entered_side=tile_entered_side
)
self.collision_data.append(collision_data)

# get rid of the last collision data as it is redundant
self.collision_data.pop()


I also built a visualizer to better see the bugs in action if you want to run it yourself:

class Editor:
def __init__(self, screen: pygame.Surface, data):
self.original_screen_size = screen.get_size()
# resize the screen to 800x600
self.screen = pygame.display.set_mode((800, 600), pygame.RESIZABLE) # TODO there may be a bug here
self.data = data
self.running = True
self.manager = pygame_gui.UIManager((800, 600))
self.clock = pygame.time.Clock()
self.time_delta = 0.0
self.top_panel = pygame_gui.elements.UIPanel(relative_rect=pygame.Rect((0, 0), (800, 50)),
manager=self.manager,
anchors={"top": "top", "left": "left", "right": "right"})
self._right_panel_ui = pygame_gui.elements.UIPanel(relative_rect=pygame.Rect((600, 50), (200, 550)),
manager=self.manager,
anchors={"top": "top", "bottom": "bottom"})
self.right_panel = pygame_gui.elements.UIScrollingContainer(relative_rect=pygame.Rect((0, 0), (200, 550)),
manager=self.manager,
container=self._right_panel_ui)
self.display_surface = pygame.Surface((600, 550))
self.display_surface.fill((255, 255, 255))

def run_editor(self):
while self.running:
self.time_delta = self.clock.tick(60) / 1000.0
self.input()
self.manager.update(self.time_delta)
self.update()
self.screen.fill((0, 0, 0))
self.draw()
self.screen.blit(self.display_surface, (0, 50))
self.manager.draw_ui(self.screen)
pygame.display.flip()
return self.data

def process_event(self, event: pygame.event.Event):
pass

def input(self):
for event in pygame.event.get():
if event.type == pygame.QUIT:
self.running = False

if event.type == pygame.VIDEORESIZE:
new_size = (event.w, event.h)
print(f"new_size = {new_size}")
self.screen = pygame.display.set_mode(new_size, pygame.RESIZABLE)
self.manager.set_window_resolution(new_size) # Update UI manager
# resize the display surface
self.display_surface = pygame.Surface((new_size[0] - 200, new_size[1] - 50))
self.display_surface.fill((255, 255, 255))
# move the right panel (ui) to the right side of the screen
self._right_panel_ui.relative_rect = pygame.Rect((new_size[0] - 200, 50), (200, new_size[1] - 50))

self.process_event(event)

self.manager.process_events(event)

def update(self):
pass

def draw(self):
pass

class UIRaycastTester(Editor):
def __init__(self, screen: pygame.Surface):
super().__init__(screen, None)
self.x1 = 0
self.y1 = 0
self.x2 = 10
self.y2 = 10
self.tile_size = 32

# add an input for the x and y values
self.x1_input = pygame_gui.elements.UITextEntryLine(relative_rect=pygame.Rect((10, 10), (100, 30)),
manager=self.manager)
self.y1_input = pygame_gui.elements.UITextEntryLine(relative_rect=pygame.Rect((120, 10), (100, 30)),
manager=self.manager)
self.x2_input = pygame_gui.elements.UITextEntryLine(relative_rect=pygame.Rect((230, 10), (100, 30)),
manager=self.manager)
self.y2_input = pygame_gui.elements.UITextEntryLine(relative_rect=pygame.Rect((340, 10), (100, 30)),
manager=self.manager)

# add a scrollable text output for the DDA algorithm to report to
self.text_output = pygame_gui.elements.UITextBox(relative_rect=pygame.Rect((0, 0), (200, 580)),
manager=self.manager,
container=self.right_panel,
html_text="", wrap_to_height=True)


def process_event(self, event: pygame.event.Event):
if event.type == pygame.MOUSEBUTTONDOWN:
# check if the mouse is on the display or not?
if event.pos[1] < 50 or event.pos[0] > 600:
return
if event.button == 1:
# scale the mouse position to the grid
x, y = pygame.mouse.get_pos()
self.x1 = (x / self.tile_size)
self.y1 = ((y - 50) / self.tile_size)
# update the input
self.x1_input.set_text(str(self.x1))
self.y1_input.set_text(str(self.y1))
elif event.button == 3:
x, y = pygame.mouse.get_pos()
self.x2 = (x / self.tile_size)
self.y2 = ((y - 50) / self.tile_size)
# update the input
self.x2_input.set_text(str(self.x2))
self.y2_input.set_text(str(self.y2))
elif event.type == pygame.USEREVENT:
if event.user_type == pygame_gui.UI_TEXT_ENTRY_FINISHED:
try:
if event.ui_element == self.x1_input:
self.x1 = float(self.x1_input.get_text())
elif event.ui_element == self.y1_input:
self.y1 = float(self.y1_input.get_text())
elif event.ui_element == self.x2_input:
self.x2 = float(self.x2_input.get_text())
elif event.ui_element == self.y2_input:
self.y2 = float(self.y2_input.get_text())
except:
# if the input is not a number, set it to 0
if event.ui_element == self.x1_input:
self.x1_input.set_text("0")
elif event.ui_element == self.y1_input:
self.y1_input.set_text("0")
elif event.ui_element == self.x2_input:
self.x2_input.set_text("0")
elif event.ui_element == self.y2_input:
self.y2_input.set_text("0")

def update(self):
pass

def draw(self):
self.display_surface.fill((255, 255, 255))
# draw the grid lines
for x in range(0, self.display_surface.get_width(), self.tile_size):
pygame.draw.line(self.display_surface, (0, 0, 0), (x, 0), (x, self.display_surface.get_height()), 1)
for y in range(0, self.display_surface.get_height(), self.tile_size):
pygame.draw.line(self.display_surface, (0, 0, 0), (0, y), (self.display_surface.get_width(), y), 1)

pygame.draw.line(self.display_surface, (255, 0, 0),
(self.x1 * self.tile_size, self.y1 * self.tile_size), (self.x2 * self.tile_size, self.y2 * self.tile_size), 1)

# draw an arrow head at the end of the line
angle = 0.5 # Arrowhead angle
arrow_length = 10 # Arrow size

# Get the line vector
dx = (self.x2 - self.x1) * self.tile_size
dy = (self.y2 - self.y1) * self.tile_size

# Find the endpoint in pixel coordinates
end_x = self.x1 * self.tile_size + dx
end_y = self.y1 * self.tile_size + dy

# Compute angles for arrowhead
line_angle = atan2(dy, dx)
angle1 = line_angle - angle
angle2 = line_angle + angle

# Compute arrowhead points
x1 = end_x - arrow_length * cos(angle1)
y1 = end_y - arrow_length * sin(angle1)
x2 = end_x - arrow_length * cos(angle2)
y2 = end_y - arrow_length * sin(angle2)

# Draw arrowhead at the correct end
pygame.draw.line(self.display_surface, (255, 0, 0), (end_x, end_y), (x1, y1), 1)
pygame.draw.line(self.display_surface, (255, 0, 0), (end_x, end_y), (x2, y2), 1)

# clear the text output
self.text_output.html_text = ""

ray_cast = RayCast((self.x1, self.y1), (self.x2, self.y2))
for collision_data in ray_cast.collision_data:
x, y = collision_data.collision_position
# scale the collision position to the grid
x = x * self.tile_size
y = y * self.tile_size
x = round(x)
y = round(y)
color = (0, 255, 0) if collision_data.tile_exited_side % 2 == 0 else (0, 0, 255)
pygame.draw.circle(self.display_surface, color, (x, y), 3)
# draw a square around the tiles
x, y = collision_data.tile_exited
x = x * self.tile_size
y = y * self.tile_size
x = floor(x)
y = floor(y)
pygame.draw.rect(self.display_surface, color, (x, y, self.tile_size, self.tile_size), 1)
x, y = collision_data.tile_entered
x = x * self.tile_size
y = y * self.tile_size
x = floor(x)
y = floor(y)
pygame.draw.rect(self.display_surface, color, (x, y, self.tile_size, self.tile_size), 1)

# report the collision data to the output
self.text_output.html_text += f"Collision Position: {collision_data.collision_position}<br>"
self.text_output.html_text += f"Tile Exited: {collision_data.tile_exited}<br>"
self.text_output.html_text += f"Tile Exited Side: {collision_data.tile_exited_side}<br>"
self.text_output.html_text += f"Tile Entered: {collision_data.tile_entered}<br>"
self.text_output.html_text += f"Tile Entered Side: {collision_data.tile_entered_side}<br>"
self.text_output.html_text += "<br>"
self.text_output.html_text += "<br>"
# update the scroll bar
self.text_output.rebuild()

Continue reading...