DDA algorithm returning incorrect collision data for specific cases

Question

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()

Answer 1

Eventually found a solution, thanks to https://til.zimventures.com/GameMaker/dda

class RayCast:
    def __init__(self, start: tuple[float, float], end: tuple[float, float]):
        self.collision_data = []

        # if the ray is zero length then return
        if start == end:
            return

        x, y = start
        rx, ry = end
        ray_dir = pygame.Vector2(rx - x, ry - y)
        ray_length = ray_dir.length()
        ray_dir.normalize_ip()

        ray_step_size_x = math.sqrt(1 + (ray_dir.y / ray_dir.x) ** 2) if ray_dir.x != 0 else float('inf')
        ray_step_size_y = math.sqrt(1 + (ray_dir.x / ray_dir.y) ** 2) if ray_dir.y != 0 else float('inf')


        map_check_x = math.floor(x)
        map_check_y = math.floor(y)

        if ray_dir.x < 0:
            step_x = -1
            ray_length_x = (x - map_check_x) * ray_step_size_x
        else:
            step_x = 1
            ray_length_x = (map_check_x + 1 - x) * ray_step_size_x

        if ray_dir.y < 0:
            step_y = -1
            ray_length_y = (y - map_check_y) * ray_step_size_y
        else:
            step_y = 1
            ray_length_y = (map_check_y + 1 - y) * ray_step_size_y

        max_distance = ray_length
        current_distance = 0.0

        while current_distance < max_distance:
            if ray_length_x < ray_length_y:
                # ray is hitting a vertical wall
                map_check_x += step_x
                current_distance = ray_length_x
                ray_length_x += ray_step_size_x
                exit_side = 3 if step_x == -1 else 1
                enter_side = 1 if step_x == -1 else 3
            else:
                map_check_y += step_y
                current_distance = ray_length_y
                ray_length_y += ray_step_size_y
                exit_side = 0 if step_y == -1 else 2
                enter_side = 2 if step_y == -1 else 0

            if current_distance > max_distance:
                break

            end_x = x + (ray_dir.x * current_distance)
            end_y = y + (ray_dir.y * current_distance)

            # if there is not a previous collision, set tile exited to the start of the ray
            if len(self.collision_data) == 0:
                exited_tile = (math.floor(x), math.floor(y))
            else:
                exited_tile = self.collision_data[-1].tile_entered


            self.collision_data.append(RayCollisionData(
                (end_x, end_y),
                exited_tile,
                exit_side,
                (map_check_x, map_check_y),
                enter_side,
                )
            )

The majority of the solution was to reduce the need for extra edge cases by improving the actual algorithm.