Procedurally Generated Voronoi Roads

1

i'm using a noise function inspired by libnoiseforjava to try and generate roads. (See below)

public class VoronoiNoise {

private static final double SQRT_2 = 1.4142135623730950488;
private static final double SQRT_3 = 1.7320508075688772935;

private long seed;
private short distanceMethod;
private final double frequency;

public VoronoiNoise(long seed, double frequency, short distanceMethod) {
    this.seed = seed;
    this.distanceMethod = distanceMethod;
    this.frequency = frequency;
}

private double getDistance(double xDist, double zDist) {
    switch(distanceMethod) {
        case 0: //EUCLIDIAN - Length
            return Math.sqrt(xDist * xDist + zDist * zDist) / SQRT_2;
        case 1: //???
            return xDist + zDist;
        case 2: //???
            return Math.pow(Math.E, Math.sqrt(xDist * xDist + zDist * zDist) / SQRT_2)/Math.E;
        case 3: //MANHATTAN
            return Math.abs(xDist) + Math.abs(zDist);
        case 4: //CHEBYCHEV
            return Math.max(Math.abs(xDist), Math.abs(zDist));
        case 5: //MINKOVSKI
            return Math.pow(Math.pow(Math.abs(xDist), Math.PI) + Math.pow(Math.abs(zDist), Math.PI), (1 / Math.PI));
        case 6: //MINKOVSKI4
            return Math.pow(xDist*xDist*xDist*xDist+zDist*zDist*zDist*zDist,0.25);
        default:
            return 1.0;
    }
}

private double getDistance(double xDist, double yDist, double zDist) {
    switch(distanceMethod) {
        case 0:
            return Math.sqrt(xDist * xDist + yDist * yDist + zDist * zDist) / SQRT_3;
        case 1:
            return xDist + yDist + zDist;
        default:
            return 1.0;
    }
}

public short getDistanceMethod() {
    return distanceMethod;
}

public long getSeed() {
    return seed;
}

public double noise(double x, double z) {
    x *= frequency;
    z *= frequency;

    int xInt = (x > .0? (int)x: (int)x - 1);
    int zInt = (z > .0? (int)z: (int)z - 1);

    double minDist = 32000000.0;

    double xCandidate = 0;
    double zCandidate = 0;

    double xCandidate2 = 0;
    double zCandidate2 = 0;
    Random random = new Random(seed);
    long xSeed = random.nextLong();
    long zSeed = random.nextLong();

    for(int zCur = zInt - 2; zCur <= zInt + 2; zCur++) {
        for(int xCur = xInt - 2; xCur <= xInt + 2; xCur++) {

            double xPos = xCur + valueNoise2D(xCur, zCur, xSeed);
            double zPos = zCur + valueNoise2D(xCur, zCur, zSeed);
            double xDist = xPos - x;
            double zDist = zPos - z;
            double dist = xDist * xDist + zDist * zDist;

            if(dist < minDist) {
                xCandidate2 = xCandidate;
                zCandidate2 = zCandidate;
                xCandidate = xPos;
                zCandidate = zPos;
                minDist = dist;
            }
        }
    }

    double xDist = xCandidate - x;
    double zDist = zCandidate - z;

    //return getDistance(xDist, zDist);
    return getDistance(xCandidate2 - x, zCandidate2 - z) - getDistance(xCandidate - x, zCandidate - z);
}

public double noise(double x, double y, double z) {
    x *= frequency;
    y *= frequency;
    z *= frequency;

    int xInt = (x > .0? (int)x: (int)x - 1);
    int yInt = (y > .0? (int)y: (int)y - 1);
    int zInt = (z > .0? (int)z: (int)z - 1);

    double minDist = 32000000.0;

    double xCandidate = 0;
    double yCandidate = 0;
    double zCandidate = 0;

    Random rand = new Random(seed);

    for(int zCur = zInt - 2; zCur <= zInt + 2; zCur++) {
        for(int yCur = yInt - 2; yCur <= yInt + 2; yCur++) {
            for(int xCur = xInt - 2; xCur <= xInt + 2; xCur++) {

                double xPos = xCur + valueNoise3D (xCur, yCur, zCur, seed);
                double yPos = yCur + valueNoise3D (xCur, yCur, zCur, rand.nextLong());
                double zPos = zCur + valueNoise3D (xCur, yCur, zCur, rand.nextLong());
                double xDist = xPos - x;
                double yDist = yPos - y;
                double zDist = zPos - z;
                double dist = xDist * xDist + yDist * yDist + zDist * zDist;

                if(dist < minDist) {
                    minDist = dist;
                    xCandidate = xPos;
                    yCandidate = yPos;
                    zCandidate = zPos;
                }
            }
        }
    }

    double xDist = xCandidate - x;
    double yDist = yCandidate - y;
    double zDist = zCandidate - z;

    return getDistance(xDist, yDist, zDist);
}

public void setDistanceMethod(short distanceMethod) {
    this.distanceMethod = distanceMethod;
}

public void setSeed(long seed) {
    this.seed = seed;
}

public static double valueNoise2D (int x, int z, long seed) {
    long n = (1619 * x + 6971 * z + 1013 * seed) & 0x7fffffff;
    n = (n >> 13) ^ n;
    return 1.0 - ((double)((n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff) / 1073741824.0);
}

public static double valueNoise3D (int x, int y, int z, long seed) {
    long n = (1619 * x + 31337 * y + 6971 * z + 1013 * seed) & 0x7fffffff;
    n = (n >> 13) ^ n;
    return 1.0 - ((double)((n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff) / 1073741824.0);
}
}

As you can see i've been calculating the Distance21 - the distance of the 1st minus the 2nd closest point. I've been using this along with Euclidian distance calculation to generate a noise map. Here is what I get: Length-Distance21 I've then been checking whether the noise is below a certain value (black colours) and using that to place roads. One problem is that some of the cells are black, some blacker than the roads causing a mass of roads. Also, the roads are more than 1 unit in width which is unacceptable for my purposes.

Here is a chart of the different types of voronoi noise. voronoi types

I was wondering if there is an algorithm for procedurally generating noise like this

enter image description here

Except that given a seed, a frequency and a point (x,y) it would return true or false whether or not the vertices pass through that point or not. Creating lines

lines

As a last resort I will use a repeating, static, image.

EDIT: I managed to do what i set out to do by checking if the 4 points around the point have a different closest point

success

I would still like to know if this is possible some other less intensive way.

java
random
noise
voronoi
procedural-generation
asked on Stack Overflow Jun 29, 2020 by FlameBlazer • edited Jun 30, 2020 by FlameBlazer

0 Answers

Nobody has answered this question yet.


User contributions licensed under CC BY-SA 3.0