# Python A Star with fewest turns and shortest path variations

I had a lot of fun writing these. I haven't seen a version minimizing turns, so that was a neat challenge. Any suggestions are very welcome.

Is there anything to gain by making more method variables like those in the search() method; visited or open_pos into instance variables?

I would like to have something returned when instantiating an object

ham = MinTurns(start, end, grid)


instead of

eggs = MinTurns(start, end, grid)
ham = eggs.search()


Is there a way to do this? Using super maybe? I have messed around but haven't come up with anything better. Am I being ridiculous?

Is the level of commenting appropriate?

Can I gain any efficiency?

from heapq import heappop, heappush

class AStar(object):

def __init__(self, start_pos: tuple, end_pos: tuple, grid: list):
"""Instantiate AStar object.

start_pos and end_pos are tuples of coordinates.
(0, 2), (0, 4)

grid is a list of length n of strings of length n where 'x' indicates a barrier.

i.e.
['...x...',
'.xxxx..',
'.x.....',
'.x.xxx.',
'.x...x.',
'..xx.x.',
'.......']

:param start_pos: Coordinates of start position.
:param end_pos: Coordinates of end position.
:param grid: List containing square grid of strings with 'x' denoting barriers.
"""
self.start_pos = start_pos
self.end_pos = end_pos
self.grid = grid

class MinTurns(AStar):

"""A star algorithm for navigating a map in the fewest turns.

Given start and end points for a grid style maze, outputs a tuple containing; a list of coordinates, number of
turns, and length of route from start to end for the route with the fewest turns.

"""

def find_neighbors(self, curr_pos: tuple, prev_pos: tuple) -> list:
"""Finds neighbors of curr_pos.

Adds coordinates of neighbors to list along with boolean(is_turn) representing whether a turn occurs to reach
the neighbor given path from prev_pos to curr_pos.

:param curr_pos: curr_pos of self.search().
:param prev_pos: position prior to curr_pos.
:return: list of tuples [((pos of neighbor), is_turn)].
"""
limit = len(self.grid) - 1
neighbors = []
# Check each position adjacent to curr_pos.
for y, x in zip([0, -1, 0, 1], [1, 0, -1, 0]):
# If adjacent position is outside of grid, skip it.
if (curr_pos[0] + y) > limit or (curr_pos[0] + y) < 0 or (curr_pos[1] + x) > limit or (curr_pos[1] + x) < 0:
continue
# If adjacent position is a barrier, skip it.
if self.grid[curr_pos[0] + y][curr_pos[1] + x] == 'x':
continue
else:
# Ensure we do not count a first step as a turn.
if curr_pos == self.start_pos:
is_turn = False
else:
# Determine direction from prev_pos to curr_pos.
if curr_pos != prev_pos[1] and curr_pos[0] == prev_pos[1][0]:
direction = 'horizontal'
else:
direction = 'vertical'

# Determine movement from curr_pos to new position.
if y != 0:
movement = 'vertical'
else:
movement = 'horizontal'

# If we're not still moving in the same direction, we have turned.
is_turn = not (movement == direction)
neighbors.append(((curr_pos[0] + y, curr_pos[1] + x), is_turn))
return neighbors

def make_path(self, curr_pos: tuple, route: dict) -> tuple:
"""Creates list of coordinates representing turns in path.

:param curr_pos: end point of path.
:param route: dict of coordinates leading to curr_pos
:return: tuple containing list of coordinates of turns, len(list of coordinates)
"""
turn_coords = []
x, path_length = 0, 1
prev_pos = curr_pos

if route.get(self.end_pos) is None:
return 'No path found.', []

while route[curr_pos] is not None:
curr_pos = route[curr_pos][1]

if curr_pos[x] != prev_pos[x]:
if x == 0:
x = 1
else:
x = 0

if prev_pos is not self.end_pos:
turn_coords.append(prev_pos)

prev_pos = curr_pos
path_length += 1

turn_coords.reverse()
return len(turn_coords), path_length

def search(self):
"""Finds path through self.grid in fewest number of turns.

Uses a priority queue to sort nodes by least number of turns required to reach it.
Continually updates number of turns needed to reach any given position if a better path is found.

:return: self.make_path().
"""
# Keep track of where we've been.
visited = set()

# We'll keep track of the route and the number of turns to reach the curr_pos with a dict.
# {(position): (turns_count, (previous-position))}
route = {self.start_pos: None}

# turn_count is used to promote routes with fewer turns.
turn_count = {self.start_pos: 0}

open_pos = []
heappush(open_pos, (0, self.start_pos))

while open_pos:
# Routes with fewest turns_so_far are up first in the priority queue.
turns_so_far, curr_pos = heappop(open_pos)

if curr_pos in visited:
continue

prev = route[curr_pos]  # Always remember where you came from so we know if we've turned.
visited.add(curr_pos)  # But keep moving forward. Never go back!

neighbors_list = self.find_neighbors(curr_pos, prev)
for pos, did_turn in neighbors_list:
if pos in visited:
continue

