src/treegen.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>,
   4                           2012-2013 RealBadAngel, Maciej Kasatkin <mk@realbadangel.pl>
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "irr_v3d.h"
  21 #include <stack>
  22 #include "util/pointer.h"
  23 #include "util/numeric.h"
  24 #include "util/mathconstants.h"
  25 #include "map.h"
  26 #include "environment.h"
  27 #include "nodedef.h"
  28 #include "treegen.h"
  29
  30 namespace treegen
  31 {
  32
  33 void make_tree(MMVManip &vmanip, v3s16 p0,
  34                 bool is_apple_tree, INodeDefManager *ndef, s32 seed)
  35 {
  36         /*
  37                 NOTE: Tree-placing code is currently duplicated in the engine
  38                 and in games that have saplings; both are deprecated but not
  39                 replaced yet
  40         */
  41         MapNode treenode(ndef->getId("mapgen_tree"));
  42         MapNode leavesnode(ndef->getId("mapgen_leaves"));
  43         MapNode applenode(ndef->getId("mapgen_apple"));
  44
  45         PseudoRandom pr(seed);
  46         s16 trunk_h = pr.range(4, 5);
  47         v3s16 p1 = p0;
  48         for (s16 ii = 0; ii < trunk_h; ii++) {
  49                 if (vmanip.m_area.contains(p1)) {
  50                         u32 vi = vmanip.m_area.index(p1);
  51                         vmanip.m_data[vi] = treenode;
  52                 }
  53                 p1.Y++;
  54         }
  55
  56         // p1 is now the last piece of the trunk
  57         p1.Y -= 1;
  58
  59         VoxelArea leaves_a(v3s16(-2, -1, -2), v3s16(2, 2, 2));
  60         //SharedPtr<u8> leaves_d(new u8[leaves_a.getVolume()]);
  61         Buffer<u8> leaves_d(leaves_a.getVolume());
  62         for (s32 i = 0; i < leaves_a.getVolume(); i++)
  63                 leaves_d[i] = 0;
  64
  65         // Force leaves at near the end of the trunk
  66         s16 d = 1;
  67         for (s16 z = -d; z <= d; z++)
  68         for (s16 y = -d; y <= d; y++)
  69         for (s16 x = -d; x <= d; x++) {
  70                 leaves_d[leaves_a.index(v3s16(x, y, z))] = 1;
  71         }
  72
  73         // Add leaves randomly
  74         for (u32 iii = 0; iii < 7; iii++) {
  75                 v3s16 p(
  76                         pr.range(leaves_a.MinEdge.X, leaves_a.MaxEdge.X - d),
  77                         pr.range(leaves_a.MinEdge.Y, leaves_a.MaxEdge.Y - d),
  78                         pr.range(leaves_a.MinEdge.Z, leaves_a.MaxEdge.Z - d)
  79                 );
  80
  81                 for (s16 z = 0; z <= d; z++)
  82                 for (s16 y = 0; y <= d; y++)
  83                 for (s16 x = 0; x <= d; x++) {
  84                         leaves_d[leaves_a.index(p + v3s16(x, y, z))] = 1;
  85                 }
  86         }
  87
  88         // Blit leaves to vmanip
  89         for (s16 z = leaves_a.MinEdge.Z; z <= leaves_a.MaxEdge.Z; z++)
  90         for (s16 y = leaves_a.MinEdge.Y; y <= leaves_a.MaxEdge.Y; y++) {
  91                 v3s16 pmin(leaves_a.MinEdge.X, y, z);
  92                 u32 i = leaves_a.index(pmin);
  93                 u32 vi = vmanip.m_area.index(pmin + p1);
  94                 for (s16 x = leaves_a.MinEdge.X; x <= leaves_a.MaxEdge.X; x++) {
  95                         v3s16 p(x, y, z);
  96                         if (vmanip.m_area.contains(p + p1) == true &&
  97                                         (vmanip.m_data[vi].getContent() == CONTENT_AIR ||
  98                                         vmanip.m_data[vi].getContent() == CONTENT_IGNORE)) {
  99                                 if (leaves_d[i] == 1) {
 100                                         bool is_apple = pr.range(0, 99) < 10;
 101                                         if (is_apple_tree && is_apple)
 102                                                 vmanip.m_data[vi] = applenode;
 103                                         else
 104                                                 vmanip.m_data[vi] = leavesnode;
 105                                 }
 106                         }
 107                         vi++;
 108                         i++;
 109                 }
 110         }
 111 }
 112
 113
 114 // L-System tree LUA spawner
 115 treegen::error spawn_ltree(ServerEnvironment *env, v3s16 p0,
 116                 INodeDefManager *ndef, TreeDef tree_definition)
 117 {
 118         ServerMap *map = &env->getServerMap();
 119         std::map<v3s16, MapBlock*> modified_blocks;
 120         MMVManip vmanip(map);
 121         v3s16 tree_blockp = getNodeBlockPos(p0);
 122         treegen::error e;
 123
 124         vmanip.initialEmerge(tree_blockp - v3s16(1, 1, 1), tree_blockp + v3s16(1, 3, 1));
 125         e = make_ltree(vmanip, p0, ndef, tree_definition);
 126         if (e != SUCCESS)
 127                 return e;
 128
 129         vmanip.blitBackAll(&modified_blocks);
 130
 131         // update lighting
 132         std::map<v3s16, MapBlock*> lighting_modified_blocks;
 133         lighting_modified_blocks.insert(modified_blocks.begin(), modified_blocks.end());
 134         map->updateLighting(lighting_modified_blocks, modified_blocks);
 135         // Send a MEET_OTHER event
 136         MapEditEvent event;
 137         event.type = MEET_OTHER;
 138         for (std::map<v3s16, MapBlock*>::iterator
 139                         i = modified_blocks.begin();
 140                         i != modified_blocks.end(); ++i)
 141                 event.modified_blocks.insert(i->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                 INodeDefManager *ndef, TreeDef tree_definition)
 150 {
 151         MapNode dirtnode(ndef->getId("mapgen_dirt"));
 152         s32 seed;
 153         if (tree_definition.explicit_seed)
 154                 seed = tree_definition.seed + 14002;
 155         else
 156                 seed = p0.X * 2 + p0.Y * 4 + p0.Z;  // use the tree position to seed PRNG
 157         PseudoRandom ps(seed);
 158
 159         // chance of inserting abcd rules
 160         double prop_a = 9;
 161         double prop_b = 8;
 162         double prop_c = 7;
 163         double prop_d = 6;
 164
 165         //randomize tree growth level, minimum=2
 166         s16 iterations = tree_definition.iterations;
 167         if (tree_definition.iterations_random_level > 0)
 168                 iterations -= ps.range(0, tree_definition.iterations_random_level);
 169         if (iterations < 2)
 170                 iterations = 2;
 171
 172         s16 MAX_ANGLE_OFFSET = 5;
 173         double angle_in_radians = (double)tree_definition.angle * M_PI / 180;
 174         double angleOffset_in_radians = (s16)(ps.range(0, 1) % MAX_ANGLE_OFFSET) * M_PI / 180;
 175
 176         //initialize rotation matrix, position and stacks for branches
 177         core::matrix4 rotation;
 178         rotation = setRotationAxisRadians(rotation, M_PI / 2, v3f(0, 0, 1));
 179         v3f position;
 180         position.X = p0.X;
 181         position.Y = p0.Y;
 182         position.Z = p0.Z;
 183         std::stack <core::matrix4> stack_orientation;
 184         std::stack <v3f> stack_position;
 185
 186         //generate axiom
 187         std::string axiom = tree_definition.initial_axiom;
 188         for (s16 i = 0; i < iterations; i++) {
 189                 std::string temp = "";
 190                 for (s16 j = 0; j < (s16)axiom.size(); j++) {
 191                         char axiom_char = axiom.at(j);
 192                         switch (axiom_char) {
 193                         case 'A':
 194                                 temp += tree_definition.rules_a;
 195                                 break;
 196                         case 'B':
 197                                 temp += tree_definition.rules_b;
 198                                 break;
 199                         case 'C':
 200                                 temp += tree_definition.rules_c;
 201                                 break;
 202                         case 'D':
 203                                 temp += tree_definition.rules_d;
 204                                 break;
 205                         case 'a':
 206                                 if (prop_a >= ps.range(1, 10))
 207                                         temp += tree_definition.rules_a;
 208                                 break;
 209                         case 'b':
 210                                 if (prop_b >= ps.range(1, 10))
 211                                         temp += tree_definition.rules_b;
 212                                 break;
 213                         case 'c':
 214                                 if (prop_c >= ps.range(1, 10))
 215                                         temp += tree_definition.rules_c;
 216                                 break;
 217                         case 'd':
 218                                 if (prop_d >= ps.range(1, 10))
 219                                         temp += tree_definition.rules_d;
 220                                 break;
 221                         default:
 222                                 temp += axiom_char;
 223                                 break;
 224                         }
 225                 }
 226                 axiom = temp;
 227         }
 228
 229         //make sure tree is not floating in the air
 230         if (tree_definition.trunk_type == "double") {
 231                 tree_node_placement(
 232                         vmanip,
 233                         v3f(position.X + 1, position.Y - 1, position.Z),
 234                         dirtnode
 235                 );
 236                 tree_node_placement(
 237                         vmanip,
 238                         v3f(position.X, position.Y - 1, position.Z + 1),
 239                         dirtnode
 240                 );
 241                 tree_node_placement(
 242                         vmanip,
 243                         v3f(position.X + 1, position.Y - 1, position.Z + 1),
 244                         dirtnode
 245                 );
 246         } else if (tree_definition.trunk_type == "crossed") {
 247                 tree_node_placement(
 248                         vmanip,
 249                         v3f(position.X + 1, position.Y - 1, position.Z),
 250                         dirtnode
 251                 );
 252                 tree_node_placement(
 253                         vmanip,
 254                         v3f(position.X - 1, position.Y - 1, position.Z),
 255                         dirtnode
 256                 );
 257                 tree_node_placement(
 258                         vmanip,
 259                         v3f(position.X, position.Y - 1, position.Z + 1),
 260                         dirtnode
 261                 );
 262                 tree_node_placement(
 263                         vmanip,
 264                         v3f(position.X, position.Y - 1, position.Z - 1),
 265                         dirtnode
 266                 );
 267         }
 268
 269         /* build tree out of generated axiom
 270
 271         Key for Special L-System Symbols used in Axioms
 272
 273     G  - move forward one unit with the pen up
 274     F  - move forward one unit with the pen down drawing trunks and branches
 275     f  - move forward one unit with the pen down drawing leaves (100% chance)
 276     T  - move forward one unit with the pen down drawing trunks only
 277     R  - move forward one unit with the pen down placing fruit
 278     A  - replace with rules set A
 279     B  - replace with rules set B
 280     C  - replace with rules set C
 281     D  - replace with rules set D
 282     a  - replace with rules set A, chance 90%
 283     b  - replace with rules set B, chance 80%
 284     c  - replace with rules set C, chance 70%
 285     d  - replace with rules set D, chance 60%
 286     +  - yaw the turtle right by angle degrees
 287     -  - yaw the turtle left by angle degrees
 288     &  - pitch the turtle down by angle degrees
 289     ^  - pitch the turtle up by angle degrees
 290     /  - roll the turtle to the right by angle degrees
 291     *  - roll the turtle to the left by angle degrees
 292     [  - save in stack current state info
 293     ]  - recover from stack state info
 294
 295     */
 296
 297         s16 x,y,z;
 298         for (s16 i = 0; i < (s16)axiom.size(); i++) {
 299                 char axiom_char = axiom.at(i);
 300                 core::matrix4 temp_rotation;
 301                 temp_rotation.makeIdentity();
 302                 v3f dir;
 303                 switch (axiom_char) {
 304                 case 'G':
 305                         dir = v3f(1, 0, 0);
 306                         dir = transposeMatrix(rotation, dir);
 307                         position += dir;
 308                         break;
 309                 case 'T':
 310                         tree_trunk_placement(
 311                                 vmanip,
 312                                 v3f(position.X, position.Y, position.Z),
 313                                 tree_definition
 314                         );
 315                         if (tree_definition.trunk_type == "double" &&
 316                                         !tree_definition.thin_branches) {
 317                                 tree_trunk_placement(
 318                                         vmanip,
 319                                         v3f(position.X + 1, position.Y, position.Z),
 320                                         tree_definition
 321                                 );
 322                                 tree_trunk_placement(
 323                                         vmanip,
 324                                         v3f(position.X, position.Y, position.Z + 1),
 325                                         tree_definition
 326                                 );
 327                                 tree_trunk_placement(
 328                                         vmanip,
 329                                         v3f(position.X + 1, position.Y, position.Z + 1),
 330                                         tree_definition
 331                                 );
 332                         } else if (tree_definition.trunk_type == "crossed" &&
 333                                         !tree_definition.thin_branches) {
 334                                 tree_trunk_placement(
 335                                         vmanip,
 336                                         v3f(position.X + 1, position.Y, position.Z),
 337                                         tree_definition
 338                                 );
 339                                 tree_trunk_placement(
 340                                         vmanip,
 341                                         v3f(position.X - 1, position.Y, position.Z),
 342                                         tree_definition
 343                                 );
 344                                 tree_trunk_placement(
 345                                         vmanip,
 346                                         v3f(position.X, position.Y, position.Z + 1),
 347                                         tree_definition
 348                                 );
 349                                 tree_trunk_placement(
 350                                         vmanip,
 351                                         v3f(position.X, position.Y, position.Z - 1),
 352                                         tree_definition
 353                                 );
 354                         }
 355                         dir = v3f(1, 0, 0);
 356                         dir = transposeMatrix(rotation, dir);
 357                         position += dir;
 358                         break;
 359                 case 'F':
 360                         tree_trunk_placement(
 361                                 vmanip,
 362                                 v3f(position.X, position.Y, position.Z),
 363                                 tree_definition
 364                         );
 365                         if ((stack_orientation.empty() &&
 366                                         tree_definition.trunk_type == "double") ||
 367                                         (!stack_orientation.empty() &&
 368                                         tree_definition.trunk_type == "double" &&
 369                                         !tree_definition.thin_branches)) {
 370                                 tree_trunk_placement(
 371                                         vmanip,
 372                                         v3f(position.X +1 , position.Y, position.Z),
 373                                         tree_definition
 374                                 );
 375                                 tree_trunk_placement(
 376                                         vmanip,
 377                                         v3f(position.X, position.Y, position.Z + 1),
 378                                         tree_definition
 379                                 );
 380                                 tree_trunk_placement(
 381                                         vmanip,
 382                                         v3f(position.X + 1, position.Y, position.Z + 1),
 383                                         tree_definition
 384                                 );
 385                         } else if ((stack_orientation.empty() &&
 386                                         tree_definition.trunk_type == "crossed") ||
 387                                         (!stack_orientation.empty() &&
 388                                         tree_definition.trunk_type == "crossed" &&
 389                                         !tree_definition.thin_branches)) {
 390                                 tree_trunk_placement(
 391                                         vmanip,
 392                                         v3f(position.X + 1, position.Y, position.Z),
 393                                         tree_definition
 394                                 );
 395                                 tree_trunk_placement(
 396                                         vmanip,
 397                                         v3f(position.X - 1, position.Y, position.Z),
 398                                         tree_definition
 399                                 );
 400                                 tree_trunk_placement(
 401                                         vmanip,
 402                                         v3f(position.X, position.Y, position.Z + 1),
 403                                         tree_definition
 404                                 );
 405                                 tree_trunk_placement(
 406                                         vmanip,
 407                                         v3f(position.X, position.Y, position.Z - 1),
 408                                         tree_definition
 409                                 );
 410                         } if (stack_orientation.empty() == false) {
 411                                 s16 size = 1;
 412                                 for (x = -size; x <= size; x++)
 413                                 for (y = -size; y <= size; y++)
 414                                 for (z = -size; z <= size; z++) {
 415                                         if (abs(x) == size &&
 416                                                         abs(y) == size &&
 417                                                         abs(z) == size) {
 418                                                 tree_leaves_placement(
 419                                                         vmanip,
 420                                                         v3f(position.X + x + 1, position.Y + y,
 421                                                                         position.Z + z),
 422                                                         ps.next(),
 423                                                         tree_definition
 424                                                 );
 425                                                 tree_leaves_placement(
 426                                                         vmanip,
 427                                                         v3f(position.X + x - 1, position.Y + y,
 428                                                                         position.Z + z),
 429                                                         ps.next(),
 430                                                         tree_definition
 431                                                 );
 432                                                 tree_leaves_placement(
 433                                                         vmanip,v3f(position.X + x, position.Y + y,
 434                                                                         position.Z + z + 1),
 435                                                         ps.next(),
 436                                                         tree_definition
 437                                                 );
 438                                                 tree_leaves_placement(
 439                                                         vmanip,v3f(position.X + x, position.Y + y,
 440                                                                         position.Z + z - 1),
 441                                                         ps.next(),
 442                                                         tree_definition
 443                                                 );
 444                                         }
 445                                 }
 446                         }
 447                         dir = v3f(1, 0, 0);
 448                         dir = transposeMatrix(rotation, dir);
 449                         position += dir;
 450                         break;
 451                 case 'f':
 452                         tree_single_leaves_placement(
 453                                 vmanip,
 454                                 v3f(position.X, position.Y, position.Z),
 455                                 ps.next(),
 456                                 tree_definition
 457                         );
 458                         dir = v3f(1, 0, 0);
 459                         dir = transposeMatrix(rotation, dir);
 460                         position += dir;
 461                         break;
 462                 case 'R':
 463                         tree_fruit_placement(
 464                                 vmanip,
 465                                 v3f(position.X, position.Y, position.Z),
 466                                 tree_definition
 467                         );
 468                         dir = v3f(1, 0, 0);
 469                         dir = transposeMatrix(rotation, dir);
 470                         position += dir;
 471                         break;
 472
 473                 // turtle orientation commands
 474                 case '[':
 475                         stack_orientation.push(rotation);
 476                         stack_position.push(position);
 477                         break;
 478                 case ']':
 479                         if (stack_orientation.empty())
 480                                 return UNBALANCED_BRACKETS;
 481                         rotation = stack_orientation.top();
 482                         stack_orientation.pop();
 483                         position = stack_position.top();
 484                         stack_position.pop();
 485                         break;
 486                 case '+':
 487                         temp_rotation.makeIdentity();
 488                         temp_rotation = setRotationAxisRadians(temp_rotation,
 489                                         angle_in_radians + angleOffset_in_radians, v3f(0, 0, 1));
 490                         rotation *= temp_rotation;
 491                         break;
 492                 case '-':
 493                         temp_rotation.makeIdentity();
 494                         temp_rotation = setRotationAxisRadians(temp_rotation,
 495                                         angle_in_radians + angleOffset_in_radians, v3f(0, 0, -1));
 496                         rotation *= temp_rotation;
 497                         break;
 498                 case '&':
 499                         temp_rotation.makeIdentity();
 500                         temp_rotation = setRotationAxisRadians(temp_rotation,
 501                                         angle_in_radians + angleOffset_in_radians, v3f(0, 1, 0));
 502                         rotation *= temp_rotation;
 503                         break;
 504                 case '^':
 505                         temp_rotation.makeIdentity();
 506                         temp_rotation = setRotationAxisRadians(temp_rotation,
 507                                         angle_in_radians + angleOffset_in_radians, v3f(0, -1, 0));
 508                         rotation *= temp_rotation;
 509                         break;
 510                 case '*':
 511                         temp_rotation.makeIdentity();
 512                         temp_rotation = setRotationAxisRadians(temp_rotation,
 513                                         angle_in_radians, v3f(1, 0, 0));
 514                         rotation *= temp_rotation;
 515                         break;
 516                 case '/':
 517                         temp_rotation.makeIdentity();
 518                         temp_rotation = setRotationAxisRadians(temp_rotation,
 519                                         angle_in_radians, v3f(-1, 0, 0));
 520                         rotation *= temp_rotation;
 521                         break;
 522                 default:
 523                         break;
 524                 }
 525         }
 526
 527         return SUCCESS;
 528 }
 529
 530
 531 void tree_node_placement(MMVManip &vmanip, v3f p0, MapNode node)
 532 {
 533         v3s16 p1 = v3s16(myround(p0.X), myround(p0.Y), myround(p0.Z));
 534         if (vmanip.m_area.contains(p1) == false)
 535                 return;
 536         u32 vi = vmanip.m_area.index(p1);
 537         if (vmanip.m_data[vi].getContent() != CONTENT_AIR
 538                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 539                 return;
 540         vmanip.m_data[vmanip.m_area.index(p1)] = node;
 541 }
 542
 543
 544 void tree_trunk_placement(MMVManip &vmanip, v3f p0, TreeDef &tree_definition)
 545 {
 546         v3s16 p1 = v3s16(myround(p0.X), myround(p0.Y), myround(p0.Z));
 547         if (vmanip.m_area.contains(p1) == false)
 548                 return;
 549         u32 vi = vmanip.m_area.index(p1);
 550         if (vmanip.m_data[vi].getContent() != CONTENT_AIR
 551                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 552                 return;
 553         vmanip.m_data[vmanip.m_area.index(p1)] = tree_definition.trunknode;
 554 }
 555
 556
 557 void tree_leaves_placement(MMVManip &vmanip, v3f p0,
 558                 PseudoRandom ps, TreeDef &tree_definition)
 559 {
 560         MapNode leavesnode = tree_definition.leavesnode;
 561         if (ps.range(1, 100) > 100 - tree_definition.leaves2_chance)
 562                 leavesnode = tree_definition.leaves2node;
 563         v3s16 p1 = v3s16(myround(p0.X), myround(p0.Y), myround(p0.Z));
 564         if (vmanip.m_area.contains(p1) == false)
 565                 return;
 566         u32 vi = vmanip.m_area.index(p1);
 567         if (vmanip.m_data[vi].getContent() != CONTENT_AIR
 568                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 569                 return;
 570         if (tree_definition.fruit_chance > 0) {
 571                 if (ps.range(1, 100) > 100 - tree_definition.fruit_chance)
 572                         vmanip.m_data[vmanip.m_area.index(p1)] = tree_definition.fruitnode;
 573                 else
 574                         vmanip.m_data[vmanip.m_area.index(p1)] = leavesnode;
 575         } else if (ps.range(1, 100) > 20) {
 576                 vmanip.m_data[vmanip.m_area.index(p1)] = leavesnode;
 577         }
 578 }
 579
 580
 581 void tree_single_leaves_placement(MMVManip &vmanip, v3f p0,
 582                 PseudoRandom ps, TreeDef &tree_definition)
 583 {
 584         MapNode leavesnode = tree_definition.leavesnode;
 585         if (ps.range(1, 100) > 100 - tree_definition.leaves2_chance)
 586                 leavesnode = tree_definition.leaves2node;
 587         v3s16 p1 = v3s16(myround(p0.X), myround(p0.Y), myround(p0.Z));
 588         if (vmanip.m_area.contains(p1) == false)
 589                 return;
 590         u32 vi = vmanip.m_area.index(p1);
 591         if (vmanip.m_data[vi].getContent() != CONTENT_AIR
 592                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 593                 return;
 594         vmanip.m_data[vmanip.m_area.index(p1)] = leavesnode;
 595 }
 596
 597
 598 void tree_fruit_placement(MMVManip &vmanip, v3f p0, TreeDef &tree_definition)
 599 {
 600         v3s16 p1 = v3s16(myround(p0.X), myround(p0.Y), myround(p0.Z));
 601         if (vmanip.m_area.contains(p1) == false)
 602                 return;
 603         u32 vi = vmanip.m_area.index(p1);
 604         if (vmanip.m_data[vi].getContent() != CONTENT_AIR
 605                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 606                 return;
 607         vmanip.m_data[vmanip.m_area.index(p1)] = tree_definition.fruitnode;
 608 }
 609
 610
 611 irr::core::matrix4 setRotationAxisRadians(irr::core::matrix4 M, double angle, v3f axis)
 612 {
 613         double c = cos(angle);
 614         double s = sin(angle);
 615         double t = 1.0 - c;
 616
 617         double tx  = t * axis.X;
 618         double ty  = t * axis.Y;
 619         double tz  = t * axis.Z;
 620         double sx  = s * axis.X;
 621         double sy  = s * axis.Y;
 622         double sz  = s * axis.Z;
 623
 624         M[0] = tx * axis.X + c;
 625         M[1] = tx * axis.Y + sz;
 626         M[2] = tx * axis.Z - sy;
 627
 628         M[4] = ty * axis.X - sz;
 629         M[5] = ty * axis.Y + c;
 630         M[6] = ty * axis.Z + sx;
 631
 632         M[8]  = tz * axis.X + sy;
 633         M[9]  = tz * axis.Y - sx;
 634         M[10] = tz * axis.Z + c;
 635         return M;
 636 }
 637
 638
 639 v3f transposeMatrix(irr::core::matrix4 M, v3f v)
 640 {
 641         v3f translated;
 642         double x = M[0] * v.X + M[4] * v.Y + M[8]  * v.Z +M[12];
 643         double y = M[1] * v.X + M[5] * v.Y + M[9]  * v.Z +M[13];
 644         double z = M[2] * v.X + M[6] * v.Y + M[10] * v.Z +M[14];
 645         translated.X = x;
 646         translated.Y = y;
 647         translated.Z = z;
 648         return translated;
 649 }
 650
 651
 652 void make_jungletree(MMVManip &vmanip, v3s16 p0, INodeDefManager *ndef, 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) == true &&
 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, INodeDefManager *ndef, s32 seed)
 752 {
 753         /*
 754                 NOTE: Tree-placing code is currently duplicated in the engine
 755                 and in games that have saplings; both are deprecated but not
 756                 replaced yet
 757         */
 758         content_t c_tree   = ndef->getId("mapgen_pine_tree");
 759         content_t c_leaves = ndef->getId("mapgen_pine_needles");
 760         content_t c_snow = ndef->getId("mapgen_snow");
 761         if (c_tree == CONTENT_IGNORE)
 762                 c_tree = ndef->getId("mapgen_tree");
 763         if (c_leaves == CONTENT_IGNORE)
 764                 c_leaves = ndef->getId("mapgen_leaves");
 765         if (c_snow == CONTENT_IGNORE)
 766                 c_snow = CONTENT_AIR;
 767
 768         MapNode treenode(c_tree);
 769         MapNode leavesnode(c_leaves);
 770         MapNode snownode(c_snow);
 771
 772         PseudoRandom pr(seed);
 773         s16 trunk_h = pr.range(9, 13);
 774         v3s16 p1 = p0;
 775         for (s16 ii = 0; ii < trunk_h; ii++) {
 776                 if (vmanip.m_area.contains(p1)) {
 777                         u32 vi = vmanip.m_area.index(p1);
 778                         vmanip.m_data[vi] = treenode;
 779                 }
 780                 p1.Y++;
 781         }
 782
 783         // Make p1 the top node of the trunk
 784         p1.Y -= 1;
 785
 786         VoxelArea leaves_a(v3s16(-3, -6, -3), v3s16(3, 3, 3));
 787         //SharedPtr<u8> leaves_d(new u8[leaves_a.getVolume()]);
 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         s16 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         u32 i = leaves_a.index(v3s16(0, 1, 0));
 812         leaves_d[i] = 1;
 813         i = leaves_a.index(v3s16(0, 2, 0));
 814         leaves_d[i] = 1;
 815         i = leaves_a.index(v3s16(0, 3, 0));
 816         leaves_d[i] = 2;
 817
 818         // Lower branches
 819         s16 my = -6;
 820         for (u32 iii = 0; iii < 20; iii++) {
 821                 s16 xi = pr.range(-3, 2);
 822                 s16 yy = pr.range(-6, -5);
 823                 s16 zi = pr.range(-3, 2);
 824                 if (yy > my)
 825                         my = yy;
 826                 for (s16 zz = zi; zz <= zi + 1; zz++) {
 827                         u32 i = leaves_a.index(v3s16(xi, yy, zz));
 828                         u32 ia = leaves_a.index(v3s16(xi, yy + 1, zz));
 829                         for (s16 xx = xi; xx <= xi + 1; xx++) {
 830                                 leaves_d[i] = 1;
 831                                 if (leaves_d[ia] == 0)
 832                                         leaves_d[ia] = 2;
 833                                 i++;
 834                                 ia++;
 835                         }
 836                 }
 837         }
 838
 839         dev = 2;
 840         for (s16 yy = my + 1; yy <= my + 2; yy++) {
 841                 for (s16 zz = -dev; zz <= dev; zz++) {
 842                         u32 i = leaves_a.index(v3s16(-dev, yy, zz));
 843                         u32 ia = leaves_a.index(v3s16(-dev, yy + 1, zz));
 844                         for (s16 xx = -dev; xx <= dev; xx++) {
 845                                 if (pr.range(0, 20) <= 19 - dev) {
 846                                         leaves_d[i] = 1;
 847                                         leaves_d[ia] = 2;
 848                                 }
 849                                 i++;
 850                                 ia++;
 851                         }
 852                 }
 853                 dev--;
 854         }
 855
 856         // Blit leaves to vmanip
 857         for (s16 z = leaves_a.MinEdge.Z; z <= leaves_a.MaxEdge.Z; z++)
 858         for (s16 y = leaves_a.MinEdge.Y; y <= leaves_a.MaxEdge.Y; y++) {
 859                 v3s16 pmin(leaves_a.MinEdge.X, y, z);
 860                 u32 i = leaves_a.index(pmin);
 861                 u32 vi = vmanip.m_area.index(pmin + p1);
 862                 for (s16 x = leaves_a.MinEdge.X; x <= leaves_a.MaxEdge.X; x++) {
 863                         v3s16 p(x, y, z);
 864                         if (vmanip.m_area.contains(p + p1) == true &&
 865                                         (vmanip.m_data[vi].getContent() == CONTENT_AIR ||
 866                                         vmanip.m_data[vi].getContent() == CONTENT_IGNORE ||
 867                                         vmanip.m_data[vi] == snownode)) {
 868                                 if (leaves_d[i] == 1)
 869                                         vmanip.m_data[vi] = leavesnode;
 870                                 else if (leaves_d[i] == 2)
 871                                         vmanip.m_data[vi] = snownode;
 872                         }
 873                         vi++;
 874                         i++;
 875                 }
 876         }
 877 }
 878
 879 }; // namespace treegen