Look for block from entity in very large radius [256x256x256]

[MSpace-Dev]

Hey everyone,

 

I am making a block that acts on entities in an area of 256x256x256. The problem I am having is that iterating through all these block pos's obviously puts EVERYTHING at a halt.  Makes sense, since it's iterating through 16,777,216 blocks! I have no idea how you could possible optimize something like this! I was looking through the MEGA TORCH source code, and couldn't really figure out what he could have possibly done to make his thing work in a 64x64x64 radius. Any help appreciated!

 My (16 million block check) code:

Iterable<BlockPos> tileEntityRadiusBlock = BlockPos.getAllInBox(eventPos.add(256.0f, 256.0f, 256.0f), eventPos.add(-256.0f, -256.0f, -256.0f)); // 256x256x256 range

for(BlockPos pos : tileEntityRadiusBlock) {
            Utils.getLogger().info(pos); // Starts printing 16.7 million lines of block pos =p
            if(world.getTileEntity(pos) != null){
                if(world.getTileEntity(pos) instanceof TileEntityRadiusBlock){
                    // Run code here
                }
            }
        }

 

Really guys! All help is appreciated! This is a HUGE BRICK WALL for me!

[MSpace-Dev]

So, instead of using Iterable<BlockPos> = BlockPos#getAllInBox. How do I find all chunks in the radius instead?

[MSpace-Dev]

Awesome, I'll give it a shot!

[MSpace-Dev]

Boy... I am not experienced with this...

Firstly,  I am having trouble accessing Chunk::getTileEntityMap, as I have no clue how to get the Chunk using these chunk coords. Secondly, won't you still be iterating through all BlockPos because you're still converting all of them into chunk coords, meaning, you'll get the same chunk out of multiple BlockPos'. How would I skip the chunk once I've found and checked it? Thridly, how do I check if TileEntities are in "block coordiante boundaries", and if they're not, how do I make them.

Super confused, sorry

 

This is literally all I have. I've been thinking about it, and have no idea where to go from here.

for (BlockPos pos : boxRadius) {
            int chunkCoordX = pos.getX() >> 4;
            int chunkCoordZ = pos.getZ() >> 4;
        }

 

[larsgerrits]

27 minutes ago, diesieben07 said:

int chunkCoord = blockCoord >> 4;

Just a question: what's the benefit of bit-shifting by 4 instead of dividing by 16? Isn't it just premature optimization?

[Matryoshika]

3 minutes ago, MSpace-Dev said:

Boy... I am not experienced with this...

Firstly,  I am having trouble accessing Chunk::getTileEntityMap, as I have no clue how to get the Chunk using these chunk coords. Secondly, won't you still be iterating through all BlockPos because you're still converting all of them into chunk coords, meaning, you'll get the same chunk out of multiple BlockPos'. How would I skip the chunk once I've found and checked it? Thridly, how do I check if TileEntities are in "block coordiante boundaries", and if they're not, how do I make them.

Super confused, sorry

 

This is literally all I have. I've been thinking about it, and have no idea where to go from here.

for (BlockPos pos : boxRadius) {
            int chunkCoordX = pos.getX() >> 4;
            int chunkCoordZ = pos.getZ() >> 4;
        }

 

You are iterating through all Blocks, to get their chunk... which contains 256*height blocks already, leading to getting the same chunk about as many times....

Get the BlockPos at whatever is looking for all of these tileentities (the blockpos of this scanner). Get the ChunkPos from that. Great you got the center chunk.
Now you have the ChunkX & ChunkZ values. As Chunks are 16 blocks across, you need to do as Diesieben said and run 2 for-loops, from each counting from -8 to 8 (inclusive (128 blocks radius)).
Then you add the first loops value to either chunk values, and the other loop-values to the other. Now you got all chunks in this 256^3 area.
Stuff these different ChunkPos coordinates you just calculated in a collection, and loop throughChunk::getTileEntityMap as described again by Diesieben.

[larsgerrits]

