```"""
Path-related functions.

"""
from shapely import speedups  # type: ignore
from shapely.geometry import LineString, Polygon  # type: ignore

from arcade import Point, check_for_collision_with_list, SpriteList, Sprite
from typing import Union, List, Tuple, Set

speedups.enable()

[docs]def has_line_of_sight(point_1: Point,
point_2: Point,
walls: SpriteList,
max_distance: int = -1) -> bool:
"""
Determine if we have line of sight between two points. Having a line of
sight means, that you can connect both points with straight line without
intersecting any obstacle.
Thanks to the shapely efficiency and speedups boost, this function is very
fast. It can easily test 10 000 lines_of_sight.

:param point_1: tuple -- coordinates of first position (x, y)
:param point_2: tuple -- coordinates of second position (x, y)
:param walls: list -- Obstacle objects to check against
:param max_distance: int --
:return: tuple -- (bool, list)
"""
line_of_sight = LineString([point_1, point_2])
if 0 < max_distance < line_of_sight.length:
return False
if not walls:
return True
return not any((Polygon(o.get_adjusted_hit_box()).crosses(line_of_sight) for o in walls))

"""
Classic A-star algorithm for path finding.
"""

def _spot_is_blocked(position: Union[Tuple[float, float], List[float]],
moving_sprite: Sprite,
blocking_sprites: SpriteList)\
-> bool:
original_pos = moving_sprite.position
moving_sprite.position = position
hit_list = check_for_collision_with_list(moving_sprite, blocking_sprites)
moving_sprite.position = original_pos
if len(hit_list) > 0:
return True
else:
return False

def _heuristic(start: Point, goal: Point):
"""

Args:
start:
goal:

Returns:

"""
# Use Chebyshev distance heuristic if we can move one square either
d = 1
d2 = 1
dx = abs(start[0] - goal[0])
dy = abs(start[1] - goal[1])
return d * (dx + dy) + (d2 - 2 * d) * min(dx, dy)

class _AStarGraph(object):
# Define a class board like grid with two barriers

def __init__(self, barriers: Union[List, Tuple, Set],
left: int,
right: int,
bottom: int,
top: int,
diagonal_movement: bool):
if barriers is set:
self.barriers = barriers
else:
self.barriers = set(barriers)

self.left = left
self.right = right
self.top = top
self.bottom = bottom

if diagonal_movement:
self.movement_directions = (  # type: ignore
(1, 0), (-1, 0),
(0, 1), (0, -1),
(1, 1), (-1, 1),
(1, -1), (-1, -1)
)
else:
self.movement_directions = (1, 0), (-1, 0), (0, 1), (0, -1)  # type: ignore

def get_vertex_neighbours(self, pos: Point) -> List[Tuple[float, float]]:
n = []
# Moves allow link a chess king
for dx, dy in self.movement_directions:
x2 = pos[0] + dx
y2 = pos[1] + dy
if x2 < self.left or x2 > self.right or y2 < self.bottom or y2 > self.top:
continue
n.append((x2, y2))
return n

def move_cost(self, a: Point, b: Point):
if b in self.barriers:
# print("Ping")
return float('inf')  # Infitely high cost to enter barrier squares

elif a[0] == b[0] or a[1] == b[1]:
return 1  # Normal movement cost
else:
return 1.42

def _AStarSearch(start: Point, end: Point, graph: _AStarGraph):
G = {}  # Actual movement cost to each position from the start position
F = {}  # Estimated movement cost of start to end going via this position

# Initialize starting values
G[start] = 0
F[start] = _heuristic(start, end)

closed_vertices = set()
open_vertices = {start}
came_from = {}  # type: ignore

count = 0
while len(open_vertices) > 0:
count += 1
if count > 500:
break
# Get the vertex in the open list with the lowest F score
current = None
current_fscore = None
for pos in sorted(open_vertices):
if current is None or F[pos] < current_fscore:
current_fscore = F[pos]
current = pos

# Check if we have reached the goal
if current == end:
# Retrace our route backward
path = [current]
while current in came_from:
current = came_from[current]
path.append(current)  # type: ignore
path.reverse()
if F[end] >= 10000:
return None
else:
return path
# return path, F[end]  # Done!

# Mark the current vertex as closed
open_vertices.remove(current)  # type: ignore

# Update scores for vertices near the current position
for neighbour in sorted(graph.get_vertex_neighbours(current)):  # type: ignore
if neighbour in closed_vertices:
continue  # We have already processed this node exhaustively
candidate_g = G[current] + graph.move_cost(current, neighbour)  # type: ignore

if neighbour not in open_vertices:
open_vertices.add(neighbour)  # Discovered a new vertex
elif candidate_g >= G[neighbour]:
continue  # This G score is worse than previously found

came_from[neighbour] = current
G[neighbour] = candidate_g
h = _heuristic(neighbour, end)
F[neighbour] = G[neighbour] + h

# Out-of-bounds
return None

def _collapse(pos: Point, grid_size: float):
return int(pos[0] // grid_size), int(pos[1] // grid_size)

def _expand(pos: Point, grid_size: float):
return int(pos[0] * grid_size), int(pos[1] * grid_size)

[docs]class AStarBarrierList:
"""
Class that manages a list of barriers that can be encountered during
A* path finding.

:param Sprite moving_sprite: Sprite that will be moving
:param SpriteList blocking_sprites: Sprites that can block movement
:param int grid_size: Size of the grid, in pixels
:param int left: Left border of playing field
:param int right: Right border of playing field
:param int bottom: Bottom of playing field
:param int top: Top of playing field
"""
def __init__(self,
moving_sprite: Sprite,
blocking_sprites: SpriteList,
grid_size: int,
left: int,
right: int,
bottom: int,
top: int):

self.grid_size = grid_size
self.bottom = int(bottom // grid_size)
self.top = int(top // grid_size)
self.left = int(left // grid_size)
self.right = int(right // grid_size)
self.moving_sprite = moving_sprite
self.blocking_sprites = blocking_sprites
self.barrier_list = None

self.recalculate()

[docs]    def recalculate(self):
"""
Recalculate blocking sprites.
"""
# --- Iterate through the blocking sprites and find where we are blocked

# Save original location
original_pos = self.moving_sprite.position
# Create a set of barriers
self.barrier_list = set()
# Loop through the grid
for cx in range(self.left, self.right + 1):
for cy in range(self.bottom, self.top + 1):
# Grid location
cpos = cx, cy
# Pixel location
pos = _expand(cpos, self.grid_size)

# See if we'll have a collision if our sprite is at this location
self.moving_sprite.position = pos
if len(check_for_collision_with_list(self.moving_sprite, self.blocking_sprites)) > 0:

# Restore original location
self.moving_sprite.position = original_pos
self.barrier_list = sorted(self.barrier_list)

[docs]def astar_calculate_path(start_point: Point,
end_point: Point,
astar_barrier_list: AStarBarrierList,
diagonal_movement=True):
"""
:param Point start_point:
:param Point end_point:
:param AStarBarrierList astar_barrier_list:
:param bool diagonal_movement:

Returns: List

"""

grid_size = astar_barrier_list.grid_size
mod_start = _collapse(start_point, grid_size)
mod_end = _collapse(end_point, grid_size)

left = astar_barrier_list.left
right = astar_barrier_list.right

bottom = astar_barrier_list.bottom
top = astar_barrier_list.top

barrier_list = astar_barrier_list.barrier_list

graph = _AStarGraph(barrier_list, left, right, bottom, top, diagonal_movement)  # type: ignore
result = _AStarSearch(mod_start, mod_end, graph)

if result is None:
return None

# Currently 'result' is in grid locations. We need to convert them to pixel
# locations.
revised_result = [_expand(p, grid_size) for p in result]
return revised_result
```