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