Как мне объединить эти два алгоритма оптимизации двухмерного преобразования лучей в Python? [дубликат] ⇐ Python

[Anonymous]

Я знаю, что делает каждый алгоритм:
DDA:
"Алгоритм соединения углов": https://www. redblobgames.com/articles/visibility/
Но я не знаю, как использовать алгоритм DDA и алгоритм соединения углов вместе.
Я пытался реализовать алгоритм соединения углов (см. ниже), но он не работает, не знаю почему.
Я нашел скрипт для алгоритма DDA, он работает.
CORNER -АЛГОРИТМ ПРИСОЕДИНЕНИЯ
##############################################################################

import pygame
import math

#######################################

# Links:
# https://www.redblobgames.com/articles/visibility/

#######################################

pygame.init()

X, Y = 800, 800
DISPLAY = pygame.display.set_mode((X, Y))
clock = pygame.time.Clock()
FPS = 60
pygame.display.set_caption("2D Ray Tracing")

white = (255, 255, 255)
black = (0, 0, 0)
red = (255, 0, 0)

##############################################################################

def drawRays(origin, shapesList):
# Corner-Joining Algorithm
#var endpoints # list of endpoints, sorted by angle
#var allWalls # list of all walls the sweep line intersects

#loop over endpoints:
# remember which wall is nearest to the player
# ADD walls that BEGIN at this endpoint
# DELETE walls that END at this endPoint
# figure out which wall is now nearest to the player
# if the nearest wall changed:
# fill the current triangle and begin a new one

endPoints = [] # List of endpoints, sorted by angle
for shape in shapesList:
for point in shape:
# Find the angle from player to point (0 degrees = up)
triangleSides = [abs(origin[0]-point[0]), abs(origin[1]-point[1])]
radius = math.sqrt(triangleSides[0]**2+triangleSides[1]**2)
angle = math.degrees(math.atan2(point[1]-origin[1], point[0]-origin[0])-math.atan2((origin[1]-radius)-origin[1], origin[0]-origin[0]))
if angle < 0: angle += 360
endPoints.append([point, round(angle, 2)])
# Bubble sort the endPoints in ascending angles
for count1 in range(len(endPoints)):
for count2 in range(0, len(endPoints)-count1-1):
if endPoints[count2][1] > endPoints[count2+1][1]:
endPoints[count2], endPoints[count2+1] = endPoints[count2+1], endPoints[count2]

allWalls = [] # List of walls, sorted by distance
for shape in shapesList:
for count in range(len(shape)):
point1 = shape[count]
if count+1 > len(shape)-1: point2 = shape[0]
else: point2 = shape[count+1]
triangleSides = [abs(point1[0]-point2[0]), abs(point1[1]-point2[1])]
middleOfWall = [point2[0]-(triangleSides[0]/2), point2[1]-(triangleSides[1]/2)]
if middleOfWall[1] > Y: middleOfWall[1] -= triangleSides[1]
if middleOfWall[1] < 0: middleOfWall[1] += triangleSides[1]
if middleOfWall[0] > X: middleOfWall[0] -= triangleSides[0]
if middleOfWall[0] < 0: middleOfWall[0] += triangleSides[0]
# Find distance from player -> middleOfWall
triangleSides = [abs(origin[0]-middleOfWall[0]), abs(origin[1]-middleOfWall[1])]
distance = math.sqrt(triangleSides[0]**2+triangleSides[1]**2)
allWalls.append([point1, middleOfWall, point2, distance])
# Bubble sort the walls in ascending distance (from player)
for count1 in range(len(allWalls)):
for count2 in range(0, len(allWalls)-count1-1):
if allWalls[count2][3] > allWalls[count2+1][3]:
allWalls[count2], allWalls[count2+1] = allWalls[count2+1], allWalls[count2]

