Hey im a novice programer and I wanted to use this is the background for map generation for a game im making. How do i go about actually integrating the functionality into my scripts?

[Pperson25]

I tried creating an instance of the Delaunay class in one script after installing everything according to instructions. I feel like Im missing something that's probably obvious to everyone else.

[nol1fe]

Hello @Pperson25

As a starting point you can try to get the Unity samples from package manager.

After import open SampleScene and select DelaunatorPreview game object from scene hierarchy. Double click on DelaunatorPreview script to open your IDE and see base usage of delaunator library.

In general to create instance of delaunator you need to pass some points into constructor. They can be generated from some alghoritms, created from transforms of objects from the unity scene, or loaded from some json/csv.

Check Create() method in DelaunatorPreview.cs (line 81) to see how it's done.

delaunator = new Delaunator(points);

after you got the instance of Delaunator that contains all the magic with the calculations, you need to call its methods to create visual presentation of it. Stuff like edges of triangles, edges of voronoi, hull etc.

Visit this site for more information about how to generate awesome maps from it.

Cheers

[Pperson25]

Thank you for this writeup. It seems that my algorithm for map generation uses Vector2s for the centers of the cells while this uses Vector3s. I guess its just a matter of saying points[i] = new Vector3(centers[i].x, centers[i].y, 0f); for each of the points I want. Again I can not thank you enough for how much time and effort you have saved me on this project. If it ever pans out into a full game I will make sure to put in the proper license and accreditation.

edit: I was wrong, it takes IPoints as an argument. There's probably an explanation of them somewhere already on this git page, but I'll look for it later. Again, thank you for the help!

[nol1fe]

Perhaps these extensions might help you.

Add using DelaunatorSharp.Unity.Extensions; at the top of your class, then you will be able to call .ToPoints() on your Vector2 enumerable.

Other solution If you are using your own vector/point class is to implement interface IPoint from DelaunatorSharp namespace. You will be able to create Delaunator from it.

Another solution is to use System.Linq and call it like so

