src/voxel.cpp

   1 /*
   2 Minetest-c55
   3 Copyright (C) 2010 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2 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 General Public License for more details.
  14
  15 You should have received a copy of the GNU 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 "voxel.h"
  21 #include "map.h"
  22 #include "utility.h" // For TimeTaker
  23 #include "gettime.h"
  24 #include "content_mapnode.h"
  25
  26 /*
  27         Debug stuff
  28 */
  29 u32 addarea_time = 0;
  30 u32 emerge_time = 0;
  31 u32 emerge_load_time = 0;
  32 u32 clearflag_time = 0;
  33 //u32 getwaterpressure_time = 0;
  34 //u32 spreadwaterpressure_time = 0;
  35 u32 updateareawaterpressure_time = 0;
  36 u32 flowwater_pre_time = 0;
  37
  38
  39 VoxelManipulator::VoxelManipulator():
  40         m_data(NULL),
  41         m_flags(NULL)
  42 {
  43 }
  44
  45 VoxelManipulator::~VoxelManipulator()
  46 {
  47         clear();
  48         if(m_data)
  49                 delete[] m_data;
  50         if(m_flags)
  51                 delete[] m_flags;
  52 }
  53
  54 void VoxelManipulator::clear()
  55 {
  56         // Reset area to volume=0
  57         m_area = VoxelArea();
  58         if(m_data)
  59                 delete[] m_data;
  60         m_data = NULL;
  61         if(m_flags)
  62                 delete[] m_flags;
  63         m_flags = NULL;
  64 }
  65
  66 void VoxelManipulator::print(std::ostream &o, VoxelPrintMode mode)
  67 {
  68         v3s16 em = m_area.getExtent();
  69         v3s16 of = m_area.MinEdge;
  70         o<<"size: "<<em.X<<"x"<<em.Y<<"x"<<em.Z
  71          <<" offset: ("<<of.X<<","<<of.Y<<","<<of.Z<<")"<<std::endl;
  72
  73         for(s32 y=m_area.MaxEdge.Y; y>=m_area.MinEdge.Y; y--)
  74         {
  75                 if(em.X >= 3 && em.Y >= 3)
  76                 {
  77                         if     (y==m_area.MinEdge.Y+2) o<<"^     ";
  78                         else if(y==m_area.MinEdge.Y+1) o<<"|     ";
  79                         else if(y==m_area.MinEdge.Y+0) o<<"y x-> ";
  80                         else                           o<<"      ";
  81                 }
  82
  83                 for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
  84                 {
  85                         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
  86                         {
  87                                 u8 f = m_flags[m_area.index(x,y,z)];
  88                                 char c;
  89                                 if(f & VOXELFLAG_NOT_LOADED)
  90                                         c = 'N';
  91                                 else if(f & VOXELFLAG_INEXISTENT)
  92                                         c = 'I';
  93                                 else
  94                                 {
  95                                         c = 'X';
  96                                         content_t m = m_data[m_area.index(x,y,z)].getContent();
  97                                         u8 pr = m_data[m_area.index(x,y,z)].param2;
  98                                         if(mode == VOXELPRINT_MATERIAL)
  99                                         {
 100                                                 if(m <= 9)
 101                                                         c = m + '0';
 102                                         }
 103                                         else if(mode == VOXELPRINT_WATERPRESSURE)
 104                                         {
 105                                                 if(m == CONTENT_WATER)
 106                                                 {
 107                                                         c = 'w';
 108                                                         if(pr <= 9)
 109                                                                 c = pr + '0';
 110                                                 }
 111                                                 else if(m == CONTENT_AIR)
 112                                                 {
 113                                                         c = ' ';
 114                                                 }
 115                                                 else
 116                                                 {
 117                                                         c = '#';
 118                                                 }
 119                                         }
 120                                 }
 121                                 o<<c;
 122                         }
 123                         o<<' ';
 124                 }
 125                 o<<std::endl;
 126         }
 127 }
 128
 129 void VoxelManipulator::addArea(VoxelArea area)
 130 {
 131         // Cancel if requested area has zero volume
 132         if(area.getExtent() == v3s16(0,0,0))
 133                 return;
 134
 135         // Cancel if m_area already contains the requested area
 136         if(m_area.contains(area))
 137                 return;
 138
 139         TimeTaker timer("addArea", &addarea_time);
 140
 141         // Calculate new area
 142         VoxelArea new_area;
 143         // New area is the requested area if m_area has zero volume
 144         if(m_area.getExtent() == v3s16(0,0,0))
 145         {
 146                 new_area = area;
 147         }
 148         // Else add requested area to m_area
 149         else
 150         {
 151                 new_area = m_area;
 152                 new_area.addArea(area);
 153         }
 154
 155         s32 new_size = new_area.getVolume();
 156
 157         /*dstream<<"adding area ";
 158         area.print(dstream);
 159         dstream<<", old area ";
 160         m_area.print(dstream);
 161         dstream<<", new area ";
 162         new_area.print(dstream);
 163         dstream<<", new_size="<<new_size;
 164         dstream<<std::endl;*/
 165
 166         // Allocate and clear new data
 167         MapNode *new_data = new MapNode[new_size];
 168         u8 *new_flags = new u8[new_size];
 169         for(s32 i=0; i<new_size; i++)
 170         {
 171                 new_flags[i] = VOXELFLAG_NOT_LOADED;
 172         }
 173
 174         // Copy old data
 175
 176         for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
 177         for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
 178         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
 179         {
 180                 // If loaded, copy data and flags
 181                 if((m_flags[m_area.index(x,y,z)] & VOXELFLAG_NOT_LOADED) == false)
 182                 {
 183                         new_data[new_area.index(x,y,z)] = m_data[m_area.index(x,y,z)];
 184                         new_flags[new_area.index(x,y,z)] = m_flags[m_area.index(x,y,z)];
 185                 }
 186         }
 187
 188         // Replace area, data and flags
 189
 190         m_area = new_area;
 191
 192         MapNode *old_data = m_data;
 193         u8 *old_flags = m_flags;
 194
 195         /*dstream<<"old_data="<<(int)old_data<<", new_data="<<(int)new_data
 196         <<", old_flags="<<(int)m_flags<<", new_flags="<<(int)new_flags<<std::endl;*/
 197
 198         m_data = new_data;
 199         m_flags = new_flags;
 200
 201         if(old_data)
 202                 delete[] old_data;
 203         if(old_flags)
 204                 delete[] old_flags;
 205
 206         //dstream<<"addArea done"<<std::endl;
 207 }
 208
 209 void VoxelManipulator::copyFrom(MapNode *src, VoxelArea src_area,
 210                 v3s16 from_pos, v3s16 to_pos, v3s16 size)
 211 {
 212         for(s16 z=0; z<size.Z; z++)
 213         for(s16 y=0; y<size.Y; y++)
 214         {
 215                 s32 i_src = src_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
 216                 s32 i_local = m_area.index(to_pos.X, to_pos.Y+y, to_pos.Z+z);
 217                 memcpy(&m_data[i_local], &src[i_src], size.X*sizeof(MapNode));
 218                 memset(&m_flags[i_local], 0, size.X);
 219         }
 220 }
 221
 222 void VoxelManipulator::copyTo(MapNode *dst, VoxelArea dst_area,
 223                 v3s16 dst_pos, v3s16 from_pos, v3s16 size)
 224 {
 225         for(s16 z=0; z<size.Z; z++)
 226         for(s16 y=0; y<size.Y; y++)
 227         {
 228                 s32 i_dst = dst_area.index(dst_pos.X, dst_pos.Y+y, dst_pos.Z+z);
 229                 s32 i_local = m_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
 230                 memcpy(&dst[i_dst], &m_data[i_local], size.X*sizeof(MapNode));
 231         }
 232 }
 233
 234 /*
 235         Algorithms
 236         -----------------------------------------------------
 237 */
 238
 239 void VoxelManipulator::clearFlag(u8 flags)
 240 {
 241         // 0-1ms on moderate area
 242         TimeTaker timer("clearFlag", &clearflag_time);
 243
 244         v3s16 s = m_area.getExtent();
 245
 246         /*dstream<<"clearFlag clearing area of size "
 247                         <<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
 248                         <<std::endl;*/
 249
 250         //s32 count = 0;
 251
 252         /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
 253         for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
 254         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
 255         {
 256                 u8 f = m_flags[m_area.index(x,y,z)];
 257                 m_flags[m_area.index(x,y,z)] &= ~flags;
 258                 if(m_flags[m_area.index(x,y,z)] != f)
 259                         count++;
 260         }*/
 261
 262         s32 volume = m_area.getVolume();
 263         for(s32 i=0; i<volume; i++)
 264         {
 265                 m_flags[i] &= ~flags;
 266         }
 267
 268         /*s32 volume = m_area.getVolume();
 269         for(s32 i=0; i<volume; i++)
 270         {
 271                 u8 f = m_flags[i];
 272                 m_flags[i] &= ~flags;
 273                 if(m_flags[i] != f)
 274                         count++;
 275         }
 276
 277         dstream<<"clearFlag changed "<<count<<" flags out of "
 278                         <<volume<<" nodes"<<std::endl;*/
 279 }
 280
 281 void VoxelManipulator::unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 282                 core::map<v3s16, bool> & light_sources)
 283 {
 284         v3s16 dirs[6] = {
 285                 v3s16(0,0,1), // back
 286                 v3s16(0,1,0), // top
 287                 v3s16(1,0,0), // right
 288                 v3s16(0,0,-1), // front
 289                 v3s16(0,-1,0), // bottom
 290                 v3s16(-1,0,0), // left
 291         };
 292
 293         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));
 294
 295         // Loop through 6 neighbors
 296         for(u16 i=0; i<6; i++)
 297         {
 298                 // Get the position of the neighbor node
 299                 v3s16 n2pos = p + dirs[i];
 300
 301                 u32 n2i = m_area.index(n2pos);
 302
 303                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 304                         continue;
 305
 306                 MapNode &n2 = m_data[n2i];
 307
 308                 /*
 309                         If the neighbor is dimmer than what was specified
 310                         as oldlight (the light of the previous node)
 311                 */
 312                 if(n2.getLight(bank) < oldlight)
 313                 {
 314                         /*
 315                                 And the neighbor is transparent and it has some light
 316                         */
 317                         if(n2.light_propagates() && n2.getLight(bank) != 0)
 318                         {
 319                                 /*
 320                                         Set light to 0 and add to queue
 321                                 */
 322
 323                                 u8 current_light = n2.getLight(bank);
 324                                 n2.setLight(bank, 0);
 325
 326                                 unspreadLight(bank, n2pos, current_light, light_sources);
 327
 328                                 /*
 329                                         Remove from light_sources if it is there
 330                                         NOTE: This doesn't happen nearly at all
 331                                 */
 332                                 /*if(light_sources.find(n2pos))
 333                                 {
 334                                         std::cout<<"Removed from light_sources"<<std::endl;
 335                                         light_sources.remove(n2pos);
 336                                 }*/
 337                         }
 338                 }
 339                 else{
 340                         light_sources.insert(n2pos, true);
 341                 }
 342         }
 343 }
 344
 345 #if 1
 346 /*
 347         Goes recursively through the neighbours of the node.
 348
 349         Alters only transparent nodes.
 350
 351         If the lighting of the neighbour is lower than the lighting of
 352         the node was (before changing it to 0 at the step before), the
 353         lighting of the neighbour is set to 0 and then the same stuff
 354         repeats for the neighbour.
 355
 356         The ending nodes of the routine are stored in light_sources.
 357         This is useful when a light is removed. In such case, this
 358         routine can be called for the light node and then again for
 359         light_sources to re-light the area without the removed light.
 360
 361         values of from_nodes are lighting values.
 362 */
 363 void VoxelManipulator::unspreadLight(enum LightBank bank,
 364                 core::map<v3s16, u8> & from_nodes,
 365                 core::map<v3s16, bool> & light_sources)
 366 {
 367         if(from_nodes.size() == 0)
 368                 return;
 369
 370         core::map<v3s16, u8>::Iterator j;
 371         j = from_nodes.getIterator();
 372
 373         for(; j.atEnd() == false; j++)
 374         {
 375                 v3s16 pos = j.getNode()->getKey();
 376
 377                 //MapNode &n = m_data[m_area.index(pos)];
 378
 379                 u8 oldlight = j.getNode()->getValue();
 380
 381                 unspreadLight(bank, pos, oldlight, light_sources);
 382         }
 383 }
 384 #endif
 385
 386 #if 0
 387 /*
 388         Goes recursively through the neighbours of the node.
 389
 390         Alters only transparent nodes.
 391
 392         If the lighting of the neighbour is lower than the lighting of
 393         the node was (before changing it to 0 at the step before), the
 394         lighting of the neighbour is set to 0 and then the same stuff
 395         repeats for the neighbour.
 396
 397         The ending nodes of the routine are stored in light_sources.
 398         This is useful when a light is removed. In such case, this
 399         routine can be called for the light node and then again for
 400         light_sources to re-light the area without the removed light.
 401
 402         values of from_nodes are lighting values.
 403 */
 404 void VoxelManipulator::unspreadLight(enum LightBank bank,
 405                 core::map<v3s16, u8> & from_nodes,
 406                 core::map<v3s16, bool> & light_sources)
 407 {
 408         v3s16 dirs[6] = {
 409                 v3s16(0,0,1), // back
 410                 v3s16(0,1,0), // top
 411                 v3s16(1,0,0), // right
 412                 v3s16(0,0,-1), // front
 413                 v3s16(0,-1,0), // bottom
 414                 v3s16(-1,0,0), // left
 415         };
 416
 417         if(from_nodes.size() == 0)
 418                 return;
 419
 420         core::map<v3s16, u8> unlighted_nodes;
 421         core::map<v3s16, u8>::Iterator j;
 422         j = from_nodes.getIterator();
 423
 424         for(; j.atEnd() == false; j++)
 425         {
 426                 v3s16 pos = j.getNode()->getKey();
 427
 428                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
 429
 430                 //MapNode &n = m_data[m_area.index(pos)];
 431
 432                 u8 oldlight = j.getNode()->getValue();
 433
 434                 // Loop through 6 neighbors
 435                 for(u16 i=0; i<6; i++)
 436                 {
 437                         // Get the position of the neighbor node
 438                         v3s16 n2pos = pos + dirs[i];
 439
 440                         u32 n2i = m_area.index(n2pos);
 441
 442                         if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 443                                 continue;
 444
 445                         MapNode &n2 = m_data[n2i];
 446
 447                         /*
 448                                 If the neighbor is dimmer than what was specified
 449                                 as oldlight (the light of the previous node)
 450                         */
 451                         if(n2.getLight(bank) < oldlight)
 452                         {
 453                                 /*
 454                                         And the neighbor is transparent and it has some light
 455                                 */
 456                                 if(n2.light_propagates() && n2.getLight(bank) != 0)
 457                                 {
 458                                         /*
 459                                                 Set light to 0 and add to queue
 460                                         */
 461
 462                                         u8 current_light = n2.getLight(bank);
 463                                         n2.setLight(bank, 0);
 464
 465                                         unlighted_nodes.insert(n2pos, current_light);
 466
 467                                         /*
 468                                                 Remove from light_sources if it is there
 469                                                 NOTE: This doesn't happen nearly at all
 470                                         */
 471                                         /*if(light_sources.find(n2pos))
 472                                         {
 473                                                 std::cout<<"Removed from light_sources"<<std::endl;
 474                                                 light_sources.remove(n2pos);
 475                                         }*/
 476                                 }
 477                         }
 478                         else{
 479                                 light_sources.insert(n2pos, true);
 480                         }
 481                 }
 482         }
 483
 484         /*dstream<<"unspreadLight(): Changed block "
 485                         <<blockchangecount<<" times"
 486                         <<" for "<<from_nodes.size()<<" nodes"
 487                         <<std::endl;*/
 488
 489         if(unlighted_nodes.size() > 0)
 490                 unspreadLight(bank, unlighted_nodes, light_sources);
 491 }
 492 #endif
 493
 494 void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p)
 495 {
 496         const v3s16 dirs[6] = {
 497                 v3s16(0,0,1), // back
 498                 v3s16(0,1,0), // top
 499                 v3s16(1,0,0), // right
 500                 v3s16(0,0,-1), // front
 501                 v3s16(0,-1,0), // bottom
 502                 v3s16(-1,0,0), // left
 503         };
 504
 505         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));
 506
 507         u32 i = m_area.index(p);
 508
 509         if(m_flags[i] & VOXELFLAG_INEXISTENT)
 510                 return;
 511
 512         MapNode &n = m_data[i];
 513
 514         u8 oldlight = n.getLight(bank);
 515         u8 newlight = diminish_light(oldlight);
 516
 517         // Loop through 6 neighbors
 518         for(u16 i=0; i<6; i++)
 519         {
 520                 // Get the position of the neighbor node
 521                 v3s16 n2pos = p + dirs[i];
 522
 523                 u32 n2i = m_area.index(n2pos);
 524
 525                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 526                         continue;
 527
 528                 MapNode &n2 = m_data[n2i];
 529
 530                 /*
 531                         If the neighbor is brighter than the current node,
 532                         add to list (it will light up this node on its turn)
 533                 */
 534                 if(n2.getLight(bank) > undiminish_light(oldlight))
 535                 {
 536                         spreadLight(bank, n2pos);
 537                 }
 538                 /*
 539                         If the neighbor is dimmer than how much light this node
 540                         would spread on it, add to list
 541                 */
 542                 if(n2.getLight(bank) < newlight)
 543                 {
 544                         if(n2.light_propagates())
 545                         {
 546                                 n2.setLight(bank, newlight);
 547                                 spreadLight(bank, n2pos);
 548                         }
 549                 }
 550         }
 551 }
 552
 553 #if 0
 554 /*
 555         Lights neighbors of from_nodes, collects all them and then
 556         goes on recursively.
 557
 558         NOTE: This is faster on small areas but will overflow the
 559               stack on large areas. Thus it is not used.
 560 */
 561 void VoxelManipulator::spreadLight(enum LightBank bank,
 562                 core::map<v3s16, bool> & from_nodes)
 563 {
 564         if(from_nodes.size() == 0)
 565                 return;
 566
 567         core::map<v3s16, bool> lighted_nodes;
 568         core::map<v3s16, bool>::Iterator j;
 569         j = from_nodes.getIterator();
 570
 571         for(; j.atEnd() == false; j++)
 572         {
 573                 v3s16 pos = j.getNode()->getKey();
 574
 575                 spreadLight(bank, pos);
 576         }
 577 }
 578 #endif
 579
 580 #if 1
 581 /*
 582         Lights neighbors of from_nodes, collects all them and then
 583         goes on recursively.
 584 */
 585 void VoxelManipulator::spreadLight(enum LightBank bank,
 586                 core::map<v3s16, bool> & from_nodes)
 587 {
 588         const v3s16 dirs[6] = {
 589                 v3s16(0,0,1), // back
 590                 v3s16(0,1,0), // top
 591                 v3s16(1,0,0), // right
 592                 v3s16(0,0,-1), // front
 593                 v3s16(0,-1,0), // bottom
 594                 v3s16(-1,0,0), // left
 595         };
 596
 597         if(from_nodes.size() == 0)
 598                 return;
 599
 600         core::map<v3s16, bool> lighted_nodes;
 601         core::map<v3s16, bool>::Iterator j;
 602         j = from_nodes.getIterator();
 603
 604         for(; j.atEnd() == false; j++)
 605         {
 606                 v3s16 pos = j.getNode()->getKey();
 607
 608                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
 609
 610                 u32 i = m_area.index(pos);
 611
 612                 if(m_flags[i] & VOXELFLAG_INEXISTENT)
 613                         continue;
 614
 615                 MapNode &n = m_data[i];
 616
 617                 u8 oldlight = n.getLight(bank);
 618                 u8 newlight = diminish_light(oldlight);
 619
 620                 // Loop through 6 neighbors
 621                 for(u16 i=0; i<6; i++)
 622                 {
 623                         // Get the position of the neighbor node
 624                         v3s16 n2pos = pos + dirs[i];
 625
 626                         try
 627                         {
 628                                 u32 n2i = m_area.index(n2pos);
 629
 630                                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
 631                                         continue;
 632
 633                                 MapNode &n2 = m_data[n2i];
 634
 635                                 /*
 636                                         If the neighbor is brighter than the current node,
 637                                         add to list (it will light up this node on its turn)
 638                                 */
 639                                 if(n2.getLight(bank) > undiminish_light(oldlight))
 640                                 {
 641                                         lighted_nodes.insert(n2pos, true);
 642                                 }
 643                                 /*
 644                                         If the neighbor is dimmer than how much light this node
 645                                         would spread on it, add to list
 646                                 */
 647                                 if(n2.getLight(bank) < newlight)
 648                                 {
 649                                         if(n2.light_propagates())
 650                                         {
 651                                                 n2.setLight(bank, newlight);
 652                                                 lighted_nodes.insert(n2pos, true);
 653                                         }
 654                                 }
 655                         }
 656                         catch(InvalidPositionException &e)
 657                         {
 658                                 continue;
 659                         }
 660                 }
 661         }
 662
 663         /*dstream<<"spreadLight(): Changed block "
 664                         <<blockchangecount<<" times"
 665                         <<" for "<<from_nodes.size()<<" nodes"
 666                         <<std::endl;*/
 667
 668         if(lighted_nodes.size() > 0)
 669                 spreadLight(bank, lighted_nodes);
 670 }
 671 #endif
 672
 673 //END