if turn_count.get(pos):  # Have we been here before?
# If so, lets update our turn_count with the route containing the fewest turns.
turn_count[pos] = min(turn_count[pos], turns_so_far + int(did_turn))
else:
turn_count[pos] = turns_so_far + int(did_turn)

# In any case add this place to the list of places to explore.
heappush(open_pos, (turn_count[pos], pos))

old_route = route.get(pos)  # Do we know of another way to get here?
# If so, does the old_route take more turns than the current route to get to pos?
if old_route and turn_count[pos] < old_route[0]:
# If pos can be reached in fewer turns by the current route, we overwrite the old route.
route[pos] = (turn_count[pos], curr_pos)
if not old_route:
route[pos] = (turn_count[pos], curr_pos)

# Wait until open_pos is exhausted to ensure a shorter path doesn't end our search prematurely.
return self.make_path(self.end_pos, route)

class ShortestRoute(AStar):

"""Algorithm to find shortest path between coordinates in a grid style maze

"""

def find_neighbors(self, curr_pos: tuple) -> list:
"""Finds neighbors of curr_pos.

Adds coordinates of neighbors to list.

:param curr_pos: curr_pos of self.search().
:return: list of tuples [((pos of neighbor), is_turn)].
"""
limit = len(self.grid) - 1
neighbors = []
# Check each position adjacent to curr_pos
for y, x in zip([0, -1, 0, 1], [1, 0, -1, 0]):
# If adjacent position is outside of grid, skip it.
if (curr_pos[0] + y) > limit or (curr_pos[0] + y) < 0 or (curr_pos[1] + x) > limit or (curr_pos[1] + x) < 0:
continue
# If adjacent position is a barrier, skip it.
if self.grid[curr_pos[0] + y][curr_pos[1] + x] == 'x':
continue
neighbors.append((curr_pos[0] + y, curr_pos[1] + x))
return neighbors

def make_path(self, route: dict):
"""Creates list of coordinates in path.

:param route: dict of coordinates leading to curr_pos.
:return: tuple containing list of coordinates.
"""
path = []
curr_pos = self.end_pos
while curr_pos is not None:
path.append(curr_pos)
curr_pos = route[curr_pos][1]
path.reverse()
return len(path)

def search(self):
"""Finds shortest path through self.grid.

Uses a deque to hold coordinates of positions to explore.
Continually updates length to reach any given position if a shorter path to that position is found.

:return: self.make_path().
"""
visited = set()
route = {self.start_pos: (1, None)}
open_pos = []
heappush(open_pos, (1, self.start_pos))
while open_pos:
length, curr_pos = heappop(open_pos)
if curr_pos == self.end_pos:
return self.make_path(route)
if curr_pos in visited:
continue
visited.add(curr_pos)
neighbors = self.find_neighbors(curr_pos)
for neighbor in neighbors:
if neighbor in visited:
continue
# if neighbor not in open_pos:
length += 1  # neighbor is one step farther than curr_pos.
heappush(open_pos, (length, neighbor))
old_route = route.get(neighbor)  # Do we know of another way to get here?
# If so, is it shorter than the current route to get to neighbor?
if old_route and length < old_route[0]:
# If neighbor can be reached faster by the current route, we overwrite the old route.
route[neighbor] = (length, curr_pos)
if not old_route:
route[neighbor] = (length, curr_pos)
return 'No path found.', []


Import and run:

from random import randint
from a_star import AStar, MinTurns, ShortestRoute

def make_maze_line(size):
items = ['.', '.', '.', 'x']
maze_line = [items[randint(0, 3)] for _ in range(size)]
return ''.join(maze_line)

def make_maze(size):
return [make_maze_line(size) for _ in range(size)]

maze = ['...x.....',
'.x.xx..x.',
'.x...x.x.',
'.xxx.x.x.',
'...x...x.',
'.x.x.x.x.',
'.x.....x.',
'..xxxxx..',
'.........']
maze = make_maze(60)

for line in maze:
print(line)
start, stop = (3, 2), (42, 54)

def main():
route_1 = MinTurns(start, stop, maze).search()
route_2 = ShortestRoute(start, stop, maze).search()
print(route_1)
print(route_2)

if __name__ == "__main__":
main()


## 1 Answer

One test is to see if a backward run produces the same number of turns. This test fails given inputs like:

start, end = (1, 0), (1, 4) grid = ['.....', '...x.', 'xxxxx', ...]

MinTurns(start, end, grid).search() results in output ([(1, 2), (0, 2), (0, 4)], 3, 8)

MinTurns(end, start, grid).search() results in output ([(0, 4), (0, 0)]), 2, 8)

I'm finding that, since a turn is assigned and carried through the path along the top row starting with (1, 1), the bottom row will be called first out of open_pos causing (0, 2) to become a child of (1, 2) instead of a child of (0, 1). By the time we realize an extra turn will result from this path (0, 2) is in the visited set and won't be rewritten.

I can't see a way to correct this without adding a lot of complexity to the algorithm, and because of the heuristic nature of the algorithm, I don't see a one off in rare circumstances as all that bad.

Given all the above we can gain quite a bit of efficiency by returning the path when end is first encountered rather than waiting for all open_pos to be exhausted.