>>> bd_astar = BidirectionalAStar((0, 0), (len(grid) - 1, len(grid[0]) - 1)) >>> bd_astar.fwd_astar.start.pos == bd_astar.bwd_astar.target.pos True >>> bd_astar.retrace_bidirectional_path(bd_astar.fwd_astar.start, ... bd_astar.bwd_astar.start)
| 169 | |
| 170 | |
| 171 | class BidirectionalAStar: |
| 172 | """ |
| 173 | >>> bd_astar = BidirectionalAStar((0, 0), (len(grid) - 1, len(grid[0]) - 1)) |
| 174 | >>> bd_astar.fwd_astar.start.pos == bd_astar.bwd_astar.target.pos |
| 175 | True |
| 176 | >>> bd_astar.retrace_bidirectional_path(bd_astar.fwd_astar.start, |
| 177 | ... bd_astar.bwd_astar.start) |
| 178 | [(0, 0)] |
| 179 | >>> bd_astar.search() # doctest: +NORMALIZE_WHITESPACE |
| 180 | [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), |
| 181 | (2, 5), (3, 5), (4, 5), (5, 5), (5, 6), (6, 6)] |
| 182 | """ |
| 183 | |
| 184 | def __init__(self, start: TPosition, goal: TPosition) -> None: |
| 185 | self.fwd_astar = AStar(start, goal) |
| 186 | self.bwd_astar = AStar(goal, start) |
| 187 | self.reached = False |
| 188 | |
| 189 | def search(self) -> list[TPosition]: |
| 190 | while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes: |
| 191 | self.fwd_astar.open_nodes.sort() |
| 192 | self.bwd_astar.open_nodes.sort() |
| 193 | current_fwd_node = self.fwd_astar.open_nodes.pop(0) |
| 194 | current_bwd_node = self.bwd_astar.open_nodes.pop(0) |
| 195 | |
| 196 | if current_bwd_node.pos == current_fwd_node.pos: |
| 197 | return self.retrace_bidirectional_path( |
| 198 | current_fwd_node, current_bwd_node |
| 199 | ) |
| 200 | |
| 201 | self.fwd_astar.closed_nodes.append(current_fwd_node) |
| 202 | self.bwd_astar.closed_nodes.append(current_bwd_node) |
| 203 | |
| 204 | self.fwd_astar.target = current_bwd_node |
| 205 | self.bwd_astar.target = current_fwd_node |
| 206 | |
| 207 | successors = { |
| 208 | self.fwd_astar: self.fwd_astar.get_successors(current_fwd_node), |
| 209 | self.bwd_astar: self.bwd_astar.get_successors(current_bwd_node), |
| 210 | } |
| 211 | |
| 212 | for astar in [self.fwd_astar, self.bwd_astar]: |
| 213 | for child_node in successors[astar]: |
| 214 | if child_node in astar.closed_nodes: |
| 215 | continue |
| 216 | |
| 217 | if child_node not in astar.open_nodes: |
| 218 | astar.open_nodes.append(child_node) |
| 219 | else: |
| 220 | # retrieve the best current path |
| 221 | better_node = astar.open_nodes.pop( |
| 222 | astar.open_nodes.index(child_node) |
| 223 | ) |
| 224 | |
| 225 | if child_node.g_cost < better_node.g_cost: |
| 226 | astar.open_nodes.append(child_node) |
| 227 | else: |
| 228 | astar.open_nodes.append(better_node) |
no outgoing calls
no test coverage detected