walls = allWalls.copy()
for point, angle in endPoints:
nearestWall = walls[0]
# ADD walls that BEGIN at this endpoint
for data in allWalls:
if point == data[0]:
if data != walls:
walls.append(data)
else:
break
# Remove duplicate walls
noDuplicates = []
for wall in walls:
if wall not in noDuplicates:
noDuplicates.append(wall)
walls = noDuplicates.copy()
# DELETE walls that END at this endpoint
count = 0
while count < len(walls):
if point == walls[count][2]:
del(walls[count])
count += 1
# Bubble sort the walls in ascending distance (from player)
for count1 in range(len(walls)):
for count2 in range(0, len(walls)-count1-1):
if walls[count2][3] > walls[count2+1][3]:
walls[count2], walls[count2+1] = walls[count2+1], walls[count2]
if walls[0] != nearestWall: # Fill the current triangle (point1, point2, origin) and begin a new one
for data in allWalls:
if point == data[0]:
point1 = data[0]
point2 = data[2]
break
pygame.draw.polygon(DISPLAY, red, [point1, point2, origin])

#######################################

def renderPlayer(playerXY):
pygame.draw.circle(DISPLAY, white, playerXY, radius=10)

#######################################

def renderObjects(shapesList):
for shape in shapesList:
pygame.draw.polygon(DISPLAY, white, shape, width=5)

##############################################################################

playerXY = [400, 400]

shapesList = [
[(20, 20), (X-20, 20), (X-20, Y-20), (20, Y-20)], # Outer boundary
# Obstacles
[(100, 50), (150, 50), (150, 100), (100, 100)],
]

#######################################

while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
exit()
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_q:
pygame.quit()
exit()

heldKeys = pygame.key.get_pressed()
if heldKeys[pygame.K_w] is True:
playerXY[1] -= 5
if heldKeys[pygame.K_a] is True:
playerXY[0] -= 5
if heldKeys[pygame.K_s] is True:
playerXY[1] += 5
if heldKeys[pygame.K_d] is True:
playerXY[0] += 5

DISPLAY.fill(black)
drawRays(playerXY, shapesList)
renderObjects(shapesList)
renderPlayer(playerXY)

pygame.display.update()
clock.tick(FPS)

##############################################################################

АЛГОРИТМ DDA
import pygame
import math

# Initialize Pygame
pygame.init()

def DDA(targetX, targetY):

mouse_cell_x = targetX / cell_size
mouse_cell_y = targetY / cell_size

# DDA Algorithm
ray_start_x, ray_start_y = player_x, player_y
ray_dir_x = (mouse_cell_x - player_x)
ray_dir_y = (mouse_cell_y - player_y)
ray_dir_len = math.sqrt(ray_dir_x ** 2 + ray_dir_y ** 2)
if ray_dir_len != 0:
ray_dir_x /= ray_dir_len
ray_dir_y /= ray_dir_len

ray_unit_step_x = math.sqrt(1 + (ray_dir_y / ray_dir_x) ** 2) if ray_dir_x != 0 else float('inf')
ray_unit_step_y = math.sqrt(1 + (ray_dir_x / ray_dir_y) ** 2) if ray_dir_y != 0 else float('inf')

map_check_x, map_check_y = int(ray_start_x), int(ray_start_y)
ray_length_x, ray_length_y = 0, 0
step_x, step_y = 0, 0

if ray_dir_x < 0:
step_x = -1
ray_length_x = (ray_start_x - map_check_x) * ray_unit_step_x
else:
step_x = 1
ray_length_x = (map_check_x + 1 - ray_start_x) * ray_unit_step_x

if ray_dir_y < 0:
step_y = -1
ray_length_y = (ray_start_y - map_check_y) * ray_unit_step_y
else:
step_y = 1
ray_length_y = (map_check_y + 1 - ray_start_y) * ray_unit_step_y

tile_found = False
max_distance = 100.0
distance = 0.0

while not tile_found and distance < max_distance:
if ray_length_x < ray_length_y:
map_check_x += step_x
distance = ray_length_x
ray_length_x += ray_unit_step_x
else:
map_check_y += step_y
distance = ray_length_y
ray_length_y += ray_unit_step_y

if 0

Подробнее здесь: https://stackoverflow.com/questions/792 ... er-in-pyth