A Python 3 and 2 Pathfinder with Pygame Example

From RogueBasin
Revision as of 11:32, 28 January 2017 by Shade (Talk | contribs)

Jump to: navigation, search

by James Spencer

Originally my Roguelike had a pathfinder that predated me even starting to write a Roguelike. It suffered badly from being both my first serious pathfinder and some of my earliest Python code. Layer on a raft of incremental additions, and it got complicated and weird, and well, it had to go. I intend to use this pathfinder as a base for any personal Python project that requires pathfinder. I designed this pathfinder to take advantage of the similarities between A-Star and Dijkstra pathfinding, while leveraging the high level nature of Python to make the actual search functions as simple and pseudocode like as possible. This implementation is designed to work on grid based worlds (with the concept of distance as opposed to steps), though extending it to work with hex based worlds would be trivial. It is intended to be minimal and comprehensible, and doesn't include any provisions for variable movement costs though they would be easy to add.

Secondly, let me make it clear that this is not intended as a tutorial on A-Star pathfinding or Dijkstra pathfinding, it is intended as a pure python pathfinder that is: 1) drop in ready, 2) easily modifiable, and 3) fast enough.

If you are interested in tutorials on pathfinding I would suggest:


The Pathfinder(Area()) class has four public functions:

  1. find_point(self, x1, y1, x2, y2, use_diagonals=True, best_path=True, abort=False)
  2. is_point_findable(self, x1, y1, x2, y2, use_diagonals=True, abort=False)
  3. find_tile(self, x1, y1, tile, use_diagonals=True, best_path=True, abort=False)
  4. nearest(self, x1, y1, tile, use_diagonals=True, abort=False)

All of these functions are documented in the code. In short, 'find_point()' will return deque() with a path from x1, y1 to x2, y2 (or None if no path is found), 'is_point_findable()' will return a Boolean if a point can be found, 'find_tile()' will return deque() with a path from x1, y1 to the nearest tile (or tile in an iterable of tiles) as specified by 'tile' (or None if no path is found), and finally 'nearest()' will look for a tile (or tile in an iterable of tiles) and return a Tuple of '(x, y, tile name)' (or None if no tile is found).

Both 'find_point()' and 'is_point_findable()' use an A-Star search, while 'find_tile()' and 'nearest()' use a Dijkstra search. As was mentioned this implementation is designed for grid based worlds, and is distance aware, meaning that it will generate paths based on the shortest distance as opposed to the fewest steps. While largely moot for cardinal only movement, this does have implications when diagonal movement is allowed (use_diagonals == True).


