Finding blocks connected to a start position

[Jay Avery]

It's kind of hard to describe this in an abstract way so I'll just give my specific example: I'm trying to do various things with trees (e.g. make a whole tree fall when the trunk breaks) that require 'finding' every log and leaf block that's part of the tree. I'm just having trouble figuring out the most efficient way to do that.

 

My first (obvious) idea was to just search a cuboid of co-ordinates, checking every block and selecting it if it's log or leaves. The trouble with this is that it risks selecting blocks that belong to other nearby trees, plus it involves probably checking the state of loads of unnecessary air blocks which is surely bad for performance.

 

A better idea would be some kind of cleverer searching that moves from one block to the next and stops if it hits air. But I don't really know how I would begin making something like this - something like recursion to check all adjacent blocks at each block? Maybe that would end up being just a performance heavy as the first option, I don't know!

 

My best idea to avoid bringing down blocks from nearby trees is to keep a count of how many leaves have been selected and just stop after a certain limit is reached. But that means that whatever searching method I use needs to start from the centre of the tree and work outwards evenly, otherwise it risks selecting all the leaves from one side of a cuboid and leaving loads behind (or similar issues).

 

Does anyone have any suggestions for this? Examples of similar functionality would be appreciated, as would information about this stuff in general coding terms (I feel like 3D searching algorithms are surely something that people will have studied a lot, but I have no idea how to find out about that, I'm just a self-taught amateur).

 

Edit: An update for anyone who's interested. I've made a searching algorithm that finds all connected trunk blocks, and connected leaves up to a certain count, starting closest to the trunk. I use it in this method, (and use the search results to make all the tree blocks fall). If anyone has ideas on how to improve the performance I'd be grateful - I know I've used several different collections to keep track of all the checking but I couldn't think of any way to reduce that further.

Edited March 20, 2017 by Jay Avery

[Draco18s]

TL;DR: You can't insure you only get this tree's leaves. But you can get all of the log blocks.

 

Every log in a tree is connected to every other log in one of the following ways:

Up

North

South

East

West

NE

NW

SE

SW

Up+North

Up+South

Up+East

Up+West

Up+NE

Up+NW

Up+SE

Up+SW

[OreCruncher]

Other thing to do is spread the scan/break operation across several ticks.  Of course this would require maintaining some state for the operation but that shouldn't be too much an issue.

[clowcadia]

Also kinda working on the same thing, just no idea how to find what one block is connected too like log that connected to another log

[clowcadia]

On 2017-03-15 at 10:52 AM, Draco18s said:

TL;DR: You can't insure you only get this tree's leaves. But you can get all of the log blocks.

 

Every log in a tree is connected to every other log in one of the following ways:

Up

North

South

East

West

NE

NW

SE

SW

Up+North

Up+South

Up+East

Up+West

Up+NE

Up+NW

Up+SE

Up+SW

How exactly would you determine a logs neighbor/s?

[Draco18s]

4 hours ago, clowcadia said:

How exactly would you determine a logs neighbor/s?

Like I get any other block.

world.getBlock(pos) only with an offset in a direction. world.getBlock(pos.offset(facing))

 

#Seriously? #NotThatHard

[clowcadia]

I understand, i just thought there were premade methods in block/blockstates. it would be nice upon building trees there would be a setlist in array of all tree blocks that belong to one tree, like when u chop down all logs of tree all the tree leaves brake. there must be something like that in code somewhere

[Draco18s]

There isn't.

</thread>

[clowcadia]

I think its in BlockLeaves

the code is hard to understand though

public void updateTick(World worldIn, BlockPos pos, IBlockState state, Random rand)
    {
        if (!worldIn.isRemote)
        {
            if (((Boolean)state.getValue(CHECK_DECAY)).booleanValue() && ((Boolean)state.getValue(DECAYABLE)).booleanValue())
            {
                int i = 4;
                int j = 5;
                int k = pos.getX();
                int l = pos.getY();
                int i1 = pos.getZ();
                int j1 = 32;
                int k1 = 1024;
                int l1 = 16;

                if (this.surroundings == null)
                {
                    this.surroundings = new int[32768];
                }

                if (worldIn.isAreaLoaded(new BlockPos(k - 5, l - 5, i1 - 5), new BlockPos(k + 5, l + 5, i1 + 5)))
                {
                    BlockPos.MutableBlockPos blockpos$mutableblockpos = new BlockPos.MutableBlockPos();

                    for (int i2 = -4; i2 <= 4; ++i2)
                    {
                        for (int j2 = -4; j2 <= 4; ++j2)
                        {
                            for (int k2 = -4; k2 <= 4; ++k2)
                            {
                                IBlockState iblockstate = worldIn.getBlockState(blockpos$mutableblockpos.setPos(k + i2, l + j2, i1 + k2));
                                Block block = iblockstate.getBlock();

                                if (!block.canSustainLeaves(iblockstate, worldIn, blockpos$mutableblockpos.setPos(k + i2, l + j2, i1 + k2)))
                                {
                                    if (block.isLeaves(iblockstate, worldIn, blockpos$mutableblockpos.setPos(k + i2, l + j2, i1 + k2)))
                                    {
                                        this.surroundings[(i2 + 16) * 1024 + (j2 + 16) * 32 + k2 + 16] = -2;
                                    }
                                    else
                                    {
                                        this.surroundings[(i2 + 16) * 1024 + (j2 + 16) * 32 + k2 + 16] = -1;
                                    }
                                }
                                else
                                {
                                    this.surroundings[(i2 + 16) * 1024 + (j2 + 16) * 32 + k2 + 16] = 0;
                                }
                            }
                        }
                    }

                    for (int i3 = 1; i3 <= 4; ++i3)
                    {
                        for (int j3 = -4; j3 <= 4; ++j3)
                        {
                            for (int k3 = -4; k3 <= 4; ++k3)
                            {
                                for (int l3 = -4; l3 <= 4; ++l3)
                                {
                                    if (this.surroundings[(j3 + 16) * 1024 + (k3 + 16) * 32 + l3 + 16] == i3 - 1)
                                    {
                                        if (this.surroundings[(j3 + 16 - 1) * 1024 + (k3 + 16) * 32 + l3 + 16] == -2)
                                        {
                                            this.surroundings[(j3 + 16 - 1) * 1024 + (k3 + 16) * 32 + l3 + 16] = i3;
                                        }

                                        if (this.surroundings[(j3 + 16 + 1) * 1024 + (k3 + 16) * 32 + l3 + 16] == -2)
                                        {
                                            this.surroundings[(j3 + 16 + 1) * 1024 + (k3 + 16) * 32 + l3 + 16] = i3;
                                        }

                                        if (this.surroundings[(j3 + 16) * 1024 + (k3 + 16 - 1) * 32 + l3 + 16] == -2)
                                        {
                                            this.surroundings[(j3 + 16) * 1024 + (k3 + 16 - 1) * 32 + l3 + 16] = i3;
                                        }

                                        if (this.surroundings[(j3 + 16) * 1024 + (k3 + 16 + 1) * 32 + l3 + 16] == -2)
                                        {
                                            this.surroundings[(j3 + 16) * 1024 + (k3 + 16 + 1) * 32 + l3 + 16] = i3;
                                        }

                                        if (this.surroundings[(j3 + 16) * 1024 + (k3 + 16) * 32 + (l3 + 16 - 1)] == -2)
                                        {
                                            this.surroundings[(j3 + 16) * 1024 + (k3 + 16) * 32 + (l3 + 16 - 1)] = i3;
                                        }

                                        if (this.surroundings[(j3 + 16) * 1024 + (k3 + 16) * 32 + l3 + 16 + 1] == -2)
                                        {
                                            this.surroundings[(j3 + 16) * 1024 + (k3 + 16) * 32 + l3 + 16 + 1] = i3;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }

                int l2 = this.surroundings[16912];

                if (l2 >= 0)
                {
                    worldIn.setBlockState(pos, state.withProperty(CHECK_DECAY, Boolean.valueOf(false)), 4);
                }
                else
                {
                    this.destroy(worldIn, pos);
                }
            }
        }
    }

 

[clowcadia]

I just dont understand what do they mean by a mutable blockpos... i believe this it to know how block leaves fall ass they devay or get destroyed when the trunk is destroyed i believe

[clowcadia]

Hey Jay Every check out my AI task that chops a whole tree down, see what you thing . any criticism

https://github.com/Clowcadia/MinecraftForge/blob/master/1.11/NPCTesting/src/main/java/com/clowcadia/test/entities/living/ai/AIGoto.java

[clowcadia]

oh i just realized once all the log blocks are done u could probably check if the leave block is decaying to make sure it belongs to the tree

[Daeruin]

I have been interested in doing this, as well, and got some code working a few days ago that broke the logs for any tree. I was using a HarvestEvent. I was just letting the leaves decay on their own. I got sidetracked trying to re-place the logs horizontally on the ground, and now it's all messy and not working at the moment.

 

clowcadia, it's pretty clear that code from BlockLeaves isn't checking some predefined data about which leaves belong to any particular tree. I haven't gone through in detail, but it looks like it's just checking a 4x4x4 area around the leaf block in question to see if that area contains a block that can sustain leaves (i.e., a log block). You could do something similar and just break every leaf within 4 blocks of each log in the tree.

 

A more promising direction would be looking at the world gen classes to see how trees are generated. If you're cutting down an oak log, you can do a scan that mimics how the world generator places oak trees and destroy all the leaves in that area.

[clowcadia]

wow seams like we are working on the exact same thing, realisting wood chopper haha

yea that a good idea, one of my next steps is to place the log onthe ground with a tree leaves (i just realized to match the tree leave structure will be difficult, i was just gonna do block like bush, but not realistic enough), and then i am gonna take a look at the leaf connection to a tree

[Draco18s]

45 minutes ago, Daeruin said:

You could do something similar and just break every leaf within 4 blocks of each log in the tree.

That would strip other, nearby trees of their leaves, leaving bare logs.

38 minutes ago, clowcadia said:

wow seams like we are working on the exact same thing, realisting wood chopper haha

Because it's soooo unique...

Seriously, *I* wrote a tree-killing algorithm three years ago.  And I wasn't even the first.  TerrafirmaCraft and RotaryCraft both did it before I did.

[clowcadia]

lol the beginner modders challenge this is

[JTK222]

Ok simple explanation, however I don't know if it's still needed.

Every Log that is beeing broken informs all leaves in a specific range of this, the Leaves check then if there are any other Logs in range that can maintain them.

If not its decay tag will be changed to true, this means you can simply check for leaves having their decay tag set to true.

[clowcadia]

i was just about to say\

state.getValue(CHECK_DECAY)

[clowcadia]

cant figure out how get that to work

if(getBlock(pos).isLeaves(getIBS(pos),this.test.world,pos) && (BlockLeaves)getIBS(pos).getValue(CHECK_DECAY)){

 

CHECK_DECAY is in red

[clowcadia]

I dotn want to create a new topic for this, as my issues is with he the same theme..

[Jay Avery]

9 hours ago, clowcadia said:

cant figure out how get that to work

if(getBlock(pos).isLeaves(getIBS(pos),this.test.world,pos) && (BlockLeaves)getIBS(pos).getValue(CHECK_DECAY)){

 

CHECK_DECAY is in red

 

7 minutes ago, clowcadia said:

I dotn want to create a new topic for this, as my issues is with he the same theme..

Your problem on that line is a simple java error, nothing to do with this issue. CHECK_DECAY is a static field in the BlockLeaves class, so unless your code is in a subclass of BlockLeaves, you need to explicitly refer to the class the field is in.

[clowcadia]

not sure how to do that, something like this

(BlockLeaves)getBlock(pos).

[Jay Avery]

An update for anyone who's interested. I've made a searching algorithm that finds all connected trunk blocks, and connected leaves up to a certain count, starting closest to the trunk. I use it in this method, (and use the search results to make all the tree blocks fall). If anyone has ideas on how to improve the performance I'd be grateful - I know I've used several different collections to keep track of all the checking but I couldn't think of any way to reduce that further.

[Jay Avery]

4 minutes ago, clowcadia said:

not sure how to do that, something like this

(BlockLeaves)getBlock(pos).

Come on man, basic java. Accessing a static field from a class: TheClass.STATIC_FIELD. -> BlockLeaves.CHECK_DECAY.

[clowcadia]

but how does it know its that exact block