Hey all,
Thank you to everyone who has taken the time to answer my numerous, and often stupid, questions over the last couple of days. You have all been really helpful, and in the interest of giving back, I wanted to type of a rather detail post about what I recently built as a learning process.
I already had this implemented in “standard” Unity as an Editor based tool, but I wanted to re-implement it using runtime ECS.
Essentially what this does is build a relaxed Voronoi diagram. The end result is a series of entities, with each rep[resenting a final MapCell based on the Sites of the Voronoi Diagram. As a last step I spawn GameObjects in order to render the actual edges of each cell for visualization to verify it generated what I expected it to.
This project uses four Entity Archetypes, four Components, and Three different Systems. It is fully “reactive” rather than a hardcoded series of steps as suggested by @5argon in one of my many threads. This means that the “map generation” is always running and looking for the proper entities and just does its thing when its sees them, each step proceeding as the data is transformed along the way. When the “Generate” button is clicked in the UI (not seen in the screenshot), a series of entities is created. The systems then see those entities and shepherd them through the process, not caring.
Components
VoronoiPositionData : float2
public struct VoronoiPositionData : IComponentData
{
public float2 Value;
}
VoronoiRelaxationData : int
public struct VoronoiRelaxationData : IComponentData
{
public int RelaxationsRemaining;
}
DynamicBuffer : float2
[InternalBufferCapacity(12)]
public struct VoronoiEdgePointElement : IBufferElementData
{
public float2 Value;
public static implicit operator float2(VoronoiEdgePointElement element)
{
return element.Value;
}
public static implicit operator VoronoiEdgePointElement(float2 f)
{
return new VoronoiEdgePointElement {Value = f};
}
}
GameObjectRepFlag
csharp__ __ public struct GameObjectRepFlag : IComponentData {}__ __
Entity Archetypes
I know these aren’t really defined exactly, but it helps me to think of them as a way to provide scope to what I’m seeing. One of the largest problems I am having adapting to ECS code in general are the mental demands of seeing the big picture, so this helps a bit.
MapSeedPoint : VoronoiPositionData, VoronoiRelaxationData
When the “Generate” button is clicked, these entities are what are created to jump start the process. A MapSeedPoint is essentially a candidate point that will eventually be used to generate the Voronoi diagram. These entities have a VoronoiPositionData component and a VoronoiRelaxationData component.
MapSite: VoronoiPositionData, VoronoiRelaxationData, DynamicBuffer
Seed points are consumed to generate the Voronoi diagram. As a byproduct of that transformation, these new entities are emitted. Each represents one site in the Voronoi diagram. In addition to copying over the Position and Relaxation data, we add a DynamicBuffer component to the new entities. This buffer is a list of points which make up the geometric edges of the site in the diagram.
MapCell: VoronoiPositionData, DynamicBuffer
These represent the final, fully relaxed, Voronoi Site which is now a Cell in the map. These entities contain Position and EdgePoints, but Lose the Releaxation data once they are fully relaxed.
VisualMapCell : VoronoiPositionData, DynamicBuffer, GameObjectRepFlag
These are essentially the same thing as the MapCell, but have been processed as a final step to create visual GameObject representations. The flag component is added so that they don’t get created again to infinity and beyond.
Systems
We start by generating MapSeedPoints which are just random points in a defined space along the XY plane, and contain a preset Relaxation value representing how many times the final diagram will be relaxed. For this right now I used a value of 10, so the final Voronoi Diagram represents a diagram with 10 relaxation iterations.
The first system, PointsToSitesSystem, is probably the most complicated. It gathers up any seed points it finds, and puts the points positions into a NativeArray, as well as noting the Relaxation number. It then deletes the entities. Next, it generates the Voronoi Diagram from the points stored in the NativeArray. This is a main thread job as I’m using a backend library that isn’t setup for Unity ECS. Once the diagram is generated, the system iterates through all of the Sites in the diagram, and creates a new MapSite entity from each site. It stores the same Position point that was from the original Seed point, as well as the points that make up the edges of this site. It also sets the Relaxation to what was recorded. If the relaxation is <= 0 it removes that component. This was an important thing I learned. Instead of checking the value of Relaxation at various points to see if it was above 0, it is simpler to just remove the component once it drops below 0. Then if the component is present you know it is above 0 by the very nature of its existence.
using Unity.Collections;
#if USE_ENTITIES
using System.Collections.Generic;
using Unity.Entities;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEngine;
using VoronoiLib;
using VoronoiLib.Structures;
namespace voronoi.Entities
{
/// <summary>
/// Looks for seed points, if found, generates a voronoi diagram from the seed points, and creates site entities
/// </summary>
public class PointsToSitesSystem : JobComponentSystem
{
// gather up all the points into an array
// generate voronoi from points
// add edges to each point as appropriate (should we try to keep the same entities and just add the new data or make new entities and destroy the old ones?)
private EntityQuery query;
private EndSimulationEntityCommandBufferSystem endSimulationCommandBufferSystem;
protected override void OnCreate()
{
var queryDesc = new EntityQueryDesc
{
All = new ComponentType[]{ComponentType.ReadOnly<VoronoiPositionData>(), typeof(VoronoiRelaxationData)},
None = new ComponentType[]{typeof(VoronoiEdgePointElement)}
};
query = GetEntityQuery(queryDesc);
endSimulationCommandBufferSystem = World.GetOrCreateSystem<EndSimulationEntityCommandBufferSystem>();
}
protected override JobHandle OnUpdate(JobHandle inputDeps)
{
var relaxationsArray = new NativeArray<int>(1, Allocator.TempJob);
var positionArray = new NativeArray<VoronoiPositionData>(query.CalculateEntityCount(), Allocator.TempJob);
var ecb = endSimulationCommandBufferSystem.CreateCommandBuffer().ToConcurrent();
// Get all entities that have a position for a voronoi point, and a relaxation
// Store the relaxation and positions and delete the entities
JobHandle getPositions = Entities.WithNone<VoronoiEdgePointElement>()
.ForEach((Entity entity, int entityInQueryIndex, in VoronoiPositionData position, in VoronoiRelaxationData relaxations) =>
{
positionArray[entityInQueryIndex] = position;
relaxationsArray[0] = relaxations.RelaxationsRemaining;
ecb.DestroyEntity(entityInQueryIndex, entity);
}).Schedule(inputDeps);
endSimulationCommandBufferSystem.AddJobHandleForProducer(getPositions);
getPositions.Complete();
// Now we have an array of point positions, so generate a voronoi diagram from those
List<FortuneSite> sites = new List<FortuneSite>(positionArray.Length);
foreach (var positionData in positionArray)
{
sites.Add(new FortuneSite(positionData.Value.x, positionData.Value.y));
}
positionArray.Dispose();
FortunesAlgorithm.Run(sites, 0, 0, 1000, 1000);
// Next, take the voronoi sites generated and make new entities with the site positions and the edges
// Also copy over the relaxation from the previous point set
EntityManager manager = World.EntityManager;
EntityArchetype archetype = manager.CreateArchetype(typeof(VoronoiPositionData), typeof(VoronoiRelaxationData), typeof(VoronoiEdgePointElement));
foreach (var site in sites)
{
Entity newEntity = manager.CreateEntity(archetype);
manager.SetComponentData(newEntity, new VoronoiPositionData{Value = new float2(site.x, site.y)});
if (relaxationsArray[0] >= 0)
{
manager.SetComponentData(newEntity, new VoronoiRelaxationData{RelaxationsRemaining = relaxationsArray[0]});
}
else
{
manager.RemoveComponent<VoronoiRelaxationData>(newEntity);
}
DynamicBuffer<VoronoiEdgePointElement> buffer = manager.AddBuffer<VoronoiEdgePointElement>(newEntity);
foreach (Vector2 sitePoint in site.Points)
{
buffer.Add(new VoronoiEdgePointElement {Value = new float2(sitePoint.x, sitePoint.y)});
}
}
relaxationsArray.Dispose();
return default;
}
}
}
#endif
The next system, RelaxSitesSystem, is rather simple. It is simply looking for MapSite entities (which the previous system emitted) and when it finds them it calculates the centroid of that site, updates its Position to be that point, then removes the EdgePoints component. Finally it decrements the Relaxation data. The end result is we have a new MapSeedPoint but one that has been moved slightly by the relaxation. That means the first system, PointsToSitesSystem, will pick it up as if it was a freshly created point and generate a new diagram. I find the elegance of this to be sweet.
using Unity.Entities;
using Unity.Jobs;
using Unity.Mathematics;
namespace voronoi.Entities
{
public class RelaxSitesSystem : JobComponentSystem
{
// Looks for entities that represent voronoi sites with > 0 relaxations left on them
// Then relaxes them by computing a new centroid
// The EdgePoints data is then removed making them valid to get turned into a new voronoi
private EndSimulationEntityCommandBufferSystem endSimulationCommandBufferSystem;
protected override void OnCreate()
{
endSimulationCommandBufferSystem = World.GetOrCreateSystem<EndSimulationEntityCommandBufferSystem>();
}
protected override JobHandle OnUpdate(JobHandle inputDeps)
{
var ecb = endSimulationCommandBufferSystem.CreateCommandBuffer().ToConcurrent();
JobHandle relaxPoints = Entities.ForEach((Entity entity, int entityInQueryIndex, ref VoronoiPositionData position, ref VoronoiRelaxationData relaxation,
in DynamicBuffer<VoronoiEdgePointElement> edgePoints) =>
{
relaxation.RelaxationsRemaining = relaxation.RelaxationsRemaining - 1;
float2 centroid = float2.zero;
float determinant = 0;
int numVertices = edgePoints.Length;
for (var i = 0; i < numVertices; i++)
{
int j;
if (i + 1 == numVertices)
j = 0;
else
{
j = i + 1;
}
// compute the determinant
float2 thisPoint = edgePoints[i].Value;
float2 refPoint = edgePoints[j].Value;
float tempDeterminant = thisPoint.x * refPoint.y - refPoint.x * thisPoint.y;
determinant += tempDeterminant;
centroid.x += (thisPoint.x + refPoint.x) * tempDeterminant;
centroid.y += (thisPoint.y + refPoint.y) * tempDeterminant;
}
// divide by the total mass of the polygon
centroid.x /= 3 * determinant;
centroid.y /= 3 * determinant;
position.Value.x = centroid.x;
position.Value.y = centroid.y;
ecb.RemoveComponent<VoronoiEdgePointElement>(entityInQueryIndex, entity);
}).Schedule(inputDeps);
endSimulationCommandBufferSystem.AddJobHandleForProducer(relaxPoints);
return relaxPoints;
}
}
}
The entities will essentially just bounce back and forth between those two systems, generating a diagram, relaxing the points, generating a new diagram, etc until the relaxation count reaches 0. At that point we end up with an Entity that has a Position, and EdgePoints but no Relaxation component which means both systems will ignore it, and its Archetype is now a MapCell.
The last system, VoronoiSiteToMapCellSystem, sees these final MapCell entities, and creates a GameObject with a LinRenderer from them so that there is a visual result.
using Unity.Entities;
using Unity.Jobs;
using UnityEngine;
using voronoi.Entities;
namespace galaxias.ecs
{
// This system makes a GameObject from the final voronoi site for visualization
[AlwaysSynchronizeSystem]
public class VoronoiSiteToMapCellSystem : JobComponentSystem
{
private EndSimulationEntityCommandBufferSystem endSimulationCommandBufferSystem;
protected override void OnCreate()
{
endSimulationCommandBufferSystem = World.GetOrCreateSystem<EndSimulationEntityCommandBufferSystem>();
}
protected override JobHandle OnUpdate(JobHandle inputDeps)
{
var ecb = endSimulationCommandBufferSystem.CreateCommandBuffer();
Entities.WithNone<GameObjectRepFlag>().WithNone<VoronoiRelaxationData>().ForEach((Entity entity, int entityInQueryIndex, in VoronoiPositionData position, in DynamicBuffer<VoronoiEdgePointElement> edgePoints) =>
{
string name = $"MapCell {position.Value.x},{position.Value.y}";
ecb.AddComponent<GameObjectRepFlag>(entity);
GameObject go = new GameObject(name);
LineRenderer lineComponent = go.AddComponent<LineRenderer>();
Vector3[] points = new Vector3[edgePoints.Length];
for (int i = 0; i < edgePoints.Length; i++)
{
points[i] = new Vector3(edgePoints[i].Value.x, edgePoints[i].Value.y, 0f);
}
lineComponent.positionCount = edgePoints.Length;
lineComponent.SetPositions(points);
lineComponent.loop = true;
lineComponent.widthMultiplier = 0.5f;
}).WithoutBurst().Run();
return default;
}
}
}
