Solved Flood-fill algorithm not reaching an end

Discussion in 'Plugin Development' started by OzeroDamyx, Sep 2, 2019.

  1. Offline

    OzeroDamyx

    Hi guys, i recently started a server with some friends and decided to make use of my Java knowledge.
    I'll make it quick.. i was trying to do a plugin capable of planting crops in the area adjacent to the hand-planted one, so i thought a 4-ways flood-fill algorithm could work, and it probably does, but for some reason it just doesn't stop, it keeps going on quickly getting my cpu to 100% usage.

    This is the code i'm using:
    Code:
    EDIT: solved
    
    Note that i preferred to use a queue instead of a recursive implementation because of java limited stack capacity.
    I don't know why it's not stopping, theoretically once it starts encountering blocks that aren't farmland or that are covered by something else, it shouldn't add more blocks to the queue, but it just keeps going.
    I can't provide an error log because there are no errors, it just keeps going on.
    Also, if you search for the flood-fill algorithm you'll notice that: in the floodFill method there are some checks before the queue thing, but i skipped them because if the player plants a crop and the event is not cancelled, then i already know that the first blockBelow is farmland, while the others need to be checked.


    My question is, am i doing something wrong on the java end, or is there some bukkit knowledge i'm missing?
     
    Last edited: Sep 2, 2019
  2. Offline

    timtower Moderator Moderator

    @OzeroDamyx You are adding the block back to the queue, also if you didn't change it.
     
  3. Offline

    OzeroDamyx

    Waaaaait, how am i adding it back? I only do queue.remove() and then.. oh wait, maybe i got it, i'll try one thing

    EDIT
    I got it working, ty sir, i didn't notice i kept adding back the same blocks, it was basically looping on them
     
    Last edited: Sep 2, 2019
    timtower likes this.
  4. Offline

    timtower Moderator Moderator

    I use a similar mechanic in one of my plugins so I know the big pitfalls :p
     
    OzeroDamyx likes this.
  5. Offline

    OzeroDamyx

    Ehy sorry if i reopen this, i'll leave the solved tag as it's not really a problem that needs a solution, i was just experimenting.
    I thought about adding the possibility to use area-of-effect bonemeal with the same code but i can't find the right method to do it.
    In this thread https://bukkit.org/threads/apply-bonemeal-effect-programmatically.63470/ the op uses a function from net.minecraft.server which for some reason i cant import. In my pom.xml i added as dependencies both bukkit and spigot-api, is there anything i'm missing?
    Code:
    @EventHandler
        public void onBoneMealUsage(PlayerInteractEvent event) {
            if (this.enabled) {
                if (event.getAction() == Action.RIGHT_CLICK_BLOCK && event.getMaterial() == Material.BONE_MEAL) {
                    Block clickedBlock = event.getClickedBlock();
                    if (canBeBoneMealed(clickedBlock)) {
                        aoeBoneMeal(clickedBlock);
                    }
                }
            }
        }
    
        private void aoeBoneMeal(Block block) {
            Queue<Block> queue = new LinkedList<Block>();
            queue.add(block.getRelative(BlockFace.EAST));
            queue.add(block.getRelative(BlockFace.WEST));
            queue.add(block.getRelative(BlockFace.SOUTH));
            queue.add(block.getRelative(BlockFace.NORTH));
            while (!queue.isEmpty()) {
                block = queue.remove();
                if (canBeBoneMealed(block)) {
                    //must add checks to avoid loops
                    useBoneMeal(block);
                    queue.add(block.getRelative(BlockFace.EAST));
                    queue.add(block.getRelative(BlockFace.WEST));
                    queue.add(block.getRelative(BlockFace.SOUTH));
                    queue.add(block.getRelative(BlockFace.NORTH));
                }
            }
        }
    
        private void useBoneMeal(Block block) {
            //?????
        }
     

Share This Page