FOSS gamedev and creative worlds

Hello

I've always thought the leafdecay algorithm is one of the heaviest features of Minetest, since it's executed for hundreds of leaves every second, and that for every leaf, it needs to iterate over dozens of nodes.
I've seen that there is an optimization with trunk cache, but it still needs to iterate for many leaves.
I've an idea of a completely different method that may save time and allow bigger radius (up to 7), using param2.
The param2 for leaves is unused for now (except param2=1 for manually placed leaves).

My idea is to set a param2 for leaves. The param2 value can be converted into a relative position. The leafdecay algorithm consists in checking that a tree takes place at this position. So, every leaves block belongs to one tree. This solves a problem that I've very often seen: when you cut a trunk, the leaves falls, but if there is another tree next to it, most of the leaves don't fall.
My idea was to change the param2 values of schematics according to that. But a schematic can be placed at a random rotation. So a param2 value should match 4 positions (with 90° rotations) and we only have to iterate over 4 nodes.
This allows to spawn wider trees. It may slow down the mapgen, but not the leafdecay algorithm, since it has only 4 positions to check, no matter the radius.

I've made a test mod for that, with a modified pine tree schematic. You can see the code used to convert between param2 and vector, it's the function get_value in init.lua. It can handle an horizontal radius up to 7 (only the nearest are used for pine tree) and a vertical offset from -3 to +1. I've explained that in vector.txt.

This sounds great. However, wouldn't it be simpler and more efficient to remove the abms altogether and make leaf decay an on_destruct function of tree-type nodes? The main reason for leaf decay is to keep people from having to clean up when they chop down a tree, and that's easy enough to deal with each time they remove a node.

There are two cases where this wouldn't work. First, leaves left hanging by the mapgen, but in most of these instances pieces of trunk are left in the air as well, so leaf decay is only marginally useful. Second, cases where you use voxelmanip or overwrite with a schematic. Even then, it might be worth leaving a few leaves to save the CPU time that an abm uses.

duane wrote:This sounds great. However, wouldn't it be simpler and more efficient to remove the abms altogether and make leaf decay an on_destruct function of tree-type nodes?

That's an interesting avenue to explore. If you were to find all of the connected nodes that might not be very efficient. The other option would be to use find nodes in area to check an area for other tree nodes, and if no tree nodes are found then use find nodes in area to find all leaf nodes and decay them.

Another question is -- how much time does leaf decay actually take at the moment? Even when I turn it completely off for every node, it doesn't seem to make much difference on my system.

The reason is not only to save time. It should improve the way leaves are removed. Instead of removing the leaves that are at more than n nodes from the trunk, it removes leaves that have been spawned with the tree, even if they are close to another tree, so it better respects the shape of the nearby trees, instead of leaving an ugly square of leaves next to the tree. In fact, that's the most important thing for me. The time saving argument has only made me think about it.

duane wrote:Another question is -- how much time does leaf decay actually take at the moment? Even when I turn it completely off for every node, it doesn't seem to make much difference on my system.

Last time I ran a profiler I don't remember it being toward the top.

some trees do sort of huddle together. So do we get a tree-cadastre?


some jungle trees in disguise from this post

If leaves replace the leaves from another tree and then you remove the tree, the other tree gets destroyed.

So, attaching leaves to a tree doesn't work, IMHO

I always thought of why in the first place we can dig the leaves and retrieve them. In my minetest subgame Idea I removed doing so. Then again I had a idea how about when the tree is removed it causes the leaves to far like gravel and sand but have it a flat height (1/16) and they will set there forevermore and change color according to humanity setup. And one to get leaves will need a Trimmer or a Rake (if on ground). However I have no idea how do all this so.. I staying with remove cannot retrieve leaves.

But overall we need maybe a way leaves decay from not getting water maybe too.

Gael de Sailly wrote:The reason is not only to save time. It should improve the way leaves are removed. Instead of removing the leaves that are at more than n nodes from the trunk, it removes leaves that have been spawned with the tree, even if they are close to another tree, so it better respects the shape of the nearby trees, instead of leaving an ugly square of leaves next to the tree. In fact, that's the most important thing for me. The time saving argument has only made me think about it.

