DDA算法在起点坐标大于终点时的实现异常求助

问题描述 #

我正在实现DDA算法，用来确定2D网格中两点之间的所有单元格，给瓦片游戏做射线投射功能。当前代码在起点坐标小于终点坐标时运行正常，但添加方向修正（X/Y值需要减小时用-1作为增量系数）适配全方向后，反向场景下输出不符合预期。

原始代码 #

import math
import pygame

screen_width = 800
screen_height = 800
screen = pygame.display.set_mode([screen_width, screen_height])
clock = pygame.time.Clock()
done = False

matrix = []

tile_size = 20
w = 38
h = 38

for _ in range(w):
    sub = []
    for _ in range(h):
        sub.append(0)
    matrix.append(sub)

startx = 2
starty = 7
endx = 1
endy = 1

currentx = startx
currenty = starty

dx = endx - startx
dy = endy - starty

if startx > endx:
    x_direction = -1
else:
    x_direction = 1

if starty > endy:
    y_direction = -1
else:
    y_direction = 1    

Sx = math.sqrt(1**2 + (dy/dx)**2)
Sy = math.sqrt(1**2 + (dx/dy)**2)

x_incrementer = 1
y_incrementer = 1

coords_list = []
coords_list.append([startx, starty])


while (currentx != endx) and (currenty != endy):

    if (Sx * x_incrementer) <= (Sy * y_incrementer):
        x_incrementer += 1
        currentx += 1 * x_direction
        coords_list.append([currentx, currenty])
    
    elif (Sx * x_incrementer) > (Sy * y_incrementer):
        y_incrementer += 1
        currenty += 1 * y_direction
        coords_list.append([currentx, currenty])
    
for coord in coords_list:
    matrix[coord[1]][coord[0]] = 1

print("Start: X:",startx, "Y:", starty)
print("End: X:",endx, "Y:", endy)
print("Coordinates:", coords_list)

while not done:

    mouse_x, mouse_y = pygame.mouse.get_pos()
    screen.fill([255,255,255])

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            done = True

    y_counter = 0
    for y in matrix:
        x_counter = 0
        for x in y:

            if x == 1:
                pygame.draw.rect(screen, [0,162,232], ((x_counter*tile_size)+tile_size, (y_counter*tile_size)+tile_size, tile_size, tile_size))
            pygame.draw.rect(screen, [0,0,0], ((x_counter*tile_size)+tile_size, (y_counter*tile_size)+tile_size, tile_size, tile_size), 1)

            x_counter +=1
        y_counter +=1
    
    pygame.draw.line(screen, [255,0,0], [(startx*tile_size)+tile_size, (starty*tile_size)+tile_size], [(endx*tile_size)+tile_size, (endy*tile_size)+tile_size], 3)

    clock.tick(60) 
    pygame.display.flip()

效果对比 #

• 正常工作场景（起点x/y: 1,1 | 终点x/y: 2,7）
  

• 异常场景（起点x/y: 2,7 | 终点x/y:1,1）
  

问题分析与修复 #

核心问题 #

1. 步长计算错误：Sx和Sy的计算没有使用绝对值，当dx或dy为负数时，比例值的符号会导致步长计算偏差，影响单元格选择逻辑。
2. 循环条件限制过严：原循环while (currentx != endx) and (currenty != endy)会在其中一个坐标到达终点时直接停止，漏处理剩余方向的单元格。
3. 未处理零差情况：当dx或dy为0（水平/垂直射线）时，会触发除以0错误。

修复后的代码 #

import math
import pygame

screen_width = 800
screen_height = 800
screen = pygame.display.set_mode([screen_width, screen_height])
clock = pygame.time.Clock()
done = False

matrix = []

tile_size = 20
w = 38
h = 38

for _ in range(w):
    sub = []
    for _ in range(h):
        sub.append(0)
    matrix.append(sub)

startx = 2
starty = 7
endx = 1
endy = 1

currentx = startx
currenty = starty

dx = endx - startx
dy = endy - starty

# 确定方向系数
x_direction = -1 if startx > endx else 1
y_direction = -1 if starty > endy else 1    

# 计算步长，使用绝对值避免符号影响，处理dx/dy为0的情况
if dx != 0:
    Sx = math.sqrt(1**2 + (abs(dy/dx))**2)
else:
    Sx = float('inf')  # 垂直射线，x方向步长无穷大

if dy != 0:
    Sy = math.sqrt(1**2 + (abs(dx/dy))**2)
else:
    Sy = float('inf')  # 水平射线，y方向步长无穷大

x_incrementer = 1
y_incrementer = 1

coords_list = []
coords_list.append([startx, starty])

# 修改循环条件：只要有一个坐标未到达终点就继续
while currentx != endx or currenty != endy:
    # 优先处理已到达终点的方向，避免无效判断
    if currentx == endx:
        y_incrementer += 1
        currenty += 1 * y_direction
        coords_list.append([currentx, currenty])
        continue
    if currenty == endy:
        x_incrementer += 1
        currentx += 1 * x_direction
        coords_list.append([currentx, currenty])
        continue

    # 正常判断步长，选择下一个单元格
    if (Sx * x_incrementer) <= (Sy * y_incrementer):
        x_incrementer += 1
        currentx += 1 * x_direction
        coords_list.append([currentx, currenty])
    else:
        y_incrementer += 1
        currenty += 1 * y_direction
        coords_list.append([currentx, currenty])
    
for coord in coords_list:
    matrix[coord[1]][coord[0]] = 1

print("Start: X:",startx, "Y:", starty)
print("End: X:",endx, "Y:", endy)
print("Coordinates:", coords_list)

while not done:
    mouse_x, mouse_y = pygame.mouse.get_pos()
    screen.fill([255,255,255])

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            done = True

    y_counter = 0
    for y in matrix:
        x_counter = 0
        for x in y:
            if x == 1:
                pygame.draw.rect(screen, [0,162,232], ((x_counter*tile_size)+tile_size, (y_counter*tile_size)+tile_size, tile_size, tile_size))
            pygame.draw.rect(screen, [0,0,0], ((x_counter*tile_size)+tile_size, (y_counter*tile_size)+tile_size, tile_size, tile_size), 1)
            x_counter +=1
        y_counter +=1
    
    pygame.draw.line(screen, [255,0,0], [(startx*tile_size)+tile_size, (starty*tile_size)+tile_size], [(endx*tile_size)+tile_size, (endy*tile_size)+tile_size], 3)

    clock.tick(60) 
    pygame.display.flip()

修复说明 #

1. 步长计算使用abs()确保比例为正数，避免方向符号干扰步长判断；同时处理dx/dy为0的情况，防止除以0错误。
2. 循环条件改为currentx != endx or currenty != endy，确保所有路径上的单元格都被遍历。
3. 增加方向终点判断，当某一方向已到达终点时，直接处理另一方向，避免无效的步长比较。

内容的提问来源于stack exchange，提问作者Zoler1337