# Source code for arcade.paths

```
"""
Path-related functions.
"""
from arcade import Point
from arcade import get_distance
from arcade import lerp_vec
from arcade import get_sprites_at_point
from arcade import check_for_collision_with_list
from arcade import Sprite
from arcade import SpriteList
[docs]def has_line_of_sight(point_1: Point,
point_2: Point,
walls: SpriteList,
max_distance: int = -1,
check_resolution: int = 2):
"""
Determine if we have line of sight between two points. Try to make sure
that spatial hashing is enabled on the wall SpriteList or this will be
very slow.
:param Point point_1: Start position
:param Point point_2: End position position
:param SpriteList walls: List of all blocking sprites
:param int max_distance: Max distance point 1 can see
:param int check_resolution: Check every x pixels for a sprite. Trade-off
between accuracy and speed.
"""
distance = get_distance(point_1[0], point_1[1],
point_2[0], point_2[1])
steps = int(distance // check_resolution)
for step in range(steps + 1):
step_distance = step * check_resolution
u = step_distance / distance
midpoint = lerp_vec(point_1, point_2, u)
if max_distance != -1 and step_distance > max_distance:
return False
# print(point_1, point_2, step, u, step_distance, midpoint)
sprite_list = get_sprites_at_point(midpoint, walls)
if len(sprite_list) > 0:
return False
return True
"""
Classic A-star algorithm for path finding.
"""
def _spot_is_blocked(position, moving_sprite, blocking_sprites):
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
class _AStarGraph(object):
# Define a class board like grid with two barriers
def __init__(self, barriers, left, right, bottom, top, diagonal_movement):
self.barriers = barriers
self.left = left
self.right = right
self.top = top
self.bottom = bottom
if diagonal_movement:
self.movement_directions = (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)
def heuristic(self, start, goal):
"""
Args:
start:
goal:
Returns:
"""
# Use Chebyshev distance heuristic if we can move one square either
# adjacent or diagonal
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)
def get_vertex_neighbours(self, pos):
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, b):
if b in self.barriers:
# print("Ping")
return 10 # Extremely high cost to enter barrier squares
elif a[0] == b[0] or a[1] == b[1]:
return 1
else:
return 1.414
return 1 # Normal movement cost
def _AStarSearch(start, end, graph):
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] = graph.heuristic(start, end)
closedVertices = set()
openVertices = set([start])
cameFrom = {}
count = 0
while len(openVertices) > 0:
count += 1
if count > 2500:
break
# Get the vertex in the open list with the lowest F score
current = None
currentFscore = None
for pos in sorted(openVertices):
if current is None or F[pos] < currentFscore:
currentFscore = F[pos]
current = pos
# Check if we have reached the goal
if current == end:
# Retrace our route backward
path = [current]
while current in cameFrom:
current = cameFrom[current]
path.append(current)
path.reverse()
if F[end] >= 10000:
return None
else:
return path
# return path, F[end] # Done!
# Mark the current vertex as closed
openVertices.remove(current)
closedVertices.add(current)
# Update scores for vertices near the current position
for neighbour in sorted(graph.get_vertex_neighbours(current)):
if neighbour in closedVertices:
continue # We have already processed this node exhaustively
candidateG = G[current] + graph.move_cost(current, neighbour)
if neighbour not in openVertices:
openVertices.add(neighbour) # Discovered a new vertex
elif candidateG >= G[neighbour]:
continue # This G score is worse than previously found
# Adopt this G score
cameFrom[neighbour] = current
G[neighbour] = candidateG
H = graph.heuristic(neighbour, end)
F[neighbour] = G[neighbour] + H
# Out-of-bounds
return None
def _collapse(pos, grid_size):
return int(pos[0] // grid_size), int(pos[1] // grid_size)
def _expand(pos, grid_size):
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.
"""
[docs] def __init__(self,
moving_sprite: Sprite,
blocking_sprites: SpriteList,
grid_size: int,
left: int,
right: int,
bottom: int,
top: int):
"""
: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
"""
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:
self.barrier_list.add(cpos)
# 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)
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
```