src/mapgen/mapgen.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2018 celeron55, Perttu Ahola <celeron55@gmail.com>
   4 Copyright (C) 2013-2018 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
   5 Copyright (C) 2015-2018 paramat
   6
   7 This program is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Lesser General Public License as published by
   9 the Free Software Foundation; either version 2.1 of the License, or
  10 (at your option) any later version.
  11
  12 This program is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU Lesser General Public License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public License along
  18 with this program; if not, write to the Free Software Foundation, Inc.,
  19 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  20 */
  21
  22 #include "mapgen.h"
  23 #include "voxel.h"
  24 #include "noise.h"
  25 #include "gamedef.h"
  26 #include "mg_biome.h"
  27 #include "mapblock.h"
  28 #include "mapnode.h"
  29 #include "map.h"
  30 #include "content_sao.h"
  31 #include "nodedef.h"
  32 #include "emerge.h"
  33 #include "voxelalgorithms.h"
  34 #include "porting.h"
  35 #include "profiler.h"
  36 #include "settings.h"
  37 #include "treegen.h"
  38 #include "serialization.h"
  39 #include "util/serialize.h"
  40 #include "util/numeric.h"
  41 #include "filesys.h"
  42 #include "log.h"
  43 #include "mapgen_carpathian.h"
  44 #include "mapgen_flat.h"
  45 #include "mapgen_fractal.h"
  46 #include "mapgen_v5.h"
  47 #include "mapgen_v6.h"
  48 #include "mapgen_v7.h"
  49 #include "mapgen_valleys.h"
  50 #include "mapgen_singlenode.h"
  51 #include "cavegen.h"
  52 #include "dungeongen.h"
  53
  54 FlagDesc flagdesc_mapgen[] = {
  55         {"caves",       MG_CAVES},
  56         {"dungeons",    MG_DUNGEONS},
  57         {"light",       MG_LIGHT},
  58         {"decorations", MG_DECORATIONS},
  59         {"biomes",      MG_BIOMES},
  60         {NULL,          0}
  61 };
  62
  63 FlagDesc flagdesc_gennotify[] = {
  64         {"dungeon",          1 << GENNOTIFY_DUNGEON},
  65         {"temple",           1 << GENNOTIFY_TEMPLE},
  66         {"cave_begin",       1 << GENNOTIFY_CAVE_BEGIN},
  67         {"cave_end",         1 << GENNOTIFY_CAVE_END},
  68         {"large_cave_begin", 1 << GENNOTIFY_LARGECAVE_BEGIN},
  69         {"large_cave_end",   1 << GENNOTIFY_LARGECAVE_END},
  70         {"decoration",       1 << GENNOTIFY_DECORATION},
  71         {NULL,               0}
  72 };
  73
  74 struct MapgenDesc {
  75         const char *name;
  76         bool is_user_visible;
  77 };
  78
  79 ////
  80 //// Built-in mapgens
  81 ////
  82
  83 static MapgenDesc g_reg_mapgens[] = {
  84         {"v5",         true},
  85         {"v6",         true},
  86         {"v7",         true},
  87         {"flat",       true},
  88         {"fractal",    true},
  89         {"valleys",    true},
  90         {"singlenode", true},
  91         {"carpathian", true},
  92 };
  93
  94 STATIC_ASSERT(
  95         ARRLEN(g_reg_mapgens) == MAPGEN_INVALID,
  96         registered_mapgens_is_wrong_size);
  97
  98 ////
  99 //// Mapgen
 100 ////
 101
 102 Mapgen::Mapgen(int mapgenid, MapgenParams *params, EmergeManager *emerge) :
 103         gennotify(emerge->gen_notify_on, &emerge->gen_notify_on_deco_ids)
 104 {
 105         id           = mapgenid;
 106         water_level  = params->water_level;
 107         mapgen_limit = params->mapgen_limit;
 108         flags        = params->flags;
 109         csize        = v3s16(1, 1, 1) * (params->chunksize * MAP_BLOCKSIZE);
 110
 111         /*
 112                 We are losing half our entropy by doing this, but it is necessary to
 113                 preserve reverse compatibility.  If the top half of our current 64 bit
 114                 seeds ever starts getting used, existing worlds will break due to a
 115                 different hash outcome and no way to differentiate between versions.
 116
 117                 A solution could be to add a new bit to designate that the top half of
 118                 the seed value should be used, essentially a 1-bit version code, but
 119                 this would require increasing the total size of a seed to 9 bytes (yuck)
 120
 121                 It's probably okay if this never gets fixed.  4.2 billion possibilities
 122                 ought to be enough for anyone.
 123         */
 124         seed = (s32)params->seed;
 125
 126         ndef      = emerge->ndef;
 127 }
 128
 129
 130 MapgenType Mapgen::getMapgenType(const std::string &mgname)
 131 {
 132         for (size_t i = 0; i != ARRLEN(g_reg_mapgens); i++) {
 133                 if (mgname == g_reg_mapgens[i].name)
 134                         return (MapgenType)i;
 135         }
 136
 137         return MAPGEN_INVALID;
 138 }
 139
 140
 141 const char *Mapgen::getMapgenName(MapgenType mgtype)
 142 {
 143         size_t index = (size_t)mgtype;
 144         if (index == MAPGEN_INVALID || index >= ARRLEN(g_reg_mapgens))
 145                 return "invalid";
 146
 147         return g_reg_mapgens[index].name;
 148 }
 149
 150
 151 Mapgen *Mapgen::createMapgen(MapgenType mgtype, MapgenParams *params,
 152         EmergeManager *emerge)
 153 {
 154         switch (mgtype) {
 155         case MAPGEN_CARPATHIAN:
 156                 return new MapgenCarpathian((MapgenCarpathianParams *)params, emerge);
 157         case MAPGEN_FLAT:
 158                 return new MapgenFlat((MapgenFlatParams *)params, emerge);
 159         case MAPGEN_FRACTAL:
 160                 return new MapgenFractal((MapgenFractalParams *)params, emerge);
 161         case MAPGEN_SINGLENODE:
 162                 return new MapgenSinglenode((MapgenSinglenodeParams *)params, emerge);
 163         case MAPGEN_V5:
 164                 return new MapgenV5((MapgenV5Params *)params, emerge);
 165         case MAPGEN_V6:
 166                 return new MapgenV6((MapgenV6Params *)params, emerge);
 167         case MAPGEN_V7:
 168                 return new MapgenV7((MapgenV7Params *)params, emerge);
 169         case MAPGEN_VALLEYS:
 170                 return new MapgenValleys((MapgenValleysParams *)params, emerge);
 171         default:
 172                 return nullptr;
 173         }
 174 }
 175
 176
 177 MapgenParams *Mapgen::createMapgenParams(MapgenType mgtype)
 178 {
 179         switch (mgtype) {
 180         case MAPGEN_CARPATHIAN:
 181                 return new MapgenCarpathianParams;
 182         case MAPGEN_FLAT:
 183                 return new MapgenFlatParams;
 184         case MAPGEN_FRACTAL:
 185                 return new MapgenFractalParams;
 186         case MAPGEN_SINGLENODE:
 187                 return new MapgenSinglenodeParams;
 188         case MAPGEN_V5:
 189                 return new MapgenV5Params;
 190         case MAPGEN_V6:
 191                 return new MapgenV6Params;
 192         case MAPGEN_V7:
 193                 return new MapgenV7Params;
 194         case MAPGEN_VALLEYS:
 195                 return new MapgenValleysParams;
 196         default:
 197                 return nullptr;
 198         }
 199 }
 200
 201
 202 void Mapgen::getMapgenNames(std::vector<const char *> *mgnames, bool include_hidden)
 203 {
 204         for (u32 i = 0; i != ARRLEN(g_reg_mapgens); i++) {
 205                 if (include_hidden || g_reg_mapgens[i].is_user_visible)
 206                         mgnames->push_back(g_reg_mapgens[i].name);
 207         }
 208 }
 209
 210
 211 u32 Mapgen::getBlockSeed(v3s16 p, s32 seed)
 212 {
 213         return (u32)seed   +
 214                 p.Z * 38134234 +
 215                 p.Y * 42123    +
 216                 p.X * 23;
 217 }
 218
 219
 220 u32 Mapgen::getBlockSeed2(v3s16 p, s32 seed)
 221 {
 222         u32 n = 1619 * p.X + 31337 * p.Y + 52591 * p.Z + 1013 * seed;
 223         n = (n >> 13) ^ n;
 224         return (n * (n * n * 60493 + 19990303) + 1376312589);
 225 }
 226
 227
 228 // Returns Y one under area minimum if not found
 229 s16 Mapgen::findGroundLevelFull(v2s16 p2d)
 230 {
 231         const v3s16 &em = vm->m_area.getExtent();
 232         s16 y_nodes_max = vm->m_area.MaxEdge.Y;
 233         s16 y_nodes_min = vm->m_area.MinEdge.Y;
 234         u32 i = vm->m_area.index(p2d.X, y_nodes_max, p2d.Y);
 235         s16 y;
 236
 237         for (y = y_nodes_max; y >= y_nodes_min; y--) {
 238                 MapNode &n = vm->m_data[i];
 239                 if (ndef->get(n).walkable)
 240                         break;
 241
 242                 VoxelArea::add_y(em, i, -1);
 243         }
 244         return (y >= y_nodes_min) ? y : y_nodes_min - 1;
 245 }
 246
 247
 248 // Returns -MAX_MAP_GENERATION_LIMIT if not found
 249 s16 Mapgen::findGroundLevel(v2s16 p2d, s16 ymin, s16 ymax)
 250 {
 251         const v3s16 &em = vm->m_area.getExtent();
 252         u32 i = vm->m_area.index(p2d.X, ymax, p2d.Y);
 253         s16 y;
 254
 255         for (y = ymax; y >= ymin; y--) {
 256                 MapNode &n = vm->m_data[i];
 257                 if (ndef->get(n).walkable)
 258                         break;
 259
 260                 VoxelArea::add_y(em, i, -1);
 261         }
 262         return (y >= ymin) ? y : -MAX_MAP_GENERATION_LIMIT;
 263 }
 264
 265
 266 // Returns -MAX_MAP_GENERATION_LIMIT if not found or if ground is found first
 267 s16 Mapgen::findLiquidSurface(v2s16 p2d, s16 ymin, s16 ymax)
 268 {
 269         const v3s16 &em = vm->m_area.getExtent();
 270         u32 i = vm->m_area.index(p2d.X, ymax, p2d.Y);
 271         s16 y;
 272
 273         for (y = ymax; y >= ymin; y--) {
 274                 MapNode &n = vm->m_data[i];
 275                 if (ndef->get(n).walkable)
 276                         return -MAX_MAP_GENERATION_LIMIT;
 277
 278                 if (ndef->get(n).isLiquid())
 279                         break;
 280
 281                 VoxelArea::add_y(em, i, -1);
 282         }
 283         return (y >= ymin) ? y : -MAX_MAP_GENERATION_LIMIT;
 284 }
 285
 286
 287 void Mapgen::updateHeightmap(v3s16 nmin, v3s16 nmax)
 288 {
 289         if (!heightmap)
 290                 return;
 291
 292         //TimeTaker t("Mapgen::updateHeightmap", NULL, PRECISION_MICRO);
 293         int index = 0;
 294         for (s16 z = nmin.Z; z <= nmax.Z; z++) {
 295                 for (s16 x = nmin.X; x <= nmax.X; x++, index++) {
 296                         s16 y = findGroundLevel(v2s16(x, z), nmin.Y, nmax.Y);
 297
 298                         heightmap[index] = y;
 299                 }
 300         }
 301 }
 302
 303
 304 void Mapgen::getSurfaces(v2s16 p2d, s16 ymin, s16 ymax,
 305         std::vector<s16> &floors, std::vector<s16> &ceilings)
 306 {
 307         const v3s16 &em = vm->m_area.getExtent();
 308
 309         bool is_walkable = false;
 310         u32 vi = vm->m_area.index(p2d.X, ymax, p2d.Y);
 311         MapNode mn_max = vm->m_data[vi];
 312         bool walkable_above = ndef->get(mn_max).walkable;
 313         VoxelArea::add_y(em, vi, -1);
 314
 315         for (s16 y = ymax - 1; y >= ymin; y--) {
 316                 MapNode mn = vm->m_data[vi];
 317                 is_walkable = ndef->get(mn).walkable;
 318
 319                 if (is_walkable && !walkable_above) {
 320                         floors.push_back(y);
 321                 } else if (!is_walkable && walkable_above) {
 322                         ceilings.push_back(y + 1);
 323                 }
 324
 325                 VoxelArea::add_y(em, vi, -1);
 326                 walkable_above = is_walkable;
 327         }
 328 }
 329
 330
 331 inline bool Mapgen::isLiquidHorizontallyFlowable(u32 vi, v3s16 em)
 332 {
 333         u32 vi_neg_x = vi;
 334         VoxelArea::add_x(em, vi_neg_x, -1);
 335         if (vm->m_data[vi_neg_x].getContent() != CONTENT_IGNORE) {
 336                 const ContentFeatures &c_nx = ndef->get(vm->m_data[vi_neg_x]);
 337                 if (c_nx.floodable && !c_nx.isLiquid())
 338                         return true;
 339         }
 340         u32 vi_pos_x = vi;
 341         VoxelArea::add_x(em, vi_pos_x, +1);
 342         if (vm->m_data[vi_pos_x].getContent() != CONTENT_IGNORE) {
 343                 const ContentFeatures &c_px = ndef->get(vm->m_data[vi_pos_x]);
 344                 if (c_px.floodable && !c_px.isLiquid())
 345                         return true;
 346         }
 347         u32 vi_neg_z = vi;
 348         VoxelArea::add_z(em, vi_neg_z, -1);
 349         if (vm->m_data[vi_neg_z].getContent() != CONTENT_IGNORE) {
 350                 const ContentFeatures &c_nz = ndef->get(vm->m_data[vi_neg_z]);
 351                 if (c_nz.floodable && !c_nz.isLiquid())
 352                         return true;
 353         }
 354         u32 vi_pos_z = vi;
 355         VoxelArea::add_z(em, vi_pos_z, +1);
 356         if (vm->m_data[vi_pos_z].getContent() != CONTENT_IGNORE) {
 357                 const ContentFeatures &c_pz = ndef->get(vm->m_data[vi_pos_z]);
 358                 if (c_pz.floodable && !c_pz.isLiquid())
 359                         return true;
 360         }
 361         return false;
 362 }
 363
 364 void Mapgen::updateLiquid(UniqueQueue<v3s16> *trans_liquid, v3s16 nmin, v3s16 nmax)
 365 {
 366         bool isignored, isliquid, wasignored, wasliquid, waschecked, waspushed;
 367         const v3s16 &em  = vm->m_area.getExtent();
 368
 369         for (s16 z = nmin.Z + 1; z <= nmax.Z - 1; z++)
 370         for (s16 x = nmin.X + 1; x <= nmax.X - 1; x++) {
 371                 wasignored = true;
 372                 wasliquid = false;
 373                 waschecked = false;
 374                 waspushed = false;
 375
 376                 u32 vi = vm->m_area.index(x, nmax.Y, z);
 377                 for (s16 y = nmax.Y; y >= nmin.Y; y--) {
 378                         isignored = vm->m_data[vi].getContent() == CONTENT_IGNORE;
 379                         isliquid = ndef->get(vm->m_data[vi]).isLiquid();
 380
 381                         if (isignored || wasignored || isliquid == wasliquid) {
 382                                 // Neither topmost node of liquid column nor topmost node below column
 383                                 waschecked = false;
 384                                 waspushed = false;
 385                         } else if (isliquid) {
 386                                 // This is the topmost node in the column
 387                                 bool ispushed = false;
 388                                 if (isLiquidHorizontallyFlowable(vi, em)) {
 389                                         trans_liquid->push_back(v3s16(x, y, z));
 390                                         ispushed = true;
 391                                 }
 392                                 // Remember waschecked and waspushed to avoid repeated
 393                                 // checks/pushes in case the column consists of only this node
 394                                 waschecked = true;
 395                                 waspushed = ispushed;
 396                         } else {
 397                                 // This is the topmost node below a liquid column
 398                                 u32 vi_above = vi;
 399                                 VoxelArea::add_y(em, vi_above, 1);
 400                                 if (!waspushed && (ndef->get(vm->m_data[vi]).floodable ||
 401                                                 (!waschecked && isLiquidHorizontallyFlowable(vi_above, em)))) {
 402                                         // Push back the lowest node in the column which is one
 403                                         // node above this one
 404                                         trans_liquid->push_back(v3s16(x, y + 1, z));
 405                                 }
 406                         }
 407
 408                         wasliquid = isliquid;
 409                         wasignored = isignored;
 410                         VoxelArea::add_y(em, vi, -1);
 411                 }
 412         }
 413 }
 414
 415
 416 void Mapgen::setLighting(u8 light, v3s16 nmin, v3s16 nmax)
 417 {
 418         ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update", SPT_AVG);
 419         VoxelArea a(nmin, nmax);
 420
 421         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 422                 for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 423                         u32 i = vm->m_area.index(a.MinEdge.X, y, z);
 424                         for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++)
 425                                 vm->m_data[i].param1 = light;
 426                 }
 427         }
 428 }
 429
 430
 431 void Mapgen::lightSpread(VoxelArea &a, v3s16 p, u8 light)
 432 {
 433         if (light <= 1 || !a.contains(p))
 434                 return;
 435
 436         u32 vi = vm->m_area.index(p);
 437         MapNode &n = vm->m_data[vi];
 438
 439         // Decay light in each of the banks separately
 440         u8 light_day = light & 0x0F;
 441         if (light_day > 0)
 442                 light_day -= 0x01;
 443
 444         u8 light_night = light & 0xF0;
 445         if (light_night > 0)
 446                 light_night -= 0x10;
 447
 448         // Bail out only if we have no more light from either bank to propogate, or
 449         // we hit a solid block that light cannot pass through.
 450         if ((light_day  <= (n.param1 & 0x0F) &&
 451                 light_night <= (n.param1 & 0xF0)) ||
 452                 !ndef->get(n).light_propagates)
 453                 return;
 454
 455         // Since this recursive function only terminates when there is no light from
 456         // either bank left, we need to take the max of both banks into account for
 457         // the case where spreading has stopped for one light bank but not the other.
 458         light = MYMAX(light_day, n.param1 & 0x0F) |
 459                         MYMAX(light_night, n.param1 & 0xF0);
 460
 461         n.param1 = light;
 462
 463         lightSpread(a, p + v3s16(0, 0, 1), light);
 464         lightSpread(a, p + v3s16(0, 1, 0), light);
 465         lightSpread(a, p + v3s16(1, 0, 0), light);
 466         lightSpread(a, p - v3s16(0, 0, 1), light);
 467         lightSpread(a, p - v3s16(0, 1, 0), light);
 468         lightSpread(a, p - v3s16(1, 0, 0), light);
 469 }
 470
 471
 472 void Mapgen::calcLighting(v3s16 nmin, v3s16 nmax, v3s16 full_nmin, v3s16 full_nmax,
 473         bool propagate_shadow)
 474 {
 475         ScopeProfiler sp(g_profiler, "EmergeThread: mapgen lighting update", SPT_AVG);
 476         //TimeTaker t("updateLighting");
 477
 478         propagateSunlight(nmin, nmax, propagate_shadow);
 479         spreadLight(full_nmin, full_nmax);
 480
 481         //printf("updateLighting: %dms\n", t.stop());
 482 }
 483
 484
 485 void Mapgen::propagateSunlight(v3s16 nmin, v3s16 nmax, bool propagate_shadow)
 486 {
 487         //TimeTaker t("propagateSunlight");
 488         VoxelArea a(nmin, nmax);
 489         bool block_is_underground = (water_level >= nmax.Y);
 490         const v3s16 &em = vm->m_area.getExtent();
 491
 492         // NOTE: Direct access to the low 4 bits of param1 is okay here because,
 493         // by definition, sunlight will never be in the night lightbank.
 494
 495         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 496                 for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++) {
 497                         // see if we can get a light value from the overtop
 498                         u32 i = vm->m_area.index(x, a.MaxEdge.Y + 1, z);
 499                         if (vm->m_data[i].getContent() == CONTENT_IGNORE) {
 500                                 if (block_is_underground)
 501                                         continue;
 502                         } else if ((vm->m_data[i].param1 & 0x0F) != LIGHT_SUN &&
 503                                         propagate_shadow) {
 504                                 continue;
 505                         }
 506                         VoxelArea::add_y(em, i, -1);
 507
 508                         for (int y = a.MaxEdge.Y; y >= a.MinEdge.Y; y--) {
 509                                 MapNode &n = vm->m_data[i];
 510                                 if (!ndef->get(n).sunlight_propagates)
 511                                         break;
 512                                 n.param1 = LIGHT_SUN;
 513                                 VoxelArea::add_y(em, i, -1);
 514                         }
 515                 }
 516         }
 517         //printf("propagateSunlight: %dms\n", t.stop());
 518 }
 519
 520
 521 void Mapgen::spreadLight(v3s16 nmin, v3s16 nmax)
 522 {
 523         //TimeTaker t("spreadLight");
 524         VoxelArea a(nmin, nmax);
 525
 526         for (int z = a.MinEdge.Z; z <= a.MaxEdge.Z; z++) {
 527                 for (int y = a.MinEdge.Y; y <= a.MaxEdge.Y; y++) {
 528                         u32 i = vm->m_area.index(a.MinEdge.X, y, z);
 529                         for (int x = a.MinEdge.X; x <= a.MaxEdge.X; x++, i++) {
 530                                 MapNode &n = vm->m_data[i];
 531                                 if (n.getContent() == CONTENT_IGNORE)
 532                                         continue;
 533
 534                                 const ContentFeatures &cf = ndef->get(n);
 535                                 if (!cf.light_propagates)
 536                                         continue;
 537
 538                                 // TODO(hmmmmm): Abstract away direct param1 accesses with a
 539                                 // wrapper, but something lighter than MapNode::get/setLight
 540
 541                                 u8 light_produced = cf.light_source;
 542                                 if (light_produced)
 543                                         n.param1 = light_produced | (light_produced << 4);
 544
 545                                 u8 light = n.param1;
 546                                 if (light) {
 547                                         lightSpread(a, v3s16(x,     y,     z + 1), light);
 548                                         lightSpread(a, v3s16(x,     y + 1, z    ), light);
 549                                         lightSpread(a, v3s16(x + 1, y,     z    ), light);
 550                                         lightSpread(a, v3s16(x,     y,     z - 1), light);
 551                                         lightSpread(a, v3s16(x,     y - 1, z    ), light);
 552                                         lightSpread(a, v3s16(x - 1, y,     z    ), light);
 553                                 }
 554                         }
 555                 }
 556         }
 557
 558         //printf("spreadLight: %dms\n", t.stop());
 559 }
 560
 561
 562 ////
 563 //// MapgenBasic
 564 ////
 565
 566 MapgenBasic::MapgenBasic(int mapgenid, MapgenParams *params, EmergeManager *emerge)
 567         : Mapgen(mapgenid, params, emerge)
 568 {
 569         this->m_emerge = emerge;
 570         this->m_bmgr   = emerge->biomemgr;
 571
 572         //// Here, 'stride' refers to the number of elements needed to skip to index
 573         //// an adjacent element for that coordinate in noise/height/biome maps
 574         //// (*not* vmanip content map!)
 575
 576         // Note there is no X stride explicitly defined.  Items adjacent in the X
 577         // coordinate are assumed to be adjacent in memory as well (i.e. stride of 1).
 578
 579         // Number of elements to skip to get to the next Y coordinate
 580         this->ystride = csize.X;
 581
 582         // Number of elements to skip to get to the next Z coordinate
 583         this->zstride = csize.X * csize.Y;
 584
 585         // Z-stride value for maps oversized for 1-down overgeneration
 586         this->zstride_1d = csize.X * (csize.Y + 1);
 587
 588         // Z-stride value for maps oversized for 1-up 1-down overgeneration
 589         this->zstride_1u1d = csize.X * (csize.Y + 2);
 590
 591         //// Allocate heightmap
 592         this->heightmap = new s16[csize.X * csize.Z];
 593
 594         //// Initialize biome generator
 595         // TODO(hmmmm): should we have a way to disable biomemanager biomes?
 596         biomegen = m_bmgr->createBiomeGen(BIOMEGEN_ORIGINAL, params->bparams, csize);
 597         biomemap = biomegen->biomemap;
 598
 599         //// Look up some commonly used content
 600         c_stone              = ndef->getId("mapgen_stone");
 601         c_desert_stone       = ndef->getId("mapgen_desert_stone");
 602         c_sandstone          = ndef->getId("mapgen_sandstone");
 603         c_water_source       = ndef->getId("mapgen_water_source");
 604         c_river_water_source = ndef->getId("mapgen_river_water_source");
 605         c_lava_source        = ndef->getId("mapgen_lava_source");
 606
 607         // Fall back to more basic content if not defined
 608         // river_water_source cannot fallback to water_source because river water
 609         // needs to be non-renewable and have a short flow range.
 610         if (c_desert_stone == CONTENT_IGNORE)
 611                 c_desert_stone = c_stone;
 612         if (c_sandstone == CONTENT_IGNORE)
 613                 c_sandstone = c_stone;
 614
 615         //// Content used for dungeon generation
 616         c_cobble                = ndef->getId("mapgen_cobble");
 617         c_mossycobble           = ndef->getId("mapgen_mossycobble");
 618         c_stair_cobble          = ndef->getId("mapgen_stair_cobble");
 619         c_stair_desert_stone    = ndef->getId("mapgen_stair_desert_stone");
 620         c_sandstonebrick        = ndef->getId("mapgen_sandstonebrick");
 621         c_stair_sandstone_block = ndef->getId("mapgen_stair_sandstone_block");
 622
 623         // Fall back to more basic content if not defined
 624         if (c_mossycobble == CONTENT_IGNORE)
 625                 c_mossycobble = c_cobble;
 626         if (c_stair_cobble == CONTENT_IGNORE)
 627                 c_stair_cobble = c_cobble;
 628         if (c_stair_desert_stone == CONTENT_IGNORE)
 629                 c_stair_desert_stone = c_desert_stone;
 630         if (c_sandstonebrick == CONTENT_IGNORE)
 631                 c_sandstonebrick = c_sandstone;
 632         if (c_stair_sandstone_block == CONTENT_IGNORE)
 633                 c_stair_sandstone_block = c_sandstonebrick;
 634 }
 635
 636
 637 MapgenBasic::~MapgenBasic()
 638 {
 639         delete biomegen;
 640         delete []heightmap;
 641 }
 642
 643
 644 void MapgenBasic::generateBiomes()
 645 {
 646         // can't generate biomes without a biome generator!
 647         assert(biomegen);
 648         assert(biomemap);
 649
 650         const v3s16 &em = vm->m_area.getExtent();
 651         u32 index = 0;
 652
 653         noise_filler_depth->perlinMap2D(node_min.X, node_min.Z);
 654
 655         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 656         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 657                 Biome *biome = NULL;
 658                 biome_t water_biome_index = 0;
 659                 u16 depth_top = 0;
 660                 u16 base_filler = 0;
 661                 u16 depth_water_top = 0;
 662                 u16 depth_riverbed = 0;
 663                 s16 biome_y_min = -MAX_MAP_GENERATION_LIMIT;
 664                 u32 vi = vm->m_area.index(x, node_max.Y, z);
 665
 666                 // Check node at base of mapchunk above, either a node of a previously
 667                 // generated mapchunk or if not, a node of overgenerated base terrain.
 668                 content_t c_above = vm->m_data[vi + em.X].getContent();
 669                 bool air_above = c_above == CONTENT_AIR;
 670                 bool river_water_above = c_above == c_river_water_source;
 671                 bool water_above = c_above == c_water_source || river_water_above;
 672
 673                 biomemap[index] = BIOME_NONE;
 674
 675                 // If there is air or water above enable top/filler placement, otherwise force
 676                 // nplaced to stone level by setting a number exceeding any possible filler depth.
 677                 u16 nplaced = (air_above || water_above) ? 0 : U16_MAX;
 678
 679                 for (s16 y = node_max.Y; y >= node_min.Y; y--) {
 680                         content_t c = vm->m_data[vi].getContent();
 681                         // Biome is (re)calculated:
 682                         // 1. At the surface of stone below air or water.
 683                         // 2. At the surface of water below air.
 684                         // 3. When stone or water is detected but biome has not yet been calculated.
 685                         // 4. When stone or water is detected just below a biome's lower limit.
 686                         bool is_stone_surface = (c == c_stone) &&
 687                                 (air_above || water_above || !biome || y < biome_y_min); // 1, 3, 4
 688
 689                         bool is_water_surface =
 690                                 (c == c_water_source || c == c_river_water_source) &&
 691                                 (air_above || !biome || y < biome_y_min); // 2, 3, 4
 692
 693                         if (is_stone_surface || is_water_surface) {
 694                                 // (Re)calculate biome
 695                                 biome = biomegen->getBiomeAtIndex(index, v3s16(x, y, z));
 696
 697                                 // Add biome to biomemap at first stone surface detected
 698                                 if (biomemap[index] == BIOME_NONE && is_stone_surface)
 699                                         biomemap[index] = biome->index;
 700
 701                                 // Store biome of first water surface detected, as a fallback
 702                                 // entry for the biomemap.
 703                                 if (water_biome_index == 0 && is_water_surface)
 704                                         water_biome_index = biome->index;
 705
 706                                 depth_top = biome->depth_top;
 707                                 base_filler = MYMAX(depth_top +
 708                                         biome->depth_filler +
 709                                         noise_filler_depth->result[index], 0.0f);
 710                                 depth_water_top = biome->depth_water_top;
 711                                 depth_riverbed = biome->depth_riverbed;
 712                                 biome_y_min = biome->min_pos.Y;
 713                         }
 714
 715                         if (c == c_stone) {
 716                                 content_t c_below = vm->m_data[vi - em.X].getContent();
 717
 718                                 // If the node below isn't solid, make this node stone, so that
 719                                 // any top/filler nodes above are structurally supported.
 720                                 // This is done by aborting the cycle of top/filler placement
 721                                 // immediately by forcing nplaced to stone level.
 722                                 if (c_below == CONTENT_AIR
 723                                                 || c_below == c_water_source
 724                                                 || c_below == c_river_water_source)
 725                                         nplaced = U16_MAX;
 726
 727                                 if (river_water_above) {
 728                                         if (nplaced < depth_riverbed) {
 729                                                 vm->m_data[vi] = MapNode(biome->c_riverbed);
 730                                                 nplaced++;
 731                                         } else {
 732                                                 nplaced = U16_MAX;  // Disable top/filler placement
 733                                                 river_water_above = false;
 734                                         }
 735                                 } else if (nplaced < depth_top) {
 736                                         vm->m_data[vi] = MapNode(biome->c_top);
 737                                         nplaced++;
 738                                 } else if (nplaced < base_filler) {
 739                                         vm->m_data[vi] = MapNode(biome->c_filler);
 740                                         nplaced++;
 741                                 } else {
 742                                         vm->m_data[vi] = MapNode(biome->c_stone);
 743                                         nplaced = U16_MAX;  // Disable top/filler placement
 744                                 }
 745
 746                                 air_above = false;
 747                                 water_above = false;
 748                         } else if (c == c_water_source) {
 749                                 vm->m_data[vi] = MapNode((y > (s32)(water_level - depth_water_top))
 750                                                 ? biome->c_water_top : biome->c_water);
 751                                 nplaced = 0;  // Enable top/filler placement for next surface
 752                                 air_above = false;
 753                                 water_above = true;
 754                         } else if (c == c_river_water_source) {
 755                                 vm->m_data[vi] = MapNode(biome->c_river_water);
 756                                 nplaced = 0;  // Enable riverbed placement for next surface
 757                                 air_above = false;
 758                                 water_above = true;
 759                                 river_water_above = true;
 760                         } else if (c == CONTENT_AIR) {
 761                                 nplaced = 0;  // Enable top/filler placement for next surface
 762                                 air_above = true;
 763                                 water_above = false;
 764                         } else {  // Possible various nodes overgenerated from neighbouring mapchunks
 765                                 nplaced = U16_MAX;  // Disable top/filler placement
 766                                 air_above = false;
 767                                 water_above = false;
 768                         }
 769
 770                         VoxelArea::add_y(em, vi, -1);
 771                 }
 772                 // If no stone surface detected in mapchunk column and a water surface
 773                 // biome fallback exists, add it to the biomemap. This avoids water
 774                 // surface decorations failing in deep water.
 775                 if (biomemap[index] == BIOME_NONE && water_biome_index != 0)
 776                         biomemap[index] = water_biome_index;
 777         }
 778 }
 779
 780
 781 void MapgenBasic::dustTopNodes()
 782 {
 783         if (node_max.Y < water_level)
 784                 return;
 785
 786         const v3s16 &em = vm->m_area.getExtent();
 787         u32 index = 0;
 788
 789         for (s16 z = node_min.Z; z <= node_max.Z; z++)
 790         for (s16 x = node_min.X; x <= node_max.X; x++, index++) {
 791                 Biome *biome = (Biome *)m_bmgr->getRaw(biomemap[index]);
 792
 793                 if (biome->c_dust == CONTENT_IGNORE)
 794                         continue;
 795
 796                 // Check if mapchunk above has generated, if so, drop dust from 16 nodes
 797                 // above current mapchunk top, above decorations that will extend above
 798                 // the current mapchunk. If the mapchunk above has not generated, it
 799                 // will provide this required dust when it does.
 800                 u32 vi = vm->m_area.index(x, full_node_max.Y, z);
 801                 content_t c_full_max = vm->m_data[vi].getContent();
 802                 s16 y_start;
 803
 804                 if (c_full_max == CONTENT_AIR) {
 805                         y_start = full_node_max.Y - 1;
 806                 } else if (c_full_max == CONTENT_IGNORE) {
 807                         vi = vm->m_area.index(x, node_max.Y + 1, z);
 808                         content_t c_max = vm->m_data[vi].getContent();
 809
 810                         if (c_max == CONTENT_AIR)
 811                                 y_start = node_max.Y;
 812                         else
 813                                 continue;
 814                 } else {
 815                         continue;
 816                 }
 817
 818                 vi = vm->m_area.index(x, y_start, z);
 819                 for (s16 y = y_start; y >= node_min.Y - 1; y--) {
 820                         if (vm->m_data[vi].getContent() != CONTENT_AIR)
 821                                 break;
 822
 823                         VoxelArea::add_y(em, vi, -1);
 824                 }
 825
 826                 content_t c = vm->m_data[vi].getContent();
 827                 NodeDrawType dtype = ndef->get(c).drawtype;
 828                 // Only place on cubic, walkable, non-dust nodes.
 829                 // Dust check needed due to avoid double layer of dust caused by
 830                 // dropping dust from 16 nodes above mapchunk top.
 831                 if ((dtype == NDT_NORMAL ||
 832                                 dtype == NDT_ALLFACES ||
 833                                 dtype == NDT_ALLFACES_OPTIONAL ||
 834                                 dtype == NDT_GLASSLIKE ||
 835                                 dtype == NDT_GLASSLIKE_FRAMED ||
 836                                 dtype == NDT_GLASSLIKE_FRAMED_OPTIONAL) &&
 837                                 ndef->get(c).walkable && c != biome->c_dust) {
 838                         VoxelArea::add_y(em, vi, 1);
 839                         vm->m_data[vi] = MapNode(biome->c_dust);
 840                 }
 841         }
 842 }
 843
 844
 845 void MapgenBasic::generateCavesNoiseIntersection(s16 max_stone_y)
 846 {
 847         if (node_min.Y > max_stone_y)
 848                 return;
 849
 850         CavesNoiseIntersection caves_noise(ndef, m_bmgr, csize,
 851                 &np_cave1, &np_cave2, seed, cave_width);
 852
 853         caves_noise.generateCaves(vm, node_min, node_max, biomemap);
 854 }
 855
 856
 857 void MapgenBasic::generateCavesRandomWalk(s16 max_stone_y, s16 large_cave_depth)
 858 {
 859         if (node_min.Y > max_stone_y || node_max.Y > large_cave_depth)
 860                 return;
 861
 862         PseudoRandom ps(blockseed + 21343);
 863         u32 bruises_count = ps.range(0, 2);
 864
 865         for (u32 i = 0; i < bruises_count; i++) {
 866                 CavesRandomWalk cave(ndef, &gennotify, seed, water_level,
 867                         c_water_source, c_lava_source, lava_depth, biomegen);
 868
 869                 cave.makeCave(vm, node_min, node_max, &ps, true, max_stone_y,
 870                         heightmap);
 871         }
 872 }
 873
 874
 875 bool MapgenBasic::generateCavernsNoise(s16 max_stone_y)
 876 {
 877         if (node_min.Y > max_stone_y || node_min.Y > cavern_limit)
 878                 return false;
 879
 880         CavernsNoise caverns_noise(ndef, csize, &np_cavern,
 881                 seed, cavern_limit, cavern_taper, cavern_threshold);
 882
 883         return caverns_noise.generateCaverns(vm, node_min, node_max);
 884 }
 885
 886
 887 void MapgenBasic::generateDungeons(s16 max_stone_y)
 888 {
 889         if (max_stone_y < node_min.Y)
 890                 return;
 891
 892         // Get biome at mapchunk midpoint
 893         v3s16 chunk_mid = node_min + (node_max - node_min) / v3s16(2, 2, 2);
 894         Biome *biome = (Biome *)biomegen->getBiomeAtPoint(chunk_mid);
 895
 896         DungeonParams dp;
 897
 898         dp.seed             = seed;
 899         dp.only_in_ground   = true;
 900         dp.corridor_len_min = 1;
 901         dp.corridor_len_max = 13;
 902         dp.rooms_min        = 2;
 903         dp.rooms_max        = 16;
 904
 905         dp.np_density       = nparams_dungeon_density;
 906         dp.np_alt_wall      = nparams_dungeon_alt_wall;
 907
 908         // Biome-defined dungeon nodes
 909         if (biome->c_dungeon != CONTENT_IGNORE) {
 910                 dp.c_wall              = biome->c_dungeon;
 911                 // If 'node_dungeon_alt' is not defined by biome, it and dp.c_alt_wall
 912                 // become CONTENT_IGNORE which skips the alt wall node placement loop in
 913                 // dungeongen.cpp.
 914                 dp.c_alt_wall          = biome->c_dungeon_alt;
 915                 // Stairs fall back to 'c_dungeon' if not defined by biome
 916                 dp.c_stair = (biome->c_dungeon_stair != CONTENT_IGNORE) ?
 917                         biome->c_dungeon_stair : biome->c_dungeon;
 918
 919                 dp.diagonal_dirs       = false;
 920                 dp.holesize            = v3s16(2, 2, 2);
 921                 dp.room_size_min       = v3s16(6, 4, 6);
 922                 dp.room_size_max       = v3s16(10, 6, 10);
 923                 dp.room_size_large_min = v3s16(10, 8, 10);
 924                 dp.room_size_large_max = v3s16(18, 16, 18);
 925                 dp.notifytype          = GENNOTIFY_DUNGEON;
 926
 927         // Otherwise classic behaviour
 928         } else if (biome->c_stone == c_stone) {
 929                 dp.c_wall              = c_cobble;
 930                 dp.c_alt_wall          = c_mossycobble;
 931                 dp.c_stair             = c_stair_cobble;
 932
 933                 dp.diagonal_dirs       = false;
 934                 dp.holesize            = v3s16(1, 2, 1);
 935                 dp.room_size_min       = v3s16(4, 4, 4);
 936                 dp.room_size_max       = v3s16(8, 6, 8);
 937                 dp.room_size_large_min = v3s16(8, 8, 8);
 938                 dp.room_size_large_max = v3s16(16, 16, 16);
 939                 dp.notifytype          = GENNOTIFY_DUNGEON;
 940
 941         } else if (biome->c_stone == c_desert_stone) {
 942                 dp.c_wall              = c_desert_stone;
 943                 dp.c_alt_wall          = CONTENT_IGNORE;
 944                 dp.c_stair             = c_stair_desert_stone;
 945
 946                 dp.diagonal_dirs       = true;
 947                 dp.holesize            = v3s16(2, 3, 2);
 948                 dp.room_size_min       = v3s16(6, 9, 6);
 949                 dp.room_size_max       = v3s16(10, 11, 10);
 950                 dp.room_size_large_min = v3s16(10, 13, 10);
 951                 dp.room_size_large_max = v3s16(18, 21, 18);
 952                 dp.notifytype          = GENNOTIFY_TEMPLE;
 953
 954         } else if (biome->c_stone == c_sandstone) {
 955                 dp.c_wall              = c_sandstonebrick;
 956                 dp.c_alt_wall          = CONTENT_IGNORE;
 957                 dp.c_stair             = c_stair_sandstone_block;
 958
 959                 dp.diagonal_dirs       = false;
 960                 dp.holesize            = v3s16(2, 2, 2);
 961                 dp.room_size_min       = v3s16(6, 4, 6);
 962                 dp.room_size_max       = v3s16(10, 6, 10);
 963                 dp.room_size_large_min = v3s16(10, 8, 10);
 964                 dp.room_size_large_max = v3s16(18, 16, 18);
 965                 dp.notifytype          = GENNOTIFY_DUNGEON;
 966
 967         // Fallback to using biome 'node_stone'
 968         } else {
 969                 dp.c_wall              = biome->c_stone;
 970                 dp.c_alt_wall          = CONTENT_IGNORE;
 971                 dp.c_stair             = biome->c_stone;
 972
 973                 dp.diagonal_dirs       = false;
 974                 dp.holesize            = v3s16(2, 2, 2);
 975                 dp.room_size_min       = v3s16(6, 4, 6);
 976                 dp.room_size_max       = v3s16(10, 6, 10);
 977                 dp.room_size_large_min = v3s16(10, 8, 10);
 978                 dp.room_size_large_max = v3s16(18, 16, 18);
 979                 dp.notifytype          = GENNOTIFY_DUNGEON;
 980         }
 981
 982         DungeonGen dgen(ndef, &gennotify, &dp);
 983         dgen.generate(vm, blockseed, full_node_min, full_node_max);
 984 }
 985
 986
 987 ////
 988 //// GenerateNotifier
 989 ////
 990
 991 GenerateNotifier::GenerateNotifier(u32 notify_on,
 992         std::set<u32> *notify_on_deco_ids)
 993 {
 994         m_notify_on = notify_on;
 995         m_notify_on_deco_ids = notify_on_deco_ids;
 996 }
 997
 998
 999 void GenerateNotifier::setNotifyOn(u32 notify_on)
