Merge remote branch 'origin/master'
[oweals/minetest.git] / src / voxel.cpp
1 /*
2 Minetest
3 Copyright (C) 2013 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 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 "voxel.h"
21 #include "map.h"
22 #include "gettime.h"
23 #include "nodedef.h"
24 #include "util/timetaker.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                 for (s16 x = 0; x < size.X; x++) {
248                         if (m_data[i_local].getContent() != CONTENT_IGNORE)
249                                 dst[i_dst] = m_data[i_local];
250                         i_dst++;
251                         i_local++;
252                 }
253                 //memcpy(&dst[i_dst], &m_data[i_local], size.X*sizeof(MapNode));
254         }
255 }
256
257 /*
258         Algorithms
259         -----------------------------------------------------
260 */
261
262 void VoxelManipulator::clearFlag(u8 flags)
263 {
264         // 0-1ms on moderate area
265         TimeTaker timer("clearFlag", &clearflag_time);
266
267         v3s16 s = m_area.getExtent();
268
269         /*dstream<<"clearFlag clearing area of size "
270                         <<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
271                         <<std::endl;*/
272
273         //s32 count = 0;
274
275         /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
276         for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
277         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
278         {
279                 u8 f = m_flags[m_area.index(x,y,z)];
280                 m_flags[m_area.index(x,y,z)] &= ~flags;
281                 if(m_flags[m_area.index(x,y,z)] != f)
282                         count++;
283         }*/
284
285         s32 volume = m_area.getVolume();
286         for(s32 i=0; i<volume; i++)
287         {
288                 m_flags[i] &= ~flags;
289         }
290
291         /*s32 volume = m_area.getVolume();
292         for(s32 i=0; i<volume; i++)
293         {
294                 u8 f = m_flags[i];
295                 m_flags[i] &= ~flags;
296                 if(m_flags[i] != f)
297                         count++;
298         }
299
300         dstream<<"clearFlag changed "<<count<<" flags out of "
301                         <<volume<<" nodes"<<std::endl;*/
302 }
303
304 void VoxelManipulator::unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
305                 core::map<v3s16, bool> & light_sources, INodeDefManager *nodemgr)
306 {
307         v3s16 dirs[6] = {
308                 v3s16(0,0,1), // back
309                 v3s16(0,1,0), // top
310                 v3s16(1,0,0), // right
311                 v3s16(0,0,-1), // front
312                 v3s16(0,-1,0), // bottom
313                 v3s16(-1,0,0), // left
314         };
315         
316         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));
317
318         // Loop through 6 neighbors
319         for(u16 i=0; i<6; i++)
320         {
321                 // Get the position of the neighbor node
322                 v3s16 n2pos = p + dirs[i];
323                 
324                 u32 n2i = m_area.index(n2pos);
325
326                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
327                         continue;
328
329                 MapNode &n2 = m_data[n2i];
330                 
331                 /*
332                         If the neighbor is dimmer than what was specified
333                         as oldlight (the light of the previous node)
334                 */
335                 u8 light2 = n2.getLight(bank, nodemgr);
336                 if(light2 < oldlight)
337                 {
338                         /*
339                                 And the neighbor is transparent and it has some light
340                         */
341                         if(nodemgr->get(n2).light_propagates && light2 != 0)
342                         {
343                                 /*
344                                         Set light to 0 and add to queue
345                                 */
346
347                                 n2.setLight(bank, 0, nodemgr);
348                                 
349                                 unspreadLight(bank, n2pos, light2, light_sources, nodemgr);
350                                 
351                                 /*
352                                         Remove from light_sources if it is there
353                                         NOTE: This doesn't happen nearly at all
354                                 */
355                                 /*if(light_sources.find(n2pos))
356                                 {
357                                         std::cout<<"Removed from light_sources"<<std::endl;
358                                         light_sources.remove(n2pos);
359                                 }*/
360                         }
361                 }
362                 else{
363                         light_sources.insert(n2pos, true);
364                 }
365         }
366 }
367
368 #if 1
369 /*
370         Goes recursively through the neighbours of the node.
371
372         Alters only transparent nodes.
373
374         If the lighting of the neighbour is lower than the lighting of
375         the node was (before changing it to 0 at the step before), the
376         lighting of the neighbour is set to 0 and then the same stuff
377         repeats for the neighbour.
378
379         The ending nodes of the routine are stored in light_sources.
380         This is useful when a light is removed. In such case, this
381         routine can be called for the light node and then again for
382         light_sources to re-light the area without the removed light.
383
384         values of from_nodes are lighting values.
385 */
386 void VoxelManipulator::unspreadLight(enum LightBank bank,
387                 core::map<v3s16, u8> & from_nodes,
388                 core::map<v3s16, bool> & light_sources, INodeDefManager *nodemgr)
389 {
390         if(from_nodes.size() == 0)
391                 return;
392         
393         core::map<v3s16, u8>::Iterator j;
394         j = from_nodes.getIterator();
395
396         for(; j.atEnd() == false; j++)
397         {
398                 v3s16 pos = j.getNode()->getKey();
399                 
400                 //MapNode &n = m_data[m_area.index(pos)];
401                 
402                 u8 oldlight = j.getNode()->getValue();
403
404                 unspreadLight(bank, pos, oldlight, light_sources, nodemgr);
405         }
406 }
407 #endif
408
409 #if 0
410 /*
411         Goes recursively through the neighbours of the node.
412
413         Alters only transparent nodes.
414
415         If the lighting of the neighbour is lower than the lighting of
416         the node was (before changing it to 0 at the step before), the
417         lighting of the neighbour is set to 0 and then the same stuff
418         repeats for the neighbour.
419
420         The ending nodes of the routine are stored in light_sources.
421         This is useful when a light is removed. In such case, this
422         routine can be called for the light node and then again for
423         light_sources to re-light the area without the removed light.
424
425         values of from_nodes are lighting values.
426 */
427 void VoxelManipulator::unspreadLight(enum LightBank bank,
428                 core::map<v3s16, u8> & from_nodes,
429                 core::map<v3s16, bool> & light_sources)
430 {
431         v3s16 dirs[6] = {
432                 v3s16(0,0,1), // back
433                 v3s16(0,1,0), // top
434                 v3s16(1,0,0), // right
435                 v3s16(0,0,-1), // front
436                 v3s16(0,-1,0), // bottom
437                 v3s16(-1,0,0), // left
438         };
439         
440         if(from_nodes.size() == 0)
441                 return;
442         
443         core::map<v3s16, u8> unlighted_nodes;
444         core::map<v3s16, u8>::Iterator j;
445         j = from_nodes.getIterator();
446
447         for(; j.atEnd() == false; j++)
448         {
449                 v3s16 pos = j.getNode()->getKey();
450                 
451                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
452
453                 //MapNode &n = m_data[m_area.index(pos)];
454                 
455                 u8 oldlight = j.getNode()->getValue();
456                 
457                 // Loop through 6 neighbors
458                 for(u16 i=0; i<6; i++)
459                 {
460                         // Get the position of the neighbor node
461                         v3s16 n2pos = pos + dirs[i];
462                         
463                         u32 n2i = m_area.index(n2pos);
464
465                         if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
466                                 continue;
467
468                         MapNode &n2 = m_data[n2i];
469                         
470                         /*
471                                 If the neighbor is dimmer than what was specified
472                                 as oldlight (the light of the previous node)
473                         */
474                         if(n2.getLight(bank, nodemgr) < oldlight)
475                         {
476                                 /*
477                                         And the neighbor is transparent and it has some light
478                                 */
479                                 if(nodemgr->get(n2).light_propagates && n2.getLight(bank, nodemgr) != 0)
480                                 {
481                                         /*
482                                                 Set light to 0 and add to queue
483                                         */
484
485                                         u8 current_light = n2.getLight(bank, nodemgr);
486                                         n2.setLight(bank, 0);
487
488                                         unlighted_nodes.insert(n2pos, current_light);
489                                         
490                                         /*
491                                                 Remove from light_sources if it is there
492                                                 NOTE: This doesn't happen nearly at all
493                                         */
494                                         /*if(light_sources.find(n2pos))
495                                         {
496                                                 std::cout<<"Removed from light_sources"<<std::endl;
497                                                 light_sources.remove(n2pos);
498                                         }*/
499                                 }
500                         }
501                         else{
502                                 light_sources.insert(n2pos, true);
503                         }
504                 }
505         }
506
507         /*dstream<<"unspreadLight(): Changed block "
508                         <<blockchangecount<<" times"
509                         <<" for "<<from_nodes.size()<<" nodes"
510                         <<std::endl;*/
511         
512         if(unlighted_nodes.size() > 0)
513                 unspreadLight(bank, unlighted_nodes, light_sources);
514 }
515 #endif
516
517 void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p,
518                 INodeDefManager *nodemgr)
519 {
520         const v3s16 dirs[6] = {
521                 v3s16(0,0,1), // back
522                 v3s16(0,1,0), // top
523                 v3s16(1,0,0), // right
524                 v3s16(0,0,-1), // front
525                 v3s16(0,-1,0), // bottom
526                 v3s16(-1,0,0), // left
527         };
528
529         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));
530
531         u32 i = m_area.index(p);
532         
533         if(m_flags[i] & VOXELFLAG_INEXISTENT)
534                 return;
535
536         MapNode &n = m_data[i];
537
538         u8 oldlight = n.getLight(bank, nodemgr);
539         u8 newlight = diminish_light(oldlight);
540
541         // Loop through 6 neighbors
542         for(u16 i=0; i<6; i++)
543         {
544                 // Get the position of the neighbor node
545                 v3s16 n2pos = p + dirs[i];
546                 
547                 u32 n2i = m_area.index(n2pos);
548
549                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
550                         continue;
551
552                 MapNode &n2 = m_data[n2i];
553
554                 u8 light2 = n2.getLight(bank, nodemgr);
555                 
556                 /*
557                         If the neighbor is brighter than the current node,
558                         add to list (it will light up this node on its turn)
559                 */
560                 if(light2 > undiminish_light(oldlight))
561                 {
562                         spreadLight(bank, n2pos, nodemgr);
563                 }
564                 /*
565                         If the neighbor is dimmer than how much light this node
566                         would spread on it, add to list
567                 */
568                 if(light2 < newlight)
569                 {
570                         if(nodemgr->get(n2).light_propagates)
571                         {
572                                 n2.setLight(bank, newlight, nodemgr);
573                                 spreadLight(bank, n2pos, nodemgr);
574                         }
575                 }
576         }
577 }
578
579 #if 0
580 /*
581         Lights neighbors of from_nodes, collects all them and then
582         goes on recursively.
583
584         NOTE: This is faster on small areas but will overflow the
585               stack on large areas. Thus it is not used.
586 */
587 void VoxelManipulator::spreadLight(enum LightBank bank,
588                 core::map<v3s16, bool> & from_nodes)
589 {
590         if(from_nodes.size() == 0)
591                 return;
592         
593         core::map<v3s16, bool> lighted_nodes;
594         core::map<v3s16, bool>::Iterator j;
595         j = from_nodes.getIterator();
596
597         for(; j.atEnd() == false; j++)
598         {
599                 v3s16 pos = j.getNode()->getKey();
600
601                 spreadLight(bank, pos);
602         }
603 }
604 #endif
605
606 #if 1
607 /*
608         Lights neighbors of from_nodes, collects all them and then
609         goes on recursively.
610 */
611 void VoxelManipulator::spreadLight(enum LightBank bank,
612                 core::map<v3s16, bool> & from_nodes, INodeDefManager *nodemgr)
613 {
614         const v3s16 dirs[6] = {
615                 v3s16(0,0,1), // back
616                 v3s16(0,1,0), // top
617                 v3s16(1,0,0), // right
618                 v3s16(0,0,-1), // front
619                 v3s16(0,-1,0), // bottom
620                 v3s16(-1,0,0), // left
621         };
622
623         if(from_nodes.size() == 0)
624                 return;
625         
626         core::map<v3s16, bool> lighted_nodes;
627         core::map<v3s16, bool>::Iterator j;
628         j = from_nodes.getIterator();
629
630         for(; j.atEnd() == false; j++)
631         {
632                 v3s16 pos = j.getNode()->getKey();
633
634                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
635
636                 u32 i = m_area.index(pos);
637                 
638                 if(m_flags[i] & VOXELFLAG_INEXISTENT)
639                         continue;
640
641                 MapNode &n = m_data[i];
642
643                 u8 oldlight = n.getLight(bank, nodemgr);
644                 u8 newlight = diminish_light(oldlight);
645
646                 // Loop through 6 neighbors
647                 for(u16 i=0; i<6; i++)
648                 {
649                         // Get the position of the neighbor node
650                         v3s16 n2pos = pos + dirs[i];
651                         
652                         try
653                         {
654                                 u32 n2i = m_area.index(n2pos);
655
656                                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
657                                         continue;
658
659                                 MapNode &n2 = m_data[n2i];
660
661                                 u8 light2 = n2.getLight(bank, nodemgr);
662                                 
663                                 /*
664                                         If the neighbor is brighter than the current node,
665                                         add to list (it will light up this node on its turn)
666                                 */
667                                 if(light2 > undiminish_light(oldlight))
668                                 {
669                                         lighted_nodes.insert(n2pos, true);
670                                 }
671                                 /*
672                                         If the neighbor is dimmer than how much light this node
673                                         would spread on it, add to list
674                                 */
675                                 if(light2 < newlight)
676                                 {
677                                         if(nodemgr->get(n2).light_propagates)
678                                         {
679                                                 n2.setLight(bank, newlight, nodemgr);
680                                                 lighted_nodes.insert(n2pos, true);
681                                         }
682                                 }
683                         }
684                         catch(InvalidPositionException &e)
685                         {
686                                 continue;
687                         }
688                 }
689         }
690
691         /*dstream<<"spreadLight(): Changed block "
692                         <<blockchangecount<<" times"
693                         <<" for "<<from_nodes.size()<<" nodes"
694                         <<std::endl;*/
695         
696         if(lighted_nodes.size() > 0)
697                 spreadLight(bank, lighted_nodes, nodemgr);
698 }
699 #endif
700
701 //END