DDA瓦片碰撞检测算法在特定边界场景下返回错误碰撞数据的问题排查求助

我现在遇到个头疼的问题：用DDA算法做基于瓦片的碰撞检测，目的是防止高速物体穿透碰撞体，但我写的算法在某些特定的边界场景下会返回完全无效的结果。这里需要说明的是，我的DDA算法是支持浮点坐标的。

下面是几个典型的错误案例：

案例1：垂直方向沿瓦片边界移动 #

比如一条从(1.0, 1.0)垂直向上到(1.0, 2.0)的DDA线，算法返回了错误结果：

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

而正确的结果应该是这样的：

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

（直观来看，这条线明明是从(1,1)瓦片的顶部出去，应该进入正上方的(1,2)瓦片，但算法却错误指向了(0,0)）

案例2：增大移动距离后错误依旧 #

即使把移动距离拉大，结果还是不对。比如从(1,1.0)水平向右移动到更远位置时，算法返回：

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

（本来应该是从(1,1)右侧出去进入(2,1)，结果算法却指向了(1,0)，完全偏离方向）

案例3：对角线移动的部分错误 #

从(2, 2)到(3, 3)的对角线移动，算法虽然返回了经过的2个瓦片，但结果对应的是(2,2)附近的瓦片，而不是预期的(3,3)方向：

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

（这条线是向右上方走，本该进入(3,3)附近的瓦片，但算法却停留在(2,2)）

正常场景表现 #

需要说明的是，当射线不在瓦片边界上，只是穿过瓦片边缘时，算法工作是正常的，只有在刚好沿瓦片边界移动时才会出问题。

问题代码 #

我的RayCast类代码如下：

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

可视化测试工具 #

为了更直观地看问题，我还做了一个基于Pygame的可视化测试工具，代码如下：

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)

备注：内容来源于stack exchange，提问作者Ico Twilight