src/treegen.cpp

   1 /*
   2 Minetest-c55
   3 Copyright (C) 2010-2012 celeron55, Perttu Ahola <celeron55@gmail.com>,
   4                                    2012 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 "noise.h"
  23 #include "map.h"
  24 #include "environment.h"
  25 #include "nodedef.h"
  26 #include "treegen.h"
  27
  28 namespace treegen
  29 {
  30
  31 void make_tree(ManualMapVoxelManipulator &vmanip, v3s16 p0,
  32                 bool is_apple_tree, INodeDefManager *ndef)
  33 {
  34         MapNode treenode(ndef->getId("mapgen_tree"));
  35         MapNode leavesnode(ndef->getId("mapgen_leaves"));
  36         MapNode applenode(ndef->getId("mapgen_apple"));
  37
  38         s16 trunk_h = myrand_range(4, 5);
  39         v3s16 p1 = p0;
  40         for(s16 ii=0; ii<trunk_h; ii++)
  41         {
  42                 if(vmanip.m_area.contains(p1))
  43                         if(ii == 0 || vmanip.getNodeNoExNoEmerge(p1).getContent() == CONTENT_AIR)
  44                                 vmanip.m_data[vmanip.m_area.index(p1)] = treenode;
  45                 p1.Y++;
  46         }
  47
  48         // p1 is now the last piece of the trunk
  49         p1.Y -= 1;
  50
  51         VoxelArea leaves_a(v3s16(-2,-1,-2), v3s16(2,2,2));
  52         //SharedPtr<u8> leaves_d(new u8[leaves_a.getVolume()]);
  53         Buffer<u8> leaves_d(leaves_a.getVolume());
  54         for(s32 i=0; i<leaves_a.getVolume(); i++)
  55                 leaves_d[i] = 0;
  56
  57         // Force leaves at near the end of the trunk
  58         {
  59                 s16 d = 1;
  60                 for(s16 z=-d; z<=d; z++)
  61                 for(s16 y=-d; y<=d; y++)
  62                 for(s16 x=-d; x<=d; x++)
  63                 {
  64                         leaves_d[leaves_a.index(v3s16(x,y,z))] = 1;
  65                 }
  66         }
  67
  68         // Add leaves randomly
  69         for(u32 iii=0; iii<7; iii++)
  70         {
  71                 s16 d = 1;
  72
  73                 v3s16 p(
  74                         myrand_range(leaves_a.MinEdge.X, leaves_a.MaxEdge.X-d),
  75                         myrand_range(leaves_a.MinEdge.Y, leaves_a.MaxEdge.Y-d),
  76                         myrand_range(leaves_a.MinEdge.Z, leaves_a.MaxEdge.Z-d)
  77                 );
  78
  79                 for(s16 z=0; z<=d; z++)
  80                 for(s16 y=0; y<=d; y++)
  81                 for(s16 x=0; x<=d; x++)
  82                 {
  83                         leaves_d[leaves_a.index(p+v3s16(x,y,z))] = 1;
  84                 }
  85         }
  86
  87         // Blit leaves to vmanip
  88         for(s16 z=leaves_a.MinEdge.Z; z<=leaves_a.MaxEdge.Z; z++)
  89         for(s16 y=leaves_a.MinEdge.Y; y<=leaves_a.MaxEdge.Y; y++)
  90         for(s16 x=leaves_a.MinEdge.X; x<=leaves_a.MaxEdge.X; x++)
  91         {
  92                 v3s16 p(x,y,z);
  93                 p += p1;
  94                 if(vmanip.m_area.contains(p) == false)
  95                         continue;
  96                 u32 vi = vmanip.m_area.index(p);
  97                 if(vmanip.m_data[vi].getContent() != CONTENT_AIR
  98                                 && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
  99                         continue;
 100                 u32 i = leaves_a.index(x,y,z);
 101                 if(leaves_d[i] == 1) {
 102                         bool is_apple = myrand_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         }
 110 }
 111
 112 // L-System tree LUA spawner
 113 void spawn_ltree (ServerEnvironment *env, v3s16 p0, INodeDefManager *ndef, TreeDef tree_definition)
 114 {
 115         ServerMap *map = &env->getServerMap();
 116         core::map<v3s16, MapBlock*> modified_blocks;
 117         ManualMapVoxelManipulator vmanip(map);
 118         v3s16 tree_blockp = getNodeBlockPos(p0);
 119         vmanip.initialEmerge(tree_blockp - v3s16(1,1,1), tree_blockp + v3s16(1,1,1));
 120         make_ltree (vmanip, p0, ndef, tree_definition);
 121         vmanip.blitBackAll(&modified_blocks);
 122
 123         // update lighting
 124         core::map<v3s16, MapBlock*> lighting_modified_blocks;
 125         for(core::map<v3s16, MapBlock*>::Iterator
 126                 i = modified_blocks.getIterator();
 127                 i.atEnd() == false; i++)
 128         {
 129                 lighting_modified_blocks.insert(i.getNode()->getKey(), i.getNode()->getValue());
 130         }
 131         map->updateLighting(lighting_modified_blocks, modified_blocks);
 132         // Send a MEET_OTHER event
 133         MapEditEvent event;
 134         event.type = MEET_OTHER;
 135         for(core::map<v3s16, MapBlock*>::Iterator
 136                 i = modified_blocks.getIterator();
 137                 i.atEnd() == false; i++)
 138         {
 139                 v3s16 p = i.getNode()->getKey();
 140                 event.modified_blocks.insert(p, true);
 141         }
 142         map->dispatchEvent(&event);
 143 }
 144
 145 //L-System tree generator
 146 void make_ltree(ManualMapVoxelManipulator &vmanip, v3s16 p0, INodeDefManager *ndef,
 147                 TreeDef tree_definition)
 148 {
 149         MapNode dirtnode(ndef->getId("mapgen_dirt"));
 150
 151         // chance of inserting abcd rules
 152         double prop_a = 9;
 153         double prop_b = 8;
 154         double prop_c = 7;
 155         double prop_d = 6;
 156
 157         //randomize tree growth level, minimum=2
 158         s16 iterations = tree_definition.iterations;
 159         if (tree_definition.iterations_random_level>0)
 160                 iterations -= myrand_range(0,tree_definition.iterations_random_level);
 161         if (iterations<2)
 162                 iterations=2;
 163
 164         s16 MAX_ANGLE_OFFSET = 5;
 165         double angle_in_radians = (double)tree_definition.angle*M_PI/180;
 166         double angleOffset_in_radians = (s16)(myrand_range(0,1)%MAX_ANGLE_OFFSET)*M_PI/180;
 167
 168         //initialize rotation matrix, position and stacks for branches
 169         core::matrix4 rotation;
 170         rotation=setRotationAxisRadians(rotation, M_PI/2,v3f(0,0,1));
 171         v3f position = v3f(0,0,0);
 172         std::stack <core::matrix4> stack_orientation;
 173         std::stack <v3f> stack_position;
 174
 175         //generate axiom
 176         std::string axiom = tree_definition.initial_axiom;
 177         for(s16 i=0; i<iterations; i++)
 178         {
 179                 std::string temp = "";
 180                 for(s16 j=0; j<(s16)axiom.size(); j++)
 181                 {
 182                         char axiom_char = axiom.at(j);
 183                         switch (axiom_char)
 184                         {
 185                         case 'A':
 186                                 temp+=tree_definition.rules_a;
 187                                 break;
 188                         case 'B':
 189                                 temp+=tree_definition.rules_b;
 190                                 break;
 191                         case 'C':
 192                                 temp+=tree_definition.rules_c;
 193                                 break;
 194                         case 'D':
 195                                 temp+=tree_definition.rules_d;
 196                                 break;
 197                         case 'a':
 198                                 if (prop_a >= myrand_range(1,10))
 199                                         temp+=tree_definition.rules_a;
 200                                 break;
 201                         case 'b':
 202                                 if (prop_b >= myrand_range(1,10))
 203                                         temp+=tree_definition.rules_b;
 204                                 break;
 205                         case 'c':
 206                                 if (prop_c >= myrand_range(1,10))
 207                                         temp+=tree_definition.rules_c;
 208                                 break;
 209                         case 'd':
 210                                 if (prop_d >= myrand_range(1,10))
 211                                         temp+=tree_definition.rules_d;
 212                                 break;
 213                         default:
 214                                 temp+=axiom_char;
 215                                 break;
 216                         }
 217                 }
 218                 axiom=temp;
 219         }
 220
 221         //make sure tree is not floating in the air
 222         if (tree_definition.thin_trunks == false)
 223         {
 224                 make_tree_node_placement(vmanip,v3f(p0.X+position.X+1,p0.Y+position.Y-1,p0.Z+position.Z),dirtnode);
 225                 make_tree_node_placement(vmanip,v3f(p0.X+position.X-1,p0.Y+position.Y-1,p0.Z+position.Z),dirtnode);
 226                 make_tree_node_placement(vmanip,v3f(p0.X+position.X,p0.Y+position.Y-1,p0.Z+position.Z+1),dirtnode);
 227                 make_tree_node_placement(vmanip,v3f(p0.X+position.X,p0.Y+position.Y-1,p0.Z+position.Z-1),dirtnode);
 228         }
 229
 230         /* build tree out of generated axiom
 231
 232         Key for Special L-System Symbols used in Axioms
 233
 234     G  - move forward one unit with the pin down
 235     F  - move forward one unit with the pin up
 236     A  - replace with rules set A
 237     B  - replace with rules set B
 238     C  - replace with rules set C
 239     D  - replace with rules set D
 240     a  - replace with rules set A, chance 90%
 241     b  - replace with rules set B, chance 80%
 242     c  - replace with rules set C, chance 70%
 243     d  - replace with rules set D, chance 60%
 244     +  - yaw the turtle right by angle degrees
 245     -  - yaw the turtle left by angle degrees
 246     &  - pitch the turtle down by angle degrees
 247     ^  - pitch the turtle up by angle degrees
 248     /  - roll the turtle to the right by angle degrees
 249     *  - roll the turtle to the left by angle degrees
 250     [  - save in stack current state info
 251     ]  - recover from stack state info
 252
 253     */
 254
 255         s16 x,y,z;
 256         for(s16 i=0; i<(s16)axiom.size(); i++)
 257         {
 258                 char axiom_char = axiom.at(i);
 259                 core::matrix4 temp_rotation;
 260                 temp_rotation.makeIdentity();
 261                 v3f dir;
 262                 switch (axiom_char)
 263                 {
 264                 case 'G':
 265                         dir = v3f(-1,0,0);
 266                         dir = transposeMatrix(rotation,dir);
 267                         position+=dir;
 268                         break;
 269                 case 'F':
 270                         make_tree_trunk_placement(vmanip,v3f(p0.X+position.X,p0.Y+position.Y,p0.Z+position.Z),tree_definition);
 271                         if (tree_definition.thin_trunks == false)
 272                         {
 273                                 make_tree_trunk_placement(vmanip,v3f(p0.X+position.X+1,p0.Y+position.Y,p0.Z+position.Z),tree_definition);
 274                                 make_tree_trunk_placement(vmanip,v3f(p0.X+position.X-1,p0.Y+position.Y,p0.Z+position.Z),tree_definition);
 275                                 make_tree_trunk_placement(vmanip,v3f(p0.X+position.X,p0.Y+position.Y,p0.Z+position.Z+1),tree_definition);
 276                                 make_tree_trunk_placement(vmanip,v3f(p0.X+position.X,p0.Y+position.Y,p0.Z+position.Z-1),tree_definition);
 277                         }
 278                         if (stack_orientation.empty() == false)
 279                         {
 280                                 s16 size = 1;
 281                                 for(x=-size; x<size+1; x++)
 282                                         for(y=-size; y<size+1; y++)
 283                                                 for(z=-size; z<size+1; z++)
 284                                                         if (abs(x) == size and abs(y) == size and abs(z) == size)
 285                                                         {
 286                                                                 make_tree_leaves_placement(vmanip,v3f(p0.X+position.X+x+1,p0.Y+position.Y+y,p0.Z+position.Z+z),tree_definition);
 287                                                                 make_tree_leaves_placement(vmanip,v3f(p0.X+position.X+x-1,p0.Y+position.Y+y,p0.Z+position.Z+z),tree_definition);
 288                                                                 make_tree_leaves_placement(vmanip,v3f(p0.X+position.X+x,p0.Y+position.Y+y,p0.Z+position.Z+z+1),tree_definition);
 289                                                                 make_tree_leaves_placement(vmanip,v3f(p0.X+position.X+x,p0.Y+position.Y+y,p0.Z+position.Z+z-1),tree_definition);
 290                                                         }
 291                         }
 292                         dir = v3f(1,0,0);
 293                         dir = transposeMatrix(rotation,dir);
 294                         position+=dir;
 295                         break;
 296                 // turtle commands
 297                 case '[':
 298                         stack_orientation.push(rotation);
 299                         stack_position.push(position);
 300                         break;
 301                 case ']':
 302                         rotation=stack_orientation.top();
 303                         stack_orientation.pop();
 304                         position=stack_position.top();
 305                         stack_position.pop();
 306                         break;
 307                 case '+':
 308                         temp_rotation.makeIdentity();
 309                         temp_rotation=setRotationAxisRadians(temp_rotation, angle_in_radians+angleOffset_in_radians,v3f(0,0,1));
 310                         rotation*=temp_rotation;
 311                         break;
 312                 case '-':
 313                         temp_rotation.makeIdentity();
 314                         temp_rotation=setRotationAxisRadians(temp_rotation, angle_in_radians+angleOffset_in_radians,v3f(0,0,-1));
 315                         rotation*=temp_rotation;
 316                         break;
 317                 case '&':
 318                         temp_rotation.makeIdentity();
 319                         temp_rotation=setRotationAxisRadians(temp_rotation, angle_in_radians+angleOffset_in_radians,v3f(0,1,0));
 320                         rotation*=temp_rotation;
 321                         break;
 322                 case '^':
 323                         temp_rotation.makeIdentity();
 324                         temp_rotation=setRotationAxisRadians(temp_rotation, angle_in_radians+angleOffset_in_radians,v3f(0,-1,0));
 325                         rotation*=temp_rotation;
 326                         break;
 327                 case '*':
 328                         temp_rotation.makeIdentity();
 329                         temp_rotation=setRotationAxisRadians(temp_rotation, angle_in_radians,v3f(1,0,0));
 330                         rotation*=temp_rotation;
 331                         break;
 332                 case '/':
 333                         temp_rotation.makeIdentity();
 334                         temp_rotation=setRotationAxisRadians(temp_rotation, angle_in_radians,v3f(-1,0,0));
 335                         rotation*=temp_rotation;
 336                         break;
 337                 default:
 338                         break;
 339                 }
 340         }
 341 }
 342
 343 void make_tree_node_placement(ManualMapVoxelManipulator &vmanip, v3f p0,
 344                 MapNode node)
 345 {
 346         v3s16 p1 = v3s16(round(p0.X),round(p0.Y),round(p0.Z));
 347         if(vmanip.m_area.contains(p1) == false)
 348                 return;
 349         u32 vi = vmanip.m_area.index(p1);
 350         if(vmanip.m_data[vi].getContent() != CONTENT_AIR
 351                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 352                 return;
 353         vmanip.m_data[vmanip.m_area.index(p1)] = node;
 354 }
 355
 356 void make_tree_trunk_placement(ManualMapVoxelManipulator &vmanip, v3f p0,
 357                 TreeDef &tree_definition)
 358 {
 359         v3s16 p1 = v3s16(round(p0.X),round(p0.Y),round(p0.Z));
 360         if(vmanip.m_area.contains(p1) == false)
 361                 return;
 362         u32 vi = vmanip.m_area.index(p1);
 363         if(vmanip.m_data[vi].getContent() != CONTENT_AIR
 364                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 365                 return;
 366         vmanip.m_data[vmanip.m_area.index(p1)] = tree_definition.trunknode;
 367 }
 368
 369 void make_tree_leaves_placement(ManualMapVoxelManipulator &vmanip, v3f p0,
 370                 TreeDef &tree_definition)
 371 {
 372         v3s16 p1 = v3s16(round(p0.X),round(p0.Y),round(p0.Z));
 373         if(vmanip.m_area.contains(p1) == false)
 374                 return;
 375         u32 vi = vmanip.m_area.index(p1);
 376         if(vmanip.m_data[vi].getContent() != CONTENT_AIR
 377                         && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 378                 return;
 379         if (tree_definition.fruit_tree)
 380         {
 381                 if (myrand_range(1,100) > 90+tree_definition.iterations)
 382                         vmanip.m_data[vmanip.m_area.index(p1)] = tree_definition.fruitnode;
 383                 else
 384                         vmanip.m_data[vmanip.m_area.index(p1)] = tree_definition.leavesnode;
 385         }
 386         else if (myrand_range(1,100) > 20)
 387                 vmanip.m_data[vmanip.m_area.index(p1)] = tree_definition.leavesnode;
 388 }
 389
 390 irr::core::matrix4 setRotationAxisRadians(irr::core::matrix4 M, double angle, v3f axis)
 391 {
 392         double c = cos(angle);
 393         double s = sin(angle);
 394         double t = 1.0 - c;
 395
 396         double tx  = t * axis.X;
 397         double ty  = t * axis.Y;
 398         double tz  = t * axis.Z;
 399         double sx  = s * axis.X;
 400         double sy  = s * axis.Y;
 401         double sz  = s * axis.Z;
 402
 403         M[0] = tx * axis.X + c;
 404         M[1] = tx * axis.Y + sz;
 405         M[2] = tx * axis.Z - sy;
 406
 407         M[4] = ty * axis.X - sz;
 408         M[5] = ty * axis.Y + c;
 409         M[6] = ty * axis.Z + sx;
 410
 411         M[8]  = tz * axis.X + sy;
 412         M[9]  = tz * axis.Y - sx;
 413         M[10] = tz * axis.Z + c;
 414         return M;
 415 }
 416
 417 v3f transposeMatrix(irr::core::matrix4 M, v3f v)
 418 {
 419         v3f translated;
 420         double x = M[0] * v.X + M[4] * v.Y + M[8]  * v.Z +M[12];
 421         double y = M[1] * v.X + M[5] * v.Y + M[9]  * v.Z +M[13];
 422         double z = M[2] * v.X + M[6] * v.Y + M[10] * v.Z +M[14];
 423         translated.X=x;
 424         translated.Y=y;
 425         translated.Z=z;
 426         return translated;
 427 }
 428
 429 #if 0
 430 static void make_jungletree(VoxelManipulator &vmanip, v3s16 p0,
 431                 INodeDefManager *ndef)
 432 {
 433         MapNode treenode(ndef->getId("mapgen_jungletree"));
 434         MapNode leavesnode(ndef->getId("mapgen_leaves"));
 435
 436         for(s16 x=-1; x<=1; x++)
 437         for(s16 z=-1; z<=1; z++)
 438         {
 439                 if(myrand_range(0, 2) == 0)
 440                         continue;
 441                 v3s16 p1 = p0 + v3s16(x,0,z);
 442                 v3s16 p2 = p0 + v3s16(x,-1,z);
 443                 if(vmanip.m_area.contains(p2)
 444                                 && vmanip.m_data[vmanip.m_area.index(p2)] == CONTENT_AIR)
 445                         vmanip.m_data[vmanip.m_area.index(p2)] = treenode;
 446                 else if(vmanip.m_area.contains(p1))
 447                         vmanip.m_data[vmanip.m_area.index(p1)] = treenode;
 448         }
 449
 450         s16 trunk_h = myrand_range(8, 12);
 451         v3s16 p1 = p0;
 452         for(s16 ii=0; ii<trunk_h; ii++)
 453         {
 454                 if(vmanip.m_area.contains(p1))
 455                         vmanip.m_data[vmanip.m_area.index(p1)] = treenode;
 456                 p1.Y++;
 457         }
 458
 459         // p1 is now the last piece of the trunk
 460         p1.Y -= 1;
 461
 462         VoxelArea leaves_a(v3s16(-3,-2,-3), v3s16(3,2,3));
 463         //SharedPtr<u8> leaves_d(new u8[leaves_a.getVolume()]);
 464         Buffer<u8> leaves_d(leaves_a.getVolume());
 465         for(s32 i=0; i<leaves_a.getVolume(); i++)
 466                 leaves_d[i] = 0;
 467
 468         // Force leaves at near the end of the trunk
 469         {
 470                 s16 d = 1;
 471                 for(s16 z=-d; z<=d; z++)
 472                 for(s16 y=-d; y<=d; y++)
 473                 for(s16 x=-d; x<=d; x++)
 474                 {
 475                         leaves_d[leaves_a.index(v3s16(x,y,z))] = 1;
 476                 }
 477         }
 478
 479         // Add leaves randomly
 480         for(u32 iii=0; iii<30; iii++)
 481         {
 482                 s16 d = 1;
 483
 484                 v3s16 p(
 485                         myrand_range(leaves_a.MinEdge.X, leaves_a.MaxEdge.X-d),
 486                         myrand_range(leaves_a.MinEdge.Y, leaves_a.MaxEdge.Y-d),
 487                         myrand_range(leaves_a.MinEdge.Z, leaves_a.MaxEdge.Z-d)
 488                 );
 489
 490                 for(s16 z=0; z<=d; z++)
 491                 for(s16 y=0; y<=d; y++)
 492                 for(s16 x=0; x<=d; x++)
 493                 {
 494                         leaves_d[leaves_a.index(p+v3s16(x,y,z))] = 1;
 495                 }
 496         }
 497
 498         // Blit leaves to vmanip
 499         for(s16 z=leaves_a.MinEdge.Z; z<=leaves_a.MaxEdge.Z; z++)
 500         for(s16 y=leaves_a.MinEdge.Y; y<=leaves_a.MaxEdge.Y; y++)
 501         for(s16 x=leaves_a.MinEdge.X; x<=leaves_a.MaxEdge.X; x++)
 502         {
 503                 v3s16 p(x,y,z);
 504                 p += p1;
 505                 if(vmanip.m_area.contains(p) == false)
 506                         continue;
 507                 u32 vi = vmanip.m_area.index(p);
 508                 if(vmanip.m_data[vi].getContent() != CONTENT_AIR
 509                                 && vmanip.m_data[vi].getContent() != CONTENT_IGNORE)
 510                         continue;
 511                 u32 i = leaves_a.index(x,y,z);
 512                 if(leaves_d[i] == 1)
 513                         vmanip.m_data[vi] = leavesnode;
 514         }
 515 }
 516 #endif
 517
 518 }; // namespace treegen