Gfrktyl

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()

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.