Solved Two-Dimensional Area

Discussion in 'Spigot Plugin Development' started by ExoBiTe, Apr 15, 2017.

  1. Hello
    While playing around with a bit of locations/vectors i made myself a way to create Shapes with unlimited corners/sides.
    Now i want to get a List<Location> filled with every Block -Location inside my created Area.
    For example i want to get the Location of every Block inside the gold Blocks:
    [​IMG]
    I create the Shape using a List<Location> of all the outline Locations. But i have no idea how to get all Blocks inside. I first thought about getting the max and min x and z of the corners and then do something like this:
    Code (Text):
               int maxx;
                int minx;
                int maxz;
                int minz;
                int area = (maxx-minx) * (maxz-minz);
    But i think this wont work with a shape like this:
    [​IMG]

    It would be cool if someones has an idea and he/she is nice enough to tell it to me :)
    Thanks!
     
  2. I'm not a developer, but I used World Edit a lot. Obviously World Edit is squares and boxes, but could you possibly make the plugin detect the outline of the gold blocks, and only count the ones inside it on a flat plain?
     
    • Like Like x 1
  3. Thats a nice idea... or at least a beginning. I could try to get the length of both sides and then count every block inside the gold blocks and then move one row over to the next.
     
  4. Without having to put math and complex algorithms into the equation (no pun intended) i'd say get an imaginary rectangle that fills the area getting the max x, y, z and then loop for all block and dispose of the ones off
     
  5. Could you explain this a bit further to me? I wasn´t the best in Geometry/Math in school.

    btw.
    this ^ doesn´t work.
     
  6. This might be a bit server intensive,depending on how big the shape is, but you could choose a point you know is inside the shape, and expand out in blocks until it hits a block on the outer edge, and put the location in the list the placed blocks, until it gets all blocks in the shape. Almost as if you put a water source in a smaller shape, it would fill it up. This would not work with self-intersecting shapes though.
     
  7. Thats also a good idea, and it wouldn´t use much performance as i could do this on an async thread, but it isn´t as flexible as i want it do be. :/
     
  8. Good point with the async thread. What else do you need it to do? (There's no need to place the blocks inside the shape, that's more of a visual to see if it gets all blocks in testing phases)
     
  9. Yes, the block-placing is just for testing purposes. I just want to create a List with all Locations/xyz in it.
    Later i just want to iterate through this list, but nothing really performance-needing.
     
  10. Feels kinda like a pathfinding problem to me. Just create a square using min/max X/Z. For each non-gold block in this square (preferably in random order), do a search and try if you can escape the square. If you can, continue with a new block. If you cannot, all blocks that were used in this depth first search are the blocks you are looking for. Important; keep track of which blocks were used in previous searches to prevent doing duplicate work.

    For example, pick a random block within your shape and get something like this. The example is made using https://qiao.github.io/PathFinding.js/visual/ and uses Dijkstra, but the idea of visualization is somewhat equivalent for any pathfinding algorithm. The blue blocks are the searched blocks and are what I believe you are looking for.
    [​IMG]

    Now assume the red block in the image to be your "escape" (e.g. the block is outside your square). If the randomly chosen point is outside your shape, you manage to "escape", which looks something like this. When this happens, pick a new random block and retry. What I meant with "keep track of which blocks were used in previous searches to prevent doing duplicate work", was that you should not use any of the searched area (blue at the end) as a new starting point for a next search.
    [​IMG]

    I hope I did not make this too complicated, and I hope this helps you finding a efficient solution.

    Kind regards,
    Sander.
     
    • Agree Agree x 2
    • Winner Winner x 1
    • Informative Informative x 1
  11. (Aside from the 'escape' block, which is a good idea) That's basically what I was thinking of. I like the visuals too, by the way.
     
  12. Thats a nice idea (as its nearly the same than @RubbaBoy said), but this pathfinding processes wont work with shapes like (for example) this.
    [​IMG]
     
  13. There is not just one escape block. All blocks that are outside the square (found by finding min/max X and Z) are "escape blocks", but I couldn't find a way to add multiple target blocks on that website.

    For the problem you just showed in the image, you are right. But you could simply continue until you have gone over every block at least ones. Then combine the results of the multiple different searches.
     
  14. You could have a block or two 'buffer' outside of the pathfinding edge, to detect if there's a 2 block thick wall, and start again from the space after, but I'm not sure how that would work in practice, as the turns usually have 2 block thick areas in them. The method @ExoBiTe has for creating the shapes might not even be capable of creating such shapes, so that might be worth finding out.
     
  15. I got another idea, inspired by your ideas.
    [​IMG]

    I could just place the start-point outside on the outside of the shape (the inner rings are my shape ingame) and tell the pathfinding to not go further away from the shape than 2 blocks (which are the outer lines here). So the pathfinding shoud find all the blocks outside and subtract the amount from the amount of the whole area. This should return me the inner area.
     
    #15 ExoBiTe, Apr 16, 2017
    Last edited: Apr 16, 2017
  16. I don't see why that wouldn't work, except if you don't want to include the outer outline, because sometimes there's double blocks when there are curves, or slight turns like bottom right, and some other places in the image you posted.
     
  17. Quite smart to tackle the problem of multiple areas by simply making the outer square 2 blocks bigger, I like it!

    By the way, we call it a "path finding", but no difficult or highly efficient pathfinding algorithm is needed here I think, just use something like a breath first search.
     
  18. Strahan

    Benefactor

    Hmm I'm having trouble with pathfinding for this one

    [​IMG]

    lol
     
    • Like Like x 2
    • Funny Funny x 1
    • Creative Creative x 1
  19. FrostedSnowman

    Resource Staff

    kek
     
  20. No the outer line is just drawn to show you what i mean.

    I think i just will expand the start location into all four directions until it hits a wall.
     
    • Like Like x 1