planet.py

mail@pastecode.io avatar
unknown
plain_text
2 years ago
11 kB
6
Indexable
#!/usr/bin/env python3

# Attention: Do not import the ev3dev.ev3 module in this file
import math
from enum import IntEnum, unique
from typing import List, Tuple, Dict, Union


@unique
class Direction(IntEnum):
    """ Directions in shortcut """
    NORTH = 0
    EAST = 90
    SOUTH = 180
    WEST = 270


Weight = int
"""
Weight of a given path (received from the server)

Value:  -1 if blocked path
        >0 for all other paths
        never 0
"""


class Path:

    def __init__(self, start, target, weight, start_dir, end_dir):
        self.start = start
        self.target = target
        self.weight = weight
        self.start_dir = start_dir
        self.end_dir = end_dir


class Planet:
    """
    Contains the representation of the map and provides certain functions to manipulate or extend
    it according to the specifications
    """

    def __init__(self):
        """ Initializes the data structure """
        self.target = None
        self.planet_dict = {}
        self.scanned_nodes = []
        self.unexplored_edges = {}

    # If the start point of the path to add is not in the planet dictionary, an entry is created for it. The same is
    # done for the end point of the path to add. Afterwards, a key-value pair is added to the inner dictionaries of the
    # start and end points. If the inner dictionaries of either the start point or the end point contain 4 key-value
    # pairs and the respective point is not in the list of fully scanned nodes, then it is added to that list.
    def add_path(self, start: Tuple[Tuple[int, int], Direction], target: Tuple[Tuple[int, int], Direction],
                 weight: int):
        """
         Adds a bidirectional path defined between the start and end coordinates to the map and assigns the weight to it

        Example:
            add_path(((0, 3), Direction.NORTH), ((0, 3), Direction.WEST), 1)
        :param start: 2-Tuple
        :param target:  2-Tuple
        :param weight: Integer
        :return: void
        """

        path_to_add = Path(start[0], target[0], weight, start[1], target[1])

        if path_to_add.start not in self.planet_dict and path_to_add.start is not None:
            self.planet_dict[path_to_add.start] = {}

        if path_to_add.target not in self.planet_dict and path_to_add.target is not None:
            self.planet_dict[path_to_add.target] = {}

        self.planet_dict[path_to_add.start][path_to_add.start_dir] = (path_to_add.target, path_to_add.end_dir,
                                                                      path_to_add.weight)

        self.planet_dict[path_to_add.target][path_to_add.end_dir] = (path_to_add.start, path_to_add.start_dir,
                                                                     path_to_add.weight)

        if len(self.planet_dict[path_to_add.start]) == 4 and path_to_add.start not in self.scanned_nodes:
            self.scanned_nodes.append(path_to_add.start)

        if len(self.planet_dict[path_to_add.target]) == 4 and path_to_add.target not in self.scanned_nodes:
            self.scanned_nodes.append(path_to_add.target)

    def get_paths(self) -> Dict[Tuple[int, int], Dict[Direction, Tuple[Tuple[int, int], Direction, Weight]]]:
        """
        Returns all paths

        Example:
            {
                (0, 3): {
                    Direction.NORTH: ((0, 3), Direction.WEST, 1),
                    Direction.EAST: ((1, 3), Direction.WEST, 2),
                    Direction.WEST: ((0, 3), Direction.NORTH, 1)
                },
                (1, 3): {
                    Direction.WEST: ((0, 3), Direction.EAST, 2),
                    ...
                },
                ...
            }
        :return: Dict
        """

        return self.planet_dict

    # Returns a list of all the nodes in the planet dictionary.
    def get_nodes(self) -> List[Tuple[int, int]]:
        nodes = []

        for node in self.planet_dict.keys():
            nodes.append(node)

        return nodes

    # Returns the next direction to take in the shortest path (the second element in the first tuple in the shortest
    # path).
    def shortest_next_dir(self, start: Tuple[int, int], target: Tuple[int, int]) -> Direction:
        shortest_path = self.shortest_path(start, target)

        return shortest_path[0][1]

    # Maps an unexplored edge to a node in the dictionary of unexplored edges (used when scanning for edges at a node).
    def add_unexplored_edge(self, node: Tuple[int, int], direction: Direction) -> None:
        if node not in self.unexplored_edges:
            self.unexplored_edges[node] = []

        self.unexplored_edges[node].append(direction)

    # Removes an unexplored edge from the list of unexplored edges that is mapped to a node in the dictionary of
    # unexplored edges. Afterwards, if an empty list of unexplored edges is mapped to the node, the key-value pair is
    # removed from the dictionary.
    def remove_unexplored_edge(self, start: Tuple[Tuple[int, int], Direction], end: Tuple[Tuple[int, int], Direction])\
            -> None:
        start_dir = start[1]
        end_dir = end[1]
        start_point = start[0]
        end_point = end[0]

        if start_point in self.unexplored_edges and start_dir in self.unexplored_edges[start_point]:
            self.unexplored_edges[start_point].remove(start_dir)

            if len(self.unexplored_edges[start_point]) == 0:
                del self.unexplored_edges[start_point]

        if end_point in self.unexplored_edges and end_dir in self.unexplored_edges[end_point]:
            self.unexplored_edges[end_point].remove(end_dir)

            if len(self.unexplored_edges[end_point]) == 0:
                del self.unexplored_edges[end_point]

    # Implementation of Dijkstra's algorithm.
    def shortest_path(self, start: Tuple[int, int], target: Tuple[int, int]) -> Union[None, List[Tuple[Tuple[int, int],
                                                                                                       Direction]]]:
        """
        Returns a shortest path between two nodes

        Examples:
            shortest_path((0,0), (2,2)) returns: [((0, 0), Direction.EAST), ((1, 0), Direction.NORTH)]
            shortest_path((0,0), (1,2)) returns: None
        :param start: 2-Tuple
        :param target: 2-Tuple
        :return: 2-Tuple[List, Direction]
        """

        unvisited = {}
        current_node = start
        precursor_compass_dict = {}
        shortest_path = []

        if start == target:
            return shortest_path

        # If the target node is not in the planet dictionary, then it cannot be found/reached. Return None.
        if target not in self.planet_dict.keys():
            return None

        # If no path exists between the start node and the target, return None.
        if not self.path_exists(start, target):
            return None

        # All nodes are marked unvisited. The start node is given the tentative distance of 0, and the other nodes are
        # given the tentative distance of infinity.
        for node in self.planet_dict.keys():
            if node == start:
                unvisited[node] = 0
            else:
                unvisited[node] = math.inf

        # Until the target has been marked as visited: check the neighbors of the current node, reassign neighbors'
        # tentative distances, and map tentative precursor nodes to neighbors, if necessary.
        while target in unvisited:
            current_neighbors = self.planet_dict[current_node].items()
            for (start_dir, path) in current_neighbors:
                if path[0] in unvisited.keys() and path[2] != -1:
                    neighbor = path[0]
                    neighbor_weight = path[2]
                    tentative_dist = unvisited[neighbor]
                    if unvisited[current_node] + neighbor_weight < tentative_dist:
                        tentative_dist = unvisited[current_node] + neighbor_weight
                        unvisited[neighbor] = tentative_dist
                        precursor_compass_dict[neighbor] = (current_node, start_dir)

            # Mark the current node as visited after checking its neighbors.
            unvisited.pop(current_node)

            # Find the unvisited node with the lowest tentative distance and set it as the new current node.
            for (node, distance) in unvisited.items():
                if distance == min(unvisited.values()):
                    current_node = node

        # Exit the while loop when the target has been marked as visited and initialize the shortest path.
        if target in precursor_compass_dict.keys():
            shortest_path.append(precursor_compass_dict[target])
        else:
            return None

        # Iterate over the shortest path until the start node is reached. On every iteration, add the respective node's
        # precursor to the shortest path. When the iteration is finished, reverse the shortest path and return it as the
        # result.
        for (coord, direc) in shortest_path:
            if coord != start:
                shortest_path.append(precursor_compass_dict[coord])

        shortest_path.reverse()

        return shortest_path

    # Helper function for determining whether a given target node can be reached from a given start node. Intended to
    # prevent shortest_path from attempting to create a shortest path to a node that is located in the planet dictionary
    # but cannot be reached.
    def path_exists(self, start: Tuple[int, int], target: Tuple[int, int]) -> bool:
        to_check = []
        checked = []

        to_check.append(start)

        while len(to_check) != 0:
            removed = to_check[0]
            checked.append(removed)
            to_check.remove(removed)
            neighbors = self.planet_dict[removed].items()

            for (start_dir, path) in neighbors:
                if path[0] == target and path[2] == -1:
                    pass
                elif path[0] == target:
                    return True
                if path[0] not in checked and path[2] != -1:
                    to_check.append(path[0])

        return False

    # Calculates the distance of the shortest path between a start point and a target point.
    def shortest_distance(self, start: Tuple[int, int], target: Tuple[int, int]) -> Union[int, float]:
        shortest = self.shortest_path(start, target)

        if shortest is None:
            return math.inf

        weight = 0
        for (pos, direction) in shortest:
            weight += self.planet_dict[pos][direction][2]

        return weight