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