1000 {
1001         m_notify_on = notify_on;
1002 }
1003
1004
1005 void GenerateNotifier::setNotifyOnDecoIds(std::set<u32> *notify_on_deco_ids)
1006 {
1007         m_notify_on_deco_ids = notify_on_deco_ids;
1008 }
1009
1010
1011 bool GenerateNotifier::addEvent(GenNotifyType type, v3s16 pos, u32 id)
1012 {
1013         if (!(m_notify_on & (1 << type)))
1014                 return false;
1015
1016         if (type == GENNOTIFY_DECORATION &&
1017                 m_notify_on_deco_ids->find(id) == m_notify_on_deco_ids->end())
1018                 return false;
1019
1020         GenNotifyEvent gne;
1021         gne.type = type;
1022         gne.pos  = pos;
1023         gne.id   = id;
1024         m_notify_events.push_back(gne);
1025
1026         return true;
1027 }
1028
1029
1030 void GenerateNotifier::getEvents(
1031         std::map<std::string, std::vector<v3s16> > &event_map)
1032 {
1033         std::list<GenNotifyEvent>::iterator it;
1034
1035         for (it = m_notify_events.begin(); it != m_notify_events.end(); ++it) {
1036                 GenNotifyEvent &gn = *it;
1037                 std::string name = (gn.type == GENNOTIFY_DECORATION) ?
1038                         "decoration#"+ itos(gn.id) :
1039                         flagdesc_gennotify[gn.type].name;
1040
1041                 event_map[name].push_back(gn.pos);
1042         }
1043 }
1044
1045
1046 void GenerateNotifier::clearEvents()
1047 {
1048         m_notify_events.clear();
1049 }
1050
1051
1052 ////
1053 //// MapgenParams
1054 ////
1055
1056
1057 MapgenParams::~MapgenParams()
1058 {
1059         delete bparams;
1060 }
1061
1062
1063 void MapgenParams::readParams(const Settings *settings)
1064 {
1065         std::string seed_str;
1066         const char *seed_name = (settings == g_settings) ? "fixed_map_seed" : "seed";
1067
1068         if (settings->getNoEx(seed_name, seed_str)) {
1069                 if (!seed_str.empty())
1070                         seed = read_seed(seed_str.c_str());
1071                 else
1072                         myrand_bytes(&seed, sizeof(seed));
1073         }
1074
1075         std::string mg_name;
1076         if (settings->getNoEx("mg_name", mg_name)) {
1077                 mgtype = Mapgen::getMapgenType(mg_name);
1078                 if (mgtype == MAPGEN_INVALID)
1079                         mgtype = MAPGEN_DEFAULT;
1080         }
1081
1082         settings->getS16NoEx("water_level", water_level);
1083         settings->getS16NoEx("mapgen_limit", mapgen_limit);
1084         settings->getS16NoEx("chunksize", chunksize);
1085         settings->getFlagStrNoEx("mg_flags", flags, flagdesc_mapgen);
1086
1087         delete bparams;
1088         bparams = BiomeManager::createBiomeParams(BIOMEGEN_ORIGINAL);
1089         if (bparams) {
1090                 bparams->readParams(settings);
1091                 bparams->seed = seed;
1092         }
1093 }
1094
1095
1096 void MapgenParams::writeParams(Settings *settings) const
1097 {
1098         settings->set("mg_name", Mapgen::getMapgenName(mgtype));
1099         settings->setU64("seed", seed);
1100         settings->setS16("water_level", water_level);
1101         settings->setS16("mapgen_limit", mapgen_limit);
1102         settings->setS16("chunksize", chunksize);
1103         settings->setFlagStr("mg_flags", flags, flagdesc_mapgen, U32_MAX);
1104
1105         if (bparams)
1106                 bparams->writeParams(settings);
1107 }
1108
1109
1110 // Calculate exact edges of the outermost mapchunks that are within the
1111 // set 'mapgen_limit'.
1112 void MapgenParams::calcMapgenEdges()
1113 {
1114         // Central chunk offset, in blocks
1115         s16 ccoff_b = -chunksize / 2;
1116         // Chunksize, in nodes
1117         s32 csize_n = chunksize * MAP_BLOCKSIZE;
1118         // Minp/maxp of central chunk, in nodes
1119         s16 ccmin = ccoff_b * MAP_BLOCKSIZE;
1120         s16 ccmax = ccmin + csize_n - 1;
1121         // Fullminp/fullmaxp of central chunk, in nodes
1122         s16 ccfmin = ccmin - MAP_BLOCKSIZE;
1123         s16 ccfmax = ccmax + MAP_BLOCKSIZE;
1124         // Effective mapgen limit, in blocks
1125         // Uses same calculation as ServerMap::blockpos_over_mapgen_limit(v3s16 p)
1126         s16 mapgen_limit_b = rangelim(mapgen_limit,
1127                 0, MAX_MAP_GENERATION_LIMIT) / MAP_BLOCKSIZE;
1128         // Effective mapgen limits, in nodes
1129         s16 mapgen_limit_min = -mapgen_limit_b * MAP_BLOCKSIZE;
1130         s16 mapgen_limit_max = (mapgen_limit_b + 1) * MAP_BLOCKSIZE - 1;
1131         // Number of complete chunks from central chunk fullminp/fullmaxp
1132         // to effective mapgen limits.
1133         s16 numcmin = MYMAX((ccfmin - mapgen_limit_min) / csize_n, 0);
1134         s16 numcmax = MYMAX((mapgen_limit_max - ccfmax) / csize_n, 0);
1135         // Mapgen edges, in nodes
1136         mapgen_edge_min = ccmin - numcmin * csize_n;
1137         mapgen_edge_max = ccmax + numcmax * csize_n;
1138
1139         m_mapgen_edges_calculated = true;
1140 }
1141
1142
1143 s32 MapgenParams::getSpawnRangeMax()
1144 {
1145         if (!m_mapgen_edges_calculated)
1146                 calcMapgenEdges();
1147
1148         return MYMIN(-mapgen_edge_min, mapgen_edge_max);
1149 }