planet.py
unknown
plain_text
2 years ago
11 kB
6
Indexable
Never
#!/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