If you have a schematic that over-writes one tree with another, which probably happens a lot in the mapgen, wouldn't you still get ugly holes when you remove the newer of the two?

duane wrote:If you have a schematic that over-writes one tree with another, which probably happens a lot in the mapgen, wouldn't you still get ugly holes when you remove the newer of the two?

I've seen it but for me it's not worse than previously.
With the current minetest_game leafdecay, in a very dense forest, if you dig a tree, you don't get any leaves.
With this new leafdecay, it will still make a hole in the forest (what is expected).
It's normal that, when you cut a tree that is very close to another, this other tree has not its own shape. But I've not really seen "big holes". The fact that a param2 matches 4 positions means that some leaves (mostly those who are between 2 trees) are attached to 2 or more trees, and so will not disappear if you dig one of these trees.

duane wrote:Wouldn't it be simpler and more efficient to remove the abms altogether and make leaf decay an on_destruct function of tree-type nodes?

Very interesting too.

BrandonReese wrote:

duane wrote:This sounds great. However, wouldn't it be simpler and more efficient to remove the abms altogether and make leaf decay an on_destruct function of tree-type nodes?

That's an interesting avenue to explore. If you were to find all of the connected nodes that might not be very efficient. The other option would be to use find nodes in area to check an area for other tree nodes, and if no tree nodes are found then use find nodes in area to find all leaf nodes and decay them.

I'll probably play with it a bit, but the only advantage is time, and it seems like that's not much of an issue. Now, if I could find a way to make mobs more efficient, that would be worthwhile.

The idea sounds very intresting. Some additional information as to which tree trunk a particular leaf thinks it belongs to would make lumberjack mods (cut the whole tree including leaves) more efficient and leave less leaves floating around. Leaf decay can be very slow at times on servers.

duane wrote:the only advantage is time

...

Gael de Sailly wrote:The leafdecay algorithm consists in checking that a tree takes place at this position. So, every leaves block belongs to one tree. This solves a problem that I've very often seen: when you cut a trunk, the leaves falls, but if there is another tree next to it, most of the leaves don't fall.

Is this not also an advantage?

SegFault22 wrote:

duane wrote:the only advantage is time

...

Gael de Sailly wrote:The leafdecay algorithm consists in checking that a tree takes place at this position. So, every leaves block belongs to one tree. This solves a problem that I've very often seen: when you cut a trunk, the leaves falls, but if there is another tree next to it, most of the leaves don't fall.

Is this not also an advantage?

I was referring to my idea sucking, not the original post.

duane wrote:

SegFault22 wrote: ~ka-snip~

I was referring to my idea sucking, not the original post.

Oh. Okay, then, that's all good.

For Voxelgarden I made some time ago a slightly different leafdecay. It work like nodeupdate in that it checks for surrounding nodes. Sparked by this discussion I also added a callback to run leafupdate after a tree was dug.
It's fast, and the abm only needs to run with an interval of 5 and chance of 90 (compared to 2 and 5 in MTG). However it leaves sometimes large chuncks of leaves in the air which only decay after a longer waiting period.

I like the trees to instantly "fall" when the bottom node is cut with an axe (all tree-trunk-block nodes turn to items and fall, all leaf-blocks decay instantly and some drop saplings) - however, when you have two or more trees close together, the leaves can interfere, and half of the leaves on one tree (or worse, all of them on all connected trees) will be cut as well. Assigning metadata to each leaf-block telling what tree-node(s) are connected, will solve this problem; maybe its also possible for the metadata of outer leaf blocks to reference the inner leaf blocks, that way when you remove the inner leaf blocks, the outer ones decay instead of just floating there around the tree-trunk.

I like SegFault's idea. I'm going to implement this for the moretrees mod, every tree should get an Id assigned (maybe the tree's position) and when one trunk node is chopped down in that tree, the entire tree with that id decays.