1.15.2 Fastest way of checking if a player is inside a "custom region"

Discussion in 'Spigot Plugin Development' started by Xuho, Jan 13, 2020.

  1. I'm working on a protection system based on a central location (like the typical protection stone plugin) but I can't find the best way (less laggy method) to check if a block is inside of one of those regions (there will be thousands of regions).
    Right now I iterate through all the regions to check if the block is in any of them but I don't think it's a very efficient method.

    Also I store all the regions on a yml file and when the server starts I load them in a custom object and I save them periodically. (Any ideas of how to improve this?)

    Note: I only store the central location of the region, not the corners (I calculate them)
     
    #1 Xuho, Jan 13, 2020
    Last edited: Jan 13, 2020
  2. Suppose your region is defined by the corners of it, meaning the region is defined by the two vectors (x1, y1, z1) and (x2, y2, z2) that define the cube this region lives in. You can test if anything that you can access the location of is inside that region by simple comparison:
    Code (Java):
    final Location location = something.getLocation();
    final double x = location.getX();
    final double y = location.getY();
    final double z = location.getZ();
    if ((x > x1 && x < x2) &&
        (y > y1 && y < y2) &&
        (z > z1 && z < z2)) {
        // location is inside the boundary
    }
     
    • Like Like x 1
    • Agree Agree x 1
  3. Yes, right now I do that but imagine if there are 10.000 regions, I would have to do that check with all the regions every time I want to know if a block is inside a region.
     
  4. That still wouldn't be too heavy.
     
  5. But that method will be called hundreds of times per second as this is for a protection plugin
     
  6. Load all regions in Enable process and add new when player create region.

    Something like

    Code (Text):
    public class Region {
    private double corner1X;
    private double corner2X;
    private double corner1Y;
    private double corner2Y;
    private double corner1Z;
    private double corner2Z;
    //else what you need at region settings

    public Region(double corner1X, ... double corner2Z){
    this.corner1X=corner1X
    ...
    }
    }

    /* getting and also */
     
    and in Events what you wanna check in regions - check if block by Coordinates is between corners coordinate. You must think about math how that must calculate, i think that method doesn`t get a lot of memory but if in server will play a lot of players that must be very good host

    Sorry for my english i wanna help
     
    • Agree Agree x 1
  7. Make a Region class, add a method to calculate if a certain location is inside this region (let's call it #contains). Then let's say you have a Set of Region (let's call it regions). What you would do then is use the stream API and #anyMatch
    Code (Java):
    if (regions.stream().anyMatch(region -> region.contains(location)) {
        //One or more of the regions have this location
    }
     
    • Agree Agree x 5
  8. Why not do it on an event basis then? I assume this is for protection, so listen for BlockBreakEvent.
     
  9. Yes I already do that, but with my playerbase that method will be called thousands of times per second. on a BlockBreakEvent for example.
     
  10. What are the advantages of doing this over iterating through the list? Also, with this, how I would know which regions contains that block?
     
  11. It would iterate through until it finds 1 that matches, then it stops.
    So if you have regions 0, 1, 2, 3, and region 2 has the block inside:
    Check region 0: false
    Check region 1: false
    Check region 2: true
    So it wouldn't check region 3.

    To actually get the found region, I'm thinking a foreach loop would be better.
     
  12. Okay, here's my solution to this problem. What you are lacking is something like a "global view" on the map. In other words, you can't check block.isRegion(). So you'll need to make your own "global map". In other words, you need a 2D-Array storing every block-position with the respective region in it.
    As you can easily imagine, this is inefficient. So there are 2 ways of making this more efficiently:

    1) Use a hash-function to reduce your problem. What I mean is instead of storing each region inside an array of blocks, store the regions that - let's say every chunk - contains. So if any block in a certain chunk contains a region, that region will be stored in that "chunk map". If that is still too small, use 32x32 big-areas or even bigger and store a set of regions in this area. For computational reasons, I recommend using sizes that are powers of 2.
    Now let's suppose you want to check for a certain block. You can find suitable regions for this block via a simple lookup in the array in O(1) - since you know the dimensions. Depending on the size, there are N or no regions. If there are no regions, you are done. If there are any regions, you need to iterate over these N regions in the way described above.

    If you wanted to further improve efficiency, you could make the size of the array variable. If the regions are very "packed", the array would contain close to only one block per entry. If the regions are far apart, the array would contain very big entries.

    2) Only put loaded chunks inside that map. If a chunk gets unloaded, remove it, if a chunk gets loaded, put it into the map.

    I hope I explained this somewhat understandable...
     
    • Funny Funny x 1
  13. Strahan

    Benefactor

    You have multiple thousands of players online simultaneously? If you have that kind of user base, you must have a hefty budget so rather than tinker with it why are you not just hiring a professional developer?
     
    • Agree Agree x 1
  14. 2D Array of all block positions...
    I mean... or you could do something sane.
    of course there would be the possibility to pack a block position in a long and use a Long2ObjectMap<Set<Region>> but thats just stupid.)
    Code (Java):
      public static long getBlockKey(int x, int y, int z) {
        return (long) x & 0x7FFFFFFL | ((long) z & 0x7FFFFFFL) << 27 | (long) y << 54;
      }
    We have cubes with nice uniform geometry.
    A protection system should always be based on vectors. Spigot already has a nice implementation for this: BoundingBox.
    A BB is defined by two vectors (lower and upper corner) and you can easily check if a Vector is inside this box.
    You just base your protection system on them and group them in chunks.

    The general data structure looks like this.

    WorldID > ChunkKey > set of Regions which run through the chunk
    Map<UUID, Map<Long, Set<Region>>>

    now just check if the set is empty. If not check every region inside the set and apply your actions.
    I implemented my protection like this and it takes only some micros per tick even with explosions, pistons, block break etc.

    PS: pls encapsulate the data structure in smaller pieces like:
    ProtectionHandler => Map<UUID, WorldProtectionDomain>
    WorldProtectionDomain => Map<Long, ChunkProtectionDomain>
    ChunkProtectionDomain => Set<ProtectedRegion>

    Or something like that.
     
    • Agree Agree x 1
  15. I believe what he wants is to avoid looping through all possible boxes.
    What I mean is not an array of blocks, but a hashed version of that, e.g. an Array of boxes of size 16x16 or 64x64. But each box is represented by one entry in the array. Those boxes could (obviously) contain more than one region, so here you'd have to iterate over a set of regions. This set of regions, however, is way smaller than the original one.
     
  16. I think your math is wrong there. Thousands of times per second, assuming that players are mining non stop, could be 1000 - 2000 players. Even without taking into account that your server is not only mining, 1000 players is a lot. You would have a large network seperating players between servers, so this issue would never be encountered.
    That too ^

    If he absolutely must, he could keep a List<Region> per world, but that wouldn't save him that many resources.

    My advice would be is implement the method however the first few posts highlighted, then run timings to see how your plugin actually affects your server. You'll probably find it's not as heavy as you think. (y)
     
    • Agree Agree x 1
  17. Meant that list of Regions, not boxes...

    But I agree. I find it unlikely to have a player-base that big.
    On the other hand, imagine just sweeping through a meadow that belongs to some region. You'd have to check for a fairly high number of block breaks. If every player did this and there were like 50 online, maybe you would notice something. But other than that, timing should probably not be a problem
     
  18. FrostedSnowman

    Resource Staff

    You’re over thinking this, there aren’t going to be thousands of block breaks happening on the same tick. I don’t believe you quite understand how many computations a computer can produce in what to us would be instantly—especially with simple arithmetic. Simply checking if the target locations coordinates are within the regions bounds will suffice.

    Simple iteration over a collection of regions will not be an issue either. A simple list for loop will be fine. The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.
     
    #18 FrostedSnowman, Jan 13, 2020
    Last edited: Jan 13, 2020
    • Agree Agree x 1
  19. md_5

    Administrator Developer

    WorldGuard itself did a simple loop for years and years
     
    • Agree Agree x 2
    • Like Like x 1
  20. Oh, I fully understand what computers are capable of.
    That being said, I was trying to make an extreme example that should prove your point, but it's probably not extreme enough.