1 minute ago, diesieben07 said:

It's not a "benefit", dividing by 16 is simply incorrect for negative block positions:

-15 >> 4 == -1 but -15 / 16 == 0.

I can't believe I didn't realise that. Thanks for explaining!

[jabelar]

This is some good stuff from diesieben07.

 

@MSpace-Devto summarize, instead of looking 256 blocks in each direction you'll look 16 chunks in each direction (i.e. your main loop). For each chunk cooordinates (calculated by shifting the bits in their corner block's position as mentioned by diesieben07), you use the world's getChunkFromChunkCoordinates() method to get the chunk, and then use the getTileEntityMap() method on that chunk, then do whatever you need to with the tile entities in the map.

 

By the way, if your code is still lagging after all this you can consider distributing the execution over several ticks. In most cases things don't have to all happen together in exactly the same tick, so for example you could process all chunks in one direction in one tick, all in in another direction in the next tick, etc. and then repeat.

 

One other thing to consider is that 16 chunks away is a pretty big distance. There is a reason why Minecraft stops tracking entities at a distance, only loads chunks when needed, and basically limits the scope of what needs to be processed. While it is nice to consider mod features that process the "whole" world, there are practical considerations. Since the performance workload grows as the square of the radius. So just reducing the radius a bit will greatly improve performance. So you if you have problem at 16 chunks, try 15, 14, etc.

[MSpace-Dev]

Thank you everyone! @diesieben07 for specifics on the code syntax and explantion, @Matryoshika for pointing out that I'm not iterating through all Block Pos' to get chunks from each and clarifying the rest of pretty much everything, and finally @jabelar for the super helpful tips!

 

I have finally got everything working, and it is working great. I'm super grateful and really happy with how it's turned out. With this, my mod is fairly close to complete, code side. Couldn't have figured this out without the awesome, in-depth explanations from you guys.

[MSpace-Dev]

Thought I'd paste my final function here:

 

public static void findRadiusBlock(Event event, int radius) {
	BlockPos pos = event.getEntity().getPosition();

    int chunkPosX = pos.getX() >> 4;
    int chunkPosZ = pos.getZ() >> 4;

    if (!event.getWorld().isRemote) {
        for (int x = chunkPosX - radius; x < chunkPosX + radius; x++) {
            for (int z = chunkPosZ - radius; z < chunkPosZ + radius; z++) {
                Map<BlockPos, TileEntity> currentChunkTE = event.getWorld().getChunkFromChunkCoords(x, z).getTileEntityMap();
                for (TileEntity te : currentChunkTE.values()) {
                    if (te != null) {
                        if (te instanceof TileEntityRadiusBlock) {
                            myFunction();
                        }
                    }
                }
            }
        }
    }
}

 

[jredfox]

On 12/18/2017 at 4:41 PM, MSpace-Dev said:

Thought I'd paste my final function here:

 

public static void findRadiusBlock(Event event, int radius) {
	BlockPos pos = event.getEntity().getPosition();

    int chunkPosX = pos.getX() >> 4;
    int chunkPosZ = pos.getZ() >> 4;

    if (!event.getWorld().isRemote) {
        for (int x = chunkPosX - radius; x < chunkPosX + radius; x++) {
            for (int z = chunkPosZ - radius; z < chunkPosZ + radius; z++) {
                Map<BlockPos, TileEntity> currentChunkTE = event.getWorld().getChunkFromChunkCoords(x, z).getTileEntityMap();
                for (TileEntity te : currentChunkTE.values()) {
                    if (te != null) {
                        if (te instanceof TileEntityRadiusBlock) {
                            myFunction();
                        }
                    }
                }
            }
        }
    }
}

 

you need to insert <= not < as I painted a radius of pixels around a middle pixel and it didn't work without the <= . So your not scanning the entire radius but, thanks for that equation couldn't think off the top of my head how this is done without 500 lines of code that will probably mess up

Edited March 1, 2018 by jredfox