>>> astar = AStar((0, 0), (len(grid) - 1, len(grid[0]) - 1)) >>> (astar.start.pos_y + delta[3][0], astar.start.pos_x + delta[3][1]) (0, 1) >>> [x.pos for x in astar.get_successors(astar.start)] [(1, 0), (0, 1)] >>> (astar.start.pos_y + delta[2][0], astar.start.pos_x + delta[
| 76 | |
| 77 | |
| 78 | class AStar: |
| 79 | """ |
| 80 | >>> astar = AStar((0, 0), (len(grid) - 1, len(grid[0]) - 1)) |
| 81 | >>> (astar.start.pos_y + delta[3][0], astar.start.pos_x + delta[3][1]) |
| 82 | (0, 1) |
| 83 | >>> [x.pos for x in astar.get_successors(astar.start)] |
| 84 | [(1, 0), (0, 1)] |
| 85 | >>> (astar.start.pos_y + delta[2][0], astar.start.pos_x + delta[2][1]) |
| 86 | (1, 0) |
| 87 | >>> astar.retrace_path(astar.start) |
| 88 | [(0, 0)] |
| 89 | >>> astar.search() # doctest: +NORMALIZE_WHITESPACE |
| 90 | [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (3, 3), |
| 91 | (4, 3), (4, 4), (5, 4), (5, 5), (6, 5), (6, 6)] |
| 92 | """ |
| 93 | |
| 94 | def __init__(self, start: TPosition, goal: TPosition): |
| 95 | self.start = Node(start[1], start[0], goal[1], goal[0], 0, None) |
| 96 | self.target = Node(goal[1], goal[0], goal[1], goal[0], 99999, None) |
| 97 | |
| 98 | self.open_nodes = [self.start] |
| 99 | self.closed_nodes: list[Node] = [] |
| 100 | |
| 101 | self.reached = False |
| 102 | |
| 103 | def search(self) -> list[TPosition]: |
| 104 | while self.open_nodes: |
| 105 | # Open Nodes are sorted using __lt__ |
| 106 | self.open_nodes.sort() |
| 107 | current_node = self.open_nodes.pop(0) |
| 108 | |
| 109 | if current_node.pos == self.target.pos: |
| 110 | return self.retrace_path(current_node) |
| 111 | |
| 112 | self.closed_nodes.append(current_node) |
| 113 | successors = self.get_successors(current_node) |
| 114 | |
| 115 | for child_node in successors: |
| 116 | if child_node in self.closed_nodes: |
| 117 | continue |
| 118 | |
| 119 | if child_node not in self.open_nodes: |
| 120 | self.open_nodes.append(child_node) |
| 121 | else: |
| 122 | # retrieve the best current path |
| 123 | better_node = self.open_nodes.pop(self.open_nodes.index(child_node)) |
| 124 | |
| 125 | if child_node.g_cost < better_node.g_cost: |
| 126 | self.open_nodes.append(child_node) |
| 127 | else: |
| 128 | self.open_nodes.append(better_node) |
| 129 | |
| 130 | return [self.start.pos] |
| 131 | |
| 132 | def get_successors(self, parent: Node) -> list[Node]: |
| 133 | """ |
| 134 | Returns a list of successors (both in the grid and free spaces) |
| 135 | """ |
no outgoing calls
no test coverage detected