Shade_JS

A Python 3 and 2 Pathfinder with Pygame Example

Jan 27th, 2017
338
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #! /usr/bin/env python3
  2. # coding: utf-8
  3.  
  4. # pathfinder.py, a python pathfinder and demo by
  5. # James Spencer <jamessp [at] gmail.com>.
  6.  
  7. # To the extent possible under law, the person who associated CC0 with
  8. # pathfinder.py has waived all copyright and related or neighboring rights
  9. # to pathfinder.py.
  10.  
  11. # You should have received a copy of the CC0 legalcode along with this
  12. # work. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
  13.  
  14. from __future__ import print_function
  15. from __future__ import division
  16. from __future__ import unicode_literals
  17. from collections import deque
  18. import heapq
  19. from sys import version_info
  20.  
  21.  
  22. if version_info[0] < 3:
  23.         range = xrange
  24.  
  25.  
  26. class Config(object):
  27.     '''This class is a minimal subset of <config.py> from my project, and much
  28.    of the data herein was parsed from config files, hence the irregular
  29.    naming. Feel free top plop the dicts into a <config.py> of your own and
  30.    import it.
  31.    '''
  32.  
  33.     def __init__(self):
  34.         self.TERRAIN_CHARACTERS = {'open secret door'   : '~',
  35.                                    'closed secret door' : '§',
  36.                                    'flagstone'          : '.',
  37.                                    'stone brick'        : '#',
  38.                                    'closed door'        : '+',
  39.                                    'open door'          : '-',
  40.                                    'solid stone'        : '&'}
  41.         self.TERRAIN_COLORS = {'closed door'        : 'aqua',
  42.                                'flagstone'          : 'silver',
  43.                                'open secret door'   : 'aqua',
  44.                                'open door'          : 'aqua',
  45.                                'solid stone'        : 'black',
  46.                                'stone brick'        : 'white',
  47.                                'closed secret door' : 'aqua'}
  48.         # NOTE: This could easily be a dict where the keys are the obstructions
  49.         # and the values are the tile characters, pygame surfaces, etc.
  50.         self.OBSTRUCTION_CHARACTERS = {'closed secret door', 'stone brick',
  51.                                        'closed door', 'solid stone'}
  52.         # 16 of the DB32 colors, as they are easier on the eyes than VGA16.
  53.         self.COLORNAMES = {'white':   (255, 255, 255),
  54.                            'yellow':  (251, 242, 54),
  55.                            'fuchsia': (215, 123, 186),
  56.                            'red':     (172, 50, 50),
  57.                            'silver':  (155, 173, 183),
  58.                            'gray':    (105, 106, 106),
  59.                            'olive':   (143, 151, 74),
  60.                            'purple':  (118, 66, 138),
  61.                            'maroon':  (102, 57, 49),
  62.                            'aqua':    (96, 205, 228),
  63.                            'lime':    (153, 229, 80),
  64.                            'teal':    (48, 96, 130),
  65.                            'green':   (75, 105, 47),
  66.                            'blue':    (91, 110, 225),
  67.                            'navy':    (63, 63, 116),
  68.                            'black':   (0, 0, 0)}
  69.  
  70.  
  71. # To 'fake' my projects <config.py>
  72. config = Config()
  73.  
  74.  
  75. class Area(object):
  76.         '''The relevant to pathfinding bits of my project's Area() class. See
  77.        the example at the end to see how this is used.
  78.        '''
  79.  
  80.         def __init__(self):
  81.             self.terrain = None
  82.             self.width = None
  83.             self.height = None
  84.  
  85.  
  86. class Pathfinder(object):
  87.     '''Find a path form x1, y1 to a point or tile(s).
  88.  
  89.    area -- An instance of the Area() class. See Area() at the top, and the
  90.    pygame example at the end of the file for a minimal implementation.
  91.    c_dist -- Integer or Float, the distance of a step in a cardinal
  92.    direction.
  93.    d_dist -- Integer or Float, the distance of a step in a diagonal
  94.    direction.
  95.    obstruction_characters -- An iterable of characters that obstruct movement.
  96.    '''
  97.  
  98.     def __init__(self, area):
  99.         self.area = area    # An instance of the Area() class.
  100.         self.c_dist = 70    # Could be 70, 1.0,                10, 100, 1000.
  101.         self.d_dist = 99    # Could be 99, 1.4142135623730951, 14, 141, 1414.
  102.         self.obstruction_characters = config.OBSTRUCTION_CHARACTERS
  103.         self._unobstruct_goals = None    # Find a goal that is an obstruction.
  104.         self._cardinals = [( 0, -1, self.c_dist), ( 1,  0, self.c_dist),
  105.                            ( 0,  1, self.c_dist), (-1,  0, self.c_dist)]
  106.         self._diagonals = [(-1, -1, self.d_dist), ( 1, -1, self.d_dist),
  107.                            ( 1,  1, self.d_dist), (-1,  1, self.d_dist)]
  108.         self._directions = None          # Cardinals, or cardinals + diagonals.
  109.         self._heuristic = None           # The A-Star heuristic
  110.         self._x2, self._y2 = None, None  # Used if the goal is a point.
  111.         self._tile, self._tiles = None, None         # goal is a tile, tiles.
  112.         self._closed_set_coords = set()  # Just the coords to speed up checks.
  113.         # List of lists of parent coordinates to help retrace the path.
  114.         # NOTE: This is a literal Dijkstra map. See ._purge_private() for info.
  115.         self.__parent_map_row = [None] * self.area.width
  116.         self._closed_set_parent_map = []
  117.         self._open_set = []             # Tiles to be evaluated.
  118.         self._open_set_coords = set()   # Just the coords to speed up checks.
  119.         self._is_goal = None            # Is this tile the goal?
  120.         self._print_path_info = False   # Print info from retrace path.
  121.  
  122.     def _is_goal_point(self, current_tile):
  123.         '''Is this the goal point?
  124.  
  125.        current_tile -- List in [current + estimated distance, estimated
  126.        distance, distance so far, (current x, current y), (parent x,
  127.        parent y)] format.
  128.  
  129.        Return: Boolean. (True if the goal is found.)
  130.        '''
  131.  
  132.         return current_tile[3] == (self._x2, self._y2)
  133.  
  134.     def _is_goal_tile(self, current_tile):
  135.         '''Is this the goal tile?
  136.  
  137.        current_tile -- List in [current + estimated distance, estimated
  138.        distance, distance so far, (current x, current y), (parent x,
  139.        parent y)] format.
  140.  
  141.  
  142.        Return: Boolean. (True if the goal is found.)
  143.        '''
  144.  
  145.         cur_x1, cur_y1 = current_tile[3]
  146.  
  147.         return self.area.terrain[cur_y1][cur_x1] == self._tile
  148.  
  149.     def _is_goal_iterable(self, current_tile):
  150.         '''Is this the goal as found in the iterable?
  151.  
  152.        current_tile -- List in [current + estimated distance, estimated
  153.        distance, distance so far, (current x, current y), (parent x,
  154.        parent y)] format.
  155.  
  156.  
  157.        Return: Boolean. (True if the goal is found.)
  158.        '''
  159.  
  160.         cur_x1, cur_y1 = current_tile[3]
  161.  
  162.         return self.area.terrain[cur_y1][cur_x1] in self._tiles
  163.  
  164.     def _cardinal_heuristic(self, x1, y1, x2, y2):
  165.         '''Return the Manhattan distance.
  166.  
  167.        x1, y1, x2, y2 -- Integers. Start and end coordinates.
  168.  
  169.        Return: Integer or Float. (The distance estimate.)
  170.        '''
  171.  
  172.         d_x, d_y = abs(x1 - x2), abs(y1 - y2)
  173.  
  174.         return (d_x + d_y) * self.c_dist
  175.  
  176.     def _diagonal_heuristic(self, x1, y1, x2, y2):
  177.         '''Return a distance estimate for grids that allow diagonal movement.
  178.  
  179.        This is the 'octile heuristic' as defined on:
  180.        https://github.com/riscy/a_star_on_grids#on-an-8-connected-grid
  181.  
  182.        x1, y1, x2, y2 -- Integers. Start and end coordinates.
  183.  
  184.        1: /r/rogulikedev's RIngan suggested:
  185.        Chebyshev distance:
  186.        max(d_x, d_y) * self.c_dist
  187.  
  188.        While simple, fast, and producing an admissible heuristic, the more
  189.        diagonal the path the more an estimate would be low.
  190.  
  191.        2: /r/rogulikedev's chrisrayner suggested:
  192.        https://github.com/riscy/a_star_on_grids#on-an-8-connected-grid
  193.  
  194.        C, D = self.c_dist, self.d_dist
  195.        E = 2 * C - D
  196.        (E * abs(d_x - d_y) + D * (d_x + d_y)) / 2
  197.  
  198.        or
  199.  
  200.        B = self.d_dist - self.c_dist
  201.        C * d_x + B * d_y if d_x > d_y else
  202.        C * d_y + B * d_x
  203.  
  204.        for a more accurate estimate. I settled on the latter.
  205.  
  206.        Return: Integer or Float. (The distance estimate.)
  207.        '''
  208.  
  209.         d_x, d_y = abs(x1 - x2), abs(y1 - y2)
  210.  
  211.         # NOTE: Doing this with a max() and min() was slower on Python 3
  212.         if d_x > d_y:
  213.             return self.c_dist * d_x + (self.d_dist - self.c_dist) * d_y
  214.         else:
  215.             return self.c_dist * d_y + (self.d_dist - self.c_dist) * d_x
  216.  
  217.     def _purge_private(self):
  218.         '''Purge Pathfinder()'s private values, usually before finding a new
  219.        path.
  220.  
  221.        NOTE: self._heuristic = None preforms a Dijkstra search, set it to a
  222.        heuristic to use an A-Star search.
  223.        NOTE 2: self._closed_set_parent_map is a List of Lists initialized to
  224.        None. Tiles in ._closed_set_coords put their parent coordinates at
  225.        self._closed_set_parent_map[y][x] in (parent x, parent y) format.
  226.        '''
  227.  
  228.         self._x2, self._y2 = None, None
  229.         self._tile, self._tiles = None, None
  230.         self._heuristic = None
  231.         self._directions = None
  232.         self._open_set_coords = set()
  233.         self._open_set = []
  234.         self._closed_set_coords = set()
  235.         self._closed_set_parent_map = [self.__parent_map_row[:] for row in
  236.                                        range(self.area.height)]
  237.         self._is_goal = None
  238.         self._unobstruct_goals = None
  239.  
  240.     def _look_for_open(self, current_tile, best_path):
  241.         '''Add the eligible neighbours to open_set adjusting other tiles as
  242.        needed.
  243.  
  244.        current_tile -- List in [current + estimated distance, estimated
  245.        distance, distance so far, (current x, current y), (parent x,
  246.        parent y)] format.
  247.        best_path -- Boolean. 'True' to look for the best path. This is slower
  248.        as it involves modifying already processed tiles and possibly breaking
  249.        the heap invariant.
  250.        '''
  251.  
  252.         x, y = current_tile[3]
  253.         current_dist = current_tile[2]
  254.  
  255.         for direction in self._directions:
  256.             # NOTE: Implementing a '1' based movement cost system should be
  257.             # trivial in the following code.
  258.             x_mod, y_mod, step_dist = direction
  259.             new_x, new_y = x+x_mod, y+y_mod
  260.  
  261.             # If it's not in bounds...
  262.             if 0 > new_x == self.area.width or 0 > new_y == self.area.height:
  263.  
  264.                 continue
  265.             else:
  266.                 the_tile = self.area.terrain[new_y][new_x]
  267.  
  268.             # Or if it is in the closed_set...
  269.             if (new_x, new_y) in self._closed_set_coords:
  270.  
  271.                 continue
  272.  
  273.             # If not unobstructing goals and it hits an obstruction...
  274.             elif not self._unobstruct_goals and the_tile in\
  275.                 self.obstruction_characters:
  276.  
  277.                 continue
  278.  
  279.             # When looking for a goal find it even if it's an obstruction when
  280.             # unobstructing goals...
  281.             elif self._unobstruct_goals and the_tile in\
  282.                 self.obstruction_characters:
  283.  
  284.                 if self._x2 and self._y2 and (
  285.                      new_x, new_y) != (self._x2, self._y2):
  286.  
  287.                     continue
  288.                 elif self._tile and self.area.terrain[
  289.                      new_y][new_x] != self._tile:
  290.  
  291.                     continue
  292.                 elif self._tiles and self.area.terrain[
  293.                      new_y][new_x] not in self._tiles:
  294.  
  295.                     continue
  296.  
  297.             # Update the distance travelled
  298.             dist = current_dist + step_dist
  299.             # Generate a heuristic distance for a goal that's a point.
  300.             # NOTE: if self._heuristic == None then do a Dijkstra search
  301.             # where the heuristic distance is just the distance traveled so
  302.             # far, and the distance estimate is None.
  303.             heuristic_estimate = None
  304.             heuristic_distance = dist
  305.             if self._heuristic:
  306.                 heuristic_estimate = self._heuristic(new_x, new_y,
  307.                                                      self._x2, self._y2)
  308.                 heuristic_distance += heuristic_estimate
  309.            
  310.             # Not in the open_set so add it.
  311.             if (new_x, new_y) not in self._open_set_coords:
  312.                 self._open_set_coords.add((new_x, new_y))
  313.                 heapq.heappush(self._open_set,
  314.                                [heuristic_distance,     # Heuristic distance
  315.                                 heuristic_estimate,     # Estimated distance
  316.                                 dist,                   # Distance traveled
  317.                                 (new_x, new_y),         # (x, y)
  318.                                 (x, y)])                # (parent_x, parent_y)
  319.  
  320.                 continue
  321.             # In the open_set and we want the best path.
  322.             elif best_path and (new_x, new_y) in self._open_set_coords:
  323.                 for tile in self._open_set:
  324.                     if (new_x, new_y) == tile[3]:
  325.                         # In the open_set and better.
  326.                         if tile[2] > dist:
  327.                             tile[0] = heuristic_distance
  328.                             tile[1] = heuristic_estimate
  329.                             tile[2] = dist
  330.                             tile[4] = (x, y)
  331.                             # Turns out naively re-heapifying is faster.
  332.                             heapq.heapify(self._open_set)
  333.  
  334.                         break
  335.  
  336.     def _retrace_path(self, current_tile):
  337.         '''Retrace a path to the start.
  338.  
  339.        current_tile -- List in [current + estimated distance, estimated
  340.        distance, distance so far, (current x, current y), (parent x,
  341.        parent y)] format.
  342.  
  343.        Retrace a path to (x1, y1). A path includes the (x, y) of the goal /
  344.        target, but not that of the starting tile.
  345.  
  346.        NOTE: This will retrace the path of any tile back to the starting
  347.        point, and may be useful for a number of purposes like building
  348.        Dijkstra maps for multiple consumers.
  349.  
  350.        NOTE 2: Given python's recursion limit making this recursive is an iffy
  351.        proposition.
  352.  
  353.        Return: deque(). (A deque of (x, y) Tuples representing the path.)
  354.        '''
  355.  
  356.         parent = current_tile[4]
  357.         the_path = deque()
  358.         if parent:
  359.             # Add the endpoint.
  360.             the_path.appendleft(current_tile[3])
  361.  
  362.             while parent:
  363.                 # Add the parent until we get to to the starting x, y
  364.                 x, y = parent
  365.                 if self._closed_set_parent_map[y][x]:
  366.                     the_path.appendleft(parent)
  367.                 parent = self._closed_set_parent_map[y][x]
  368.  
  369.         if self._print_path_info:
  370.             print("\n\n==========")
  371.             print("\nCurrent:")
  372.             print(current_tile)
  373.             # print("\nOpen Set Coordinates:")
  374.             # print(self._open_set_coords)
  375.             print("\nOpen Set Length:")
  376.             print(len(self._open_set_coords))
  377.             # print("\nClosed Set Coordinates:")
  378.             # print(self._closed_set_coords)
  379.             print("\nClosed Set Length:")
  380.             print(len(self._closed_set_coords))
  381.             print("\nPath:")
  382.             print(the_path)
  383.             print("\nTile Steps:")
  384.             print(len(the_path))
  385.  
  386.         return the_path
  387.  
  388.     def _find_path(self, best_path, abort, goal_only):
  389.         '''Find a path.
  390.  
  391.        best_path -- Boolean. 'True' to look for the best path. This is slower
  392.        as it involves modifying already processed tiles and possibly breaking
  393.        the heap invariant.
  394.        abort -- False, or Integer. If the len(self._closed_set_coords) > abort
  395.        stop searching. This should stop any 'too slow' away searches.
  396.        goal_only -- Boolean. If True it will only return the (x, y, tile name)
  397.        of the goal, and not the path. Faster than retracing the path.
  398.  
  399.        Return: deque, list, or None. (A deque of (x, y) Tuples, or a Tuple of
  400.        (x, y, tile name) if goal only == true, or None if no path is found.)
  401.        '''
  402.  
  403.         while self._open_set:
  404.             current_tile = heapq.heappop(self._open_set)
  405.             self._open_set_coords.remove(current_tile[3])
  406.             x, y = current_tile[3]
  407.  
  408.             # Yay, we found the goal!
  409.             if self._is_goal(current_tile) and not goal_only:
  410.                 return self._retrace_path(current_tile)
  411.             elif self._is_goal(current_tile) and goal_only:
  412.                 return (x, y, self.area.terrain[y][x])
  413.  
  414.             # No goal, let's update the self._closed_set* and look for more
  415.             # tiles...
  416.             self._closed_set_coords.add(current_tile[3])
  417.             # Abort search. Remember False == 0.
  418.             if len(self._closed_set_coords) > abort > 0:
  419.                 return None
  420.             self._closed_set_parent_map[y][x] = current_tile[4]
  421.             self._look_for_open(current_tile, best_path)
  422.  
  423.         # Ooops, couldn't find a path!
  424.         return None
  425.  
  426.     def find_point(self, x1, y1, x2, y2, use_diagonals=True, best_path=True,
  427.                    abort=False):
  428.         '''Look for a specified point.
  429.  
  430.        x1, y1, x2, y2 -- Integers. The start and end point.
  431.        use_diagonals -- Boolean. Path including diagonal directions. This is
  432.        slower as it has to check twice the tiles.
  433.        best_path -- Boolean. 'True' to look for the best path. This is slower
  434.        as it involves modifying already processed tiles and possibly breaking
  435.        the heap invariant. If set to 'False' paths are often somewhat more
  436.        organic, and can somewhat approximate a 'greedy best first' search.
  437.        abort -- False, or Integer. If the 'len(self._closed_set_coords) >
  438.        abort' stop searching. This should stop any 'too slow' searches.
  439.  
  440.        NOTE: This performs an A-Star search as it sets self._heuristic.
  441.  
  442.        Return: deque or None. (A deque of (x, y) Tuples, or None if no path
  443.        is found.)
  444.        '''
  445.  
  446.         self._purge_private()
  447.         self._x2 = x2
  448.         self._y2 = y2
  449.         self._unobstruct_goals = False
  450.  
  451.         if use_diagonals:
  452.             self._heuristic = self._diagonal_heuristic
  453.             self._directions = set(self._cardinals + self._diagonals)
  454.         else:
  455.             self._heuristic = self._cardinal_heuristic
  456.             self._directions = set(self._cardinals)
  457.  
  458.         self._is_goal = self._is_goal_point
  459.         self._open_set_coords.add((x1, y1))
  460.         heuristic_estimate = self._heuristic(x1, y1, x2, y2)
  461.  
  462.         heapq.heappush(self._open_set,
  463.                        [0 + heuristic_estimate,         # A-Star
  464.                         heuristic_estimate,             # Distance estimate
  465.                         0,                              # Distance traveled
  466.                         (x1, y1),                       # (x, y)
  467.                         None])                          # (parent_x, parent_y)
  468.  
  469.         return self._find_path(best_path, abort, False)
  470.  
  471.     def is_point_findable(self, x1, y1, x2, y2, use_diagonals=True,
  472.                           abort=False):
  473.         '''Can the pathfider find a given point?
  474.  
  475.        NOTE: DO NOT USE THIS TO DETERMINE IF YOU SHOULD USE .find_point(), as
  476.        you will be doing a search to do a search. In that case just use
  477.        .find_point(). If you merely need to see if a tile is open please check
  478.        the Area().terrain data structure. If you need LOS cast a ray, or use
  479.        your FOV implementation. This is primarily useful for a 'blink' /
  480.        'teleport' that requires a valid path, but may not be directly seen.
  481.  
  482.        x1, y1, x2, y2 -- Integers. The start and end point.
  483.        use_diagonals -- Boolean. Path including diagonal directions. This is
  484.        slower as it has to check twice the tiles.
  485.        abort -- False, or Integer. If the 'len(self._closed_set_coords) >
  486.        abort' stop searching. This should stop any 'too slow' searches.
  487.  
  488.        NOTE 2: This performs an A-Star search as it sets self._heuristic.
  489.  
  490.        Return: Boolean. (True if the point is findable)
  491.        '''
  492.  
  493.         self._purge_private()
  494.         self._x2 = x2
  495.         self._y2 = y2
  496.         self._unobstruct_goals = False
  497.  
  498.         if use_diagonals:
  499.             self._heuristic = self._diagonal_heuristic
  500.             self._directions = set(self._cardinals + self._diagonals)
  501.         else:
  502.             self._heuristic = self._cardinal_heuristic
  503.             self._directions = set(self._cardinals)
  504.  
  505.         self._is_goal = self._is_goal_point
  506.         self._open_set_coords.add((x1, y1))
  507.         heuristic_estimate = self._heuristic(x1, y1, x2, y2)
  508.  
  509.         heapq.heappush(self._open_set,
  510.                        [0 + heuristic_estimate,         # A-Star
  511.                         heuristic_estimate,             # Distance estimate
  512.                         0,                              # Distance traveled
  513.                         (x1, y1),                       # (x, y)
  514.                         None])                          # (parent_x, parent_y)
  515.  
  516.         found = self._find_path(False, abort, True)
  517.         if found:
  518.             return True
  519.         else:
  520.             return False
  521.  
  522.     def find_tile(self, x1, y1, tile, use_diagonals=True, best_path=True,
  523.                   abort=False):
  524.         '''Look for a specified tile, or tile in an iterable of tiles.
  525.  
  526.        x1, y1 -- Integers. The start point.
  527.        tile -- String or Iterable. The tile, or an iterable of tiles, being
  528.        sought.
  529.        use_diagonals -- Boolean. Path including diagonal directions. This is
  530.        slower as it has to check twice the tiles.
  531.        best_path -- Boolean. 'True' to look for the best path. This is slower
  532.        as it involves modifying already processed tiles and possibly breaking
  533.        the heap invariant. If set to 'False' paths are often somewhat more
  534.        organic, and can somewhat approximate a 'greedy best first' search.
  535.        abort -- False, or Integer. If the 'len(self._closed_set_coords) >
  536.        abort' stop searching. This should stop any 'too slow' searches.
  537.  
  538.        NOTE: This performs an Dijkstra search as it doesn't set
  539.        self._heuristic.
  540.  
  541.        Return: deque or None. (A deque of (x, y) Tuples, or None if no path
  542.        is found.)
  543.        '''
  544.  
  545.         self._purge_private()
  546.  
  547.         if type(tile) == str:
  548.             self._tile = tile
  549.             self._is_goal = self._is_goal_tile
  550.         else:
  551.             self._tiles = tile
  552.             self._is_goal = self._is_goal_iterable
  553.  
  554.         self._unobstruct_goals = True
  555.  
  556.         if use_diagonals:
  557.             self._directions = set(self._cardinals + self._diagonals)
  558.         else:
  559.             self._directions = set(self._cardinals)
  560.  
  561.         self._open_set_coords.add((x1, y1))
  562.  
  563.         heapq.heappush(self._open_set,
  564.                        [0,                              # Dijkstra
  565.                         None,                           # Distance estimate
  566.                         0,                              # Distance traveled
  567.                         (x1, y1),                       # (x, y)
  568.                         None])                          # (parent_x, parent_y)
  569.  
  570.         return self._find_path(best_path, abort, False)
  571.  
  572.     def nearest(self, x1, y1, tile, use_diagonals=True, abort=False):
  573.         '''Look for a specified tile, or tile in an iterable of tiles, and
  574.        return the location and name of that tile.
  575.  
  576.        x1, y1 -- Integers. The start point.
  577.        tile -- String or Iterable. The tile, or an iterable of tiles, being
  578.        sought.
  579.        use_diagonals -- Boolean. Path including diagonal directions. This is
  580.        slower as it has to check twice the tiles.
  581.        abort -- False, or Integer. If the len(self._closed_set_coords) >
  582.        abort stop searching. This should stop any 'too slow' away searches.
  583.  
  584.        NOTE: This performs an Dijkstra search as it doesn't set
  585.        self._heuristic.
  586.  
  587.        Return: Tuple or None. (A Tuple of (x, y, tile name), or None.)
  588.        '''
  589.  
  590.         self._purge_private()
  591.  
  592.         if type(tile) == str:
  593.             self._tile = tile
  594.             self._is_goal = self._is_goal_tile
  595.         else:
  596.             self._tiles = tile
  597.             self._is_goal = self._is_goal_iterable
  598.  
  599.         self._unobstruct_goals = True
  600.  
  601.         if use_diagonals:
  602.             self._directions = set(self._cardinals + self._diagonals)
  603.         else:
  604.             self._directions = set(self._cardinals)
  605.  
  606.         self._open_set_coords.add((x1, y1))
  607.  
  608.         heapq.heappush(self._open_set,
  609.                        [0,                              # Dijkstra
  610.                         None,                           # Distance estimate
  611.                         0,                              # Distance traveled
  612.                         (x1, y1),                       # (x, y)
  613.                         None])                          # (parent_x, parent_y)
  614.  
  615.         return self._find_path(False, abort, True)
  616.  
  617.  
  618. if __name__ == '__main__':
  619.     '''Test the Pathfinder Class.'''
  620.  
  621.     dun = ["#########################################################&#######",
  622.            "#.......#...#.........#...........#...............#.....#&#.-...#",
  623.            "#######.~...#........#..........#...................#...#&#.#...#",
  624.            "&&&&&&#.#...........#...........#~###################...###.#####",
  625.            "#######.#...#####.##............#...................#.....§.....#",
  626.            "#.......#...#&&#....##..........#...................#.....#####-#",
  627.            "#####+###...####....##.......#####################..#.....#.....#",
  628.            "#..##........................#&&#................#..#.....#.....#",
  629.            "#...##...........#########...####.............#..#..#.....#.....#",
  630.            "#....##..................#......#..###############..#.....#.....#",
  631.            "#.....##.................#.#....#..#...#...#...#....#.....#.....#",
  632.            "#......##.......#######..#.#....#....#...#...#...#..#.....#.##..#",
  633.            "#...............#&&&&&#..#.#....#####################.....#.##..#",
  634.            "#........#####..#&&&&&#..#.#.............#................##.#..#",
  635.            "#........#&&&#..#######....#.............#................#.##..#",
  636.            "#........#####.............#####.....#...#...#....###...####.#..#",
  637.            "#..............##########.............#..#..#.....#&#...#&#.##..#",
  638.            "#..............#........#..............#...#......###...####.#..#",
  639.            "#.##...###..####........#..#####........#.#...............#..#..#",
  640.            "#..............-........§..#........############..........####..#",
  641.            "####.#.........#........#..#........#....#.....#.########.......#",
  642.            "#.....#........##########..#.............#.......#&&#..###-####+#",
  643.            "#.....##...................#.............#.......#####.#&#......#",
  644.            "#.......#..................#.............#.......~.....#&#......#",
  645.            "########################################################&########"]
  646.  
  647.     import pygame
  648.     from pygame.locals import *
  649.     import time
  650.     from fnmatch import filter
  651.     from sys import exit
  652.  
  653.     # Translate the character based map into Area().terrain tile names.
  654.     # Tile names are used to avoid character clashes in more complex maps.
  655.     rev = {}
  656.     tmp_terrain = []
  657.  
  658.     for tile in config.TERRAIN_CHARACTERS:
  659.         tmp = config.TERRAIN_CHARACTERS[tile]
  660.         rev[tmp] = tile
  661.  
  662.     for y in range(len(dun)):
  663.         tmp_terrain.append([])
  664.         for x in range(len(dun[y])):
  665.             tmp_terrain[y].append(rev[dun[y][x]])
  666.  
  667.     test_area = Area()
  668.     test_area.terrain = tmp_terrain
  669.     test_area.width = len(tmp_terrain[0])
  670.     test_area.height = len(tmp_terrain)
  671.  
  672.     # An instance of the pathfinder.
  673.     pathfinder = Pathfinder(test_area)
  674.  
  675.     # Initialize Pygame.
  676.     pygame.display.init()
  677.     pygame.font.init()
  678.  
  679.     clock = pygame.time.Clock()
  680.  
  681.     pygame.display.set_caption("Pathfinding Test")
  682.  
  683.     chosen_font = None
  684.     installed_fonts = pygame.font.get_fonts()
  685.  
  686.     # Pick the first font from font_names, or the first font with *mono* in
  687.     # the name.
  688.     print("\nFONTS WITH MONO IN THE NAME:\n"
  689.           "============================")
  690.     print(filter(installed_fonts, "*mono*"))
  691.     first_mono = filter(installed_fonts, "*mono*")[0]
  692.  
  693.     font_names = ["dejavusansmono",
  694.                   "liberationmono",
  695.                   "andalemono",
  696.                   "lucidamono",
  697.                   "notomono",
  698.                   first_mono]
  699.  
  700.     chosen_font = pygame.font.match_font(
  701.         [font_name for font_name in font_names if font_name in installed_fonts]
  702.         [0])
  703.  
  704.     print("\nFONT:\n"
  705.           "=====")
  706.     print("Using font: " + chosen_font + '\n')
  707.  
  708.     font_size = 20
  709.     font = pygame.font.Font(chosen_font, font_size)
  710.     font_w, font_h = font.size(" ")
  711.  
  712.     font_size2 = 14
  713.     font2 = pygame.font.Font(chosen_font, font_size2)
  714.  
  715.     # The goal and player x and y.
  716.     gx, gy = 8, 8
  717.     px, py = 10, 10
  718.  
  719.     default_fps = 60
  720.  
  721.     R_color = 'red'
  722.     G_color = 'lime'
  723.     B_color = 'blue'
  724.     F_color = 'fuchsia'
  725.  
  726.     pygame.key.set_repeat(250, 1000 // default_fps)
  727.  
  728.     win = pygame.display.set_mode((test_area.width * font_w,
  729.                                    (test_area.height + 1) * font_h))
  730.  
  731.     win.fill(config.COLORNAMES['black'])
  732.     txt1 = font.render("WSAD to move 'Ω', and ↑↓←→ to move '@'.", True,
  733.                        config.COLORNAMES['white'])
  734.     txt2 = font.render("Press an any key to begin...", True,
  735.                        config.COLORNAMES['white'])
  736.     win.blit(txt1, (0, font_h * 5))
  737.     win.blit(txt2, (0, font_h * 7))
  738.  
  739.     pygame.display.flip()
  740.  
  741.     pad_h = test_area.height - 3
  742.     pad_w = test_area.width - 3
  743.  
  744.     wait = True
  745.     while wait:
  746.         for event in pygame.event.get():
  747.             clock.tick(default_fps)
  748.             if event.type == KEYDOWN:
  749.                     wait = False
  750.  
  751.     win.fill(config.COLORNAMES['black'])
  752.  
  753.     # The main loop.
  754.     while True:
  755.         # Set the FPS
  756.         clock.tick(default_fps)
  757.  
  758.         for event in pygame.event.get():
  759.             if (event.type == QUIT or event.type == KEYDOWN and
  760.                     event.key == K_ESCAPE):
  761.                 pygame.quit()
  762.                 exit()
  763.  
  764.             if event.type == KEYDOWN:
  765.                 if event.key == K_UP:
  766.                     if py > 1:
  767.                         py -= 1
  768.                 elif event.key == K_DOWN:
  769.                     if py <= pad_h:
  770.                         py += 1
  771.                 elif event.key == K_LEFT:
  772.                     if px > 1:
  773.                         px -= 1
  774.                 elif event.key == K_RIGHT:
  775.                     if px <= pad_w:
  776.                         px += 1
  777.                 elif event.unicode == 'w':
  778.                     if gy > 1:
  779.                         gy -= 1
  780.                 elif event.unicode == 's':
  781.                     if gy <= pad_h:
  782.                         gy += 1
  783.                 elif event.unicode == 'a':
  784.                     if gx > 1:
  785.                         gx -= 1
  786.                 elif event.unicode == 'd':
  787.                     if gx <= pad_w:
  788.                         gx += 1
  789.  
  790.                 # Calculate and (crudely) time the paths.
  791.                 t1 = time.time()
  792.                 # Find the Goal 'Ω'
  793.                 r1 = pathfinder.is_point_findable(px, py, gx, gy,
  794.                                                   use_diagonals=True,
  795.                                                   abort=False)
  796.                 t2 = time.time()
  797.                 # Red Path
  798.                 r2 = pathfinder.find_point(px, py, gx, gy,
  799.                                            best_path=True,
  800.                                            use_diagonals=True,
  801.                                            abort=False)
  802.                 t3 = time.time()
  803.                 # Green Path
  804.                 r3 = pathfinder.find_tile(px, py, 'open door',
  805.                                           best_path=True,
  806.                                           use_diagonals=True,
  807.                                           abort=False)
  808.                 t4 = time.time()
  809.                 # Blue Path
  810.                 r4 = pathfinder.find_tile(px, py, ['closed door',
  811.                                                    'closed secret door'],
  812.                                           best_path=True,
  813.                                           use_diagonals=True,
  814.                                           abort=False)
  815.                 t5 = time.time()
  816.                 # Fuchsia Path
  817.                 r5 = pathfinder.nearest(px, py, 'open secret door',
  818.                                         use_diagonals=True,
  819.                                         abort=False)
  820.                 t6 = time.time()
  821.  
  822.                 win.fill(config.COLORNAMES['black'])
  823.  
  824.                 # Display the area on the given window.
  825.                 for x1 in range(test_area.width):
  826.                     for y1 in range(test_area.height):
  827.  
  828.                         char = None
  829.  
  830.                         if r2 and (x1, y1) in r2:
  831.                             color = R_color
  832.                         elif r3 and (x1, y1) in r3:
  833.                             color = G_color
  834.                         elif r4 and (x1, y1) in r4:
  835.                             color = B_color
  836.                         elif r5 and (x1, y1) ==\
  837.                             (r5[0], r5[1]):
  838.                             color = F_color
  839.                         else:
  840.                             color = config.TERRAIN_COLORS[
  841.                                         test_area.terrain[y1][x1]]
  842.  
  843.                         char = config.TERRAIN_CHARACTERS[
  844.                             test_area.terrain[y1][x1]]
  845.  
  846.                         if x1 == px and y1 == py:
  847.                             color = 'yellow'
  848.                             char = '@'
  849.  
  850.                         elif x1 == gx and y1 == gy:
  851.                             color = 'teal'
  852.                             char = 'Ω'
  853.  
  854.                         if char:
  855.                             char_surf = font.render(char, True,
  856.                                                     config.COLORNAMES[color])
  857.                             win.blit(char_surf, (x1 * font_w, y1 * font_h))
  858.  
  859.                 goal_found = 'False'
  860.                 if r1:
  861.                     goal_found = str(round(t2 - t1, 4))
  862.  
  863.                 txt = ('|R Path in: ' +
  864.                        str(round(t3 - t2, 4)) +
  865.                        ' |G Path in: ' +
  866.                        str(round(t4 - t3, 4)) +
  867.                        ' |B Path in: ' +
  868.                        str(round(t5 - t4, 4)) +
  869.                        ' |F Path in: ' +
  870.                        str(round(t6 - t5, 4)) +
  871.                        ' |Ω Found in: ' +
  872.                        goal_found + ' |')
  873.  
  874.                 txt3 = font2.render(txt, True, config.COLORNAMES['white'])
  875.                 win.blit(txt3, (0, font_h * test_area.height))
  876.  
  877.                 pygame.display.flip()
RAW Paste Data