3
\$\begingroup\$

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()
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.