Package horizons :: Package world :: Package buildability :: Module partialbinarycache
[hide private]
[frames] | no frames]

Source Code for Module horizons.world.buildability.partialbinarycache

  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  from horizons.world.buildability.terraincache import TerrainBuildabilityCache 
23 24 25 -class PartialBinaryBuildabilityCache:
26 """ 27 A cache that knows where rectangles can be placed such that they are entirely inside the area. 28 29 This cache can be used to keep track of building buildability in case the 30 buildability depends on the building being at least partly within a certain area. 31 The binary part of the name refers to the fact that a node either is or isn't part of 32 the area that the instance is about. 33 34 A query of the form (x, y) in instance.cache[(width, height)] is a very cheap way of 35 finding out whether a rectangle of size (width, height) can be placed on origin (x, y) 36 such that at least some part of it is within the given area. 37 38 All elements of instance.cache[(width, height)] can be iterated to get a complete list 39 of all such coordinates. 40 """ 41
42 - def __init__(self, terrain_cache):
43 self.terrain_cache = terrain_cache 44 self.coords_set = set() # set((x, y), ...) 45 self._row2 = set() 46 47 sizes = set(TerrainBuildabilityCache.sizes) 48 # extra sizes for the intermediate computation 49 sizes.add((3, 4)) 50 sizes.add((4, 5)) 51 sizes.add((5, 5)) 52 sizes.add((5, 6)) 53 54 self.cache = {} # {(width, height): set((x, y), ...), ...} 55 self.cache[(1, 1)] = self.coords_set 56 for size in sizes: 57 if size != (1, 1): 58 self.cache[size] = set() 59 if size[0] != size[1]: 60 self.cache[(size[1], size[0])] = set()
61 62 @classmethod
63 - def _extend_set(cls, cur_set, prev_set_additions, dx, dy):
64 base_set_additions = set() 65 for coords in prev_set_additions: 66 x, y = coords 67 prev_coords = (x - dx, y - dy) 68 if prev_coords not in cur_set: 69 cur_set.add(prev_coords) 70 base_set_additions.add(prev_coords) 71 next_coords = (x + dx, y + dy) 72 if next_coords not in prev_set_additions and coords not in cur_set: 73 cur_set.add(coords) 74 base_set_additions.add(coords) 75 return base_set_additions
76
77 - def add_area(self, new_coords_list):
78 """Add a list of new coordinates to the area.""" 79 for coords in new_coords_list: 80 assert coords not in self.coords_set 81 assert coords in self.terrain_cache.land_or_coast 82 self.coords_set.add(coords) 83 84 added_coords_set = set(new_coords_list) 85 new_row2 = self._extend_set(self._row2, added_coords_set, 1, 0) 86 new_r2x2 = self._extend_set(self.cache[(2, 2)], new_row2, 0, 1) 87 88 new_r2x3 = self._extend_set(self.cache[(2, 3)], new_r2x2, 0, 1) 89 new_r2x4 = self._extend_set(self.cache[(2, 4)], new_r2x3, 0, 1) 90 91 new_r3x2 = self._extend_set(self.cache[(3, 2)], new_r2x2, 1, 0) 92 new_r4x2 = self._extend_set(self.cache[(4, 2)], new_r3x2, 1, 0) 93 94 new_r3x3 = self._extend_set(self.cache[(3, 3)], new_r3x2, 0, 1) 95 96 # the further sizes are created just to support 4x4 and 6x6 buildings 97 new_r3x4 = self._extend_set(self.cache[(3, 4)], new_r3x3, 0, 1) 98 new_r4x4 = self._extend_set(self.cache[(4, 4)], new_r3x4, 1, 0) 99 new_r4x5 = self._extend_set(self.cache[(4, 5)], new_r4x4, 0, 1) 100 new_r5x5 = self._extend_set(self.cache[(5, 5)], new_r4x5, 1, 0) 101 new_r5x6 = self._extend_set(self.cache[(5, 6)], new_r5x5, 0, 1) 102 self._extend_set(self.cache[(6, 6)], new_r5x6, 1, 0)
103 104 @classmethod
105 - def _reduce_set(cls, cur_set, prev_set, prev_set_removals, dx, dy):
106 base_set_removals = set() 107 for coords in prev_set_removals: 108 x, y = coords 109 prev_coords = (x - dx, y - dy) 110 if prev_coords not in prev_set: 111 cur_set.discard(prev_coords) 112 base_set_removals.add(prev_coords) 113 next_coords = (x + dx, y + dy) 114 if next_coords not in prev_set_removals and next_coords not in prev_set: 115 cur_set.discard(coords) 116 base_set_removals.add(coords) 117 return base_set_removals
118
119 - def remove_area(self, removed_coords_list):
120 """Remove a list of existing coordinates from the area.""" 121 for coords in removed_coords_list: 122 assert coords in self.coords_set 123 assert coords in self.terrain_cache.land_or_coast 124 self.coords_set.discard(coords) 125 removed_coords_set = set(removed_coords_list) 126 127 removed_row2 = self._reduce_set(self._row2, self.coords_set, removed_coords_set, 1, 0) 128 removed_r2x2 = self._reduce_set(self.cache[(2, 2)], self._row2, removed_row2, 0, 1) 129 130 removed_r2x3 = self._reduce_set(self.cache[(2, 3)], self.cache[(2, 2)], removed_r2x2, 0, 1) 131 removed_r2x4 = self._reduce_set(self.cache[(2, 4)], self.cache[(2, 3)], removed_r2x3, 0, 1) 132 133 removed_r3x2 = self._reduce_set(self.cache[(3, 2)], self.cache[(2, 2)], removed_r2x2, 1, 0) 134 removed_r4x2 = self._reduce_set(self.cache[(4, 2)], self.cache[(3, 2)], removed_r3x2, 1, 0) 135 136 removed_r3x3 = self._reduce_set(self.cache[(3, 3)], self.cache[(3, 2)], removed_r3x2, 0, 1) 137 removed_r3x4 = self._reduce_set(self.cache[(3, 4)], self.cache[(3, 3)], removed_r3x3, 0, 1) 138 removed_r4x4 = self._reduce_set(self.cache[(4, 4)], self.cache[(3, 4)], removed_r3x4, 1, 0) 139 removed_r4x5 = self._reduce_set(self.cache[(4, 5)], self.cache[(4, 4)], removed_r4x4, 0, 1) 140 removed_r5x5 = self._reduce_set(self.cache[(5, 5)], self.cache[(4, 5)], removed_r4x5, 1, 0) 141 removed_r5x6 = self._reduce_set(self.cache[(5, 6)], self.cache[(5, 5)], removed_r5x5, 0, 1) 142 self._reduce_set(self.cache[(6, 6)], self.cache[(5, 6)], removed_r5x6, 1, 0)
143