Re-add jungles, apple trees
[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                 std::set<v3s16> & 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);
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                 std::map<v3s16, u8> & from_nodes,
388                 std::set<v3s16> & light_sources, INodeDefManager *nodemgr)
389 {
390         if(from_nodes.size() == 0)
391                 return;
392         
393         for(std::map<v3s16, u8>::iterator j = from_nodes.begin();
394                 j != from_nodes.end(); ++j)
395         {
396                 unspreadLight(bank, j->first, j->second, light_sources, nodemgr);
397         }
398 }
399 #endif
400
401 #if 0
402 /*
403         Goes recursively through the neighbours of the node.
404
405         Alters only transparent nodes.
406
407         If the lighting of the neighbour is lower than the lighting of
408         the node was (before changing it to 0 at the step before), the
409         lighting of the neighbour is set to 0 and then the same stuff
410         repeats for the neighbour.
411
412         The ending nodes of the routine are stored in light_sources.
413         This is useful when a light is removed. In such case, this
414         routine can be called for the light node and then again for
415         light_sources to re-light the area without the removed light.
416
417         values of from_nodes are lighting values.
418 */
419 void VoxelManipulator::unspreadLight(enum LightBank bank,
420                 core::map<v3s16, u8> & from_nodes,
421                 core::map<v3s16, bool> & light_sources)
422 {
423         v3s16 dirs[6] = {
424                 v3s16(0,0,1), // back
425                 v3s16(0,1,0), // top
426                 v3s16(1,0,0), // right
427                 v3s16(0,0,-1), // front
428                 v3s16(0,-1,0), // bottom
429                 v3s16(-1,0,0), // left
430         };
431         
432         if(from_nodes.size() == 0)
433                 return;
434         
435         core::map<v3s16, u8> unlighted_nodes;
436         core::map<v3s16, u8>::Iterator j;
437         j = from_nodes.getIterator();
438
439         for(; j.atEnd() == false; j++)
440         {
441                 v3s16 pos = j.getNode()->getKey();
442                 
443                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
444
445                 //MapNode &n = m_data[m_area.index(pos)];
446                 
447                 u8 oldlight = j.getNode()->getValue();
448                 
449                 // Loop through 6 neighbors
450                 for(u16 i=0; i<6; i++)
451                 {
452                         // Get the position of the neighbor node
453                         v3s16 n2pos = pos + dirs[i];
454                         
455                         u32 n2i = m_area.index(n2pos);
456
457                         if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
458                                 continue;
459
460                         MapNode &n2 = m_data[n2i];
461                         
462                         /*
463                                 If the neighbor is dimmer than what was specified
464                                 as oldlight (the light of the previous node)
465                         */
466                         if(n2.getLight(bank, nodemgr) < oldlight)
467                         {
468                                 /*
469                                         And the neighbor is transparent and it has some light
470                                 */
471                                 if(nodemgr->get(n2).light_propagates && n2.getLight(bank, nodemgr) != 0)
472                                 {
473                                         /*
474                                                 Set light to 0 and add to queue
475                                         */
476
477                                         u8 current_light = n2.getLight(bank, nodemgr);
478                                         n2.setLight(bank, 0);
479
480                                         unlighted_nodes.insert(n2pos, current_light);
481                                         
482                                         /*
483                                                 Remove from light_sources if it is there
484                                                 NOTE: This doesn't happen nearly at all
485                                         */
486                                         /*if(light_sources.find(n2pos))
487                                         {
488                                                 std::cout<<"Removed from light_sources"<<std::endl;
489                                                 light_sources.remove(n2pos);
490                                         }*/
491                                 }
492                         }
493                         else{
494                                 light_sources.insert(n2pos, true);
495                         }
496                 }
497         }
498
499         /*dstream<<"unspreadLight(): Changed block "
500                         <<blockchangecount<<" times"
501                         <<" for "<<from_nodes.size()<<" nodes"
502                         <<std::endl;*/
503         
504         if(unlighted_nodes.size() > 0)
505                 unspreadLight(bank, unlighted_nodes, light_sources);
506 }
507 #endif
508
509 void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p,
510                 INodeDefManager *nodemgr)
511 {
512         const v3s16 dirs[6] = {
513                 v3s16(0,0,1), // back
514                 v3s16(0,1,0), // top
515                 v3s16(1,0,0), // right
516                 v3s16(0,0,-1), // front
517                 v3s16(0,-1,0), // bottom
518                 v3s16(-1,0,0), // left
519         };
520
521         emerge(VoxelArea(p - v3s16(1,1,1), p + v3s16(1,1,1)));
522
523         u32 i = m_area.index(p);
524         
525         if(m_flags[i] & VOXELFLAG_INEXISTENT)
526                 return;
527
528         MapNode &n = m_data[i];
529
530         u8 oldlight = n.getLight(bank, nodemgr);
531         u8 newlight = diminish_light(oldlight);
532
533         // Loop through 6 neighbors
534         for(u16 i=0; i<6; i++)
535         {
536                 // Get the position of the neighbor node
537                 v3s16 n2pos = p + dirs[i];
538                 
539                 u32 n2i = m_area.index(n2pos);
540
541                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
542                         continue;
543
544                 MapNode &n2 = m_data[n2i];
545
546                 u8 light2 = n2.getLight(bank, nodemgr);
547                 
548                 /*
549                         If the neighbor is brighter than the current node,
550                         add to list (it will light up this node on its turn)
551                 */
552                 if(light2 > undiminish_light(oldlight))
553                 {
554                         spreadLight(bank, n2pos, nodemgr);
555                 }
556                 /*
557                         If the neighbor is dimmer than how much light this node
558                         would spread on it, add to list
559                 */
560                 if(light2 < newlight)
561                 {
562                         if(nodemgr->get(n2).light_propagates)
563                         {
564                                 n2.setLight(bank, newlight, nodemgr);
565                                 spreadLight(bank, n2pos, nodemgr);
566                         }
567                 }
568         }
569 }
570
571 #if 0
572 /*
573         Lights neighbors of from_nodes, collects all them and then
574         goes on recursively.
575
576         NOTE: This is faster on small areas but will overflow the
577               stack on large areas. Thus it is not used.
578 */
579 void VoxelManipulator::spreadLight(enum LightBank bank,
580                 core::map<v3s16, bool> & from_nodes)
581 {
582         if(from_nodes.size() == 0)
583                 return;
584         
585         core::map<v3s16, bool> lighted_nodes;
586         core::map<v3s16, bool>::Iterator j;
587         j = from_nodes.getIterator();
588
589         for(; j.atEnd() == false; j++)
590         {
591                 v3s16 pos = j.getNode()->getKey();
592
593                 spreadLight(bank, pos);
594         }
595 }
596 #endif
597
598 #if 1
599 /*
600         Lights neighbors of from_nodes, collects all them and then
601         goes on recursively.
602 */
603 void VoxelManipulator::spreadLight(enum LightBank bank,
604                 std::set<v3s16> & from_nodes, INodeDefManager *nodemgr)
605 {
606         const v3s16 dirs[6] = {
607                 v3s16(0,0,1), // back
608                 v3s16(0,1,0), // top
609                 v3s16(1,0,0), // right
610                 v3s16(0,0,-1), // front
611                 v3s16(0,-1,0), // bottom
612                 v3s16(-1,0,0), // left
613         };
614
615         if(from_nodes.size() == 0)
616                 return;
617         
618         std::set<v3s16> lighted_nodes;
619
620         for(std::set<v3s16>::iterator j = from_nodes.begin();
621                 j != from_nodes.end(); ++j)
622         {
623                 v3s16 pos = *j;
624
625                 emerge(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1)));
626
627                 u32 i = m_area.index(pos);
628                 
629                 if(m_flags[i] & VOXELFLAG_INEXISTENT)
630                         continue;
631
632                 MapNode &n = m_data[i];
633
634                 u8 oldlight = n.getLight(bank, nodemgr);
635                 u8 newlight = diminish_light(oldlight);
636
637                 // Loop through 6 neighbors
638                 for(u16 i=0; i<6; i++)
639                 {
640                         // Get the position of the neighbor node
641                         v3s16 n2pos = pos + dirs[i];
642                         
643                         try
644                         {
645                                 u32 n2i = m_area.index(n2pos);
646
647                                 if(m_flags[n2i] & VOXELFLAG_INEXISTENT)
648                                         continue;
649
650                                 MapNode &n2 = m_data[n2i];
651
652                                 u8 light2 = n2.getLight(bank, nodemgr);
653                                 
654                                 /*
655                                         If the neighbor is brighter than the current node,
656                                         add to list (it will light up this node on its turn)
657                                 */
658                                 if(light2 > undiminish_light(oldlight))
659                                 {
660                                         lighted_nodes.insert(n2pos);
661                                 }
662                                 /*
663                                         If the neighbor is dimmer than how much light this node
664                                         would spread on it, add to list
665                                 */
666                                 if(light2 < newlight)
667                                 {
668                                         if(nodemgr->get(n2).light_propagates)
669                                         {
670                                                 n2.setLight(bank, newlight, nodemgr);
671                                                 lighted_nodes.insert(n2pos);
672                                         }
673                                 }
674                         }
675                         catch(InvalidPositionException &e)
676                         {
677                                 continue;
678                         }
679                 }
680         }
681
682         /*dstream<<"spreadLight(): Changed block "
683                         <<blockchangecount<<" times"
684                         <<" for "<<from_nodes.size()<<" nodes"
685                         <<std::endl;*/
686         
687         if(lighted_nodes.size() > 0)
688                 spreadLight(bank, lighted_nodes, nodemgr);
689 }
690 #endif
691
692 //END