Algorithm for storing blocks.

Discussion in 'Spigot Plugin Development' started by Kilian544, Sep 15, 2019.

  1. So I want to store all blocks in an area, is there some algorithm out there which accomplishes this. I could simply store a list of all blocks, but my concern is this would take up quite some memory, and I'd rather use some cpu to calculate if a block is inside a smaller cuboid. I have made a diagram for better explaining.

    [​IMG]

    So I have painted a single iteration of my idea, You go from up left to down right. Creating a cuboid of biggest possible area each time. This way I can reduce my original 77 blocks down to just the two outer ones of a cuboid, 2x9 = 18 coordinates. Everything else would be calculating if a block is inside on of these cuboid, EG: the two locations in the cuboid. My problem is if I know where the uppermost left block is no problem, but what if I want to start from S2 instead of S1? Im sure many people have created such algorithms, is there a better more optimized version of my idea?
     
  2. A good way to know if a certain point is within a polygon, is by taking your point, going in any fixed direction from there, and seeing how many times you cross the border of your polygon. An even amount of times means your point is outside the polygon.
     
  3. Oh that's quite a nice way to do it, never thought about it like that. So the Idea here would be to store all blocks along the edge of a region. Also solves the problem I had with a starting point. How does this scale to 3D? And what would be a good way to make this usefull in the entire minecraft world without limiting the region size tremendously. I'd have to check if there is some region within a certain distance maybe, or bind the regions to a chunk, which would mean I have to limit the regions to a chunk right? Any thoughts?
     
  4. Thanks, still I am wondering how would I prevent looping from -worldborder to +worldborder. When should I stop checking and just assume the block is outside, and not mistakenly stop if there is a face to pass... I believe I shouldnt check diagonally, since the is a possibility I skip a corner, right? It also seems to me that when scaling this to a third dimension the gain from cuboids, still just two XYZ points to check "<" and ">" for, vs a N^3 increase in "borderblocks" to store wouldn't be worth it.

    I feel like I am getting stuck in optimizing code vs memory...
     
  5. if your regions are always made up of cuboids dont bother with this algorithm. just store the corners of each of the cuboids that make up the region. psuedo code for getting the region at a location
    Code (Text):
    public Region getRegionAtLocation(Location location) {
        for every region:
            for each of the cubes that make up the region:
                if the location is in between the the corners of the cube:
                    return the region
    }
    if the regions are not necessarily cuboids, then you can use the ray intersection algorithm but you dont need to physically shoot a ray to infinity waiting for it to pass through faces. you can find intersections between the ray and the faces by representing the ray with a line and representing the faces with planes then using the 3D equations of lines/planes to calculate the intersection points. youll have to verify the intersection is actually valid because planes are infinite and polyhedron faces are not. psuedo code for getting the region at a location:
    Code (Text):
    public Region getRegionAtLocation(Location location) {
        for every region:
            intersectedFaces = 0
            for each of the planes that make up the region:
                if the line intersects the plane:
                    intersectedFaces++
             if intersectedFaces % 2 == 1:
                 return the region
    }