How to get a random discrete point in a circular or ellipsoid spawn region in Minecraft?

Question

After writing my first random-spawn plugin for Minecraft, I immediately wanted to upgrade to allowing circular and ellipsoid spawn regions to act as the limited spawn region to select the random points from.

Getting two random numbers in a given range and then rounding them to the nearest integer produces a rectangular area on the cartesian plane with discrete points every unit, effectively.

That looks like this:

// in Util.java
// get a random whole number in range
public static int getRandomNumber(int min, int max) {
    return (int) ((Math.random() * (max - min)) + min);
}

// in the class that controls spawning
// get random x, z co-coordinates within range; refer to the *center* of blocks
double tryLocation_x = Math.rint(Util.getRandomNumber((int)min_x, (int)max_x)) + 0.5;
double tryLocation_z = Math.rint(Util.getRandomNumber((int)min_z, (int)max_z)) + 0.5;

But how to integrate an effective ellipsoid area as the limiting range for these discrete points?

We need to add something that allows us to ignore randomly generated numbers that would appear outside an ellipse defined by radius_X, radius_Z. This is because as discussed, coordinates generated this way produce an effective rectangular area of valid discrete points.

After a lot of research and asking around, I finally found an easy solution that does not significantly affect performance relative to regular rectangular spawn areas.

Let me explain.

Answer 1

The most difficult information for me to come across that is absolutely required for this solution is the following:

public static int isInEllipse(int h, int k, int x, int y, int a, int b) {
    // h, k are center point | x, y are co-ords to check | a, b are ellipse radii
    int p = ((int)Math.pow((x - h), 2) / (int)Math.pow(a, 2))
            + ((int)Math.pow((y - k), 2) / (int)Math.pow(b, 2));

    return p;
}

Ellipses are defined by their two radii; the short and the long radius. However, again as said before, the two randomly generated numbers can produce discrete points outside, inside, as well as on-top of the ellipse circumference.

This above method isInEllipse will return less than 1 if the coordinates are within the ellipse and 1 when it is on the circumference. Otherwise they are outside the ellipse.

---

Ok so now we have a way to check our random coordinates for validity in our defined ellipse. Let's put it to work.

// get random x, z co-coordinates within range; refer to the *center* of blocks
double tryLocation_x = Math.rint(Util.getRandomNumber((int)radius_X*-1, (int)radius_X)) + 0.5;
double tryLocation_z = Math.rint(Util.getRandomNumber((int)radius_Z*-1, (int)radius_Z)) + 0.5;
int ellipseCheck = Util.isInEllipse(0, 0, (int)tryLocation_x, (int)tryLocation_z, (int)radius_X, (int)radius_Z);

Ok great. Now we have a way to create random coordinates and then check them for whether they are within the defined ellipse area.

With that, we can proceed to loop this check until valid coordinates are found:

final double spawnLoc_x;
final double spawnLoc_z;

boolean isValidRespawn = false;
while (!isValidRespawn) {
    double tryLocation_x = Math.rint(Util.getRandomNumber((int)radius_X*-1, (int)radius_X)) + 0.5;
    double tryLocation_z = Math.rint(Util.getRandomNumber((int)radius_Z*-1, (int)radius_Z)) + 0.5;
    int ellipseCheck = Util.isInEllipse(0, 0, (int)tryLocation_x, (int)tryLocation_z, (int)radius_X, (int)radius_Z);
    
    if (ellipseCheck > 1) continue;
    else isValidRespawn = true;

    spawnLoc_x = tryLocation_x;
    spawnLoc_z = tryLocation_z;
}

You can now mutate the player's respawn location object with the coordinates you get from this. As for the Y value, you can use World.gethighestBlockAt(int x, int z) to keep it simple.

I spent many hours searching for this answer. It's my hope that this post will help many peeps get to this solution. Cheers!

Reference: https://www.geeksforgeeks.org/check-if-a-point-is-inside-outside-or-on-the-ellipse/