pacai.search.food

 1import typing
 2
 3import pacai.core.board
 4import pacai.core.gamestate
 5import pacai.core.search
 6import pacai.pacman.board
 7
 8class FoodSearchNode(pacai.core.search.SearchNode):
 9    """
10    A search node for the food search problem.
11    The state for this search problem will be
12    the current position and the remaining food positions.
13    """
14
15    def __init__(self,
16            position: pacai.core.board.Position,
17            remaining_food: typing.Iterable[pacai.core.board.Position]) -> None:
18        self.position: pacai.core.board.Position = position
19        """ The current position being searched. """
20
21        self.remaining_food: tuple[pacai.core.board.Position, ...] = tuple(sorted(list(remaining_food)))
22        """
23        The food left to eat.
24        This is kept sorted to ensure that underlying comparison checks run cleanly.
25        """
26
27    def __lt__(self, other: object) -> bool:
28        if (not isinstance(other, FoodSearchNode)):
29            return False
30
31        return ((self.position, self.remaining_food) < (other.position, other.remaining_food))
32
33    def __eq__(self, other: object) -> bool:
34        if (not isinstance(other, FoodSearchNode)):
35            return False
36
37        return ((self.position == other.position) and (self.remaining_food == other.remaining_food))
38
39    def __hash__(self) -> int:
40        return hash((self.position, self.remaining_food))
41
42class FoodSearchProblem(pacai.core.search.SearchProblem[FoodSearchNode]):
43    """
44    A search problem associated with finding the a path that collects all of the "food" in a game.
45    """
46
47    def __init__(self,
48            game_state: pacai.core.gamestate.GameState,
49            start_position: pacai.core.board.Position | None = None,
50            **kwargs: typing.Any) -> None:
51        """
52        Create a food search problem.
53
54        If no start position is provided, the current agent's position will be used.
55        """
56
57        super().__init__()
58
59        self.state: pacai.core.gamestate.GameState = game_state
60        """ Keep track of the enire game state. """
61
62        if (start_position is None):
63            start_position = game_state.get_agent_position()
64
65        if (start_position is None):
66            raise ValueError("Could not find starting position.")
67
68        self.start_position = start_position
69        """ The position to start from. """
70
71    def get_starting_node(self) -> FoodSearchNode:
72        return FoodSearchNode(self.start_position, self.state.board.get_marker_positions(pacai.pacman.board.MARKER_PELLET))
73
74    def is_goal_node(self, node: FoodSearchNode) -> bool:
75        return (len(node.remaining_food) == 0)
76
77    def complete(self, goal_node: FoodSearchNode) -> None:
78        # Mark the final node in the history.
79        self.position_history.append(goal_node.position)
80
81    def get_successor_nodes(self, node: FoodSearchNode) -> list[pacai.core.search.SuccessorInfo]:
82        successors = []
83
84        # Check all the non-wall neighbors.
85        for (action, position) in self.state.board.get_neighbors(node.position):
86            new_remaining_food = list(node.remaining_food).copy()
87            if (position in new_remaining_food):
88                new_remaining_food.remove(position)
89
90            next_node = FoodSearchNode(position, new_remaining_food)
91            successors.append(pacai.core.search.SuccessorInfo(next_node, action, 1.0))
92
93        # Do bookkeeping on the states/positions we visited.
94        self.expanded_node_count += 1
95        if (node not in self.visited_nodes):
96            self.position_history.append(node.position)
97
98        return successors