src/mapgen/treegen.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2018 celeron55, Perttu Ahola <celeron55@gmail.com>,
   4 Copyright (C) 2012-2018 RealBadAngel, Maciej Kasatkin
   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 "irr_v3d.h"
  23 #include <stack>
  24 #include "util/pointer.h"
  25 #include "util/numeric.h"
  26 #include "map.h"
  27 #include "mapblock.h"
  28 #include "nodedef.h"
  29 #include "treegen.h"
  30 #include "voxelalgorithms.h"
  31
  32 namespace treegen
  33 {
  34
  35 void make_tree(MMVManip &vmanip, v3s16 p0, bool is_apple_tree,
  36         const NodeDefManager *ndef, s32 seed)
  37 {
  38         /*
  39                 NOTE: Tree-placing code is currently duplicated in the engine
  40                 and in games that have saplings; both are deprecated but not
  41                 replaced yet
  42         */
  43         MapNode treenode(ndef->getId("mapgen_tree"));
  44         MapNode leavesnode(ndef->getId("mapgen_leaves"));
  45         MapNode applenode(ndef->getId("mapgen_apple"));
  46         if (treenode == CONTENT_IGNORE)
  47                 errorstream << "Treegen: Mapgen alias 'mapgen_tree' is invalid!" << std::endl;
  48         if (leavesnode == CONTENT_IGNORE)
  49                 errorstream << "Treegen: Mapgen alias 'mapgen_leaves' is invalid!" << std::endl;
  50         if (applenode == CONTENT_IGNORE)
  51                 errorstream << "Treegen: Mapgen alias 'mapgen_apple' is invalid!" << std::endl;
  52
  53         PseudoRandom pr(seed);
  54         s16 trunk_h = pr.range(4, 5);
  55         v3s16 p1 = p0;
  56         for (s16 ii = 0; ii < trunk_h; ii++) {
  57                 if (vmanip.m_area.contains(p1)) {
  58                         u32 vi = vmanip.m_area.index(p1);
  59                         vmanip.m_data[vi] = treenode;
  60                 }
  61                 p1.Y++;
  62         }
  63
  64         // p1 is now the last piece of the trunk
  65         p1.Y -= 1;
  66
  67         VoxelArea leaves_a(v3s16(-2, -1, -2), v3s16(2, 2, 2));
  68         Buffer<u8> leaves_d(leaves_a.getVolume());
  69         for (s32 i = 0; i < leaves_a.getVolume(); i++)
  70                 leaves_d[i] = 0;
  71
  72         // Force leaves at near the end of the trunk
  73         s16 d = 1;
  74         for (s16 z = -d; z <= d; z++)
  75         for (s16 y = -d; y <= d; y++)
  76         for (s16 x = -d; x <= d; x++) {
  77                 leaves_d[leaves_a.index(v3s16(x, y, z))] = 1;
  78         }
  79
  80         // Add leaves randomly
  81         for (u32 iii = 0; iii < 7; iii++) {
  82                 v3s16 p(
  83                         pr.range(leaves_a.MinEdge.X, leaves_a.MaxEdge.X - d),
  84                         pr.range(leaves_a.MinEdge.Y, leaves_a.MaxEdge.Y - d),
  85                         pr.range(leaves_a.MinEdge.Z, leaves_a.MaxEdge.Z - d)
  86                 );
  87
  88                 for (s16 z = 0; z <= d; z++)
  89                 for (s16 y = 0; y <= d; y++)
  90                 for (s16 x = 0; x <= d; x++) {
  91                         leaves_d[leaves_a.index(p + v3s16(x, y, z))] = 1;
  92                 }
  93         }
  94
  95         // Blit leaves to vmanip
  96         for (s16 z = leaves_a.MinEdge.Z; z <= leaves_a.MaxEdge.Z; z++)
  97         for (s16 y = leaves_a.MinEdge.Y; y <= leaves_a.MaxEdge.Y; y++) {
  98                 v3s16 pmin(leaves_a.MinEdge.X, y, z);
  99                 u32 i = leaves_a.index(pmin);
 100                 u32 vi = vmanip.m_area.index(pmin + p1);
 101                 for (s16 x = leaves_a.MinEdge.X; x <= leaves_a.MaxEdge.X; x++) {
 102                         v3s16 p(x, y, z);
 103                         if (vmanip.m_area.contains(p + p1) &&
 104                                         (vmanip.m_data[vi].getContent() == CONTENT_AIR ||
 105                                         vmanip.m_data[vi].getContent() == CONTENT_IGNORE)) {
 106                                 if (leaves_d[i] == 1) {
 107                                         bool is_apple = pr.range(0, 99) < 10;
 108                                         if (is_apple_tree && is_apple)
 109                                                 vmanip.m_data[vi] = applenode;
 110                                         else
 111                                                 vmanip.m_data[vi] = leavesnode;
 112                                 }
 113                         }
 114                         vi++;
 115                         i++;
 116                 }
 117         }
 118 }
 119
 120
 121 // L-System tree LUA spawner
 122 treegen::error spawn_ltree(ServerMap *map, v3s16 p0,
 123         const NodeDefManager *ndef, const TreeDef &tree_definition)
 124 {
 125         std::map<v3s16, MapBlock*> modified_blocks;
 126         MMVManip vmanip(map);
 127         v3s16 tree_blockp = getNodeBlockPos(p0);
 128         treegen::error e;
 129
 130         vmanip.initialEmerge(tree_blockp - v3s16(1, 1, 1), tree_blockp + v3s16(1, 3, 1));
 131         e = make_ltree(vmanip, p0, ndef, tree_definition);
 132         if (e != SUCCESS)
 133                 return e;
 134
 135         voxalgo::blit_back_with_light(map, &vmanip, &modified_blocks);
 136
 137         // Send a MEET_OTHER event
 138         MapEditEvent event;
 139         event.type = MEET_OTHER;
 140         for (auto &modified_block : modified_blocks)
 141                 event.modified_blocks.insert(modified_block.first);
 142         map->dispatchEvent(event);
 143         return SUCCESS;
 144 }
 145
 146
 147 //L-System tree generator
 148 treegen::error make_ltree(MMVManip &vmanip, v3s16 p0,
 149         const NodeDefManager *ndef, TreeDef tree_definition)
 150 {
 151         s32 seed;
 152         if (tree_definition.explicit_seed)
 153                 seed = tree_definition.seed + 14002;
 154         else
 155                 seed = p0.X * 2 + p0.Y * 4 + p0.Z;  // use the tree position to seed PRNG
 156         PseudoRandom ps(seed);
 157
 158         // chance of inserting abcd rules
 159         double prop_a = 9;
 160         double prop_b = 8;
 161         double prop_c = 7;
 162         double prop_d = 6;
 163
 164         //randomize tree growth level, minimum=2
 165         s16 iterations = tree_definition.iterations;
 166         if (tree_definition.iterations_random_level > 0)
 167                 iterations -= ps.range(0, tree_definition.iterations_random_level);
 168         if (iterations < 2)
 169                 iterations = 2;
 170
 171         s16 MAX_ANGLE_OFFSET = 5;
 172         double angle_in_radians = (double)tree_definition.angle * M_PI / 180;
 173         double angleOffset_in_radians = (s16)(ps.range(0, 1) % MAX_ANGLE_OFFSET) * M_PI / 180;
 174
 175         //initialize rotation matrix, position and stacks for branches
 176         core::matrix4 rotation;
 177         rotation = setRotationAxisRadians(rotation, M_PI / 2, v3f(0, 0, 1));
 178         v3f position;
 179         position.X = p0.X;
 180         position.Y = p0.Y;
 181         position.Z = p0.Z;
 182         std::stack <core::matrix4> stack_orientation;
 183         std::stack <v3f> stack_position;
 184
 185         //generate axiom
 186         std::string axiom = tree_definition.initial_axiom;
 187         for (s16 i = 0; i < iterations; i++) {
 188                 std::string temp;
 189                 for (s16 j = 0; j < (s16)axiom.size(); j++) {
 190                         char axiom_char = axiom.at(j);
 191                         switch (axiom_char) {
 192                         case 'A':
 193                                 temp += tree_definition.rules_a;
 194                                 break;
 195                         case 'B':
 196                                 temp += tree_definition.rules_b;
 197                                 break;
 198                         case 'C':
 199                                 temp += tree_definition.rules_c;
 200                                 break;
 201                         case 'D':
 202                                 temp += tree_definition.rules_d;
 203                                 break;
 204                         case 'a':
 205                                 if (prop_a >= ps.range(1, 10))
 206                                         temp += tree_definition.rules_a;
 207                                 break;
 208                         case 'b':
 209                                 if (prop_b >= ps.range(1, 10))
 210                                         temp += tree_definition.rules_b;
 211                                 break;
 212                         case 'c':
 213                                 if (prop_c >= ps.range(1, 10))
 214                                         temp += tree_definition.rules_c;
 215                                 break;
 216                         case 'd':
 217                                 if (prop_d >= ps.range(1, 10))
 218                                         temp += tree_definition.rules_d;
 219                                 break;
 220                         default:
 221                                 temp += axiom_char;
 222                                 break;
 223                         }
 224                 }
 225                 axiom = temp;
 226         }
 227
 228         // Add trunk nodes below a wide trunk to avoid gaps when tree is on sloping ground
 229         if (tree_definition.trunk_type == "double") {
 230                 tree_trunk_placement(
 231                         vmanip,
 232                         v3f(position.X + 1, position.Y - 1, position.Z),
 233                         tree_definition
 234                 );
 235                 tree_trunk_placement(
 236                         vmanip,
 237                         v3f(position.X, position.Y - 1, position.Z + 1),
 238                         tree_definition
 239                 );
 240                 tree_trunk_placement(
 241                         vmanip,
 242                         v3f(position.X + 1, position.Y - 1, position.Z + 1),
 243                         tree_definition
 244                 );
 245         } else if (tree_definition.trunk_type == "crossed") {
 246                 tree_trunk_placement(
 247                         vmanip,
 248                         v3f(position.X + 1, position.Y - 1, position.Z),
 249                         tree_definition
 250                 );
 251                 tree_trunk_placement(
 252                         vmanip,
 253                         v3f(position.X - 1, position.Y - 1, position.Z),
 254                         tree_definition
 255                 );
 256                 tree_trunk_placement(
 257                         vmanip,
 258                         v3f(position.X, position.Y - 1, position.Z + 1),
 259                         tree_definition
 260                 );
 261                 tree_trunk_placement(
 262                         vmanip,
 263                         v3f(position.X, position.Y - 1, position.Z - 1),
 264                         tree_definition
 265                 );
 266         }
 267
 268         /* build tree out of generated axiom
 269
 270         Key for Special L-System Symbols used in Axioms
 271
 272     G  - move forward one unit with the pen up
 273     F  - move forward one unit with the pen down drawing trunks and branches
 274     f  - move forward one unit with the pen down drawing leaves (100% chance)
 275     T  - move forward one unit with the pen down drawing trunks only
 276     R  - move forward one unit with the pen down placing fruit
 277     A  - replace with rules set A
 278     B  - replace with rules set B
 279     C  - replace with rules set C
 280     D  - replace with rules set D
 281     a  - replace with rules set A, chance 90%
 282     b  - replace with rules set B, chance 80%
 283     c  - replace with rules set C, chance 70%
 284     d  - replace with rules set D, chance 60%
 285     +  - yaw the turtle right by angle degrees
 286     -  - yaw the turtle left by angle degrees
 287     &  - pitch the turtle down by angle degrees
 288     ^  - pitch the turtle up by angle degrees
 289     /  - roll the turtle to the right by angle degrees
 290     *  - roll the turtle to the left by angle degrees
 291     [  - save in stack current state info
 292     ]  - recover from stack state info
 293
 294     */
 295
 296         s16 x,y,z;
 297         for (s16 i = 0; i < (s16)axiom.size(); i++) {
 298                 char axiom_char = axiom.at(i);
 299                 core::matrix4 temp_rotation;
 300                 temp_rotation.makeIdentity();
 301                 v3f dir;
 302                 switch (axiom_char) {
 303                 case 'G':
 304                         dir = v3f(1, 0, 0);
 305                         dir = transposeMatrix(rotation, dir);
 306                         position += dir;
 307                         break;
 308                 case 'T':
 309                         tree_trunk_placement(
 310                                 vmanip,
 311                                 v3f(position.X, position.Y, position.Z),
 312                                 tree_definition
 313                         );
 314                         if (tree_definition.trunk_type == "double" &&
 315                                         !tree_definition.thin_branches) {
 316                                 tree_trunk_placement(
 317                                         vmanip,
 318                                         v3f(position.X + 1, position.Y, position.Z),
 319                                         tree_definition
 320                                 );
 321                                 tree_trunk_placement(
 322                                         vmanip,
 323                                         v3f(position.X, position.Y, position.Z + 1),
 324                                         tree_definition
 325                                 );
 326                                 tree_trunk_placement(
 327                                         vmanip,
 328                                         v3f(position.X + 1, position.Y, position.Z + 1),
 329                                         tree_definition
 330                                 );
 331                         } else if (tree_definition.trunk_type == "crossed" &&
 332                                         !tree_definition.thin_branches) {
 333                                 tree_trunk_placement(
 334                                         vmanip,
 335                                         v3f(position.X + 1, position.Y, position.Z),
 336                                         tree_definition
 337                                 );
 338                                 tree_trunk_placement(
 339                                         vmanip,
 340                                         v3f(position.X - 1, position.Y, position.Z),
 341                                         tree_definition
 342                                 );
 343                                 tree_trunk_placement(
 344                                         vmanip,
 345                                         v3f(position.X, position.Y, position.Z + 1),
 346                                         tree_definition
 347                                 );
 348                                 tree_trunk_placement(
 349                                         vmanip,
 350                                         v3f(position.X, position.Y, position.Z - 1),
 351                                         tree_definition
 352                                 );
 353                         }
 354                         dir = v3f(1, 0, 0);
 355                         dir = transposeMatrix(rotation, dir);
 356                         position += dir;
 357                         break;
 358                 case 'F':
 359                         tree_trunk_placement(
 360                                 vmanip,
 361                                 v3f(position.X, position.Y, position.Z),
 362                                 tree_definition
 363                         );
 364                         if ((stack_orientation.empty() &&
 365                                         tree_definition.trunk_type == "double") ||
 366                                         (!stack_orientation.empty() &&
 367                                         tree_definition.trunk_type == "double" &&
 368                                         !tree_definition.thin_branches)) {
 369                                 tree_trunk_placement(
 370                                         vmanip,
 371                                         v3f(position.X + 1, position.Y, position.Z),
 372                                         tree_definition
 373                                 );
 374                                 tree_trunk_placement(
 375                                         vmanip,
 376                                         v3f(position.X, position.Y, position.Z + 1),
 377                                         tree_definition
 378                                 );
 379                                 tree_trunk_placement(
 380                                         vmanip,
 381                                         v3f(position.X + 1, position.Y, position.Z + 1),
 382                                         tree_definition
 383                                 );
 384                         } else if ((stack_orientation.empty() &&
 385                                         tree_definition.trunk_type == "crossed") ||
 386                                         (!stack_orientation.empty() &&
 387                                         tree_definition.trunk_type == "crossed" &&
 388                                         !tree_definition.thin_branches)) {
 389                                 tree_trunk_placement(
 390                                         vmanip,
 391                                         v3f(position.X + 1, position.Y, position.Z),
 392                                         tree_definition
 393                                 );
 394                                 tree_trunk_placement(
 395                                         vmanip,
 396                                         v3f(position.X - 1, position.Y, position.Z),
 397                                         tree_definition
 398                                 );
 399                                 tree_trunk_placement(
 400                                         vmanip,
 401                                         v3f(position.X, position.Y, position.Z + 1),
 402                                         tree_definition
 403                                 );
 404                                 tree_trunk_placement(
 405                                         vmanip,
 406                                         v3f(position.X, position.Y, position.Z - 1),
 407                                         tree_definition
 408                                 );
 409                         } if (!stack_orientation.empty()) {
 410                                 s16 size = 1;
 411                                 for (x = -size; x <= size; x++)
 412                                 for (y = -size; y <= size; y++)
 413                                 for (z = -size; z <= size; z++) {
 414                                         if (abs(x) == size &&
 415                                                         abs(y) == size &&
 416                                                         abs(z) == size) {
 417                                                 tree_leaves_placement(
 418                                                         vmanip,
 419                                                         v3f(position.X + x + 1, position.Y + y,
 420                                                                         position.Z + z),
 421                                                         ps.next(),
 422                                                         tree_definition
 423                                                 );
 424                                                 tree_leaves_placement(
 425                                                         vmanip,
 426                                                         v3f(position.X + x - 1, position.Y + y,
 427                                                                         position.Z + z),
 428                                                         ps.next(),
 429                                                         tree_definition
 430                                                 );
 431                                                 tree_leaves_placement(
 432                                                         vmanip,v3f(position.X + x, position.Y + y,
 433                                                                         position.Z + z + 1),
 434                                                         ps.next(),
 435                                                         tree_definition
 436                                                 );
 437                                                 tree_leaves_placement(
 438                                                         vmanip,v3f(position.X + x, position.Y + y,
 439                                                                         position.Z + z - 1),
 440                                                         ps.next(),
 441                                                         tree_definition
 442                                                 );
 443                                         }
 444                                 }
 445                         }
 446                         dir = v3f(1, 0, 0);
 447                         dir = transposeMatrix(rotation, dir);
 448                         position += dir;
 449                         break;
 450                 case 'f':
 451                         tree_single_leaves_placement(
 452                                 vmanip,
 453                                 v3f(position.X, position.Y, position.Z),
 454                                 ps.next(),
 455                                 tree_definition
 456                         );
 457                         dir = v3f(1, 0, 0);
 458                         dir = transposeMatrix(rotation, dir);
 459                         position += dir;
 460                         break;
 461                 case 'R':
 462                         tree_fruit_placement(
 463                                 vmanip,
 464                                 v3f(position.X, position.Y, position.Z),
 465                                 tree_definition
 466                         );
 467                         dir = v3f(1, 0, 0);
 468                         dir = transposeMatrix(rotation, dir);
 469                         position += dir;
 470                         break;
 471
 472                 // turtle orientation commands
 473                 case '[':
 474                         stack_orientation.push(rotation);
 475                         stack_position.push(position);
 476                         break;
 477                 case ']':
 478                         if (stack_orientation.empty())
 479                                 return UNBALANCED_BRACKETS;
 480                         rotation = stack_orientation.top();
 481                         stack_orientation.pop();
 482                         position = stack_position.top();
 483                         stack_position.pop();
 484                         break;
 485                 case '+':
 486                         temp_rotation.makeIdentity();
 487                         temp_rotation = setRotationAxisRadians(temp_rotation,
 488                                         angle_in_radians + angleOffset_in_radians, v3f(0, 0, 1));
 489                         rotation *= temp_rotation;
 490                         break;
 491                 case '-':
 492                         temp_rotation.makeIdentity();
 493                         temp_rotation = setRotationAxisRadians(temp_rotation,
 494                                         angle_in_radians + angleOffset_in_radians, v3f(0, 0, -1));
 495                         rotation *= temp_rotation;
 496                         break;
 497                 case '&':
 498                         temp_rotation.makeIdentity();
 499                         temp_rotation = setRotationAxisRadians(temp_rotation,
 500                                         angle_in_radians + angleOffset_in_radians, v3f(0, 1, 0));
 501                         rotation *= temp_rotation;
 502                         break;
 503                 case '^':
 504                         temp_rotation.makeIdentity();
 505                         temp_rotation = setRotationAxisRadians(temp_rotation,
 506                                         angle_in_radians + angleOffset_in_radians, v3f(0, -1, 0));
 507                         rotation *= temp_rotation;
 508                         break;
 509                 case '*':
 510                         temp_rotation.makeIdentity();
 511                         temp_rotation = setRotationAxisRadians(temp_rotation,
 512                                         angle_in_radians, v3f(1, 0, 0));
 513                         rotation *= temp_rotation;
 514                         break;
 515                 case '/':
 516                         temp_rotation.makeIdentity();
 517                         temp_rotation = setRotationAxisRadians(temp_rotation,
 518                                         angle_in_radians, v3f(-1, 0, 0));
 519                         rotation *= temp_rotation;
 520                         break;
 521                 default:
 522                         break;
 523                 }
 524         }
 525
 526         return SUCCESS;
 527 }
 528
 529
 530 void tree_node_placement(MMVManip &vmanip, v3f p0, MapNode node)
 531 {
 532         v3s16 p1 = v3s16(myround(p0.X), myround(p0.Y), myround(p0.Z));
 533         if (!vmanip.m_area.contains(p1))
 534                 return;
 535         u32 vi = vmanip.m_area.index(p1);
 536         if (vmanip.m_data[vi].getContent() != CONTENT_AIR
 537                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 538                 return;
 539         vmanip.m_data[vmanip.m_area.index(p1)] = node;
 540 }
 541
 542
 543 void tree_trunk_placement(MMVManip &vmanip, v3f p0, TreeDef &tree_definition)
 544 {
 545         v3s16 p1 = v3s16(myround(p0.X), myround(p0.Y), myround(p0.Z));
 546         if (!vmanip.m_area.contains(p1))
 547                 return;
 548         u32 vi = vmanip.m_area.index(p1);
 549         content_t current_node = vmanip.m_data[vi].getContent();
 550         if (current_node != CONTENT_AIR && current_node != CONTENT_IGNORE
 551                         && current_node != tree_definition.leavesnode.getContent()
 552                         && current_node != tree_definition.leaves2node.getContent()
 553                         && current_node != tree_definition.fruitnode.getContent())
 554                 return;
 555         vmanip.m_data[vi] = tree_definition.trunknode;
 556 }
 557
 558
 559 void tree_leaves_placement(MMVManip &vmanip, v3f p0,
 560                 PseudoRandom ps, TreeDef &tree_definition)
 561 {
 562         MapNode leavesnode = tree_definition.leavesnode;
 563         if (ps.range(1, 100) > 100 - tree_definition.leaves2_chance)
 564                 leavesnode = tree_definition.leaves2node;
 565         v3s16 p1 = v3s16(myround(p0.X), myround(p0.Y), myround(p0.Z));
 566         if (!vmanip.m_area.contains(p1))
 567                 return;
 568         u32 vi = vmanip.m_area.index(p1);
 569         if (vmanip.m_data[vi].getContent() != CONTENT_AIR
 570                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 571                 return;
 572         if (tree_definition.fruit_chance > 0) {
 573                 if (ps.range(1, 100) > 100 - tree_definition.fruit_chance)
 574                         vmanip.m_data[vmanip.m_area.index(p1)] = tree_definition.fruitnode;
 575                 else
 576                         vmanip.m_data[vmanip.m_area.index(p1)] = leavesnode;
 577         } else if (ps.range(1, 100) > 20) {
 578                 vmanip.m_data[vmanip.m_area.index(p1)] = leavesnode;
 579         }
 580 }
 581
 582
 583 void tree_single_leaves_placement(MMVManip &vmanip, v3f p0,
 584                 PseudoRandom ps, TreeDef &tree_definition)
 585 {
 586         MapNode leavesnode = tree_definition.leavesnode;
 587         if (ps.range(1, 100) > 100 - tree_definition.leaves2_chance)
 588                 leavesnode = tree_definition.leaves2node;
 589         v3s16 p1 = v3s16(myround(p0.X), myround(p0.Y), myround(p0.Z));
 590         if (!vmanip.m_area.contains(p1))
 591                 return;
 592         u32 vi = vmanip.m_area.index(p1);
 593         if (vmanip.m_data[vi].getContent() != CONTENT_AIR
 594                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 595                 return;
 596         vmanip.m_data[vmanip.m_area.index(p1)] = leavesnode;
 597 }
 598
 599
 600 void tree_fruit_placement(MMVManip &vmanip, v3f p0, TreeDef &tree_definition)
 601 {
 602         v3s16 p1 = v3s16(myround(p0.X), myround(p0.Y), myround(p0.Z));
 603         if (!vmanip.m_area.contains(p1))
 604                 return;
 605         u32 vi = vmanip.m_area.index(p1);
 606         if (vmanip.m_data[vi].getContent() != CONTENT_AIR
 607                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 608                 return;
 609         vmanip.m_data[vmanip.m_area.index(p1)] = tree_definition.fruitnode;
 610 }
 611
 612
 613 irr::core::matrix4 setRotationAxisRadians(irr::core::matrix4 M, double angle, v3f axis)
 614 {
 615         double c = cos(angle);
 616         double s = sin(angle);
 617         double t = 1.0 - c;
 618
 619         double tx  = t * axis.X;
 620         double ty  = t * axis.Y;
 621         double tz  = t * axis.Z;
 622         double sx  = s * axis.X;
 623         double sy  = s * axis.Y;
 624         double sz  = s * axis.Z;
 625
 626         M[0] = tx * axis.X + c;
 627         M[1] = tx * axis.Y + sz;
 628         M[2] = tx * axis.Z - sy;
 629
 630         M[4] = ty * axis.X - sz;
 631         M[5] = ty * axis.Y + c;
 632         M[6] = ty * axis.Z + sx;
 633
 634         M[8]  = tz * axis.X + sy;
 635         M[9]  = tz * axis.Y - sx;
 636         M[10] = tz * axis.Z + c;
 637         return M;
 638 }
 639
 640
 641 v3f transposeMatrix(irr::core::matrix4 M, v3f v)
 642 {
 643         v3f translated;
 644         double x = M[0] * v.X + M[4] * v.Y + M[8]  * v.Z +M[12];
 645         double y = M[1] * v.X + M[5] * v.Y + M[9]  * v.Z +M[13];
 646         double z = M[2] * v.X + M[6] * v.Y + M[10] * v.Z +M[14];
 647         translated.X = x;
 648         translated.Y = y;
 649         translated.Z = z;
 650         return translated;
 651 }
 652
 653
 654 void make_jungletree(MMVManip &vmanip, v3s16 p0, const NodeDefManager *ndef,
 655         s32 seed)
 656 {
 657         /*
 658                 NOTE: Tree-placing code is currently duplicated in the engine
 659                 and in games that have saplings; both are deprecated but not
 660                 replaced yet
 661         */
 662         content_t c_tree   = ndef->getId("mapgen_jungletree");
 663         content_t c_leaves = ndef->getId("mapgen_jungleleaves");
 664         if (c_tree == CONTENT_IGNORE)
 665                 c_tree = ndef->getId("mapgen_tree");
 666         if (c_leaves == CONTENT_IGNORE)
 667                 c_leaves = ndef->getId("mapgen_leaves");
 668         if (c_tree == CONTENT_IGNORE)
 669                 errorstream << "Treegen: Mapgen alias 'mapgen_jungletree' is invalid!" << std::endl;
 670         if (c_leaves == CONTENT_IGNORE)
 671                 errorstream << "Treegen: Mapgen alias 'mapgen_jungleleaves' is invalid!" << std::endl;
 672
 673         MapNode treenode(c_tree);
 674         MapNode leavesnode(c_leaves);
 675
 676         PseudoRandom pr(seed);
 677         for (s16 x= -1; x <= 1; x++)
 678         for (s16 z= -1; z <= 1; z++) {
 679                 if (pr.range(0, 2) == 0)
 680                         continue;
 681                 v3s16 p1 = p0 + v3s16(x, 0, z);
 682                 v3s16 p2 = p0 + v3s16(x, -1, z);
 683                 u32 vi1 = vmanip.m_area.index(p1);
 684                 u32 vi2 = vmanip.m_area.index(p2);
 685
 686                 if (vmanip.m_area.contains(p2) &&
 687                                 vmanip.m_data[vi2].getContent() == CONTENT_AIR)
 688                         vmanip.m_data[vi2] = treenode;
 689                 else if (vmanip.m_area.contains(p1) &&
 690                                 vmanip.m_data[vi1].getContent() == CONTENT_AIR)
 691                         vmanip.m_data[vi1] = treenode;
 692         }
 693         vmanip.m_data[vmanip.m_area.index(p0)] = treenode;
 694
 695         s16 trunk_h = pr.range(8, 12);
 696         v3s16 p1 = p0;
 697         for (s16 ii = 0; ii < trunk_h; ii++) {
 698                 if (vmanip.m_area.contains(p1)) {
 699                         u32 vi = vmanip.m_area.index(p1);
 700                         vmanip.m_data[vi] = treenode;
 701                 }
 702                 p1.Y++;
 703         }
 704
 705         // p1 is now the last piece of the trunk
 706         p1.Y -= 1;
 707
 708         VoxelArea leaves_a(v3s16(-3, -2, -3), v3s16(3, 2, 3));
 709         //SharedPtr<u8> leaves_d(new u8[leaves_a.getVolume()]);
 710         Buffer<u8> leaves_d(leaves_a.getVolume());
 711         for (s32 i = 0; i < leaves_a.getVolume(); i++)
 712                 leaves_d[i] = 0;
 713
 714         // Force leaves at near the end of the trunk
 715         s16 d = 1;
 716         for (s16 z = -d; z <= d; z++)
 717         for (s16 y = -d; y <= d; y++)
 718         for (s16 x = -d; x <= d; x++) {
 719                 leaves_d[leaves_a.index(v3s16(x,y,z))] = 1;
 720         }
 721
 722         // Add leaves randomly
 723         for (u32 iii = 0; iii < 30; iii++) {
 724                 v3s16 p(
 725                         pr.range(leaves_a.MinEdge.X, leaves_a.MaxEdge.X - d),
 726                         pr.range(leaves_a.MinEdge.Y, leaves_a.MaxEdge.Y - d),
 727                         pr.range(leaves_a.MinEdge.Z, leaves_a.MaxEdge.Z - d)
 728                 );
 729
 730                 for (s16 z = 0; z <= d; z++)
 731                 for (s16 y = 0; y <= d; y++)
 732                 for (s16 x = 0; x <= d; x++) {
 733                         leaves_d[leaves_a.index(p + v3s16(x, y, z))] = 1;
 734                 }
 735         }
 736
 737         // Blit leaves to vmanip
 738         for (s16 z = leaves_a.MinEdge.Z; z <= leaves_a.MaxEdge.Z; z++)
 739         for (s16 y = leaves_a.MinEdge.Y; y <= leaves_a.MaxEdge.Y; y++) {
 740                 v3s16 pmin(leaves_a.MinEdge.X, y, z);
 741                 u32 i = leaves_a.index(pmin);
 742                 u32 vi = vmanip.m_area.index(pmin + p1);
 743                 for (s16 x = leaves_a.MinEdge.X; x <= leaves_a.MaxEdge.X; x++) {
 744                         v3s16 p(x, y, z);
 745                         if (vmanip.m_area.contains(p + p1) &&
 746                                         (vmanip.m_data[vi].getContent() == CONTENT_AIR ||
 747                                         vmanip.m_data[vi].getContent() == CONTENT_IGNORE)) {
 748                                 if (leaves_d[i] == 1)
 749                                         vmanip.m_data[vi] = leavesnode;
 750                         }
 751                         vi++;
 752                         i++;
 753                 }
 754         }
 755 }
 756
 757
 758 void make_pine_tree(MMVManip &vmanip, v3s16 p0, const NodeDefManager *ndef,
 759         s32 seed)
 760 {
 761         /*
 762                 NOTE: Tree-placing code is currently duplicated in the engine
 763                 and in games that have saplings; both are deprecated but not
 764                 replaced yet
 765         */
 766         content_t c_tree   = ndef->getId("mapgen_pine_tree");
 767         content_t c_leaves = ndef->getId("mapgen_pine_needles");
 768         content_t c_snow = ndef->getId("mapgen_snow");
 769         if (c_tree == CONTENT_IGNORE)
 770                 c_tree = ndef->getId("mapgen_tree");
 771         if (c_leaves == CONTENT_IGNORE)
 772                 c_leaves = ndef->getId("mapgen_leaves");
 773         if (c_snow == CONTENT_IGNORE)
 774                 c_snow = CONTENT_AIR;
 775         if (c_tree == CONTENT_IGNORE)
 776                 errorstream << "Treegen: Mapgen alias 'mapgen_pine_tree' is invalid!" << std::endl;
 777         if (c_leaves == CONTENT_IGNORE)
 778                 errorstream << "Treegen: Mapgen alias 'mapgen_pine_needles' is invalid!" << std::endl;
 779
 780         MapNode treenode(c_tree);
 781         MapNode leavesnode(c_leaves);
 782         MapNode snownode(c_snow);
 783
 784         PseudoRandom pr(seed);
 785         u16 trunk_h = pr.range(9, 13);
 786         v3s16 p1 = p0;
 787         for (u16 ii = 0; ii < trunk_h; ii++) {
 788                 if (vmanip.m_area.contains(p1)) {
 789                         u32 vi = vmanip.m_area.index(p1);
 790                         vmanip.m_data[vi] = treenode;
 791                 }
 792                 p1.Y++;
 793         }
 794
 795         // Make p1 the top node of the trunk
 796         p1.Y -= 1;
 797
 798         VoxelArea leaves_a(v3s16(-3, -6, -3), v3s16(3, 3, 3));
 799         Buffer<u8> leaves_d(leaves_a.getVolume());
 800         for (s32 i = 0; i < leaves_a.getVolume(); i++)
 801                 leaves_d[i] = 0;
 802
 803         // Upper branches
 804         u16 dev = 3;
 805         for (s16 yy = -1; yy <= 1; yy++) {
 806                 for (s16 zz = -dev; zz <= dev; zz++) {
 807                         u32 i = leaves_a.index(v3s16(-dev, yy, zz));
 808                         u32 ia = leaves_a.index(v3s16(-dev, yy+1, zz));
 809                         for (s16 xx = -dev; xx <= dev; xx++) {
 810                                 if (pr.range(0, 20) <= 19 - dev) {
 811                                         leaves_d[i] = 1;
 812                                         leaves_d[ia] = 2;
 813                                 }
 814                                 i++;
 815                                 ia++;
 816                         }
 817                 }
 818                 dev--;
 819         }
 820
 821         // Centre top nodes
 822         leaves_d[leaves_a.index(v3s16(0, 1, 0))] = 1;
 823         leaves_d[leaves_a.index(v3s16(0, 2, 0))] = 1;
 824         leaves_d[leaves_a.index(v3s16(0, 3, 0))] = 2;
 825
 826         // Lower branches
 827         s16 my = -6;
 828         for (u32 iii = 0; iii < 20; iii++) {
 829                 s16 xi = pr.range(-3, 2);
 830                 s16 yy = pr.range(-6, -5);
 831                 s16 zi = pr.range(-3, 2);
 832                 if (yy > my)
 833                         my = yy;
 834                 for (s16 zz = zi; zz <= zi + 1; zz++) {
 835                         u32 i = leaves_a.index(v3s16(xi, yy, zz));
 836                         u32 ia = leaves_a.index(v3s16(xi, yy + 1, zz));
 837                         for (s32 xx = xi; xx <= xi + 1; xx++) {
 838                                 leaves_d[i] = 1;
 839                                 if (leaves_d[ia] == 0)
 840                                         leaves_d[ia] = 2;
 841                                 i++;
 842                                 ia++;
 843                         }
 844                 }
 845         }
 846
 847         dev = 2;
 848         for (s16 yy = my + 1; yy <= my + 2; yy++) {
 849                 for (s16 zz = -dev; zz <= dev; zz++) {
 850                         u32 i = leaves_a.index(v3s16(-dev, yy, zz));
 851                         u32 ia = leaves_a.index(v3s16(-dev, yy + 1, zz));
 852                         for (s16 xx = -dev; xx <= dev; xx++) {
 853                                 if (pr.range(0, 20) <= 19 - dev) {
 854                                         leaves_d[i] = 1;
 855                                         leaves_d[ia] = 2;
 856                                 }
 857                                 i++;
 858                                 ia++;
 859                         }
 860                 }
 861                 dev--;
 862         }
 863
 864         // Blit leaves to vmanip
 865         for (s16 z = leaves_a.MinEdge.Z; z <= leaves_a.MaxEdge.Z; z++)
 866         for (s16 y = leaves_a.MinEdge.Y; y <= leaves_a.MaxEdge.Y; y++) {
 867                 v3s16 pmin(leaves_a.MinEdge.X, y, z);
 868                 u32 i = leaves_a.index(pmin);
 869                 u32 vi = vmanip.m_area.index(pmin + p1);
 870                 for (s16 x = leaves_a.MinEdge.X; x <= leaves_a.MaxEdge.X; x++) {
 871                         v3s16 p(x, y, z);
 872                         if (vmanip.m_area.contains(p + p1) &&
 873                                         (vmanip.m_data[vi].getContent() == CONTENT_AIR ||
 874                                         vmanip.m_data[vi].getContent() == CONTENT_IGNORE ||
 875                                         vmanip.m_data[vi] == snownode)) {
 876                                 if (leaves_d[i] == 1)
 877                                         vmanip.m_data[vi] = leavesnode;
 878                                 else if (leaves_d[i] == 2)
 879                                         vmanip.m_data[vi] = snownode;
 880                         }
 881                         vi++;
 882                         i++;
 883                 }
 884         }
 885 }
 886
 887 }; // namespace treegen