Pathfinder Implementation Notes:

  • The actual pathfinder only requires Python, and the example requires Python and Pygame. Pygame should be installable via 'pip'.
  • The pathfinder expects an 'Area()' class where: 'area.terrain' is a list of lists of terrain names (like a 2D array), 'area.width' is the width of a rectangular area, and 'area.height' is the height of a rectangular area.
  • The pathfinder expects a 'config.OBSTRUCTION_CHARACTERS' set / tuple / list, where the members are tiles that can't be pathed through. This could also be dictionary where the keys are the tiles that can't be pathed through, and the values can be whatever you want (with good ideas being the character representation of the tile or a Pygame surface with the tile's graphic).
  • The pathfinder is designed to be flexible. Thus setting 'self._directions' makes it easy to choose between searching cardinal directions versus searching cardinal and diagonal directions, setting 'self._heuristic' makes it easy to do a Dijkstra search ('self._heuristic == None') or to assign an appropriate heuristic for and A-Star search, and setting 'self._is_goal' lets you discriminate goals that are points, tiles, or a tile in an iterable of tiles.
  • The pathfinder internally has 'self._closed_set' and 'self._closed_set_coords', and 'self._open_set' and 'self._open_set_coords'. This is Python specific. Testing for inclusion in a set in Python is fast necessitating the use of 'self._closed_set_coords' and 'self._open_set_coords'. Meanwhile Python's heapq wants hashable objects to sort necessitating 'self._closed_set' and 'self._open_set'.
  • 'self._closed_set_parent_map' is a list of list that is set to 'None' unless a tile has a parent that leads to the origin of a search, then it has an (x, y) Tuple of the parent's coordinates. This is basically a Dijkstra map and is mostly used to help retrace the path.
  • '._look_for_open' tries to avoid unnecessary sorting of the '._open_set' by checking to see if the heap's list order is still valid after a value is modified (as is generally the case). While this checking does incur a performance cost it is generally preferable to naively re-heapifying the '._open_set' when a value changes, especially for bigger searches.
  • Setting 'self._print_path_info = True' will print info about a found path from '_retrace_path' to the console.
  • If you want to implement variable movement costs is should be trivial if you modify '_look_for_open' at about Line 203. A 1.0 based movement system, where 1.0 is the the fastest possible movement for any given tile, and where slower terrains have a higher modifier (1.1, 1.3, etc.), should be relatively straightforward to implement.
  • if '._unobstruct_goals == True' then a goal (point, tile, iterable of tiles) will be found even if it is an obstruction. This is set to 'False' for 'find_point' and 'is_point_findable' and 'True' for 'find_tile' and 'nearest' under the assumption that if you're specifically looking for an obstruction you probably want to find it.


Example Implementation Notes:

  • Since the example doesn't bundle a font it looks for: "dejavusansmono", "liberationmono", "andalemono", "lucidamono", "notomono", and finally the first font with 'mono' in the name. If the display is hideous a list of fonts with mono in the name is printed to the console. Add a reasonable choice from that list to 'font_names' (Line 671).
  • The example times 4 functions by default, and colours the paths / found tiles. '|R Path' is the red path, '|G Path' the green path, '|B Path' is the blue path, and '|F Path' is the fuchsia (which by default is looking for the nearest 'open secret door' and not a path). The relevant code starts on Line 766 and should be easy to modify.


Image of the Pygame Example:

Pathfinding Test.png


Thoughts on Performance:

There is 1 unavoidable fact about this pathfinder: it's written in Python and not C. While it aims to be efficient Python, it will be considerably slower than any reasonable C implementation. With that being said, I don't consider it too slow for a traditional roguelike or most other turn based games, and it does bring to the table all of the advantages Python has to offer.

There are steps developers can take to mitigate any excessive slowness in this implementation. In rough order of preference (with 1-6 being reasonable, and 7-10 being more heavy handed, IMHO):

  1. Avoid recalculating paths. Both 'find_point' and 'find_tile' return a deque of (x, y) Tuples. Don't recalculate every step, just validate the next step (or maybe a few steps ahead for smarter creatures). Python's deque has a fast '.popleft()' that should come in handy for path consumers.
  2. Do you need to use diagonal movement? If not you'll get a > 40% speedup with 'use_diagonals=False'. Do you need the best path? If not you get a < 10% speedup with 'best_path=False'. If 'best_path == False' paths will tend to veer slightly toward the goal. This may actually be desirable for more organic looking paths.
  3. Do you still need diagonal movement and the best path when both the player and a creature can't see each other?
  4. Can more of your creatures be at rest until the player comes into view?
  5. Can you limit searches to a certain "as the crow flies" distance?
  6. It would be easy to make a function that produces Dijkstra maps of a given area to ANY given point. You could use these Dijkstra maps as pre-calculated paths fixed to waypoints.
  7. Can you make maps that are less twisty, maze like, and / or with fewer culs-de-sac?
  8. 'abort=' can be set to stop a long search based on the size of the '._closed_set'.
  9. Even without multiprocessing it would be relatively easy to write '_find_path_bipolar' and a 'find_point_bipolar' that searches from the start to the goal and the goal to the start. Such a search would terminate when the goal is found, or when they share an entry in the closed set. Given how an A-Star frontier expands, even without multiprocessing, it should help reduce then number of bad paths explored in maps that are twisty, maze like, and / or have culs-de-sac.
  10. You could leverage Python's 'multiprocessing' module and have one or more processes dedicated to calculating paths while you're game's main process continues on with other work until paths are calculated. Use this to pre-calculate paths where possible.


Pastebin Link to the Code:

http://pastebin.com/jHeKc6j0


The Full Code Follows Below:

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

Even if your language of choice isn't Python, I hope you find this pathfinder helpful to your endeavours. Cheers!

Personal tools