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

Source Code for Module horizons.util.random_map

  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 copy 
 23  import hashlib 
 24  import random 
 25  import re 
 26  import string 
 27  from typing import List 
 28   
 29  from horizons.constants import GROUND 
 30  from horizons.util.shapes import Circle, Point, Rect 
 31   
 32  # this is how a random island id looks like (used for creation) 
 33  _random_island_id_template = "random:${creation_method}:${width}:${height}:${seed}:${island_x}:${island_y}" 
 34   
 35  # you can check for a random island id with this: 
 36  _random_island_id_regexp = r"^random:([0-9]+):([0-9]+):([0-9]+):([\-]?[0-9]+):([\-]?[0-9]+):([\-]?[0-9]+)$" 
 37   
 38   
39 -def create_random_island(map_db, island_id, id_string):
40 """Creates a random island as sqlite db. 41 It is rather primitive; it places shapes on the dict. 42 The coordinates of tiles will be 0 <= x < width and 0 <= y < height 43 @param id_string: random island id string 44 """ 45 match_obj = re.match(_random_island_id_regexp, id_string) 46 assert match_obj 47 creation_method, width, height, seed, island_x, island_y = [int(i) for i in match_obj.groups()] 48 assert creation_method == 2, 'The only supported island creation method is 2.' 49 50 rand = random.Random(seed) 51 map_set = set() 52 53 # place this number of shapes 54 for i in range(15 + width * height // 45): 55 # place shape determined by shape_id on (x, y) 56 add = True 57 shape_id = rand.randint(2, 8) 58 rect_chance = 29 59 if rand.randint(0, 4) == 0: 60 rect_chance = 13 61 add = False 62 63 shape = None 64 if rand.randint(1, rect_chance) == 1: 65 # use a rect 66 if add: 67 x = rand.randint(8, width - 7) 68 y = rand.randint(8, height - 7) 69 else: 70 x = rand.randint(0, width) 71 y = rand.randint(0, height) 72 shape = Rect.init_from_topleft_and_size(x - 5, y - 5, rand.randint(2, 8), rand.randint(2, 8)) 73 else: 74 # use a circle such that the radius is determined by shape_id 75 radius = shape_id 76 if not add and rand.randint(0, 6) < 5: 77 x = rand.randint(-radius * 3 // 2, width + radius * 3 // 2) 78 y = rand.randint(-radius * 3 // 2, height + radius * 3 // 2) 79 shape = Circle(Point(x, y), shape_id) 80 elif width - radius - 4 >= radius + 3 and height - radius - 4 >= radius + 3: 81 x = rand.randint(radius + 3, width - radius - 4) 82 y = rand.randint(radius + 3, height - radius - 4) 83 shape = Circle(Point(x, y), shape_id) 84 85 if shape: 86 for shape_coord in shape.tuple_iter(): 87 if add: 88 map_set.add(shape_coord) 89 elif shape_coord in map_set: 90 map_set.discard(shape_coord) 91 92 # write values to db 93 map_db("BEGIN TRANSACTION") 94 95 # add grass tiles 96 for x, y in map_set: 97 map_db("INSERT INTO ground VALUES(?, ?, ?, ?, ?, ?)", island_id, island_x + x, island_y + y, *GROUND.DEFAULT_LAND) 98 99 def fill_tiny_spaces(tile): 100 """Fills 1 tile gulfs and straits with the specified tile 101 @param tile: ground tile to fill with 102 """ 103 104 all_neighbors = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)] 105 neighbors = [(-1, 0), (0, -1), (0, 1), (1, 0)] 106 corners = [(-1, -1), (-1, 1)] 107 knight_moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)] 108 bad_configs = set([0, 1 << 0, 1 << 1, 1 << 2, 1 << 3, (1 << 0) | (1 << 3), (1 << 1) | (1 << 2)]) 109 110 edge_set = copy.copy(map_set) 111 reduce_edge_set = True 112 113 while True: 114 to_fill = set() 115 to_ignore = set() 116 for x, y in edge_set: 117 # ignore the tiles with no empty neighbors 118 if reduce_edge_set: 119 is_edge = False 120 for x_offset, y_offset in all_neighbors: 121 if (x + x_offset, y + y_offset) not in map_set: 122 is_edge = True 123 break 124 if not is_edge: 125 to_ignore.add((x, y)) 126 continue 127 128 for x_offset, y_offset in neighbors: 129 x2 = x + x_offset 130 y2 = y + y_offset 131 if (x2, y2) in map_set: 132 continue 133 # (x2, y2) is now a point just off the island 134 135 neighbors_dirs = 0 136 for i in range(len(neighbors)): 137 x3 = x2 + neighbors[i][0] 138 y3 = y2 + neighbors[i][1] 139 if (x3, y3) not in map_set: 140 neighbors_dirs |= (1 << i) 141 if neighbors_dirs in bad_configs: 142 # part of a straight 1 tile gulf 143 to_fill.add((x2, y2)) 144 else: 145 for x_offset, y_offset in corners: 146 x3 = x2 + x_offset 147 y3 = y2 + y_offset 148 x4 = x2 - x_offset 149 y4 = y2 - y_offset 150 if (x3, y3) in map_set and (x4, y4) in map_set: 151 # part of a diagonal 1 tile gulf 152 to_fill.add((x2, y2)) 153 break 154 155 # block 1 tile straits 156 for x_offset, y_offset in knight_moves: 157 x2 = x + x_offset 158 y2 = y + y_offset 159 if (x2, y2) not in map_set: 160 continue 161 if abs(x_offset) == 1: 162 y2 = y + y_offset // 2 163 if (x2, y2) in map_set or (x, y2) in map_set: 164 continue 165 else: 166 x2 = x + x_offset // 2 167 if (x2, y2) in map_set or (x2, y) in map_set: 168 continue 169 to_fill.add((x2, y2)) 170 171 # block diagonal 1 tile straits 172 for x_offset, y_offset in corners: 173 x2 = x + x_offset 174 y2 = y + y_offset 175 x3 = x + 2 * x_offset 176 y3 = y + 2 * y_offset 177 if (x2, y2) not in map_set and (x3, y3) in map_set: 178 to_fill.add((x2, y2)) 179 elif (x2, y2) in map_set and (x2, y) not in map_set and (x, y2) not in map_set: 180 to_fill.add((x2, y)) 181 182 if to_fill: 183 for x, y in to_fill: 184 map_set.add((x, y)) 185 map_db("INSERT INTO ground VALUES(?, ?, ?, ?, ?, ?)", island_id, island_x + x, island_y + y, *tile) 186 187 old_size = len(edge_set) 188 edge_set = edge_set.difference(to_ignore).union(to_fill) 189 reduce_edge_set = old_size - len(edge_set) > 50 190 else: 191 break
192 193 # possible movement directions 194 all_moves = { 195 'sw': (-1, -1), 196 'w': (-1, 0), 197 'nw': (-1, 1), 198 's': (0, -1), 199 'n': (0, 1), 200 'se': (1, -1), 201 'e': (1, 0), 202 'ne': (1, 1) 203 } 204 205 def get_island_outline(): 206 """ 207 @return: the points just off the island as a dict 208 """ 209 result = set() 210 for x, y in map_set: 211 for offset_x, offset_y in all_moves.values(): 212 coords = (x + offset_x, y + offset_y) 213 if coords not in map_set: 214 result.add(coords) 215 return result 216 217 # add grass to sand tiles 218 fill_tiny_spaces(GROUND.DEFAULT_LAND) 219 outline = get_island_outline() 220 for x, y in outline: 221 filled = [] 222 for dir in sorted(all_moves): 223 coords = (x + all_moves[dir][1], y + all_moves[dir][0]) 224 if coords in map_set: 225 filled.append(dir) 226 227 tile = None 228 # straight coast or 1 tile U-shaped gulfs 229 if filled in [['s', 'se', 'sw'], ['s']]: 230 tile = GROUND.SAND_NORTH 231 elif filled in [['e', 'ne', 'se'], ['e']]: 232 tile = GROUND.SAND_WEST 233 elif filled in [['n', 'ne', 'nw'], ['n']]: 234 tile = GROUND.SAND_SOUTH 235 elif filled in [['nw', 'sw', 'w'], ['w']]: 236 tile = GROUND.SAND_EAST 237 # slight turn (looks best with straight coast) 238 elif filled in [['e', 'se'], ['e', 'ne']]: 239 tile = GROUND.SAND_WEST 240 elif filled in [['n', 'ne'], ['n', 'nw']]: 241 tile = GROUND.SAND_SOUTH 242 elif filled in [['nw', 'w'], ['sw', 'w']]: 243 tile = GROUND.SAND_EAST 244 elif filled in [['s', 'sw'], ['s', 'se']]: 245 tile = GROUND.SAND_NORTH 246 # sandy corner 247 elif filled == ['se']: 248 tile = GROUND.SAND_NORTHWEST1 249 elif filled == ['ne']: 250 tile = GROUND.SAND_SOUTHWEST1 251 elif filled == ['nw']: 252 tile = GROUND.SAND_SOUTHEAST1 253 elif filled == ['sw']: 254 tile = GROUND.SAND_NORTHEAST1 255 # grassy corner 256 elif 3 <= len(filled) <= 5: 257 coast_set = set(filled) 258 if 'e' in coast_set and 'se' in coast_set and 's' in coast_set: 259 tile = GROUND.SAND_NORTHEAST3 260 elif 's' in coast_set and 'sw' in coast_set and 'w' in coast_set: 261 tile = GROUND.SAND_NORTHWEST3 262 elif 'w' in coast_set and 'nw' in coast_set and 'n' in coast_set: 263 tile = GROUND.SAND_SOUTHWEST3 264 elif 'n' in coast_set and 'ne' in coast_set and 'e' in coast_set: 265 tile = GROUND.SAND_SOUTHEAST3 266 267 assert tile 268 map_db("INSERT INTO ground VALUES(?, ?, ?, ?, ?, ?)", island_id, island_x + x, island_y + y, *tile) 269 map_set = map_set.union(outline) 270 271 # add sand to shallow water tiles 272 fill_tiny_spaces(GROUND.SAND) 273 outline = get_island_outline() 274 for x, y in outline: 275 filled = [] 276 for dir in sorted(all_moves): 277 coords = (x + all_moves[dir][1], y + all_moves[dir][0]) 278 if coords in map_set: 279 filled.append(dir) 280 281 tile = None 282 # straight coast or 1 tile U-shaped gulfs 283 if filled in [['s', 'se', 'sw'], ['s']]: 284 tile = GROUND.COAST_NORTH 285 elif filled in [['e', 'ne', 'se'], ['e']]: 286 tile = GROUND.COAST_WEST 287 elif filled in [['n', 'ne', 'nw'], ['n']]: 288 tile = GROUND.COAST_SOUTH 289 elif filled in [['nw', 'sw', 'w'], ['w']]: 290 tile = GROUND.COAST_EAST 291 # slight turn (looks best with straight coast) 292 elif filled in [['e', 'se'], ['e', 'ne']]: 293 tile = GROUND.COAST_WEST 294 elif filled in [['n', 'ne'], ['n', 'nw']]: 295 tile = GROUND.COAST_SOUTH 296 elif filled in [['nw', 'w'], ['sw', 'w']]: 297 tile = GROUND.COAST_EAST 298 elif filled in [['s', 'sw'], ['s', 'se']]: 299 tile = GROUND.COAST_NORTH 300 # mostly wet corner 301 elif filled == ['se']: 302 tile = GROUND.COAST_NORTHWEST1 303 elif filled == ['ne']: 304 tile = GROUND.COAST_SOUTHWEST1 305 elif filled == ['nw']: 306 tile = GROUND.COAST_SOUTHEAST1 307 elif filled == ['sw']: 308 tile = GROUND.COAST_NORTHEAST1 309 # mostly dry corner 310 elif 3 <= len(filled) <= 5: 311 coast_set = set(filled) 312 if 'e' in coast_set and 'se' in coast_set and 's' in coast_set: 313 tile = GROUND.COAST_NORTHEAST3 314 elif 's' in coast_set and 'sw' in coast_set and 'w' in coast_set: 315 tile = GROUND.COAST_NORTHWEST3 316 elif 'w' in coast_set and 'nw' in coast_set and 'n' in coast_set: 317 tile = GROUND.COAST_SOUTHWEST3 318 elif 'n' in coast_set and 'ne' in coast_set and 'e' in coast_set: 319 tile = GROUND.COAST_SOUTHEAST3 320 321 assert tile 322 map_db("INSERT INTO ground VALUES(?, ?, ?, ?, ?, ?)", island_id, island_x + x, island_y + y, *tile) 323 map_set = map_set.union(outline) 324 325 # add shallow water to deep water tiles 326 fill_tiny_spaces(GROUND.SHALLOW_WATER) 327 outline = get_island_outline() 328 for x, y in outline: 329 filled = [] 330 for dir in sorted(all_moves): 331 coords = (x + all_moves[dir][1], y + all_moves[dir][0]) 332 if coords in map_set: 333 filled.append(dir) 334 335 tile = None 336 # straight coast or 1 tile U-shaped gulfs 337 if filled in [['s', 'se', 'sw'], ['s']]: 338 tile = GROUND.DEEP_WATER_NORTH 339 elif filled in [['e', 'ne', 'se'], ['e']]: 340 tile = GROUND.DEEP_WATER_WEST 341 elif filled in [['n', 'ne', 'nw'], ['n']]: 342 tile = GROUND.DEEP_WATER_SOUTH 343 elif filled in [['nw', 'sw', 'w'], ['w']]: 344 tile = GROUND.DEEP_WATER_EAST 345 # slight turn (looks best with straight coast) 346 elif filled in [['e', 'se'], ['e', 'ne']]: 347 tile = GROUND.DEEP_WATER_WEST 348 elif filled in [['n', 'ne'], ['n', 'nw']]: 349 tile = GROUND.DEEP_WATER_SOUTH 350 elif filled in [['nw', 'w'], ['sw', 'w']]: 351 tile = GROUND.DEEP_WATER_EAST 352 elif filled in [['s', 'sw'], ['s', 'se']]: 353 tile = GROUND.DEEP_WATER_NORTH 354 # mostly deep corner 355 elif filled == ['se']: 356 tile = GROUND.DEEP_WATER_NORTHWEST1 357 elif filled == ['ne']: 358 tile = GROUND.DEEP_WATER_SOUTHWEST1 359 elif filled == ['nw']: 360 tile = GROUND.DEEP_WATER_SOUTHEAST1 361 elif filled == ['sw']: 362 tile = GROUND.DEEP_WATER_NORTHEAST1 363 # mostly shallow corner 364 elif 3 <= len(filled) <= 5: 365 coast_set = set(filled) 366 if 'e' in coast_set and 'se' in coast_set and 's' in coast_set: 367 tile = GROUND.DEEP_WATER_NORTHEAST3 368 elif 's' in coast_set and 'sw' in coast_set and 'w' in coast_set: 369 tile = GROUND.DEEP_WATER_NORTHWEST3 370 elif 'w' in coast_set and 'nw' in coast_set and 'n' in coast_set: 371 tile = GROUND.DEEP_WATER_SOUTHWEST3 372 elif 'n' in coast_set and 'ne' in coast_set and 'e' in coast_set: 373 tile = GROUND.DEEP_WATER_SOUTHEAST3 374 375 assert tile 376 map_db("INSERT INTO ground VALUES(?, ?, ?, ?, ?, ?)", island_id, island_x + x, island_y + y, *tile) 377 378 map_db("COMMIT") 379 380
381 -def _simplify_seed(seed):
382 """ 383 Return the simplified seed value. The goal of this is to make it easier for users to convey the seeds orally. 384 385 This function also makes sure its return value fits into a 32bit integer. That is 386 necessary because otherwise the hash of the value could be different between 387 32 and 64 bit python interpreters. That would cause a map with seed X to be different 388 depending on the platform which we don't want to happen. 389 """ 390 391 seed = str(seed).lower().strip().encode('utf-8') 392 h = hashlib.md5(seed) 393 h.update(seed) 394 return int('0x' + h.hexdigest(), 16) % 1000000007
395 396
397 -def generate_random_map(seed, map_size, water_percent, max_island_size, 398 preferred_island_size, island_size_deviation):
399 """ 400 Generates a random map. 401 402 @param seed: random number generator seed 403 @param map_size: maximum map side length 404 @param water_percent: minimum percent of map covered with water 405 @param max_island_size: maximum island side length 406 @param preferred_island_size: mean of island side lengths 407 @param island_size_deviation: deviation of island side lengths 408 @return: filename of the SQLite database containing the map 409 """ 410 max_island_size = min(max_island_size, map_size) 411 rand = random.Random(_simplify_seed(seed)) 412 min_island_size = 20 # minimum chosen island side length (the real size my be smaller) 413 min_island_separation = 3 + map_size // 100 # minimum distance between two islands 414 max_island_side_coefficient = 4 # maximum value of island's max(side length) / min(side length) 415 416 islands = [] # type: List[Rect] 417 estimated_land = 0 418 max_land_amount = map_size * map_size * (100 - water_percent) // 100 419 420 trial_number = 0 421 while trial_number < 100: 422 trial_number += 1 423 width = max(min_island_size, min(max_island_size, int(round(rand.gauss(preferred_island_size, island_size_deviation))))) 424 side_coefficient = min(1 + abs(rand.gauss(0, 0.2)), max_island_side_coefficient) 425 side_coefficient = side_coefficient if rand.randint(0, 1) else 1.0 / side_coefficient 426 height = max(min_island_size, min(max_island_size, int(round(width * side_coefficient)))) 427 size = width * height 428 if estimated_land + size > max_land_amount: 429 continue 430 431 for _ in range(13): 432 x = rand.randint(0, map_size - width) 433 y = rand.randint(0, map_size - height) 434 435 rect = Rect.init_from_topleft_and_size(x, y, width, height) 436 blocked = False 437 for existing_island in islands: 438 if existing_island.distance(rect) < min_island_separation: 439 blocked = True 440 break 441 if not blocked: 442 islands.append(rect) 443 estimated_land += size 444 trial_number = 0 445 break 446 447 # move some of the islands to stretch the map to the right size 448 if len(islands) > 1: 449 min_top = min(rect.top for rect in islands) 450 rect = rand.choice([rect for rect in islands if rect.top == min_top]) 451 islands[islands.index(rect)] = Rect.init_from_borders(rect.left, rect.top - min_top, rect.right, rect.bottom - min_top) 452 453 max_bottom = max(rect.bottom for rect in islands) 454 rect = rand.choice([rect for rect in islands if rect.bottom == max_bottom]) 455 shift = map_size - max_bottom - 1 456 islands[islands.index(rect)] = Rect.init_from_borders(rect.left, rect.top + shift, rect.right, rect.bottom + shift) 457 458 min_left = min(rect.left for rect in islands) 459 rect = rand.choice([rect for rect in islands if rect.left == min_left]) 460 islands[islands.index(rect)] = Rect.init_from_borders(rect.left - min_left, rect.top, rect.right - min_left, rect.bottom) 461 462 max_right = max(rect.right for rect in islands) 463 rect = rand.choice([rect for rect in islands if rect.right == max_right]) 464 shift = map_size - max_right - 1 465 islands[islands.index(rect)] = Rect.init_from_borders(rect.left + shift, rect.top, rect.right + shift, rect.bottom) 466 467 island_strings = [] 468 for rect in islands: 469 # The bounds must be platform independent to make sure the same maps are generated on all platforms. 470 island_seed = rand.randint(-2147483648, 2147483647) 471 island_params = {'creation_method': 2, 'seed': island_seed, 'width': rect.width, 472 'height': rect.height, 'island_x': rect.left, 'island_y': rect.top} 473 island_string = string.Template(_random_island_id_template).safe_substitute(island_params) 474 island_strings.append(island_string) 475 return island_strings
476 477
478 -def generate_random_seed(seed):
479 rand = random.Random(seed) 480 if rand.randint(0, 1) == 0: 481 # generate a random string of 1-5 letters a-z with a dash if there are 4 or more letters 482 seq = '' 483 for i in range(rand.randint(1, 5)): 484 seq += chr(97 + rand.randint(0, 25)) 485 if len(seq) > 3: 486 split = rand.randint(2, len(seq) - 2) 487 seq = seq[:split] + '-' + seq[split:] 488 return seq 489 else: 490 # generate a numeric seed 491 fields = rand.randint(1, 3) 492 if fields == 1: 493 # generate a five digit integer 494 return str(rand.randint(10000, 99999)) 495 else: 496 # generate a sequence of 2 or 3 dash separated fields of integers 10-9999 497 parts = [] 498 for i in range(fields): 499 power = rand.randint(1, 3) 500 parts.append(str(rand.randint(10 ** power, 10 ** (power + 1) - 1))) 501 return '-'.join(parts)
502 503
504 -def generate_map_from_seed(seed):
505 """ 506 Generates a random map with the given seed and default parameters. 507 508 @param seed: random number generator seed 509 @return: filename of the SQLite database containing the map 510 """ 511 512 return generate_random_map(seed, 150, 50, 70, 70, 30)
513 514
515 -def generate_huge_map_from_seed(seed):
516 """Same as generate_map_from_seed, but making it as big as it is still reasonable""" 517 return generate_random_map(seed, 250, 20, 70, 70, 5)
518