new Delaunator(yourPoints.Select(point => new Point(point.x, point.y).ToArray());

where Point is class from DelaunatorSharp namespace that implements IPoint interface.

Cheers

[Pperson25]

I'm just using an array of Vector3s with the z cord = 0 for all of them (formally vector2s for the above reason). I switched them back to Vector2s and it seems to work now. Again I cant thank you enough for the help you have given me so far, but what I want to do is use this in the backend for map generation.

What I want to do specifically is generate a terrain mesh based on a certain desired geographic archetype that a person wants with the voronoi cells. So for example, one voronoi cell can be assigned as being for highlands and an adjacent cell is assigned to be ocean. The mesh points within the highland cells are then generated using some sort of noise generation bounded to be an appropriate height above sea level and then the ocean mesh vertexes are set to be below sea level. Then the points that are near the edge separating the cells will be tweaked to create an appealing sea cliff face. Then the points near the vertexes of the voronoi cells are tweaked to create a good blend between multiple cells, maybe even adding rock models so that it creates a cool cliff point that juts into the ocean for example.

My original idea was to generate an 2 dimensional array of indexes such that coordinate in the array is assigned to a mesh vertex (or square of mesh vertexes), fill that texture with a voronoi coloring algorithm, and then blow that texture up somehow to whatever map size I end up going with. But now that this package has a way of defining cells as polygons, maybe I can just iterate over every mesh vertex (using the GPU to parallelize this of course) and just use some sort of method to determine which cell's polygon it is in. Any advice for doing this efficiently?

edit: I guess a big part of my confusion in trying to use this is that I am not familiar with the IPoint object.

[Pperson25]

Hey sorry to bother you again, but I'm still not understanding how to use this. it seems like the code for the Delaunator class creates instances of an object called "edge" but I see no definition for such a class. Im trying to use the ForEachTriangleEdge method but I think I'm not doing it right.

[nol1fe]

Hi there,

It would be easier if you provide here the code snippet and describe what you want to achieve.

Check out these WPF and Unity examples.

Delaunator.dll contains Edge definition so you don't have to worry about it.

Cheers

[Pperson25]

Thank you. I guess I just didn't import the package correctly.

[Pperson25]

Here is the copied and pasted script that does some of the background work. It's incomplete and currently bugged so it doesn't do anything. A RandomZoneGenerator object is made by another script that uses this to display an image of different colored zones based off of certain parameters. I was trying at first to write a method that would color the tiles based off if it touches the edge of the map and if not how distant it is from the map based off of the Delaunay triangulation graph traversal distance to the bordering tiles.

My plan for the map generation is to assign different terrain types to the tiles on the edge of the map first then progressivly move into the center with valid terrain types, then doing another pass adding rivers and other niche tile types, and then pass that data to other parts of the map generation script so it knows what kind of terrain to generate for that part of the map. I'll take some screenshots of the texture its generating as a prototype.

`using System.Collections; using System.Collections.Generic; using UnityEngine; using DelaunatorSharp; using System.Linq; using DelaunatorSharp.Unity.Extensions; //using System;

//"com.nol1fe.delaunator": "https://github.com/nol1fe/delaunator-sharp.git?path=DelaunatorSharp.Unity" //remember to add the license for this

public class RandomZoneGenerator //: MonoBehaviour {

int randomSeed;
int width;
int numOfZones;
int numOfVertices;
int pointsPerSquareEdge;
int interiorPointsNumber;
int numberOfDelaunayTriangles;
public Vector2[] centers;
public Vector2[] vertices;
public bool[,] centerConnectedMatrix;
public bool[,] vertexConnectedMatrix;
public int[] exteriorCells;

public Delaunator OptimusPrime;

//ref object[] zoneObjects;

short[,] pixelIndexAssignments;

public RandomZoneGenerator(int seed, int sideLength, int numberEdgePoints, int numberInteriorPoints)
{
    randomSeed = seed;
    width = sideLength;
    pointsPerSquareEdge = numberEdgePoints;
    interiorPointsNumber = numberInteriorPoints;
    numOfZones = 4 + 4 * pointsPerSquareEdge + interiorPointsNumber;
    centers = new Vector2[numOfZones];
    //centersConnectedMatrix = new bool[numOfZones, numOfZones];
    Random.InitState(seed);
    pixelIndexAssignments = new short[sideLength + 1, sideLength + 1];
    for (int i = 0; i <= width; i++)
    {
        for (int j = 0; j <= width; j++)
        {
            pixelIndexAssignments[i, j] = -1;
        }
    }

    if (width < 1)
    {
        width = 1;
    }

    if (pointsPerSquareEdge < 0)
    {
        pointsPerSquareEdge = 0;
    }

    if (interiorPointsNumber < 0)
    {
        interiorPointsNumber = 0;
    }

    centerConnectedMatrix = new bool[numOfZones, numOfZones];

    for (int i = 0; i < numOfZones; i++)
    {
        for (int j = 0; j < numOfZones; j++)
        {
            centerConnectedMatrix[i, j] = false;
        }
    }
}

public void GenerateRandomZoneCenters()
{
    int totalEdgePoints = 4 + pointsPerSquareEdge * 4;
    float widthF = (float)width;
    float edgeSubLength = widthF/((float)(pointsPerSquareEdge + 1));

    /*
    centers[0] = new Vector2(0f, 0f);
    centers[1] = new Vector2(0f, widthF);
    centers[2] = new Vector2(widthF, 0f);
    centers[3] = new Vector2(widthF, widthF);

    for (int i = 1; i < pointsPerSquareEdge + 1; i++)
    {
        centers[4 * i] = new Vector2(0f, edgeSubLength * (float)i);
        centers[4 * i + 1] = new Vector2(edgeSubLength * (float)i, 0f);
        centers[4 * i + 2] = new Vector2(widthF, edgeSubLength * (float)i);
        centers[4 * i + 3] = new Vector2(edgeSubLength * (float)i, widthF);
    }
    */

    for (int i = 0; i < pointsPerSquareEdge + 1; i++)
    {
        centers[i] = new Vector2(edgeSubLength * (float)i, 0f);
        centers[i + pointsPerSquareEdge + 1] = new Vector2(widthF, edgeSubLength * (float)i);
        centers[i + 2 * pointsPerSquareEdge + 2] = new Vector2(widthF - (edgeSubLength * (float)i), widthF);
        centers[i + 3 * pointsPerSquareEdge + 3] = new Vector2(0f, widthF - (edgeSubLength * (float)i));
    }

    for (int i = totalEdgePoints; i < numOfZones; i++)
    {
        centers[i] = new Vector2(Random.Range(0, (float)width), Random.Range(0, (float)width));
    }

}

public void VoronoiFortunesAlgorithmVertexes()
{

}

/*private bool CheckCounterClockwiseTriangles(int a, int b, int c)
{

    Vector3 superA = new Vector3(centers[a].x, centers[a].y, 0);
    Vector3 superB = new Vector3(centers[b].x, centers[b].y, 0);
    Vector3 superC = new Vector3(centers[c].x, centers[c].y, 0);

    Vector3 u = Vector3.Subtract(superA, superB);
    Vector3 v = Vector3.Subtract(superA, superC);
    Vector3 uxv = Vector3.Cross(u, v);

    return uxv.Z >= 0;
}*/

float sign(Vector2 p1, Vector2 p2, Vector2 p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle(Vector2 v1, Vector2 v2, Vector2 v3, Vector2 pt)
{
    float d1, d2, d3;
    bool has_neg, has_pos;

    d1 = sign(pt, v1, v2);
    d2 = sign(pt, v2, v3);
    d3 = sign(pt, v3, v1);

    has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    return !(has_neg && has_pos);
}

public void ActivateDelaunator()
{
    if (OptimusPrime == null)
    {
        OptimusPrime = new Delaunator(centers.ToPoints());

    }
}

public void VoronoiJumpFlood()
{

    short compareNeighbors(int px, int py, int qx, int qy, short pIndex, short qIndex)
    {
        if (pIndex == -1 && qIndex != -1)
        {
            return qIndex;
        }
        else if (pIndex == qIndex)
        {
            return pIndex;
        }
        else if (pIndex != -1 && qIndex != -1)
        {
            Vector2 pVecter = new Vector2((float)px, (float)py);
            Vector2 qVector = new Vector2((float)qx, (float)qx);
            if (Vector2.Distance(pVecter, centers[(int)pIndex]) > Vector2.Distance(qVector, centers[(int)qIndex]))
            {
                return qIndex;
            }
            else
            {
                return pIndex;
            }
        }
        else
        {
            return pIndex;
        }
    }

    for (int i = 0; i < numOfZones; i++)
    {
        int seedX = (int)System.Math.Round(centers[i].x, 0f);
        int seedY = (int)System.Math.Round(centers[i].y, 0f);
        pixelIndexAssignments[seedX, seedY] = (short)i;
    }

    for (int k = width; k > 1; k = k / 2)
    {
        if (k < width)
        {
            for (int x = 0; x < width; x++)
            {
                for (int y = 0; y < width; y++)
                {
                    int xmk = (x - k + width) % width;
                    int xpk = (x + k + width) % width;
                    int ymk = (y - k + width) % width;
                    int ypk = (y + k + width) % width;
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xmk, ymk, pixelIndexAssignments[x, y], pixelIndexAssignments[xmk, ymk]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, x, ymk, pixelIndexAssignments[x, y], pixelIndexAssignments[x, ymk]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xpk, ymk, pixelIndexAssignments[x, y], pixelIndexAssignments[xpk, ymk]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xmk, y, pixelIndexAssignments[x, y], pixelIndexAssignments[xmk, y]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xpk, y, pixelIndexAssignments[x, y], pixelIndexAssignments[xpk, y]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xmk, ypk, pixelIndexAssignments[x, y], pixelIndexAssignments[xmk, ypk]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, x, ypk, pixelIndexAssignments[x, y], pixelIndexAssignments[x, ypk]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xpk, ypk, pixelIndexAssignments[x, y], pixelIndexAssignments[xpk, ypk]);
                }
            }
        }

        else if (k == width)
        {
            for (int x = 0; x < width; x++)
            {
                for (int y = 0; y < width; y++)
                {
                    int xmk = (x - 1 + width) % width;
                    int xpk = (x + 1 + width) % width;
                    int ymk = (y - 1 + width) % width;
                    int ypk = (y + 1 + width) % width;
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xmk, ymk, pixelIndexAssignments[x, y], pixelIndexAssignments[xmk, ymk]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, x, ymk, pixelIndexAssignments[x, y], pixelIndexAssignments[x, ymk]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xpk, ymk, pixelIndexAssignments[x, y], pixelIndexAssignments[xpk, ymk]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xmk, y, pixelIndexAssignments[x, y], pixelIndexAssignments[xmk, y]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xpk, y, pixelIndexAssignments[x, y], pixelIndexAssignments[xpk, y]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xmk, ypk, pixelIndexAssignments[x, y], pixelIndexAssignments[xmk, ypk]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, x, ypk, pixelIndexAssignments[x, y], pixelIndexAssignments[x, ypk]);
                    pixelIndexAssignments[x, y] = compareNeighbors(x, y, xpk, ypk, pixelIndexAssignments[x, y], pixelIndexAssignments[xpk, ypk]);
                }
            }
        }
    }
}

public void VoronoiBruteForceFill()
{

    Vector2 closedCenter = new Vector2(0f, 0f);
    closedCenter = centers[0];
    float shortedDistance = 0f;
    int closedIndex = 0;
    for (int x = 0; x <= width; x++)
    {
        for (int y = 0; y <= width; y++)
        {
            Vector2 pVector = new Vector2((float)x, (float)y);
            closedCenter = centers[0];
            shortedDistance = Vector2.Distance(pVector, closedCenter);
            closedIndex = 0;
            for (int i = 1; i < numOfZones; i++)
            {
                if (Vector2.Distance(pVector, centers[i]) < shortedDistance)
                {
                    closedCenter = centers[i];
                    shortedDistance = Vector2.Distance(pVector, centers[i]);
                    closedIndex = i;
                }
            }
            pixelIndexAssignments[x, y] = (short)closedIndex;
        }
    }
}

public Vector2[] SortCenterPointsByXthenYcord()
{
    Vector2[] toReturn = new Vector2[numOfZones];
    for (int i = 0; i < numOfZones; i++)
    {
        toReturn[i] = centers[i];
    }

    bool CompareCordinates(Vector2 P1, Vector2 P2){
        if (P1.x > P2.x)
        {
            return true;
        }
        else if (P1.x < P2.x)
        {
            return false;
        }
        else if (P1.y > P2.y)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

   /* void SwapVectors(Vector2 a, int b)
    {
        Vector2 newVector = new Vector2;
        newVector = a;
        a = centers[b];
        centers[b] = newVector;
    }*/

    void quickSortCenters(int lo, int hi){
        if (hi <= lo || lo < 0)
        {
            return;
        }
        else
        {
            int p = partition(lo, hi);
            quickSortCenters(lo, p - 1);
            quickSortCenters(p + 1, hi);
        }

    }

    int partition(int low, int high)
    {
        Vector2 pivot = new Vector2();
        pivot = toReturn[high];
        int i = low - 1;
        Vector2 newVector = new Vector2();
        for (int j = low; j < high; j++)
        {
            if (CompareCordinates(pivot, toReturn[j]))
            {
                i++;
                newVector = toReturn[i];
                toReturn[i] = toReturn[j];
                toReturn[j] = newVector;
            } 
        }
        i++;
        newVector = toReturn[i];
        toReturn[i] = toReturn[high];
        toReturn[high] = newVector;
        return i;
    }

    quickSortCenters(0, numOfZones - 1);

    return toReturn;
}

public void VoronoiFortunesAlgorithmFillOnly()
{

}

public void VoronoiFortunesAlgorithmFillVertex()
{

}

public void RelaxInteriorCenters(int iterations)
{

    if (iterations <= 0)
    {
        return;
    }
    int[] areaOfIndexZone = new int[numOfZones];
    float[] sumofIndexedXcords = new float[numOfZones];
    float[] sumofIndexedYcords = new float[numOfZones];
    for (int i = 0; i < iterations; i++)
    {
        for (int j = 0; j < numOfZones; j++)
        {
            areaOfIndexZone[j] = 0;
            sumofIndexedXcords[j] = 0f;
            sumofIndexedYcords[j] = 0f;
        }

        for (int x = 0; x < width + 1; x++)
        {
            for (int y = 0; y < width + 1; y++)
            {
                areaOfIndexZone[pixelIndexAssignments[x, y]]++;
                sumofIndexedXcords[pixelIndexAssignments[x, y]] += (float)x;
                sumofIndexedYcords[pixelIndexAssignments[x, y]] += (float)y;
            }
        }

        for (int j = 0; j < numOfZones; j++)
        {
            centers[j].x = sumofIndexedXcords[j] / (float)areaOfIndexZone[j];
            centers[j].y = sumofIndexedYcords[j] / (float)areaOfIndexZone[j];
        }
        this.VoronoiBruteForceFill();
    }
}

public Color[] GenerateColorMap(bool sortFirst)
{
    if (sortFirst == false) {
        Color[] colorMap = new Color[(width + 1) * (width + 1)];
        Color[] zoneColors = new Color[numOfZones];
        //System.Random randomizer = new System.Random();
        float zones = (float)numOfZones;
        for (int i = 0; i < numOfZones; i++)
        {

            float h = (float)i / zones;
            zoneColors[i] = Color.HSVToRGB(h, 1f, 1f);
        }
        for (int i = 0; i < width * width; i++)
        {
            colorMap[i] = zoneColors[pixelIndexAssignments[i % width, i / width]];
        }
        return colorMap;
    }
    else
    {
        this.centers = this.SortCenterPointsByXthenYcord();
        this.VoronoiBruteForceFill();
        Color[] colorMap = new Color[(width + 1) * (width + 1)];
        Color[] zoneColors = new Color[numOfZones];
        //System.Random randomizer = new System.Random();
        float zones = (float)numOfZones;
        for (int i = 0; i < numOfZones; i++)
        {

            float h = (float)i / zones;
            zoneColors[i] = Color.HSVToRGB(h, 1f, 1f);
        }
        for (int i = 0; i < width * width; i++)
        {
            colorMap[i] = zoneColors[pixelIndexAssignments[i % width, i / width]];
        }
        return colorMap;

    }

}
/*
public Color[] GenerateColorMapFromTileArray(MapTileObj[] mapTiles)
{

}
*/

public Color[] ColorMapFromDistanceFromMapEdge()
{
    IPoint[] hullIPoints = OptimusPrime.GetHullPoints();

}

public void GenerateVertexes()
{
    this.ActivateDelaunator();
    //OptimusPrime.
   void DoForVertexGeneration()
    {

    }
}

public void GenerateDelaunayTriangulation()
{
    this.ActivateDelaunator();
    centerConnectedMatrix = new bool[numOfZones, numOfZones];

    OptimusPrime.ForEachTriangleEdge(DoForEachEdge);
    void DoForEachEdge(IEdge edge)
    {
        int head = edge.p;
        int tail = edge.q;

    }
}

}

`

[Pperson25]

Here are the screenshots I was talking about earlier. First one is unsorted, second one is sorted. I implemented a way of sorting them because one of the Delaunay triangulation algorithms I read about online worked by sorting them by x then y coordinate. Based on the fact that I am here right now can tell you enough about how that went. In retrospect, basing this off of a bitmap texture instead of just some polygons for the voronoi part means that a lot of pixels have to be sorted through just to figure out the general biome of a part of the map let alone exact height. I got a lot of work ahead of me to fix this whole mess.

[Pperson25]

holy fucking shit I just realised what my issue is. I didn't have git installed.

[nol1fe]

holy fucking shit I just realised what my issue is. I didn't have git installed.

😄

So is everything ok now? It seems to be nice project so far! I can't wait to see final results. Keep it up!

Cheers

[Pperson25]

yes