1.16.5 Spiral Pattern algorithm

Discussion in 'Spigot Plugin Development' started by Peaches_MLG, Feb 6, 2021.

Thread Status:
Not open for further replies.
  1. For my skyblock plugin, the islands are generated in a spiral pattern. and I need a way to get the islands center via the island id.

    They generate in a spiral pattern like such

    9 2 3
    8 1 4
    7 6 5

    I need an algorithm that given the island id gives me the coords. e.g.
    1 would return 0,0
    2 would return 0, 1
    3 would return 1,1
    ect

    currently I have
    Code (Java):
        public Location getCenter(World world) {
            //TODO improve and optimise this
            int x = 0;
            int z = 0;

            int length = 1;
            int current = 0;
            Direction direction = Direction.NORTH;

            for (int i = 1; i < id; i++) {

                switch (direction) {
                    case NORTH:
                        z++;
                        break;
                    case EAST:
                        x++;
                        break;
                    case SOUTH:
                        z--;
                        break;
                    case WEST:
                        x--;
                        break;
                }

                current++;

                if (current == length) {
                    current = 0;
                    direction = direction.next();
                    if (direction == Direction.SOUTH || direction == Direction.NORTH) {
                        length++;
                    }
                }
            }
            return new Location(world, x * IridiumSkyblock.getInstance().getConfiguration().distance, 0, z * IridiumSkyblock.getInstance().getConfiguration().distance);
        }

    But this is super inefficient, does anyone know a more mathematical approach to this?
     
  2. You can get a spiral using a 3 parametric equations:

    x= radius * sin(t)
    z=radius * cos(t)
    y = h * t where h is used to make the spiral be stretched out in the y axis

    you can create an equation to get a value of t given the island id, and you also need a special case for your center island.
     
  3. that would be a circular spiral though would it not, im not sure how well that would convert to a square one
     
  4. Optimizing this is quite easy. Edit: Well I think the following is easy at least ;)

    First you calculate all this with ID = yourID - 1


    That means its starting with 0 and number 8 is the 9th plot.
    To get the coordinates from the ID, you first want to see which side length the outer square has.

    So you use the square root (sqrt) of the ID to continue.

    For example for the ID 17 it would be 4.123...
    Now you cast that number to an int (this rounds the number always down).
    In the example you have 4 now.
    Next up is that you check if the number is odd or even (number % 2 == 0 means even), as your squares have all odd side lengths.
    If the number is odd, it is the side length of the biggest completely filled square.
    If the number is even, subtract 1 to get the side length of the biggest completely filled square.
    (If you add two to the number you get the current square side length to be filled.)

    In this case we get 3 as biggest full square.

    The highest ID of the biggest full square is sidelength*sidelength - 1

    The max coordinate distance of the biggest full square is (biggest full square side length - 1) / 2.

    You can calculate the coordinates of the plot with highest ID of the biggest full square now like this:

    1. coordinate = 1 - max coordinate distance
    2. coordinate = max coordinate distance

    Now you got the ID, length and coordinates of the plot with highest ID of the biggest full square.
    You can now continue with your own, greedy algorithm with the calculated parameters as start values.

    You can also improve your greedy algorithm by not going one by one forward, but check if current ID to target ID difference is less than a side length and just add the diff to the correct coordinate.
    If the difference is bigger than side length, you can add side length to the current id and correct coordinate, change the direction and go on.
     
Thread Status:
Not open for further replies.