3 Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
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.
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.
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.
20 #include "voxelalgorithms.h"
28 void setLight(VoxelManipulator &v, VoxelArea a, u8 light,
29 INodeDefManager *ndef)
31 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
32 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
33 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
36 MapNode &n = v.getNodeRefUnsafe(p);
37 n.setLight(LIGHTBANK_DAY, light, ndef);
38 n.setLight(LIGHTBANK_NIGHT, light, ndef);
42 void clearLightAndCollectSources(VoxelManipulator &v, VoxelArea a,
43 enum LightBank bank, INodeDefManager *ndef,
44 std::set<v3s16> & light_sources,
45 std::map<v3s16, u8> & unlight_from)
47 // The full area we shall touch
48 VoxelArea required_a = a;
49 required_a.pad(v3s16(0,0,0));
50 // Make sure we have access to it
53 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
54 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
55 for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
58 MapNode &n = v.getNodeRefUnsafe(p);
59 u8 oldlight = n.getLight(bank, ndef);
60 n.setLight(bank, 0, ndef);
62 // If node sources light, add to list
63 u8 source = ndef->get(n).light_source;
65 light_sources.insert(p);
67 // Collect borders for unlighting
68 if((x==a.MinEdge.X || x == a.MaxEdge.X
69 || y==a.MinEdge.Y || y == a.MaxEdge.Y
70 || z==a.MinEdge.Z || z == a.MaxEdge.Z)
73 unlight_from[p] = oldlight;
78 SunlightPropagateResult propagateSunlight(VoxelManipulator &v, VoxelArea a,
79 bool inexistent_top_provides_sunlight,
80 std::set<v3s16> & light_sources,
81 INodeDefManager *ndef)
84 bool bottom_sunlight_valid = true;
86 // The full area we shall touch extends one extra at top and bottom
87 VoxelArea required_a = a;
88 required_a.pad(v3s16(0,1,0));
89 // Make sure we have access to it
92 s16 max_y = a.MaxEdge.Y;
93 s16 min_y = a.MinEdge.Y;
95 for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
96 for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
98 v3s16 p_overtop(x, max_y+1, z);
99 bool overtop_has_sunlight = false;
100 // If overtop node does not exist, trust heuristics
101 if(!v.exists(p_overtop))
102 overtop_has_sunlight = inexistent_top_provides_sunlight;
103 else if(v.getNodeRefUnsafe(p_overtop).getContent() == CONTENT_IGNORE)
104 overtop_has_sunlight = inexistent_top_provides_sunlight;
105 // Otherwise refer to it's light value
107 overtop_has_sunlight = (v.getNodeRefUnsafe(p_overtop).getLight(
108 LIGHTBANK_DAY, ndef) == LIGHT_SUN);
110 // Copy overtop's sunlight all over the place
111 u8 incoming_light = overtop_has_sunlight ? LIGHT_SUN : 0;
112 for(s32 y=max_y; y>=min_y; y--)
115 MapNode &n = v.getNodeRefUnsafe(p);
116 if(incoming_light == 0){
118 } else if(incoming_light == LIGHT_SUN &&
119 ndef->get(n).sunlight_propagates){
121 } else if(ndef->get(n).sunlight_propagates == false){
124 incoming_light = diminish_light(incoming_light);
126 u8 old_light = n.getLight(LIGHTBANK_DAY, ndef);
128 if(incoming_light > old_light)
129 n.setLight(LIGHTBANK_DAY, incoming_light, ndef);
131 if(diminish_light(incoming_light) != 0)
132 light_sources.insert(p);
135 // Check validity of sunlight at top of block below if it
136 // hasn't already been proven invalid
137 if(bottom_sunlight_valid)
139 bool sunlight_should_continue_down = (incoming_light == LIGHT_SUN);
140 v3s16 p_overbottom(x, min_y-1, z);
141 if(!v.exists(p_overbottom) ||
142 v.getNodeRefUnsafe(p_overbottom
143 ).getContent() == CONTENT_IGNORE){
144 // Is not known, cannot compare
146 bool overbottom_has_sunlight = (v.getNodeRefUnsafe(p_overbottom
147 ).getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN);
148 if(sunlight_should_continue_down != overbottom_has_sunlight){
149 bottom_sunlight_valid = false;
155 return SunlightPropagateResult(bottom_sunlight_valid);
167 * Two directions are opposite only if their sum is 5.
169 typedef u8 direction;
171 * Relative node position.
172 * This represents a node's position in its map block.
173 * All coordinates must be between 0 and 15.
175 typedef v3s16 relative_v3;
177 * Position of a map block (block coordinates).
178 * One block_pos unit is as long as 16 node position units.
180 typedef v3s16 mapblock_v3;
182 //! Contains information about a node whose light is about to change.
183 struct ChangingLight {
184 //! Relative position of the node in its map block.
185 relative_v3 rel_position;
186 //! Position of the node's block.
187 mapblock_v3 block_position;
188 //! Pointer to the node's block.
191 * Direction from the node that caused this node's changing
194 direction source_direction;
203 ChangingLight(relative_v3 rel_pos, mapblock_v3 block_pos,
204 MapBlock *b, direction source_dir) :
205 rel_position(rel_pos),
206 block_position(block_pos),
208 source_direction(source_dir)
213 * A fast, priority queue-like container to contain ChangingLights.
214 * The ChangingLights are ordered by the given light levels.
215 * The brightest ChangingLight is returned first.
218 //! For each light level there is a vector.
219 std::vector<ChangingLight> lights[LIGHT_SUN + 1];
220 //! Light of the brightest ChangingLight in the queue.
224 * Creates a LightQueue.
225 * \param reserve for each light level that many slots are reserved.
227 LightQueue(size_t reserve)
229 max_light = LIGHT_SUN;
230 for (u8 i = 0; i <= LIGHT_SUN; i++) {
231 lights[i].reserve(reserve);
236 * Returns the next brightest ChangingLight and
237 * removes it from the queue.
238 * If there were no elements in the queue, the given parameters
240 * \param light light level of the popped ChangingLight
241 * \param data the ChangingLight that was popped
242 * \returns true if there was a ChangingLight in the queue.
244 bool next(u8 &light, ChangingLight &data)
246 while (lights[max_light].empty()) {
247 if (max_light == 0) {
253 data = lights[max_light].back();
254 lights[max_light].pop_back();
259 * Adds an element to the queue.
260 * The parameters are the same as in ChangingLight's constructor.
261 * \param light light level of the ChangingLight
263 inline void push(u8 light, const relative_v3 &rel_pos,
264 const mapblock_v3 &block_pos, MapBlock *block,
265 direction source_dir)
267 assert(light <= LIGHT_SUN);
268 lights[light].push_back(
269 ChangingLight(rel_pos, block_pos, block, source_dir));
274 * This type of light queue is for unlighting.
275 * A node can be pushed in it only if its raw light is zero.
276 * This prevents pushing nodes twice into this queue.
277 * The light of the pushed ChangingLight must be the
278 * light of the node before unlighting it.
280 typedef LightQueue UnlightQueue;
282 * This type of light queue is for spreading lights.
283 * While spreading lights, all the nodes in it must
284 * have the same light as the light level the ChangingLights
285 * were pushed into this queue with. This prevents unnecessary
286 * re-pushing of the nodes into the queue.
287 * If a node doesn't let light trough but emits light, it can be added
290 typedef LightQueue ReLightQueue;
293 * neighbor_dirs[i] points towards
295 * See the definition of the type "direction"
297 const static v3s16 neighbor_dirs[6] = {
298 v3s16(1, 0, 0), // right
299 v3s16(0, 1, 0), // top
300 v3s16(0, 0, 1), // back
301 v3s16(0, 0, -1), // front
302 v3s16(0, -1, 0), // bottom
303 v3s16(-1, 0, 0), // left
307 * Transforms the given map block offset by one node towards
308 * the specified direction.
309 * \param dir the direction of the transformation
310 * \param rel_pos the node's relative position in its map block
311 * \param block_pos position of the node's block
313 bool step_rel_block_pos(direction dir, relative_v3 &rel_pos,
314 mapblock_v3 &block_pos)
318 if (rel_pos.X < MAP_BLOCKSIZE - 1) {
327 if (rel_pos.Y < MAP_BLOCKSIZE - 1) {
336 if (rel_pos.Z < MAP_BLOCKSIZE - 1) {
348 rel_pos.Z = MAP_BLOCKSIZE - 1;
357 rel_pos.Y = MAP_BLOCKSIZE - 1;
366 rel_pos.X = MAP_BLOCKSIZE - 1;
376 * Removes all light that is potentially emitted by the specified
377 * light sources. These nodes will have zero light.
378 * Returns all nodes whose light became zero but should be re-lighted.
380 * \param bank the light bank in which the procedure operates
381 * \param from_nodes nodes whose light is removed
382 * \param light_sources nodes that should be re-lighted
383 * \param modified_blocks output, all modified map blocks are added to this
385 void unspread_light(Map *map, INodeDefManager *nodemgr, LightBank bank,
386 UnlightQueue &from_nodes, ReLightQueue &light_sources,
387 std::map<v3s16, MapBlock*> &modified_blocks)
389 // Stores data popped from from_nodes
391 ChangingLight current;
392 // Data of the current neighbor
393 mapblock_v3 neighbor_block_pos;
394 relative_v3 neighbor_rel_pos;
396 bool is_valid_position;
397 // Direction of the brightest neighbor of the node
398 direction source_dir;
399 while (from_nodes.next(current_light, current)) {
400 // For all nodes that need unlighting
402 // There is no brightest neighbor
405 const MapNode &node = current.block->getNodeNoCheck(
406 current.rel_position, &is_valid_position);
407 const ContentFeatures &f = nodemgr->get(node);
408 // If the node emits light, it behaves like it had a
409 // brighter neighbor.
410 u8 brightest_neighbor_light = f.light_source + 1;
411 for (direction i = 0; i < 6; i++) {
414 // The node that changed this node has already zero light
415 // and it can't give light to this node
416 if (current.source_direction + i == 5) {
419 // Get the neighbor's position and block
420 neighbor_rel_pos = current.rel_position;
421 neighbor_block_pos = current.block_position;
422 MapBlock *neighbor_block;
423 if (step_rel_block_pos(i, neighbor_rel_pos, neighbor_block_pos)) {
424 neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
425 if (neighbor_block == NULL) {
429 neighbor_block = current.block;
431 // Get the neighbor itself
432 MapNode neighbor = neighbor_block->getNodeNoCheck(neighbor_rel_pos,
434 const ContentFeatures &neighbor_f = nodemgr->get(
435 neighbor.getContent());
436 u8 neighbor_light = neighbor.getLightRaw(bank, neighbor_f);
437 // If the neighbor has at least as much light as this node, then
438 // it won't lose its light, since it should have been added to
439 // from_nodes earlier, so its light would be zero.
440 if (neighbor_f.light_propagates && neighbor_light < current_light) {
441 // Unlight, but only if the node has light.
442 if (neighbor_light > 0) {
443 neighbor.setLight(bank, 0, neighbor_f);
444 neighbor_block->setNodeNoCheck(neighbor_rel_pos, neighbor);
445 from_nodes.push(neighbor_light, neighbor_rel_pos,
446 neighbor_block_pos, neighbor_block, i);
447 // The current node was modified earlier, so its block
448 // is in modified_blocks.
449 if (current.block != neighbor_block) {
450 modified_blocks[neighbor_block_pos] = neighbor_block;
454 // The neighbor can light up this node.
455 if (neighbor_light < neighbor_f.light_source) {
456 neighbor_light = neighbor_f.light_source;
458 if (brightest_neighbor_light < neighbor_light) {
459 brightest_neighbor_light = neighbor_light;
464 // If the brightest neighbor is able to light up this node,
465 // then add this node to the output nodes.
466 if (brightest_neighbor_light > 1 && f.light_propagates) {
467 brightest_neighbor_light--;
468 light_sources.push(brightest_neighbor_light, current.rel_position,
469 current.block_position, current.block,
470 (source_dir == 6) ? 6 : 5 - source_dir
471 /* with opposite direction*/);
477 * Spreads light from the specified starting nodes.
479 * Before calling this procedure, make sure that all ChangingLights
480 * in light_sources have as much light on the map as they have in
481 * light_sources (if the queue contains a node multiple times, the brightest
482 * occurrence counts).
484 * \param bank the light bank in which the procedure operates
485 * \param light_sources starting nodes
486 * \param modified_blocks output, all modified map blocks are added to this
488 void spread_light(Map *map, INodeDefManager *nodemgr, LightBank bank,
489 LightQueue &light_sources, std::map<v3s16, MapBlock*> &modified_blocks)
491 // The light the current node can provide to its neighbors.
493 // The ChangingLight for the current node.
494 ChangingLight current;
495 // Position of the current neighbor.
496 mapblock_v3 neighbor_block_pos;
497 relative_v3 neighbor_rel_pos;
499 bool is_valid_position;
500 while (light_sources.next(spreading_light, current)) {
502 for (direction i = 0; i < 6; i++) {
503 // This node can't light up its light source
504 if (current.source_direction + i == 5) {
507 // Get the neighbor's position and block
508 neighbor_rel_pos = current.rel_position;
509 neighbor_block_pos = current.block_position;
510 MapBlock *neighbor_block;
511 if (step_rel_block_pos(i, neighbor_rel_pos, neighbor_block_pos)) {
512 neighbor_block = map->getBlockNoCreateNoEx(neighbor_block_pos);
513 if (neighbor_block == NULL) {
517 neighbor_block = current.block;
519 // Get the neighbor itself
520 MapNode neighbor = neighbor_block->getNodeNoCheck(neighbor_rel_pos,
522 const ContentFeatures &f = nodemgr->get(neighbor.getContent());
523 if (f.light_propagates) {
524 // Light up the neighbor, if it has less light than it should.
525 u8 neighbor_light = neighbor.getLightRaw(bank, f);
526 if (neighbor_light < spreading_light) {
527 neighbor.setLight(bank, spreading_light, f);
528 neighbor_block->setNodeNoCheck(neighbor_rel_pos, neighbor);
529 light_sources.push(spreading_light, neighbor_rel_pos,
530 neighbor_block_pos, neighbor_block, i);
531 // The current node was modified earlier, so its block
532 // is in modified_blocks.
533 if (current.block != neighbor_block) {
534 modified_blocks[neighbor_block_pos] = neighbor_block;
543 * Returns true if the node gets sunlight from the
546 * \param pos position of the node.
548 bool is_sunlight_above(Map *map, v3s16 pos, INodeDefManager *ndef)
550 bool sunlight = true;
551 mapblock_v3 source_block_pos;
552 relative_v3 source_rel_pos;
553 getNodeBlockPosWithOffset(pos + v3s16(0, 1, 0), source_block_pos,
555 // If the node above has sunlight, this node also can get it.
556 MapBlock *source_block = map->getBlockNoCreateNoEx(source_block_pos);
557 if (source_block == NULL) {
558 // But if there is no node above, then use heuristics
559 MapBlock *node_block = map->getBlockNoCreateNoEx(getNodeBlockPos(pos));
560 if (node_block == NULL) {
563 sunlight = !node_block->getIsUnderground();
566 bool is_valid_position;
567 MapNode above = source_block->getNodeNoCheck(source_rel_pos,
569 if (is_valid_position) {
570 if (above.getContent() == CONTENT_IGNORE) {
572 if (source_block->getIsUnderground()) {
575 } else if (above.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN) {
576 // If the node above doesn't have sunlight, this
577 // node is in shadow.
585 static const LightBank banks[] = { LIGHTBANK_DAY, LIGHTBANK_NIGHT };
587 void update_lighting_nodes(Map *map, INodeDefManager *ndef,
588 std::vector<std::pair<v3s16, MapNode> > &oldnodes,
589 std::map<v3s16, MapBlock*> &modified_blocks)
591 // For node getter functions
592 bool is_valid_position;
594 // Process each light bank separately
595 for (s32 i = 0; i < 2; i++) {
596 LightBank bank = banks[i];
597 UnlightQueue disappearing_lights(256);
598 ReLightQueue light_sources(256);
599 // For each changed node process sunlight and initialize
600 for (std::vector<std::pair<v3s16, MapNode> >::iterator it =
601 oldnodes.begin(); it < oldnodes.end(); ++it) {
602 // Get position and block of the changed node
605 mapblock_v3 block_pos;
606 getNodeBlockPosWithOffset(p, block_pos, rel_pos);
607 MapBlock *block = map->getBlockNoCreateNoEx(block_pos);
608 if (block == NULL || block->isDummy()) {
612 MapNode n = block->getNodeNoCheck(rel_pos, &is_valid_position);
613 if (!is_valid_position) {
617 // Light of the old node
618 u8 old_light = it->second.getLight(bank, ndef);
620 // Add the block of the added node to modified_blocks
621 modified_blocks[block_pos] = block;
623 // Get new light level of the node
625 if (ndef->get(n).light_propagates) {
626 if (bank == LIGHTBANK_DAY && ndef->get(n).sunlight_propagates
627 && is_sunlight_above(map, p, ndef)) {
628 new_light = LIGHT_SUN;
630 new_light = ndef->get(n).light_source;
631 for (int i = 0; i < 6; i++) {
632 v3s16 p2 = p + neighbor_dirs[i];
634 MapNode n2 = map->getNodeNoEx(p2, &is_valid);
636 u8 spread = n2.getLight(bank, ndef);
637 // If the neighbor is at least as bright as
638 // this node then its light is not from
640 // Its light can spread to this node.
641 if (spread > new_light && spread >= old_light) {
642 new_light = spread - 1;
648 // If this is an opaque node, it still can emit light.
649 new_light = ndef->get(n).light_source;
653 light_sources.push(new_light, rel_pos, block_pos, block, 6);
656 if (new_light < old_light) {
657 // The node became opaque or doesn't provide as much
658 // light as the previous one, so it must be unlighted.
660 // Add to unlight queue
661 n.setLight(bank, 0, ndef);
662 block->setNodeNoCheck(rel_pos, n);
663 disappearing_lights.push(old_light, rel_pos, block_pos, block,
666 // Remove sunlight, if there was any
667 if (bank == LIGHTBANK_DAY && old_light == LIGHT_SUN) {
668 for (s16 y = p.Y - 1;; y--) {
669 v3s16 n2pos(p.X, y, p.Z);
673 n2 = map->getNodeNoEx(n2pos, &is_valid_position);
674 if (!is_valid_position)
677 // If this node doesn't have sunlight, the nodes below
678 // it don't have too.
679 if (n2.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN) {
682 // Remove sunlight and add to unlight queue.
683 n2.setLight(LIGHTBANK_DAY, 0, ndef);
684 map->setNode(n2pos, n2);
685 relative_v3 rel_pos2;
686 mapblock_v3 block_pos2;
687 getNodeBlockPosWithOffset(n2pos, block_pos2, rel_pos2);
688 MapBlock *block2 = map->getBlockNoCreateNoEx(
690 disappearing_lights.push(LIGHT_SUN, rel_pos2,
692 4 /* The node above caused the change */);
695 } else if (new_light > old_light) {
696 // It is sure that the node provides more light than the previous
697 // one, unlighting is not necessary.
698 // Propagate sunlight
699 if (bank == LIGHTBANK_DAY && new_light == LIGHT_SUN) {
700 for (s16 y = p.Y - 1;; y--) {
701 v3s16 n2pos(p.X, y, p.Z);
705 n2 = map->getNodeNoEx(n2pos, &is_valid_position);
706 if (!is_valid_position)
709 // This should not happen, but if the node has sunlight
710 // then the iteration should stop.
711 if (n2.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN) {
714 // If the node terminates sunlight, stop.
715 if (!ndef->get(n2).sunlight_propagates) {
718 relative_v3 rel_pos2;
719 mapblock_v3 block_pos2;
720 getNodeBlockPosWithOffset(n2pos, block_pos2, rel_pos2);
721 MapBlock *block2 = map->getBlockNoCreateNoEx(
723 // Mark node for lighting.
724 light_sources.push(LIGHT_SUN, rel_pos2, block_pos2,
732 unspread_light(map, ndef, bank, disappearing_lights, light_sources,
734 // Initialize light values for light spreading.
735 for (u8 i = 0; i <= LIGHT_SUN; i++) {
736 const std::vector<ChangingLight> &lights = light_sources.lights[i];
737 for (std::vector<ChangingLight>::const_iterator it = lights.begin();
738 it < lights.end(); it++) {
739 MapNode n = it->block->getNodeNoCheck(it->rel_position,
741 n.setLight(bank, i, ndef);
742 it->block->setNodeNoCheck(it->rel_position, n);
746 spread_light(map, ndef, bank, light_sources, modified_blocks);
750 } // namespace voxalgo