Package horizons :: Package ai :: Package aiplayer :: Module roadplanner
[hide private]
[frames] | no frames]

Source Code for Module horizons.ai.aiplayer.roadplanner

  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 heapq 
 23   
 24   
25 -class RoadPlanner:
26 """ 27 Finds the most reasonable road between two areas. 28 29 This class uses the A* algorithm to find a path that would look nice as a road. 30 Penalties are give for the following: 31 * not an existing road 32 * close to an existing road 33 * not straight 34 * not close to boundaries (coast, mountains, etc.) 35 """ 36
37 - def __call__(self, personality, source, destination, destination_beacon, path_nodes, blocked_coords=None):
38 """ 39 Return the path from the source to the destination or None if it is impossible. 40 41 @param personality: the personality class that contains the relevant personality bits 42 @param source: list of tuples [(x, y), ...] 43 @param destination: list of tuples [(x, y), ...] 44 @param destination_beacon: object with a defined distance_to_tuple function (must contain all of destination) 45 @param path_nodes: dict {(x, y): penalty} 46 @param blocked_coords: temporarily blocked coordinates set([(x, y), ...]) 47 """ 48 blocked_coords = blocked_coords or set() 49 target_blocked = True 50 for coords in destination: 51 if coords not in blocked_coords and coords in path_nodes: 52 target_blocked = False 53 break 54 if target_blocked: 55 return None 56 57 distance = {} 58 beacon_tuple_distance_func = destination_beacon.get_distance_function((0, 0)) 59 heap = [] 60 for coords in source: 61 if coords not in blocked_coords and coords in path_nodes: 62 for dir in range(2): # 0 -> changed x, 1 -> changed y 63 real_distance = path_nodes[coords] 64 expected_distance = beacon_tuple_distance_func(destination_beacon, coords) 65 key = (coords[0], coords[1], dir) 66 # the value is (real distance so far, previous key) 67 distance[key] = (real_distance, None) 68 # (expected distance to the destination, current real distance, key) 69 heap.append((expected_distance, real_distance, key)) 70 heapq.heapify(heap) 71 72 moves = [(-1, 0), (0, -1), (0, 1), (1, 0)] 73 final_key = None 74 75 # perform A* 76 while heap: 77 (_, distance_so_far, key) = heapq.heappop(heap) 78 if distance[key][0] < distance_so_far: 79 continue 80 if (key[0], key[1]) in destination: 81 final_key = key 82 break 83 84 for dir in range(4): 85 coords = (key[0] + moves[dir][0], key[1] + moves[dir][1]) 86 if coords not in path_nodes or coords in blocked_coords: 87 continue 88 reduced_dir = 0 if moves[dir][0] != 0 else 1 89 next_key = (coords[0], coords[1], reduced_dir) 90 real_distance = distance_so_far + path_nodes[coords] + (0 if reduced_dir == key[2] else personality.turn_penalty) 91 expected_distance = real_distance + beacon_tuple_distance_func(destination_beacon, coords) 92 if next_key not in distance or distance[next_key][0] > real_distance: 93 distance[next_key] = (real_distance, key) 94 heapq.heappush(heap, (expected_distance, real_distance, next_key)) 95 96 # save path 97 if final_key is not None: 98 path = [] 99 while final_key is not None: 100 path.append((final_key[0], final_key[1])) 101 final_key = distance[final_key][1] 102 return path 103 return None
104