Spaces:
Sleeping
Sleeping
| """Tunnel-aware Manhattan heuristic.""" | |
| from typing import Tuple, List, Optional | |
| from .manhattan import manhattan_heuristic | |
| def tunnel_aware_heuristic( | |
| state: Tuple[int, int], goal: Tuple[int, int], tunnels: Optional[List] = None | |
| ) -> float: | |
| """ | |
| Tunnel-aware Manhattan distance heuristic. | |
| h(n) = min(direct_manhattan, tunnel_shortcuts) | |
| Considers potential tunnel shortcuts that might reduce the distance. | |
| For each tunnel, calculates the cost of going to entrance, through tunnel, | |
| and from exit to goal. | |
| Admissible: Takes minimum of all options, so never overestimates. | |
| Args: | |
| state: Current position (x, y) | |
| goal: Goal position (x, y) | |
| tunnels: List of Tunnel objects with entrance1, entrance2, and cost | |
| Returns: | |
| Estimated cost to reach goal | |
| """ | |
| if goal is None: | |
| return 0.0 | |
| # Direct Manhattan distance | |
| direct = manhattan_heuristic(state, goal) | |
| if not tunnels: | |
| return direct | |
| # Check each tunnel for potential shortcut | |
| best = direct | |
| for tunnel in tunnels: | |
| entrance1 = tunnel.entrance1 | |
| entrance2 = tunnel.entrance2 | |
| tunnel_cost = tunnel.cost | |
| # Path: state -> entrance1 -> (tunnel) -> entrance2 -> goal | |
| via_tunnel_1 = ( | |
| manhattan_heuristic(state, entrance1) | |
| + tunnel_cost | |
| + manhattan_heuristic(entrance2, goal) | |
| ) | |
| # Path: state -> entrance2 -> (tunnel) -> entrance1 -> goal | |
| via_tunnel_2 = ( | |
| manhattan_heuristic(state, entrance2) | |
| + tunnel_cost | |
| + manhattan_heuristic(entrance1, goal) | |
| ) | |
| best = min(best, via_tunnel_1, via_tunnel_2) | |
| return best | |
| def create_tunnel_aware_heuristic(tunnels: List): | |
| """ | |
| Factory function to create a tunnel-aware heuristic with specific tunnels. | |
| Args: | |
| tunnels: List of Tunnel objects | |
| Returns: | |
| Heuristic function | |
| """ | |
| def heuristic(state: Tuple[int, int], goal: Tuple[int, int]) -> float: | |
| return tunnel_aware_heuristic(state, goal, tunnels) | |
| return heuristic | |