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

Source Code for Module horizons.world.buildability.binarycache

  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 LazyBinaryBuildabilityCacheElement:
26 """ 27 Lazily computed cache element of a BinaryBuildabilityCache instance. 28 29 Instances of this class are used to make less frequently needed caches of the 30 BinaryBuildabilityCache class instances get computed lazily just when it is needed. 31 """ 32
33 - def __init__(self, buildability_cache, width):
34 self._buildability_cache = buildability_cache 35 self._width = width 36 self._cache = None
37
38 - def _init_size_cache(self):
39 if self._cache is not None: 40 return 41 42 r3x3 = self._buildability_cache.cache[(3, 3)] 43 offset = self._width - 3 44 45 usable = set() 46 for coords in r3x3: 47 x, y = coords 48 if (x + offset, y) in r3x3 and (x, y + offset) in r3x3 and (x + offset, y + offset) in r3x3: 49 usable.add(coords) 50 51 self._cache = usable 52 size = (self._width, self._width) 53 # Replace the reference to this instance with the actual cache 54 self._buildability_cache.cache[size] = usable
55
56 - def __getattr__(self, name):
57 # required to make set methods such as set.intersect work 58 self._init_size_cache() 59 return getattr(self._cache, name)
60
61 - def __contains__(self, key):
62 # required to make the syntax "coords in cache" work efficiently 63 self._init_size_cache() 64 return key in self._cache
65
66 - def __iter__(self):
67 # required to make iteration work 68 self._init_size_cache() 69 return iter(self._cache)
70
71 72 -class BinaryBuildabilityCache:
73 """ 74 A cache that knows where rectangles can be placed such that they are entirely inside the area. 75 76 This cache can be used to keep track of building buildability in case the 77 buildability depends on the building being entirely within a certain area. 78 The binary part of the name refers to the fact that a node either is or isn't part of 79 the area that the instance is about. 80 81 A query of the form (x, y) in instance.cache[(width, height)] is a very cheap way of 82 finding out whether a rectangle of size (width, height) can be placed on origin (x, y) 83 such that it is entirely within the given area. 84 85 All elements of instance.cache[(width, height)] can be iterated to get a complete list 86 of all such coordinates. 87 """ 88
89 - def __init__(self, terrain_cache):
90 self.terrain_cache = terrain_cache 91 self.coords_set = set() # set((x, y), ...) 92 self._row2 = set() 93 94 self.cache = {} # {(width, height): set((x, y), ...), ...} 95 self.cache[(1, 1)] = self.coords_set 96 for size in TerrainBuildabilityCache.sizes: 97 if size != (1, 1): 98 self.cache[size] = set() 99 if size[0] != size[1]: 100 self.cache[(size[1], size[0])] = set()
101
102 - def _reset_lazy_sets(self):
103 self.cache[(4, 4)] = LazyBinaryBuildabilityCacheElement(self, 4) 104 self.cache[(6, 6)] = LazyBinaryBuildabilityCacheElement(self, 6)
105 106 @classmethod
107 - def _extend_set(cls, cur_set, prev_set, prev_set_additions, dx, dy):
108 base_set_additions = set() 109 for coords in prev_set_additions: 110 x, y = coords 111 prev_coords = (x - dx, y - dy) 112 if prev_coords in prev_set: 113 cur_set.add(prev_coords) 114 base_set_additions.add(prev_coords) 115 next_coords = (x + dx, y + dy) 116 if next_coords not in prev_set_additions and next_coords in prev_set: 117 cur_set.add(coords) 118 base_set_additions.add(coords) 119 return base_set_additions
120
121 - def add_area(self, new_coords_list):
122 """ 123 Add a list of new coordinates to the area. 124 125 This function quickly updates the information about the changed coordinates. 126 For example when (x, y) is added to the area then it will update the information 127 showing whether the 2x1 rectangles with the origin on (x - 1, y) and (x, y) are 128 now completely part of the area. Similar the things are done for the larger sizes. 129 """ 130 131 for coords in new_coords_list: 132 assert coords not in self.coords_set 133 assert coords in self.terrain_cache.land_or_coast 134 self.coords_set.add(coords) 135 136 coords_set = self.coords_set 137 new_coords_set = set(new_coords_list) 138 139 new_row2 = self._extend_set(self._row2, coords_set, new_coords_set, 1, 0) 140 new_r2x2 = self._extend_set(self.cache[(2, 2)], self._row2, new_row2, 0, 1) 141 142 new_r2x3 = self._extend_set(self.cache[(2, 3)], self.cache[(2, 2)], new_r2x2, 0, 1) 143 new_r2x4 = self._extend_set(self.cache[(2, 4)], self.cache[(2, 3)], new_r2x3, 0, 1) 144 145 new_r3x2 = self._extend_set(self.cache[(3, 2)], self.cache[(2, 2)], new_r2x2, 1, 0) 146 new_r4x2 = self._extend_set(self.cache[(4, 2)], self.cache[(3, 2)], new_r3x2, 1, 0) 147 148 self._extend_set(self.cache[(3, 3)], self.cache[(3, 2)], new_r3x2, 0, 1) 149 self._reset_lazy_sets()
150 151 @classmethod
152 - def _reduce_set(cls, cur_set, prev_set_removals, dx, dy):
153 base_set_removals = set() 154 for coords in prev_set_removals: 155 x, y = coords 156 prev_coords = (x - dx, y - dy) 157 if prev_coords in cur_set: 158 cur_set.discard(prev_coords) 159 base_set_removals.add(prev_coords) 160 next_coords = (x + dx, y + dy) 161 if next_coords not in prev_set_removals and coords in cur_set: 162 cur_set.discard(coords) 163 base_set_removals.add(coords) 164 return base_set_removals
165
166 - def remove_area(self, removed_coords_list):
167 """Remove a list of existing coordinates from the area.""" 168 for coords in removed_coords_list: 169 assert coords in self.coords_set 170 assert coords in self.terrain_cache.land_or_coast 171 self.coords_set.discard(coords) 172 removed_coords_set = set(removed_coords_list) 173 174 removed_row2 = self._reduce_set(self._row2, removed_coords_set, 1, 0) 175 removed_r2x2 = self._reduce_set(self.cache[(2, 2)], removed_row2, 0, 1) 176 177 removed_r2x3 = self._reduce_set(self.cache[(2, 3)], removed_r2x2, 0, 1) 178 removed_r2x4 = self._reduce_set(self.cache[(2, 4)], removed_r2x3, 0, 1) 179 180 removed_r3x2 = self._reduce_set(self.cache[(3, 2)], removed_r2x2, 1, 0) 181 removed_r4x2 = self._reduce_set(self.cache[(4, 2)], removed_r3x2, 1, 0) 182 183 self._reduce_set(self.cache[(3, 3)], removed_r3x2, 0, 1) 184 self._reset_lazy_sets()
185