Package horizons :: Package util :: Package pathfinding :: Module pathfinder
[hide private]
[frames] | no frames]

Source Code for Module horizons.util.pathfinding.pathfinder

  1  # ################################################### 
  2  # Copyright (C) 2008-2017 The Unknown Horizons Team 
  3  # team@unknown-horizons.org 
  4  # This file is part of Unknown Horizons. 
  5  # 
  6  # Unknown Horizons is free software; you can redistribute it and/or modify 
  7  # it under the terms of the GNU General Public License as published by 
  8  # the Free Software Foundation; either version 2 of the License, or 
  9  # (at your option) any later version. 
 10  # 
 11  # This program is distributed in the hope that it will be useful, 
 12  # but WITHOUT ANY WARRANTY; without even the implied warranty of 
 13  # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
 14  # GNU General Public License for more details. 
 15  # 
 16  # You should have received a copy of the GNU General Public License 
 17  # along with this program; if not, write to the 
 18  # Free Software Foundation, Inc., 
 19  # 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
 20  # ################################################### 
 21   
 22  import collections 
 23  import heapq 
 24   
 25  # the values are based on the configurations of the first two of the three sets of relative coordinates (previous, current, next) 
 26  COUNTERCLOCKWISE_TURNS = [((0, 0), (0, 1)), ((0, 1), (1, 1)), ((1, 0), (0, 0)), ((1, 1), (1, 0))] 
 27   
 28   
29 -def is_preferred_turn(previous_coords, current_coords, next_coords, clockwise):
30 """Returns True if and only if the turn is in the preferred direction.""" 31 min_x = min(previous_coords[0], current_coords[0], next_coords[0]) 32 min_y = min(previous_coords[1], current_coords[1], next_coords[1]) 33 relative_previous_coords = (previous_coords[0] - min_x, previous_coords[1] - min_y) 34 relative_current_coords = (current_coords[0] - min_x, current_coords[1] - min_y) 35 return ((relative_previous_coords, relative_current_coords) in COUNTERCLOCKWISE_TURNS) ^ clockwise
36 37
38 -def a_star_find_path(source, destination, nodes, clockwise=True):
39 """ 40 Finds the shortest path that should be most preferred by human players. 41 42 Return the path from the source to the destination or None if it is impossible. 43 44 @param source: (x, y) 45 @param destination: (x, y) 46 @param nodes: object that provides __contains__ (dict, list) with items (x, y) 47 @param clockwise: bool; whether to try finding the path clockwise or counterclockwise 48 """ 49 assert isinstance(nodes, collections.abc.Container) 50 51 if source not in nodes or destination not in nodes: 52 return None 53 if source == destination: 54 return [source] 55 56 distance = {} 57 heap = [] 58 for direction in range(2): # 0 -> changed x, 1 -> changed y 59 # NOTE: all distances are in the form (actual distance, number of turns, number of non-preferred turns) 60 real_distance = (1, 0, 0) 61 expected_distance = (((source[0] - destination[0]) ** 2 + (source[1] - destination[1]) ** 2) ** 0.5, 0, 0) 62 key = (source[0], source[1], direction) 63 # the value is (real distance so far, previous key) 64 distance[key] = (real_distance, None) 65 # (expected distance to the destination, current real distance, key) 66 heap.append((expected_distance, real_distance, key)) 67 heapq.heapify(heap) 68 69 moves = [(-1, 0), (0, -1), (0, 1), (1, 0)] 70 final_key = None 71 72 # perform A* 73 while heap: 74 (_, distance_so_far, key) = heapq.heappop(heap) 75 if distance[key][0] < distance_so_far: 76 continue 77 if (key[0], key[1]) == destination: 78 final_key = key 79 break 80 81 for direction in range(4): 82 coords = (key[0] + moves[direction][0], key[1] + moves[direction][1]) 83 if coords not in nodes: 84 continue 85 reduced_dir = 0 if moves[direction][0] != 0 else 1 86 next_key = (coords[0], coords[1], reduced_dir) 87 88 # determine whether this is a turn and if so then whether it is in the preferred direction 89 turn = reduced_dir != key[2] 90 if turn and distance[key][1] is None: 91 continue # disallow turning as the first step; doesn't affect the ability to find the best path 92 good_turn = is_preferred_turn(distance[key][1][:2], key[:2], coords, clockwise) if turn else True 93 94 # NOTE: all distances are in the form (actual distance, number of turns, number of non-preferred turns) 95 real_distance = (distance_so_far[0] + 1, distance_so_far[1] + (1 if turn else 0), distance_so_far[2] + (0 if good_turn else 1)) 96 expected_distance = (real_distance[0] + ((coords[0] - destination[0]) ** 2 + (coords[1] - destination[1]) ** 2) ** 0.5, real_distance[1], real_distance[2]) 97 if next_key not in distance or distance[next_key][0] > real_distance: 98 distance[next_key] = (real_distance, key) 99 heapq.heappush(heap, (expected_distance, real_distance, next_key)) 100 101 # save path 102 if final_key is not None: 103 path = [] 104 while final_key is not None: 105 path.append(final_key[:2]) 106 final_key = distance[final_key][1] 107 return path 108 return None
109