>>> grid = TEST_GRIDS[2] >>> gbf = GreedyBestFirst(grid, (0, 0), (len(grid) - 1, len(grid[0]) - 1)) >>> [x.pos for x in gbf.get_successors(gbf.start)] [(1, 0), (0, 1)] >>> (gbf.start.pos_y + delta[3][0], gbf.start.pos_x + delta[3][1]) (0, 1) >>> (gbf.start.pos_y + delta[
| 88 | |
| 89 | |
| 90 | class GreedyBestFirst: |
| 91 | """ |
| 92 | >>> grid = TEST_GRIDS[2] |
| 93 | >>> gbf = GreedyBestFirst(grid, (0, 0), (len(grid) - 1, len(grid[0]) - 1)) |
| 94 | >>> [x.pos for x in gbf.get_successors(gbf.start)] |
| 95 | [(1, 0), (0, 1)] |
| 96 | >>> (gbf.start.pos_y + delta[3][0], gbf.start.pos_x + delta[3][1]) |
| 97 | (0, 1) |
| 98 | >>> (gbf.start.pos_y + delta[2][0], gbf.start.pos_x + delta[2][1]) |
| 99 | (1, 0) |
| 100 | >>> gbf.retrace_path(gbf.start) |
| 101 | [(0, 0)] |
| 102 | >>> gbf.search() # doctest: +NORMALIZE_WHITESPACE |
| 103 | [(0, 0), (1, 0), (2, 0), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), |
| 104 | (4, 4)] |
| 105 | """ |
| 106 | |
| 107 | def __init__( |
| 108 | self, grid: list[list[int]], start: tuple[int, int], goal: tuple[int, int] |
| 109 | ): |
| 110 | self.grid = grid |
| 111 | self.start = Node(start[1], start[0], goal[1], goal[0], 0, None) |
| 112 | self.target = Node(goal[1], goal[0], goal[1], goal[0], 99999, None) |
| 113 | |
| 114 | self.open_nodes = [self.start] |
| 115 | self.closed_nodes: list[Node] = [] |
| 116 | |
| 117 | self.reached = False |
| 118 | |
| 119 | def search(self) -> Path | None: |
| 120 | """ |
| 121 | Search for the path, |
| 122 | if a path is not found, only the starting position is returned |
| 123 | """ |
| 124 | while self.open_nodes: |
| 125 | # Open Nodes are sorted using __lt__ |
| 126 | self.open_nodes.sort() |
| 127 | current_node = self.open_nodes.pop(0) |
| 128 | |
| 129 | if current_node.pos == self.target.pos: |
| 130 | self.reached = True |
| 131 | return self.retrace_path(current_node) |
| 132 | |
| 133 | self.closed_nodes.append(current_node) |
| 134 | successors = self.get_successors(current_node) |
| 135 | |
| 136 | for child_node in successors: |
| 137 | if child_node in self.closed_nodes: |
| 138 | continue |
| 139 | |
| 140 | if child_node not in self.open_nodes: |
| 141 | self.open_nodes.append(child_node) |
| 142 | |
| 143 | if not self.reached: |
| 144 | return [self.start.pos] |
| 145 | return None |
| 146 | |
| 147 | def get_successors(self, parent: Node) -> list[Node]: |