基于libnoiseforjava的Voronoi道路生成优化及算法问询

Great job landing on the neighbor-checking solution—let’s break down some lower-overhead approaches that can get you clean, 1-unit wide roads directly from Voronoi logic, without unnecessary computations.

1. Optimized Voronoi Edge Detection (Direct Distance Comparison) #

Your original Distance21 approach calculates the difference between the second-closest and closest Voronoi cell centers, but we can refine this to directly detect edge points with less work:

• Shrink the search grid: You’re currently iterating over a 5x5 grid of cells to find closest centers, but a 3x3 grid is sufficient for 2D Voronoi (the closest two centers will never be farther than one cell away from your target point’s integer grid cell). Cutting the loop from 25 iterations to 9 will immediately reduce overhead.
• Edge thresholding with normalized distance: Instead of returning the raw distance difference, normalize it to a [0, 1] range, then set a tight threshold (e.g., values < 0.05) to mark road pixels. This fixes the "too-wide roads" issue by only keeping points where the closest two centers are nearly equidistant (the definition of a Voronoi edge).
• Cache seed values: Stop creating a new Random instance every time you call noise()—your valueNoise2D function already uses a deterministic hash based on seed, so you can precompute xSeed and zSeed as class-level variables in the constructor instead of generating them on each call.

Here’s a quick tweak to your noise() method to implement this:

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 = Double.MAX_VALUE;
    double secondMinDist = Double.MAX_VALUE;
    // Precompute these seeds once in the constructor instead of per-call
    long xSeed = /* precomputed class variable */;
    long zSeed = /* precomputed class variable */;

    // Use 3x3 grid instead of 5x5 for faster iteration
    for(int zCur = zInt - 1; zCur <= zInt + 1; zCur++) {
        for(int xCur = xInt - 1; xCur <= xInt + 1; 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; // Squared distance avoids sqrt for speed
            
            if(dist < minDist) {
                secondMinDist = minDist;
                minDist = dist;
            } else if(dist < secondMinDist) {
                secondMinDist = dist;
            }
        }
    }
    // Normalize distance difference to [0,1] for consistent thresholding
    double distDiff = Math.sqrt(secondMinDist) - Math.sqrt(minDist);
    double maxPossibleDiff = SQRT_2; // Max possible difference in 3x3 grid
    return distDiff / maxPossibleDiff;
}

Then, mark a point as road if the returned value falls below your tight threshold (e.g., < 0.05).

2. Use Voronoi Distance Field Gradients #

Voronoi edges are where the direction of the distance field (pointing to the closest center) changes abruptly. You can detect this by comparing the gradient direction of nearby points:

• For a target point (x,z), calculate the closest center for (x + 0.5, z) and (x - 0.5, z).
• If the direction vectors to these centers are nearly opposite (dot product < 0.8, for example), the original point is on an edge.
• This avoids calculating the second-closest center entirely—you only need to find the closest center for two adjacent points, which is faster than tracking two closest centers for one point.

3. Precompute Voronoi Edges (For Static Maps) #

If your map size is fixed, precompute all Voronoi edges once at startup:

• Iterate through each cell in your map, find adjacent cells whose closest centers are different (similar to your current solution).
• Store the edge coordinates in a spatial grid (e.g., a 2D array of lists, where each grid cell holds the edges that pass through it).
• When querying if (x,z) is a road, look up the corresponding grid cell and check if the point lies on any of the precomputed edges.
• This reduces runtime query overhead to almost zero, since you’re just checking precomputed data instead of recalculating Voronoi values every time.

4. Refine Your Current Neighbor-Checking Method #

If you want to stick with your existing solution but lower its overhead:

• Cache the closest center for each integer grid cell instead of recalculating it for every point. Since your Voronoi centers are deterministic based on seed, you can compute the closest center for (xCur, zCur) once and store it in a hash map or 2D array.
• Only check the four cardinal neighbors (up, down, left, right) instead of all surrounding points—this is enough to detect edges between adjacent cells.

All these approaches can cut down on unnecessary computations while keeping your road generation consistent with your seed and frequency parameters.

内容的提问来源于stack exchange，提问作者FlameBlazer