groundwork for path planning implementation

1 files changed, 588 insertions, 0 deletions

diff --git a/pokemontools/vba/path.py b/pokemontools/vba/path.py
new file mode 100644
index 0000000..e861a39
--- /dev/null
+++ b/pokemontools/vba/path.py
@@ -0,0 +1,588 @@
+"""
+path finding implementation
+
+1) For each position on the map, create a node representing the position.
+2) For each NPC/item, mark nearby nodes as members of that NPC's threat zone
+   (note that they can be members of multiple zones simultaneously).
+"""
+
+PENALTIES = {
+    # The minimum cost for a step must be greater than zero or else the path
+    # finding implementation might take the player through elaborate routes
+    # through nowhere.
+    "NONE": 1,
+
+    # for any area that might be near a trainer or moving object
+    "THREAT_ZONE": 50,
+
+    # for any nodes that might be under active observation (sight) by a trainer
+    "SIGHT_RANGE": 80,
+
+    # active sight range is where the trainer will definitely see the player
+    "ACTIVE_SIGHT_RANGE": 100,
+
+    # This is impossible, but the pathfinder might have a bug, and it would be
+    # nice to know about such a bug very soon.
+    "COLLISION": -999999,
+}
+
+DIRECTIONS = {
+    "UP": "UP",
+    "DOWN": "DOWN",
+    "LEFT": "LEFT",
+    "RIGHT": "RIGHT",
+}
+
+class Node(object):
+    """
+    A ``Node`` represents a position on the map.
+    """
+
+    def __init__(self, position, threat_zones=None, contents=None):
+        self.position = position
+        self.y = position[0]
+        self.x = position[1]
+
+        # by default a node is not a member of any threat zones
+        self.threat_zones = threat_zones or set()
+
+        # by default a node does not have any objects at this location
+        self.contents = contents or set()
+
+        self.cost = self.calculate_cost()
+
+    def calculate_cost(self, PENALTIES=PENALTIES):
+        """
+        Calculates a cost associated with passing through this node.
+        """
+        penalty = PENALTIES["NONE"]
+
+        # 1) assign a penalty based on whether or not this object is passable,
+        # if it's a collision then return a priority immediately
+        if self.is_collision_by_map_data() or self.is_collision_by_map_obstacle():
+            penalty += PENALTIES["COLLISION"]
+            return penalty
+
+        # 2) assign a penalty based on whether or not this object is grass/water
+
+        # 3) assign a penalty based on whether or not there is a map_obstacle here,
+        # check each of the contents to see if there are any objects that exist
+        # at this location, if anything exists here then return a priority immediately
+
+        # 4) consider any additional penalties due to the presence of a threat
+        # zone. Only calculate detailed penalties about the threat zone if the
+        # player is within range.
+        for threat_zone in self.threat_zones:
+            # the player might be inside the threat zone or the player might be
+            # just on the boundary
+            player_y = get_player_y()
+            player_x = get_player_x()
+            if threat_zone.is_player_near(player_y, player_x):
+                consider_sight_range = True
+            else:
+                consider_sight_range = False
+
+            penalty += threat_zone.calculate_node_cost(self.y, self.x, consider_sight_range=consider_sight_range, PENALTIES=PENALTIES)
+
+        return penalty
+
+    def is_collision_by_map_data(self):
+        """
+        Checks if the player can walk on this location.
+        """
+        raise NotImplementedError
+
+    def is_collision_by_map_obstacle(self):
+        """
+        Checks if there is a map_obstacle on the current position that prevents
+        the player walking here.
+        """
+        for content in self.contents:
+            if self.content.y == self.y and self.content.x == self.x:
+                return True
+        else:
+            return False
+
+class MapObstacle(object):
+    """
+    A ``MapObstacle`` represents an item, npc or trainer on the map.
+    """
+
+    def __init__(self, some_map, identifier, sight_range=None, movement=None, turn=None, simulation=False, facing_direction=DIRECTIONS["DOWN"]):
+        """
+        :param some_map: a reference to the map that this object belongs to
+        :param identifier: which object on the map does this correspond to?
+        :param simulation: set to False to not read from RAM
+        """
+        self.simulation = simulation
+
+        self.some_map = some_map
+        self.identifier = identifier
+
+        self._sight_range = sight_range
+        if self._sight_range is None:
+            self._sight_range = self._get_sight_range()
+
+        self._movement = movement
+        if self._movement is None:
+            self._movement = self._get_movement()
+
+        self._turn = turn
+        if self._turn is None:
+            self._turn = self._get_turn()
+
+        self.facing_direction = facing_direction
+        if not self.facing_direction:
+            self.facing_direction = self.get_current_facing_direction()
+
+        self.update_location()
+
+    def update_location(self):
+        """
+        Determines the (y, x) location of the given map_obstacle object, which
+        can be a reference to an item, npc or trainer npc.
+        """
+        if self.simulation:
+            return (self.y, self.x)
+        else:
+            raise NotImplementedError
+
+            self.y = new_y
+            self.x = new_x
+
+            return (new_y, new_x)
+
+    def _get_current_facing_direction(self, DIRECTIONS=DIRECTIONS):
+        """
+        Get the current facing direction of the map_obstacle.
+        """
+        raise NotImplementedError
+
+    def get_current_facing_direction(self, DIRECTIONS=DIRECTIONS):
+        """
+        Get the current facing direction of the map_obstacle.
+        """
+        if not self.simulation:
+            self.facing_direction = self._get_current_facing_direction(DIRECTIONS=DIRECTIONS)
+        return self.facing_direction
+
+    def _get_movement(self):
+        """
+        Figures out the "movement" variable. Also, this converts from the
+        internal game's format into True or False for whether or not the object
+        is capable of moving.
+        """
+        raise NotImplementedError
+
+    @property
+    def movement(self):
+        if self._movement is None:
+            self._movement = self._get_movement()
+        return self._movement
+
+    def can_move(self):
+        """
+        Checks if this map_obstacle is capable of movement.
+        """
+        return self.movement
+
+    def _get_turn(self):
+        """
+        Checks whether or not the map_obstacle can turn. This only matters for
+        trainers.
+        """
+        raise NotImplementedError
+
+    @property
+    def turn(self):
+        if self._turn is None:
+            self._turn = self._get_turn()
+        return self._turn
+
+    def can_turn_without_moving(self):
+        """
+        Checks whether or not the map_obstacle can turn. This only matters for
+        trainers.
+        """
+        return self.turn
+
+    def _get_sight_range(self):
+        """
+        Figure out the sight range of this map_obstacle.
+        """
+        raise NotImplementedError
+
+    @property
+    def sight_range(self):
+        if self._sight_range is None:
+            self._sight_range = self._get_sight_range()
+        return self._sight_range
+
+class ThreatZone(object):
+    """
+    A ``ThreatZone`` represents the area surrounding a moving or turning object
+    that the player can try to avoid.
+    """
+
+    def __init__(self, map_obstacle, main_graph):
+        """
+        Constructs a ``ThreatZone`` based on a graph of a map and a particular
+        object on that map.
+
+        :param map_obstacle: the subject based on which to build a threat zone
+        :param main_graph: a reference to the map's nodes
+        """
+
+        self.map_obstacle = map_obstacle
+        self.main_graph = main_graph
+
+        self.sight_range = self.calculate_sight_range()
+
+        self.top_left_y = None
+        self.top_left_x = None
+        self.bottom_right_y = None
+        self.bottom_right_x = None
+        self.height = None
+        self.width = None
+        self.size = self.calculate_size()
+
+        # nodes specific to this threat zone
+        self.nodes = []
+
+    def calculate_size(self):
+        """
+        Calculate the bounds of the threat zone based on the map obstacle.
+        Returns the top left corner (y, x) and the bottom right corner (y, x)
+        in the form of ((y, x), (y, x), height, width).
+        """
+        top_left_y = 0
+        top_left_x = 0
+
+        bottom_right_y = 1
+        bottom_right_x = 1
+
+        # TODO: calculate the correct bounds of the threat zone.
+
+        raise NotImplementedError
+
+        # if there is a sight_range for this map_obstacle then increase the size of the zone.
+        if self.sight_range > 0:
+            top_left_y += self.sight_range
+            top_left_x += self.sight_range
+            bottom_right_y += self.sight_range
+            bottom_right_x += self.sight_range
+
+        top_left = (top_left_y, top_left_x)
+        bottom_right = (bottom_right_y, bottom_right_x)
+
+        height = bottom_right_y - top_left_y
+        width = bottom_right_x - top_left_x
+
+        self.top_left_y = top_left_y
+        self.top_left_x = top_left_x
+        self.bottom_right_y = bottom_right_y
+        self.bottom_right_x = bottom_right_x
+        self.height = height
+        self.width = width
+
+        return (top_left, bottom_right, height, width)
+
+    def is_player_near(self, y, x):
+        """
+        Applies a boundary of one around the threat zone, then checks if the
+        player is inside. This is how the threatzone activates to calculate an
+        updated graph or set of penalties for each step.
+        """
+        y_condition = (self.top_left_y - 1) <= y < (self.bottom_right_y + 1)
+        x_condition = (self.top_left_x - 1) <= x < (self.bottom_right_x + 1)
+        return y_condition and x_condition
+
+    def check_map_obstacle_has_sight(self):
+        """
+        Determines if the map object has the sight feature.
+        """
+        return self.map_obstacle.sight_range > 0
+
+    def calculate_sight_range(self):
+        """
+        Calculates the range that the object is able to see.
+        """
+        if not self.check_map_obstacle_has_sight():
+            return 0
+        else:
+            return self.map_obstacle.sight_range
+
+    def get_current_facing_direction(self, DIRECTIONS=DIRECTIONS):
+        """
+        Get the current facing direction of the map_obstacle.
+        """
+        return self.map_obstacle.get_current_facing_direction(DIRECTIONS=DIRECTIONS)
+
+    # this isn't used anywhere yet
+    def is_map_obstacle_in_screen_range(self):
+        """
+        Determines if the map_obstacle is within the bounds of whatever is on
+        screen at the moment. If the object is of a type that is capable of
+        moving, and it is not on screen, then it is not moving.
+        """
+        raise NotImplementedError
+
+    def mark_nodes_as_members_of_threat_zone(self):
+        """
+        Based on the nodes in this threat zone, mark each main graph's nodes as
+        members of this threat zone.
+        """
+
+        for y in range(self.top_left_y, self.top_left_y + self.height):
+            for x in range(self.top_left_x, self.top_left_x + self.width):
+                main_node = self.main_graph[y][x]
+                main_node.threat_zones.add(self)
+
+                self.nodes.append(main_node)
+
+    def update_obstacle_location(self):
+        """
+        Updates which node has the obstacle. This does not recompute the graph
+        based on this new information.
+
+        Each threat zone is responsible for updating its own map objects. So
+        there will never be a time when the current x value attached to the
+        map_obstacle does not represent the actual previous location.
+        """
+
+        # find the previous location of the obstacle
+        old_y = self.map_obstacle.y
+        old_x = self.map_obstacle.x
+
+        # remove it from the main graph
+        self.main_graph[old_y][old_x].contents.remove(self.map_obstacle)
+
+        # get the latest location
+        self.map_obstacle.update_location()
+        (new_y, new_x) = (self.map_obstacle.y, self.map_obstacle.x)
+
+        # add it back into the main graph
+        self.main_graph[new_y][new_x].contents.add(self.map_obstacle)
+
+        # update the map obstacle (not necessary, but it doesn't hurt)
+        self.map_obstacle.y = new_y
+        self.map_obstacle.x = new_x
+
+    def is_node_in_threat_zone(self, y, x):
+        """
+        Checks if the node is in the range of the threat zone.
+        """
+        y_condition = self.top_left_y <= y < self.top_left_y + self.height
+        x_condition = self.top_left_x <= x < self.top_left_x + self.width
+        return y_condition and x_condition
+
+    def is_node_in_sight_range(self, y, x, skip_range_check=False):
+        """
+        Checks if the node is in the sight range of the threat.
+        """
+        if not skip_range_check:
+            if not self.is_node_in_threat_zone(y, x):
+                return False
+
+        if self.sight_range == 0:
+            return False
+
+        # TODO: sight range can be blocked by collidable map objects. But this
+        # node wouldn't be in the threat zone anyway.
+        y_condition = self.map_obstacle.y == y
+        x_condition = self.map_obstacle.x == x
+
+        # this probably only happens if the player warps to the exact spot
+        if y_condition and x_condition:
+            raise Exception(
+                "Don't know the meaning of being on top of the map_obstacle."
+            )
+
+        # check if y or x matches the map object
+        return y_condition or x_condition
+
+    def is_node_in_active_sight_range(self,
+                                      y,
+                                      x,
+                                      skip_sight_range_check=False,
+                                      skip_range_check=False,
+                                      DIRECTIONS=DIRECTIONS):
+        """
+        Checks if the node has active sight range lock.
+        """
+
+        if not skip_sight_range_check:
+            # can't be in active sight range if not in sight range
+            if not self.is_in_sight_range(y, x, skip_range_check=skip_range_check):
+                return False
+
+        y_condition = self.map_obstacle.y == y
+        x_condition = self.map_obstacle.x == x
+
+        # this probably only happens if the player warps to the exact spot
+        if y_condition and x_condition:
+            raise Exception(
+                "Don't know the meaning of being on top of the map_obstacle."
+            )
+
+        current_facing_direction = self.get_current_facing_direction(DIRECTIONS=DIRECTIONS)
+
+        if current_facing_direction not in DIRECTIONS.keys():
+            raise Exception(
+                "Invalid direction."
+            )
+
+        if current_facing_direction in [DIRECTIONS["UP"], DIRECTIONS["DOWN"]]:
+            # map_obstacle is looking up/down but player doesn't match y
+            if not y_condition:
+                return False
+
+            if current_facing_direction == DIRECTIONS["UP"]:
+                return y < self.map_obstacle.y
+            elif current_facing_direction == DIRECTIONS["DOWN"]:
+                return y > self.map_obstacle.y
+        else:
+            # map_obstacle is looking left/right but player doesn't match x
+            if not x_condition:
+                return False
+
+            if current_facing_direction == DIRECTIONS["LEFT"]:
+                return x < self.map_obstacle.x
+            elif current_facing_direction == DIRECTIONS["RIGHT"]:
+                return x > self.map_obstacle.x
+
+    def calculate_node_cost(self, y, x, consider_sight_range=True, PENALTIES=PENALTIES):
+        """
+        Calculates the cost of the node w.r.t this threat zone. Turn off
+        consider_sight_range when not in the threat zone.
+        """
+        penalty = 0
+
+        # The node is probably in the threat zone because otherwise why would
+        # this cost function be called? Only the nodes that are members of the
+        # current threat zone would have a reference to this threat zone and
+        # this function.
+        if not self.is_node_in_threat_zone(y, x):
+            penalty += PENALTIES["NONE"]
+
+            # Additionally, if htis codepath is ever hit, the other node cost
+            # function will have already used the "NONE" penalty, so this would
+            # really be doubling the penalty of the node..
+            raise Exception(
+                "Didn't expect to calculate a non-threat-zone node's cost, "
+                "since this is a threat zone function."
+            )
+        else:
+            penalty += PENALTIES["THREAT_ZONE"]
+
+            if consider_sight_range:
+                if self.is_node_in_sight_range(y, x, skip_range_check=True):
+                    penalty += PENALTIES["SIGHT_RANGE"]
+
+                    params = {
+                        "skip_sight_range_check": True,
+                        "skip_range_check": True,
+                    }
+
+                    active_sight_range = self.is_node_in_active_sight_range(y, x, **params)
+
+                    if active_sight_range:
+                        penalty += PENALTIES["ACTIVE_SIGHT_RANGE"]
+
+        return penalty
+
+def create_graph(some_map):
+    """
+    Creates the array of nodes representing the in-game map.
+    """
+
+    map_height = some_map.height
+    map_width = some_map.width
+    map_obstacles = some_map.obstacles
+
+    nodes = [[None] * map_width] * map_height
+
+    # create a node representing each position on the map
+    for y in range(0, map_height):
+        for x in range(0, map_width):
+            position = (y, x)
+
+            # create a node describing this position
+            node = Node(position=position)
+
+            # store it on the graph
+            nodes[y][x] = node
+
+    # look through all moving characters, non-moving characters, and items
+    for map_obstacle in map_obstacles:
+        # all characters must start somewhere
+        node = nodes[map_obstacle.y][map_obstacle.x]
+
+        # store the map_obstacle on this node.
+        node.contents.add(map_obstacle)
+
+        # only create threat zones for moving/turning entities
+        if map_obstacle.can_move() or map_obstacle.can_turn_without_moving():
+            threat_zone = ThreatZone(map_obstacle, nodes, some_map)
+            threat_zone.mark_nodes_as_members_of_threat_zone()
+
+    some_map.nodes = nodes
+
+    return nodes
+
+class Map(object):
+    """
+    The ``Map`` class provides an interface for reading the currently loaded
+    map.
+    """
+
+    def __init__(self, cry, height, width):
+        """
+        :param cry: pokemon crystal emulation interface
+        :type cry: crystal
+        """
+        self.cry = cry
+
+        self.threat_zones = set()
+        self.obstacles = set()
+
+        self.height = height
+        self.width = width
+
+    def travel_to(self, destination_location):
+        """
+        Does path planning and figures out the quickest way to get to the
+        destination.
+        """
+        raise NotImplementedError
+
+    @staticmethod
+    def from_rom(cry, address):
+        """
+        Loads a map from bytes in ROM at the given address.
+
+        :param cry: pokemon crystal wrapper
+        """
+        raise NotImplementedError
+
+    @staticmethod
+    def from_wram(cry):
+        """
+        Loads a map from bytes in WRAM.
+
+        :param cry: pokemon crystal wrapper
+        """
+        raise NotImplementedError
+
+def broken_main():
+    """
+    An attempt at an entry point. This hasn't been sufficiently considered yet.
+    """
+    current_map = Map.from_wram(cry)
+
+    # make a graph based on the map
+    nodes = create_graph(current_map)
+
+    current_map.travel_to(destination_location)
+
+    return current_map