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