Resource Was block placed by player?

Discussion in 'Spigot Plugin Development' started by Iwitrag, Jun 25, 2018.

  1. EDIT: I have marked this as Resource, because this topic contains very useful and informative post from user jetp250.



    Hello community,

    how can I determine whether the block was placed by player OR naturally generated?
    Is this information stored somewhere?

    If not - then I could probably store it into Metadata

    BUT

    metadata does not persist between server restart.

    So what is the usual approach?
     
    #1 Iwitrag, Jun 25, 2018
    Last edited: Jun 27, 2019
  2. Well, you could always store the blocks in hashmap or arraylist and check when they are broken to remove the,. Although this will lag for sure when it gets into the thousand range or even hundreds not sure.

    I’m not entirely sure if you can add NBT data to a block, don’t see why you couldn’t though, so I would recommend doing that.
     
  3. You'll have a slower response time, but it might be more efficient to use hashcodes.
    Hash codes solely exist to check if one thing is another in the smallest space possible. Basically, you hash something and you get an output. Unfortunately, you can't get the original object from a hash code, however, if you have a hash code and another object, if that object's hash code is equal to your hash code, then the object from that hash code is effectively equal to your current object. (basically, it's like object.equals(secondObject), but you only have an identifier instead of objects). Hashcodes are small, fast, and efficient, so a use case like this would be perfect.
    Something like this should work:
    Code (Java):
    private static List<Integer> playerPlacedBlocks = getPlugin().getConfig().getIntegerList("blockPlaced");

    @EventHandler
    public void onPlace(BlockPlaceEvent event) {
        Location location = event.getBlockPlaced().getLocation();
        Bukkit.getScheduler().runTaskAsynchronously(this, () -> {
            int hash = location.hashCode();
            if (!playerPlacedBlocks.contains(hash)) {
                playerPlacedBlocks.add(hash);
            }
        });
    }

    @EventHandler
    public void onBreak(BlockBreakEvent event) {
        Location location = event.getBlock().getLocation();
        Bukkit.getScheduler().runTaskAsynchronously(this, () -> {
            int hash = location.hashCode();
            if (playerPlacedBlocks.contains(hash)) {
                playerPlacedBlocks.remove(hash);
            }
        });
    }
    (make sure the list is where you save the file onDisable and not null, I'd also recommend a periodic runTaskTimerAsyncronously that saves the file in case of a crash).
    This'll probably be your best bet for storage space and performance.
    (Unless someone smarter than me makes a post, in which case listen to them)
     
  4. I just checked the code, and the only block that contains this data is leaves. For any other block you will have to store the data yourself, which is no easy feat because you will have to track literally every block for every possible type of movement (like if a player pushes a block with a piston, etc etc).
     
  5. TheJavaHacker

    Supporter

    Before doing anything with any blocks, why don't you check if the block DOESN'T have a specific metadata tag, and then if it doesn't, it was naturally generated and thus should not be broken/edited, whereas on block place, add a metadata tag to the block placed to represent that it WAS placed by a player, and then look for that specific tag when modifying the block.
     
  6. Yep that would lag a lot as you say.
    Maybe save meta when block is placed into file and when server restarts apply them?

    And about NBT - I though that non-standard NBT are removed after restart... and I'm not pretty sure if NBT can be applied on blocks. I know that TileEntities are possible, but not sure about blocks though.

    This solution is good, but it's still utilizing large List of HashCodes which is not very efficient. I really want to use metadata or something similar efficient.

    I don't understand it either. ^^ :D


    Yep, thats the problem too... :/ I will probably set mob-griefing to false to make things easier a bit

    That's literally what we are talking about all the time.

    ---

    So temporary solution can be like this:
    1a. Player places block, apply metadata 'wasPlaced' to it and store the block inside the file.
    1b. Player removes block, remove metadata 'wasPlaced' from it and remove the block from the file.
    1c. Block moves somehow, like piston, shift metadata and do the same inside the file.
    2. If we want to check whether the block was placed, we just check for 'wasPlaced' metadata
    3. When server is shutting down we do nothing special, because all blocks are stored inside the file
    4. When server is starting, we load all blocks from file and apply metadata to blocks, this could take a while
     
  7. Hmm, you could actually "divide" my idea into sectors if you wanted to.
    Instead of storing each block in an a single list, it may be possible to store them separately by different worlds, quadrants, or (as I was thinking about that ChunkSnapshot thing from before), per chunk. Although this may take more time, as long as you store it as binary through an Object Output Stream instead of a JSON or YAML file, your response times will once again drastically improve (as a list of integers is relatively simple of an object, and 100% serializable as is). That way, you could simply open up an async task on (regrettably) a few dozen events, and then within find the stored list based on a name correlating with the chunk ID or some sort, then seeing if the hash code is contained or not in that list and doing as you will with it, before re-saving it.
    While this would be slower, that way you wouldn't have all the blocks loaded into memory all the time, just having a minor increase in response time, which depending on what you're trying to do, might not matter.
    The reason I'd advise against metadata is you'll end up taking basically the same amount of memory space anyway (just based on how metadata works), and I don't believe adding and reading metadata is thread safe, whereas Files and hash codes are completely thread safe.
     
    • Useful Useful x 1
  8. Why would this lag? I currently store hundreds of thousands of blocks this way, and act on the map every single time a block is broken or clicked at all. It isn't laggy. There's next to no resource drag. HashMaps have constant time complexity for get() and containskey(). The time it takes to use those methods doesn't reallyyyy change based on how many entries there are in the map. It's literally nonsensical to say that only hundreds would "lag for sure", I mean it's not like the server isn't doing MUCH MUCH more with every single block. It'd be unnoticeable and negligible. You could even optimize it unnecessarily by doing it on a chunk by chunk basis and mapping/unmapping it on chunk load/unload. But really though, the only difficulty in this is tracking every single way a block could change. Piston extend event, figuring out if any of the blocks moved are "placed", then moving the location stored alongside those blocks, piston retract event doing the same thing, entity explode- removing blocks destroyed...
     
  9. I understand this, however, the desire to be as light on the system as possible is strong. If there's a better way of doing it, sometimes you can't help but want to do it that way.
     
  10. The way I personally do it is I have a basic dumbed down location object. Stores x/y/z as integer values, and a World reference. Equals and hashcode methods are overridden to correspond to the internal values. These objects, from what I know, should take up no more than 30 bytes or so each object. I've stress tested my system, it takes roughly 40 miliseconds create 50 million of these objects (without retaining a reference so JVM subsequently garbage collects the hell out of them). I use them as keys in a HashMap, each mapped to their structure object. Whenever an action is done that requires looking up if a block is associated with a structure object, I just do thehashmap.contains(new DumbLocation(x, y, z, world)), the constant time get() and contains() are pretty noice. And there isn't a whole lot of overhead in making a few of these every now and then to use, as you see with the 50 million stress test. At 30 bytes each, an entire chunk worth of these being mapped should only eat up what, 2 megabytes?

    Maybe it isn't the most efficient way of doing it but really? Hell, not everything needs to be over-optimized and future-proofed. There isn't a single implementation I can think of that would put serious stress on any system that's been built in the past 10 years. If it can't handle 2 megabytes per chunk assuming every.single.block. in that chunk is player placed, there's bigger problems on your hands. Unless you actively try to kill your system, in which case anything will do that- don't make 50 million objects every time a player breaks a block, 1 should be fine :^)
     
  11. I appreciate the effort you spent making this post. I really do. However, I must point out why this answer is not the optimal answer, and I'll try my best to explain why, and to offer a better solution.

    First, the collection type: You're using a List<Integer>, with a contains() call. Lists are useful when you want your information to be ordered with no performance penalty and/or want to be able to access your elements by the index, which is an ability that Sets and Maps do not offer. However, since Lists do not take advantage of hashing (unlike HashMaps, HashSets and the like), a list's .contains() method's time complexity is O(n), aka linear. This means it may take at worst n iterations to find the desired element, n being the size of the list. Therefore, especially in a large collection that we're dealing with here, the amount of iterations quickly grows into crazy numbers of useless comparison tests, which is really bad; especially when that can be avoided.
    Another thing a lot of people don't likely pay attention to is the fact that the ints are auto-boxed into Integers (we have a List<Integer> instead of List<int>), which itself introduces some memory overhead, but generally negligible.

    Then, about your use of hashCode: the idea was good, but the way you implemented it does actually not make the best use of hash code, and unfortunately does not lead to the expected performance.

    Let's start from here:
    "basically, it's like object.equals(secondObject), but you only have an identifier instead of objects"

    Pretty much true, but let's take a look at the general contract of hashCode:
    "The general contract of hashCode is:

    • Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
    • If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
    • It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables."
    And while the hashCode() implementations are often designed to produce the least possible amount of collisions, they still happen. The larger the hash collection, the more collisions you will have, albeit with a good hash the number is hopefully pretty low. (There are exceptions; e.g. Integer.hashCode() returns itself and can obviously does not have collisions). .equals() is preferred when comparing equality, or == for constant values (enums, contants).


    Why this is important is, because, with the way you did it; if a hash collision occurred, the blocks at two different locations would be treated as the same. Let's say we have two blocks that have colliding hash codes, A and B. If the block A is placed by player, and so added to the List; when the block B is checked to be player-placed, it will incorrectly return true, because the hash code is in the List already.
    Hash collections deal with this by ensuring the equality with == and .equals() and doing some unfortunate iterations to find the correct element (this is why hash collisions decrease performance and are very important to try to avoid), but that won't work with a plain list like this. Therefore, unfortunately, this idea will not work.

    Another thing. You said that hash codes are fast & efficient and small: however, you're not essentially taking the advantage of that here. Right now, the results would be the same if instead of the hash code you just stored the Block itself (that would in fact fix the hash collision bug). A good use of hash codes for a compact collection can be seen in the implementation of Maps. Instead of checking for the existence of the element, it takes a hash code and converts it to an array index (Maps use an array behind the hood; even HashMap even though the elements are chained). This is also why Maps (and thus Sets) accept no duplicate elements: if a mapping is found at the index fetched from the hash, at the event of a put() operation, it is overridden.

    However, you were right that hash codes are a good and efficient solution to this problem. In fact, we'll likely want to use either a Map or a Set, because those are often already hash-based collections, have an O(1) add(), remove() and contains() operations in terms of time complexity, and accept no duplicates which is exactly what we want. Already existing implementations are also proven to be functional and efficient, so there's no reason for us to re-invent the wheel and do it all over.



    Now, Map or Set?
    Sets (in Java) are almost always backed by a Map (HashSet uses a HashMap internally, LinkedHashSet uses a LinkedHashMap and so on), and so the performance is the same. It's up to our needs; if we want to also store the player(/uuid) who placed the block, we could use a Map<K, Player>. Otherwise, if we just want to know if the block is player-placed but don't care about additional information, a Set will do just fine. Memory-wise: Map-backed Sets generally store a shared dummy object as the value so there's generally 8 bytes of "wasted" memory per insertion. Were you to use a Map, it's likely the same deal: if you f.e the player UUID as the value, you're not actually creating a new object but just point to an existing object, so the same 8-byte overhead applies.

    Unless I know I want to map additional information with the block, I'd go with a Set. This can be quickly and easily changed later on if need be, anyways.

    Now, we could use a standard HashSet (or HashMap if you're going with Maps), but let's first take a moment to think what exactly do we want to store.
    The Block instance? That seems a bit unnecessary, and with a Map it'd be inconvenient to fetch the mapped value because we'd have to get the block from the world each time. It would also have to resort to the Block.equals() call when comparing the equality. This isn't a bad thing since a Block consists from a World and 3 ints, and while it does compare the world (albeit lastly, fortunately), the worlds.equals() is fortunately also very cheap since it only compares the UUIDs.

    -- Edit for future readers: avoid using Location as the key, as the coordinates are stored as doubles. You wouldn't want to call .get() with non-integer coordinates so Location is not a fitting choice, plus it's more likely to suffer from floating-point inaccuracies. Location objects are also about 40-48 bytes each which is quite a bit for every single key!


    But, we could take it further, so let's science it out.
    A long has 64 bits. The world height is 255 blocks (technically 256 I guess, but you can't place a block at Y=256), aka 0xFF, which is 8 bits.
    After reserving the eight bits to the Y coordinate, we're left with 64-8=56 bits for X and Z, meaning 28 bits for each. 28 bits is 268 435 455 blocks total, so 134 217 727 in both directions from the world origin. The Minecraft world is 30mill^2 blocks, so this is more than enough for our needs. With an integer we'd only have 12 bits, which is merely 2047 blocks in both directions so we'll have to use a long.

    The order in which we store the coordinates does not matter, but I chose to store them in Y, X, Z order. This means that the first 28 bits (reading from the right) are for Z, next 28 are for X and last 8 are for the Y.
    Combining them in this order can be done as follows; '0xFFFFFFF' is a 28 bit integer:
    Code (Java):
    long combined = (((long) y) << 56) | ((x & 0xFFFFFFFL) << 28) | (z & 0xFFFFFFFL);
    Now, Spigot comes with FastUtil. FastUtil extends the java collections with, for example, primitive collections, including a long map and set.
    If you're going with a Set, I'd use a LongOpenHashSet; if you're going with a Map, I'd use Long2ObjectOpenHashMap.

    So, I'd end up with something like this:

    Code (Java):
    private final LongSet playerPlaced = new LongOpenHashSet();

    @EventHandler
    private void onBlockPlace(BlockPlaceEvent event) {
        playerPlaced.add(getLongKey(event.getBlock()));
    }

    @EventHandler
    private void onBlockBreak(BlockBreakEvent event) {
        playerPlaced.remove(getLongKey(event.getBlock()));
    }

    private static long getLongKey(Block block) {
        long combined = 0L;
        combined |= block.getY() << 56;
        combined |= (block.getX() & 0xFFFFFFFL) << 28;
        combined |= (block.getZ() & 0xFFFFFFFL) << 0;
        return combined;
    }
    Or with a Map:
    Code (Java):
    private final LongMap<UUID> playerPlaced = new Long2ObjectOpenHashMap<>();

    @EventHandler
    private void onBlockPlace(BlockPlaceEvent event) {
        long key = getLongKey(event.getBlock());
        playerPlaced.put(key, event.getPlayer().getUniqueId());
    }

    @EventHandler
    private void onBlockBreak(BlockBreakEvent event) {
        playerPlaced.remove(getLongKey(event.getBlock()));
    }
    Then, of course, you should account stuff like fire that burns wood, leaves that decay, and sand/gravel that might fall to a spot where a player-placed block burned/decayed, and probably other stuff like that.
     
    #13 jetp250, Jun 25, 2018
    Last edited: Jul 31, 2020
    • Winner Winner x 3
    • Informative Informative x 3
    • Like Like x 2
    • Agree Agree x 1
  12. @jetp250 Thank you a lot for your informative and very useful answer *claps hands*
     
  13. I'm... floored. That's an above and beyond explanation.
    Thank you from the bottom of my heart for this reply, even if it isn't my question or thread, because I still was able to learn from it.
     
  14. I'm not very experienced when working with bits so I have made a simple program which explained to me what was happening...

    I just changed
    (x & 0xFFFFFFFL << 28)
    to
    ((x & 0xFFFFFFFL) << 28)
    because bitwise shift has higher priority than bitwise and

    Code (Text):
    y = [32b] 00000000000000000000000001101111 (111)
    x = [32b] 00001100110101111100100101111011 (215468411)
    z = [32b] 00001011110110001101000000001111 (198758415)

    (long) y
    [64b] 0000000000000000000000000000000000000000000000000000000001101111 (111)
    (long) y << 56
    [64b] 0110111100000000000000000000000000000000000000000000000000000000 (7998392938210000896)

    0xFFFFFFF
    [32b] 00001111111111111111111111111111 (268435455)
    0xFFFFFFFL
    [64b] 0000000000000000000000000000000000001111111111111111111111111111 (268435455)
    x implicitly cast to long
    [64b] 0000000000000000000000000000000000001100110101111100100101111011 (215468411)
    x & 0xFFFFFFFL
    [64b] 0000000000000000000000000000000000001100110101111100100101111011 (215468411)
    (x & 0xFFFFFFFL) << 28
    [64b] 0000000011001101011111001001011110110000000000000000000000000000 (57839361160380416)

    0xFFFFFFFL
    [64b] 0000000000000000000000000000000000001111111111111111111111111111 (268435455)
    z implicitly cast to long
    [64b] 0000000000000000000000000000000000001011110110001101000000001111 (198758415)
    z & 0xFFFFFFFL
    [64b] 0000000000000000000000000000000000001011110110001101000000001111 (198758415)

    ((long) y << 56)
    [64b] 0110111100000000000000000000000000000000000000000000000000000000 (7998392938210000896)
    ((long) y << 56) | ((x & 0xFFFFFFFL) << 28)
    [64b] 0110111111001101011111001001011110110000000000000000000000000000 (8056232299370381312)
    ((long) y << 56) | ((x & 0xFFFFFFFL) << 28) | (z & 0xFFFFFFFL)
    [64b] 0110111111001101011111001001011110111011110110001101000000001111 (8056232299569139727)
    (I have assumed that X and Z are not longer than 28 bit so that AND with masks are not neccessary)