Spaces:
Sleeping
Sleeping
| """DeliverySearch - Search problem for package delivery.""" | |
| from typing import List, Tuple, Optional, Dict | |
| from .generic_search import GenericSearch | |
| from ..models.grid import Grid | |
| from ..models.entities import Tunnel | |
| from ..models.state import PathResult, SearchStep | |
| from ..heuristics import create_tunnel_aware_heuristic | |
| class DeliverySearch(GenericSearch): | |
| """ | |
| Search problem for finding path from a store to a destination. | |
| Implements the GenericSearch interface for the package delivery problem. | |
| Supports movement in 4 directions (up/down/left/right) and tunnel travel. | |
| """ | |
| def __init__( | |
| self, | |
| grid: Grid, | |
| start: Tuple[int, int], | |
| goal: Tuple[int, int], | |
| tunnels: Optional[List[Tunnel]] = None, | |
| ): | |
| """ | |
| Initialize the delivery search problem. | |
| Args: | |
| grid: The city grid with traffic information | |
| start: Starting position (store location) | |
| goal: Goal position (destination location) | |
| tunnels: List of available tunnels | |
| """ | |
| self.grid = grid | |
| self.start = start | |
| self.goal = goal | |
| self.tunnels = tunnels or [] | |
| # Create tunnel lookup by entrance position | |
| self._tunnel_entrances: Dict[Tuple[int, int], Tunnel] = {} | |
| for tunnel in self.tunnels: | |
| self._tunnel_entrances[tunnel.entrance1] = tunnel | |
| self._tunnel_entrances[tunnel.entrance2] = tunnel | |
| # Create tunnel-aware heuristic | |
| self._tunnel_heuristic = create_tunnel_aware_heuristic(self.tunnels) | |
| def initial_state(self) -> Tuple[int, int]: | |
| """Return the starting position.""" | |
| return self.start | |
| def goal_test(self, state: Tuple[int, int]) -> bool: | |
| """Check if current state is the goal.""" | |
| return state == self.goal | |
| def actions(self, state: Tuple[int, int]) -> List[str]: | |
| """ | |
| Return list of valid actions from current state. | |
| Actions: | |
| - up: Move up (y+1) | |
| - down: Move down (y-1) | |
| - left: Move left (x-1) | |
| - right: Move right (x+1) | |
| - tunnel: Use tunnel if at entrance | |
| Returns: | |
| List of valid action strings | |
| """ | |
| x, y = state | |
| valid_actions = [] | |
| # Check each direction | |
| directions = [ | |
| ("up", (x, y + 1)), | |
| ("down", (x, y - 1)), | |
| ("left", (x - 1, y)), | |
| ("right", (x + 1, y)), | |
| ] | |
| for action, new_pos in directions: | |
| if self.grid.is_valid_position(new_pos): | |
| if not self.grid.is_blocked(state, new_pos): | |
| valid_actions.append(action) | |
| # Check for tunnel | |
| if state in self._tunnel_entrances: | |
| valid_actions.append("tunnel") | |
| return valid_actions | |
| def result(self, state: Tuple[int, int], action: str) -> Tuple[int, int]: | |
| """ | |
| Apply action to state and return new state. | |
| Args: | |
| state: Current position | |
| action: Action to take | |
| Returns: | |
| New position after action | |
| """ | |
| x, y = state | |
| if action == "up": | |
| return (x, y + 1) | |
| elif action == "down": | |
| return (x, y - 1) | |
| elif action == "left": | |
| return (x - 1, y) | |
| elif action == "right": | |
| return (x + 1, y) | |
| elif action == "tunnel": | |
| if state in self._tunnel_entrances: | |
| tunnel = self._tunnel_entrances[state] | |
| return tunnel.get_other_entrance(state) | |
| else: | |
| raise ValueError(f"No tunnel entrance at {state}") | |
| else: | |
| raise ValueError(f"Unknown action: {action}") | |
| def step_cost( | |
| self, state: Tuple[int, int], action: str, next_state: Tuple[int, int] | |
| ) -> float: | |
| """ | |
| Return the cost of taking an action. | |
| For regular moves: cost = traffic level of the segment | |
| For tunnels: cost = Manhattan distance between entrances | |
| Args: | |
| state: Current position | |
| action: Action taken | |
| next_state: Resulting position | |
| Returns: | |
| Cost of the action | |
| """ | |
| if action == "tunnel": | |
| tunnel = self._tunnel_entrances.get(state) | |
| if tunnel: | |
| return tunnel.cost | |
| return 0.0 | |
| else: | |
| # Regular movement - cost is traffic level | |
| return self.grid.get_traffic(state, next_state) | |
| def heuristic(self, state: Tuple[int, int]) -> float: | |
| """ | |
| Tunnel-aware heuristic for A* search. | |
| Args: | |
| state: Current position | |
| Returns: | |
| Estimated cost to goal | |
| """ | |
| return self._tunnel_heuristic(state, self.goal) | |
| def path( | |
| grid: Grid, | |
| start: Tuple[int, int], | |
| goal: Tuple[int, int], | |
| tunnels: List[Tunnel], | |
| strategy: str, | |
| visualize: bool = False, | |
| ) -> Tuple[PathResult, Optional[List[SearchStep]]]: | |
| """ | |
| Find path from start to goal using specified strategy. | |
| Args: | |
| grid: The city grid | |
| start: Starting position | |
| goal: Goal position | |
| tunnels: Available tunnels | |
| strategy: Search strategy (BF, DF, ID, UC, GR1, GR2, AS1, AS2) | |
| visualize: If True, collect visualization steps | |
| Returns: | |
| Tuple of (PathResult, Optional[List[SearchStep]]) | |
| """ | |
| search = DeliverySearch(grid, start, goal, tunnels) | |
| return search.solve(strategy, visualize) | |