Spaces:
Sleeping
Sleeping
File size: 2,120 Bytes
e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | """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
|