About the Author
Mass Effect
Final Fantasy X
Batman:Arkham City
Borderlands Series
Weekly Column
Champions Online
World of Warcraft
DM of the Rings
Good Robot
Project Frontier

Pixel City Redux #6: The Distraction

By Shamus
on Tuesday May 15, 2018
Filed under:


What do you do when you want to look something up but you don’t know what it’s called? Sometimes you can just type what you know into a search engine and it will sort things out for you. I just typed “part of the car that covers the engine” and I got:

thing that you type sentence fragments into for information

thing that you type sentence fragments into for information

It’s not a perfect result. A careless reader might look at the text and think the answer is “trunk”. But it’s still really incredible that a search engine can come up with answers like this. If you’re willing to read more than the first sentence, you can find what you’re looking for, even if you don’t know what a hood was called when you started.

Sadly, things are not always this easy. Right now I know what I want to make but I don’t know what to search for. I know what it looks like and how it behaves, but not how it’s created or what you call it. In fact, I can even draw a picture of it. It looks kind of like a stained glass window. Here is one I made by hand:

Uh... Something like this.

Uh... Something like this.

You generate this by putting a bunch of points on a plane and… doing some sort of math to them. I want to use something like this to divide my city into regions. Let’s see what Google has for me:

"dividing a 2D plane into regions"

Nope. That’s not it. All these results are about using line segments to divide a plane, which is what I did a few entries ago. Now I want to use dots or control points. Maybe the dots are given a position and size / radius?

"Divide 2D plane into regions using control points"

Nope. That’s not it. These results are all about intersecting 2D planes in 3D space, and I’m not looking for that kind of trouble. Hmmm.

"2d plane divide into bounded regions using control points"

Nope. More 3D space division using 2D planes. Now that I’m thinking about it, maybe the “control points” is throwing things off. That’s what I would call these things in code, but I get the sense that this is not what a mathematician would call them. I am definitely invading the mathematics clubhouse right now and I probably need to speak their lingo. On the other hand, what DO I call these things? Points? That sounds generic enough that it could lead to anything.

This goes on for several minutes. I’ll run out of ideas and then go and watch random YouTube videos for a bit. Then I’ll get an idea, type more crap into Google, get unhelpful results, and then go back to wasting my time on YouTube.

Maybe I’m overthinking this:

"diagram that looks like stained glass window"

Nope. Although this does lead to a nice little tangent regarding Venn diagrams.

"divide 2d grid into regions with points"


"diagram with bounded regions"

Interesting, but not what I’m looking for.

"subdivide 2d plane irregular"

No. Although part way through typing that Google autocomplete suggests “subdivide 2d plane crash“, which is either hilarious or terrifying.

I try throwing “euclidian” in the mix to try and trick Google into showing me where the mathematicians keep the treasure, but Google’s having none of it.

Time passes. Eventually I try:

"diagram with irregular regions"

Boom! It doesn’t link me directly to my target, but it brings up an image search that contains the kind of thing I’m looking for, and when I follow the image back to the site I discover it’s an article about Voronoi Diagrams.

Yes! That’s the one!

Finding this was the EASY part.

Finding this was the EASY part.

I read about this thing years ago and I’d forgotten almost everything about it, aside from what the result looked like. Now that I’m reading the process, it sounds a lot more involved that I’d imagined. The key here is that if you’re on one of the region boundaries, then you’re at the point equidistant to the points on either side of the line. More informally: If this was a city and the dots were all pizza places, then when you’re in the green region, the pizza place inside that region is the closest one in town. (Assuming you can get an Uber that follows as-the-crow-flies navigation.) This diagram can have you solve problems like figuring out the closest hospital / fire station for the given address. (Again, ignoring the thorny problem of traffic routing.) Here’s a really fun diagram generator you can play with. Once you have a few dots on the board, click and drag to see the region change shape in realtime.

I’m not interested in pizza or hospital routing problems here. I just want this because it looks cool.

This thing is actually a lot more complex than I anticipated. I just need to cut my city up into regions, and there are easier ways of making that happen than to implement something like this. On the other hand… I want to anyway.

Let’s Do This

There are a lot of ways to make these things. Some are focused on speed. Some are described as if you were creating the thing by hand on paper. I usually avoid the latter sorts of explanations when I’m trying to code something, because they often leave out important details. If you’re doing a worksheet and I tell you to “circle any letters with bad kerning“, then that’s easy to say and easy for you to understand and trivial for you to do. But implementing that in code would be a massive undertaking. But in this case the art-n-crafts style explanation happens to translate pretty well into code.

I’m interested in a method that will limit code complexity. I don’t really care if this is “slow”. I don’t imagine I’ll have more than a dozen regions and I only need to do this once when generating the city, so the difference between a fast, complicated method and a slow simple one will be imperceptible. Maybe a really efficient Voronoi generator can do the job in under 1 millisecond while a shamefully slow one would dawdle and waste seven entire milliseconds. Who cares? If the second one has fewer lines of code and is easier to implement, then it’s the right choice.

The process goes like this:

Throw down a bunch of dots, one for every region. For best results, try to make sure they’re spaced out a bit and you don’t have too many clustered together.

Meh. Close enough.

Meh. Close enough.

Great. Now this is the weird part that feels like magic. Apparently you can group these points into triangles by making groups of three that do not contain any other points within their circumcircle. Imagine drawing a circle that intersects all three corners. If that circle contains any other points, then you’ve got an invalid group of three. Try three others.

Somehow, this always forms a tidy mesh of triangles without nasty acute triangles, without odd gaps between them, and without any triangles overlapping. Each triangle should have a circle associated with it, which just consists of a the circumcenter point and the radius of the circle. Note that the circumcenter point itself may fall outside the bounds of the triangle. That’s fine. As long as the circle doesn’t contain any other points, you’re good.

When I read these directions I imagined it would just produce a big pile of disjointed triangles, but when I implemented it I got:

Swiped from Wikipedia.

Swiped from Wikipedia.

Now to finish it off. Each of those circumcircles is connected to a triangle. That triangle is obviously made up of three line segments. Each of those line segments divides this circumcircle from one of its three neighbors. Draw a line from this circumcenter to each of those three neighbors. When you’ve done this for all the triangles, you’ll have your Voronoi diagram:

I guess it works.

I guess it works.

Here is the resulting code:

 * Voroni 
 * This is an implementation an an algorithm to generate a Voronoi Diagram. This
 * takes a series of points on a plane and generates regions to contain those points.
 * This has been optimized for simplicity and readability, not speed. If you plan 
 * on using this to make thousands of regions, you might want to tighten it up.
 * ---------------------------------------------------------------------------------*/
using System.Collections.Generic;
using UnityEngine;
using System.Linq;
public class TriangleJoins
	public bool ab;
	public bool bc;
	public bool ca;
	public TriangleJoins () {
		ab = bc = ca = false;
public class VoroniRegion
	public int          index;
	List<LineSegment>   perimeter;
	Vector2             center;
	Vector2             origin;
	float               radius;
	public float Radius () { return radius; }
	public VoroniRegion (Vector2 origin_in, int index_in) {
		origin = origin_in;
		index = index_in;
		perimeter = new List<LineSegment> ();
	private void CalculateCenter () {
		center = Vector2.zero;
		radius = 0f;
		for (int i = 0; i < perimeter.Count; i++) {
			center += perimeter[i].start;
			center += perimeter[i].end;
		center /= (float)perimeter.Count * 2f;
		for (int i = 0; i < perimeter.Count; i++) {
			radius = Mathf.Max (radius, (perimeter[i].start - center).magnitude);
			radius = Mathf.Max (radius, (perimeter[i].end - center).magnitude);
	public void PushLine (LineSegment s) {
		LineSegment l = new LineSegment (s.start, s.end);
		perimeter.Add (l);
		CalculateCenter ();
	public List<LineSegment> Perimeter () { return perimeter; }
	public Vector2 Center () { return center; }
	public Vector2 Origin () { return origin; }
public class Voroni
	Vector2[]               _points;
	TriangleJoins[]         _joins;
	List<LineSegment>       _lines;
	List<Triangle>          _triangles;
	public VoroniRegion[]   _regions;
	public Triangle[] Triangles () { return _triangles.ToArray (); }
	private int[] TwoClosestNeighbors (int self) {
		List<Vector2>   others = new List<Vector2>();
		//Make a version of our list that doesn't include ourselves.
		for (int i = 0; i < _points.Length; i++) {
			if (i == self)
			Vector2 other = new Vector2 ();
			other.x = (float)i;
			other.y = (_points[i] - _points[self]).magnitude;
			others.Add (other);
		others = others.OrderBy (t => t.y).ToList ();
		List<int> sorted = new List<int> ();
		int count = 0;
		foreach (Vector2 v in others) {
			sorted.Add ((int)v.x);
			if (count == 2)
		return sorted.ToArray ();
	//Put a division line between each point and its 3 closest neighbors.
	private void Triangulate () {
		for (int p1 = 0; p1 < _points.Length; p1++) {
			for (int p2 = p1 + 1; p2 < _points.Length; p2++) {
				for (int p3 = p2 + 1; p3 < _points.Length; p3++) {
					Triangle tri = new Triangle (_points, p1, p2, p3);
					//Make sure the triangle is constructed clockwise.
					Vector2 to_center = (_points[tri.b] - _points[tri.a]).normalized.TurnedRight ();
					Vector2 edge = (_points[tri.a] + _points[tri.b]) / 2f;
					Vector2 from_center = (edge - tri.center).normalized;
					float dot = Vector2.Dot (to_center, from_center);
					if (dot < 0)
						tri.Flip ();
					if (!tri.FindCircumcenter (1000))
					//Now we have the circumcirle. See if any other points land inside it.
					bool contains_other_points = false;
					for (int i = 0; i < _points.Length; i++) {
						//Doin't check our own points.
						if (i == tri.a || i == tri.b || i == tri.c)
						if ((_points[i] - tri.circumcenter).magnitude < tri.circumcircle_radius) {
							contains_other_points = true;
					if (contains_other_points)
					_triangles.Add (tri);
	//Used during triangulation. Every line segment is a divider between two regions, and all 
	//triangles are wound clockwise. So to find a neighbor triangle you search for points in 
	//reverse order. Triangle a b c will share a border with the triangle of d b a,
	//because (b a) and (a b) are the same line segment.
	private int FindTriangleWithSegment (int start, int end) {
		for (int i = 0; i < _triangles.Count; i++) {
			if (_triangles[i].a == start && _triangles[i].b == end && _joins[i].ab == false) {
				_joins[i].ab = true;
				return i;
			if (_triangles[i].b == start && _triangles[i].c == end && _joins[i].bc == false) {
				_joins[i].bc = true;
				return i;
			if (_triangles[i].c == start && _triangles[i].a == end && _joins[i].ca == false) {
				_joins[i].ca = true;
				return i;
		return -1;
	//At this point we've performed the Delaunay triangulation. We need to turn this into the 
	//N-sided polygons of the Voronoi diagram. To do this, draw a line from the circumcenter
	//of each triangle to the circumcenters of the Triangle's three neighbors. The resulting
	//lines will form the Voronoi diagram.
	private void Join (int index) {
		int neighbor;
		if (!_joins[index].ab) {
			neighbor = FindTriangleWithSegment (_triangles[index].b, _triangles[index].a);
			if (neighbor != -1) {
				_joins[index].ab = true;
				Join (neighbor);
				LineSegment l = new LineSegment ();
				l.start = _triangles[index].circumcenter;
				l.end = _triangles[neighbor].circumcenter;
				_lines.Add (l);
				_regions[_triangles[index].a].PushLine (l);
				l.Flip ();
				_regions[_triangles[index].b].PushLine (l);
		if (!_joins[index].bc) {
			neighbor = FindTriangleWithSegment (_triangles[index].c, _triangles[index].b);
			if (neighbor != -1) {
				Join (neighbor);
				_joins[index].bc = true;
				LineSegment l = new LineSegment ();
				l.start = _triangles[index].circumcenter;
				l.end = _triangles[neighbor].circumcenter;
				_lines.Add (l);
				_regions[_triangles[index].b].PushLine (l);
				l.Flip ();
				_regions[_triangles[index].c].PushLine (l);
		if (!_joins[index].ca) {
			neighbor = FindTriangleWithSegment (_triangles[index].a, _triangles[index].c);
			if (neighbor != -1) {
				Join (neighbor);
				_joins[index].ca = true;
				LineSegment l = new LineSegment ();
				l.start = _triangles[index].circumcenter;
				l.end = _triangles[neighbor].circumcenter;
				_lines.Add (l);
				_regions[_triangles[index].c].PushLine (l);
				l.Flip ();
				_regions[_triangles[index].a].PushLine (l);
	private void Join () {
		_joins = new TriangleJoins[_triangles.Count];
		for (int i = 0; i < _triangles.Count; i++)
			_joins[i] = new TriangleJoins ();
		Join (0);
	public LineSegment[] Lines () {
		return _lines.ToArray ();
	//This is our starting point. Pass in an array of points here,
	//and then extract the results from the public array of 
	//VoronoiRegions in _regions.
	public Voroni (Vector2[] points) {
		_lines = new List<LineSegment> ();
		_triangles = new List<Triangle> ();
		_regions = new VoroniRegion[points.Length];
		_points = points;
		for (int i = 0; i < _regions.Length; i++) {
			_regions[i] = new VoroniRegion (points[i], i);
		Triangulate ();
		Join ();

I apologize for putting this wall of code here. I really need to find a WordPress plugin that will let me hide big stuff like this so that people who care can click to unroll it, and everyone else can just keep scrolling. Maybe you appreciate seeing the code, maybe you’d rather I put it inside a download link. Whatever.

The point is, we got this job done in under 250 lines of code. That’s pretty good.

On the other hand, I never did learn the most important thing, which is: How the heck are you supposed to pronounce “Voronoi”?! I checked YouTube and I heard people use both “voroh-noy” and “voor-onny”. (Sounds like “Poor Johnny”.) In my head I’ve been pronouncing it “Vore-oni”. That’s certainly incorrect, but I like it because it makes this sounds like some kind of pasta: Macaroni, Ravioli, and “Voroni”.

So we’re done. The problem is…

I Don’t Really Need This Thing

My street-building code struggles when the angles get acute or when two intersections wind up too close together. Two adjacent roads will end up overlapping, which screws up their polygons, which causes a bunch of obnoxious z-fighting. The last thing I need is a system that will make the street connections even more difficult. This code I just wrote can generate different regions so I can have different buildings in different parts of the city, but I haven’t even made a proper building generator yet.

So why am I ignoring the core task (making buildings) to work on a bit of support code that’s an over-complicated solution to a problem that I don’t have yet, and which makes the existing problems even worse?

This is not the first time in the project I’ve gone off-mission and begun messing with things that don’t matter. What’s wrong with me?




It’s Unity. Or rather, it’s the process of learning Unity. It’s just so relentlessly frustrating. It would be one thing if I had to stop every fifteen minutes or so and read some documentation. That would actually be pretty nice. That sounds like a fun afternoon. Instead, it’s this never-ending rabbit-hole of mystery and bafflement.

I’ll run into some problem. The manual doesn’t have any clues. There’s an archive of an instructional livestream on the topic, but this is a problem that could be sorted out in two sentences and shouldn’t require watching an hour of unedited video.

So I turn to the forums. Someone asks a question that sounds 85% like the problem I’m having. They get three contradictory answers. I try the top answer and it doesn’t work in the version of Unity I’m using. I try the second answer and it sort of solves the problem, but creates a new one that sends me back to searching. So then I plunge down THAT rabbit-hole and end up in the same cycle of not finding anything in the manual, skipping a huge video, and going back to the forums. After an hour of that – assuming I don’t get sucked down a third rabbit-hole – I’ll give up, spend half an hour spooling through one of these videos, and discover it doesn’t actually answer my question.

Unity is really powerful. You can do amazing things with it. Stuff that might take hours on another platform can be done in seconds. But then you’ll run into something that should be trivial and ends up being insurmountable.

Perhaps an Example Would Be Useful?

The custom dialog I made for generating my city. This bit was effortless. I just told Unity which variables I wanted to edit and it made the interface for me.

The custom dialog I made for generating my city. This bit was effortless. I just told Unity which variables I wanted to edit and it made the interface for me.

I have a script that builds my city and populates it with objects. I’ve got it all wired up in the editor so that I can press a button and get a city. Then I can fiddle with some sliders, press the button again, and get another city with slightly different properties. The problem is that I need to clean up the old city, which means deleting objects, and Unity does not like you using code to delete objects in edit mode. Oh, it will let you create them by the thousands of you like, but then I guess you’re supposed to manually delete them by hand?!?

Let’s set aside my city, which I admit is a pretty complicated use-case. Let’s say you’ve got a basic shooter level and you’ve created a script that will scatter healthpacks around. You hit the button, and the script populates the level with healthpacks. Maybe you think there are too many, so you adjust the properties and hit the button again. Ideally, the script should find all objects of type “Healthpack” in the scene, delete them, and then add new ones. So you write some code:

GameObject[] medpacks = FindObjectsOfType<Medpack>();
foreach (GameObject other in medpacks) { 

But then you hit the button and the console is flooded with errors:

Destroy may not be called from edit mode! Use DestroyImmediate instead.

Oh, okay. This is something I’m only doing in the editor, so I guess that makes sense. I’ll just change Destroy () to DestroyImmediate () and…

Destroying components immediately is not permitted during physics trigger/contact, animation event callbacks or OnValidate. You must use Destroy instead.

This is a really simple thing we’re trying to do here. Absolutely trivial. And yet if you dig deep enough in the forums you’ll find people with all kinds of hacks to make this trivial action possible. The best solution I’ve found so far:

foreach (Transform child in MedpackContainer.gameObject.transform) {
	UnityEditor.EditorApplication.delayCall += () => 
	if (child.gameObject != null)
		DestroyImmediate (child.gameObject);

So you round up all the objects you want to kill, and then you kick off a delayed coroutine (kind like a new thread) to delete each one of them. This seems like a horribly over-complicated solution to the problem and I don’t even understand the syntax happening around that delayCall thing.

It took me a few hours to find that solution. I tried a lot of other things, which either failed utterly, weren’t viable in this version of Unity, or simply moved the problem to somewhere else. (I found one that did manage to kill the desired objects, but due to the way it juggled references around it also wound up deleting some of the new objects I’d just created.)

One of the Unity developers noticed this trap way back in 2014. And yet here we are, four years later, trying to piece together a convoluted solution from snatches of random forum code to solve a trivial problem with no guidance from the documentation.

I run into stuff like this constantly, and it’s just demoralizing, which is why I just spent the afternoon cooking myself a big plate of voronoi. It wasn’t something I needed to do, but it was a straightforward problem with known solutions and enough documentation to set me on my way. I could spend a few hours writing code instead of wading through noise in the forums.

The longer I use Unity, the more I’m impressed by its speed and capabilities. This is an amazingly powerful tool and when things work the way they should it makes me feel like a one-man AAA development studio. But that power is so deeply hidden that I don’t feel like I’m learning Unity so much as reverse-engineering it.

Maybe this procgen stuff is just too different from the “intended” Unity workflow. Maybe if I was sticking closer to the script I’d have an easier time learning. I don’t know.

Comments (96)

  1. Thomas says:

    and I don’t even understand the syntax happening around that delayCall thing.

    It seems that delayCall is an event and you’re adding an eventhandler to it. But instead of declaring a myEventhandler function and doing delayCall += myEventHandler you’re instead adding an anonymous function directly using the lambda syntax.

    • Ace Calhoon says:

      Came here to say this.

      They’re called “lambda expressions,” but they’re basically just inline functions. The two parenthesis are a placeholder for the (empty) parameter list. Then you have an arrow, then you have the body of the function (wrapped in curly braces because it’s more than one line, although it probably doesn’t have to be in this case).

      The neat thing about using a lambda here (instead of defining the function and then referencing it by name) is that you have access to the parent scope (e.g. child.gameObject).

    • Olivier FAURE says:

      I’m so used to anonymous functions after a few months of JavaScript coding, I didn’t even realize that was what Shamus was confused about. I though he was talking about the foreach loop or something.

      (also, using “operator+=” to register an event? Whoever designed *that* will burn in programmer hell)

      • King Marth says:

        Ah, operator overloading. One of C++’s many foot guns that made it into C#. I remember a line from a C# compiler guy’s blog, where C++ was known as the Pit of Despair that you had to climb out of, and his goal was to make C# the Pit of Quality where the default, blind thing to do would give you something useful anyway.

        I generally like C# event syntax. You declare your event in the same way you declare the delegate/function signature the event expects for callbacks, then you can hang any number of callbacks onto the event and it will fire them all when you trigger the event. Nice and clean and safely typed.

      • default_ex says:

        Using ‘+=’ and ‘-=’ to add and remove delegates to and frame a chain of delegates makes sense in C#. Your literally adding and removing delegates from a linked list of delegates, what better operators than ‘+’ and ‘-‘ to represent those actions. If you want to traverse through the list, it does have functions for that buried in the Delegates class and much more advanced functionality in reflection. In C# that stuff isn’t just hacked into the API, it’s a core feature of the language and feels like such using it. Not many languages where you can have both managed and unmanaged functions coexist together in the same chain of function pointers (essentially what delegates are). It’s sad that there aren’t many libraries for C# that utilize that last point to any good extent, it’s a perfect fit for OpenGL considering the vast majority of OpenGL can be bound to C# data types without any sort of marshalling getting involved and can be invoked directly with function class mechanisms normally used for pure C# functions (meaning no interop performance penalty like you see with traditional interop techniques).

    • Abnaxis says:

      Wait, so you’re registering a lambda function into the *editor*? From the game!?

      Who the hell thought that having a game you’re developing get its fingers into your development environment was a good idea?

      • Nick Powell says:

        That’s one of the big design choices in Unity you have to get used to. The editor is the exact same code as the game engine, only with some extra features attached. If you want to have your game logic run in the editor you just add an attribute to tell it to do that. The advantage is that every single bit of code that interacts with unity does so through the same API. The disadvantage is that you can really fuck up your scene if you’re not careful with what code you run in the editor. Also you can freeze the whole editor by writing an infinite loop into a game object script.

  2. Daemian Lucifer says:

    If you can draw a picture,you can always try google image search.Its not as precise,but it can work sometimes.

    • Olivier FAURE says:

      I don’t think Google Image Search can handle arbitrary images; I think they just look for images exactly identical to the one you’re giving them, with a few variations like different compression or image size.

      • Daemian Lucifer says:

        It always gives you a suggestion for what it guesses it might be,even if its just a random doodle.It may not always be right,but those guesses can lead you to the right path.

        I just drew a few random lines,and it suggested line art to me,with an article from wikipedia,and some random line images.Neither of those looks like my jumbled mess,because they are actual images(a fish,a leaf,a hand)

      • Daemian Lucifer says:

        And now that I had more time,I tried google image search for that thing Shamus drew.Two articles for graphic design,and some pictures.Third of those pictures,however,is from here:


        That does look like it wouldve helped.Google image search has advanced enough that it actually can be helpful.

  3. Ivan says:

    I didn’t spit-take, exactly, but when that bit about deleting came along I did say “Wait, what?” out loud to no-one. I was nodding along, figuring, ok, so you have a cleanup function that runs before all the generation happens, no worries there. But, wow.

    Without googling the syntax, that delayCall stuff reminds me of something I used to do in Javascript, that applied a function to each item in a collection as it iterates through. I don’t remember the why’s and how’s exactly, but this may be a similar thing.

    • bubba0077 says:

      I was thinking it reminded me of Java proper, where GUI tasks (and only GUI tasks) should run on the event dispatch thread (because GUIs aren’t thread-safe), so you use invokeLater or invokeAndWait for the EDT to pick them up and run them. There is likewise a method for shifting long tasks to a background thread from the EDT. I wonder if something similar is happening here. (I know little about Unity or C#.)

    • Nick Powell says:

      delayCall is an event, which is a C# type that lets you attach functions to it. Then the owner of the event can just call the event like a function and every attached function gets called automatically.

      That line is attaching a lambda to the event, and unity presumably activates the event when it’s ready and clears all the functions attached to it so they’re only called that one time.

  4. EwgB says:

    The proper pronunciation would be voh-roh-noy. A pretty normal Russian name – https://en.wikipedia.org/wiki/Georgy_Voronoy

    I love those diagrams. We had to code a couple different algorithms to generate them in Into to Computer Graphics at university. I especially love the sweep line algorithm (also known as Fortune’s_algorithm), though I still can’t tell how it works.

    • Viktor Berg says:

      The surname actually comes from the russian expression “voronaja stal'”, which is steel treated in such a way that it is blackened. It’s called bluing in English, apparently.

    • Droid says:

      I just learned about Fortune’s algorithm from the link, so take this with a grain of salt, but to me, it looks like the algorithm constructs the diagram more or less in the following way.

      Throughout, we use the fact that a parabola p is the set of all points X that have the same distance to a fixed point Y as to a line g, so
      p = {X in IR^2:||X – Y|| == ||X – F_g(X)||}
      where F_g is the foot of the perpendicular, the point on the line g with the smallest distance to X.

      Assume here that the line sweeps from left to right.
      So as soon as our sweeping line g crosses the first point, it constructs a complete parabola, opening in the opposite direction, so to the left.
      As soon as a second point is crossed, a new parabola opening in the same direction is constructed, and so the two parabolas have to cross each other in exactly one point. That’s the first point to keep track of.
      The algorithm continues until it finds a third point, and constructs a new parabola, and so on and so forth.
      For each point A, keep track of the first intersection point of their respective parabola p_A (with any other parabola) on the “upper branch” and on the “lower branch”. Every point except the uppermost and the lowermost processed point have exactly two such first intersection points, one above them, one below.

      Now, the pairs of points that share one such “first intersection point” are neighbours in the diagram. So, as Shamus described in the article, if the point B has neighbours A and C, we have to get the circumcenter point of the triangle ABC to get the vertices of our Voronoi diagram.
      Thankfully, our sweeping algorithm makes us able to skip most of the possible triplets of input points (X, Y, Z), so that we can concentrate on those that actually neighbour each other.

      The next interesting step happens when the sweep line exits the first circumcircle of three neighbouring input points. At that point, the three parabolas meet in a single point, or they would if you could stop at the exact moment the line exited the circle (instead of using small, fixed increments).
      At that point, you simply look at the three points in question and fetch the circumcenter point (that you were keeping around for just such an occasion!) and make that the first point in your diagram.

      Why wait for the line to exit the circumcircle of the three points? Because just because A, B, C are neighbours RIGHT NOW does not mean they will be when the algorithm finishes. In fact, every input point P that lies within the circumcircle of three others, but to the right of all those three points will screw up the “neighbours” algorithm until the sweep line crosses over P.

      Once the sweep line has finished its motion, connect all the circumcenters that have at least one construction point in common.

      When you’re finished with that, look at any points P that were not used to construct exactly three circumcenters (all the points on the outside which all have unbounded regions) and look at the (one or two) neighbouring points that they have, as well as any circumcenters that used P in their construction.
      Due to how the algorithm works, each such circumcenter C was constructed from P and at least one neighbouring point Q. Now you simply construct the line perpendicular to the line PQ that goes through the circumcenter C and draw the half of the line (ray) that starts in C and points towards the line PQ (the ray that crosses PQ).
      Repeat for every neighbouring point Q and every outer point P and you’re done!

      Of course, smarter minds than I will have found more efficient ways to implement this, but this seems to be a working step-by-step guide that loosely follows what that algorithm does.

      Hope you found this helpful!

  5. Tizzy says:

    I’ve never heard anyone pronounce it “voor oony” or whatever. The guy was Ukrainian, so it sounds probably “varanoy” almost like “paranoid” without a d.

    Anyway, superb trolling by Shamus in misspelling it Varani in the code.

    • Echo Tango says:

      With that spelling in English, and the Ukrainian background, I’d say it’s more likely “voar ohh noi” (like a fast “boar” a truncated “oh” like the Ukrainian word for God (unless I’m misremembering, it’s “Boh”) and noi like Android with an “N”). But I’m also a Canadian who speaks terrible Ukrainian.

  6. Knut says:

    Isn’t these diagrams what we did with school coverage in Sim City? :)

    • Decius says:

      Those diagrams on the non-Euclidean geometry that accounts for travel distance variables is how good school districting works.
      Transforming maps into an equal-travel map is nontrivial.

      • Niriel says:

        Non trivial for sure. Is that even a continuous transformation?

        • Droid says:

          As soon as there’s one home with two equally fast routes to the target, it can’t be.

          After all, there’s a neighbourhood that is mapped to a disconnected set. ;-D

          But nerdy math jokes aside, that depends wholly on the topology you choose on the image space (assuming you’re using the Euclidean norm/topology in the standard map). It’s not even clear what a useful topology would be on that space. Maybe some sort of travel-distance-from-center metric.

  7. steve? says:

    A thought and a question.

    The thought:
    Would it be worth having quick bleg posts or something to deal with these questions? I know sometimes wading through to get the answer to a question provides some meat to the post, but often I’m guessing that a quicker answer to “what is this stained glass algorithm called?” would be helpful. For instance, if you had posted that question on the blog, I could (and would) have instantly told you that it’s a Voronoi tessellation (or at least as instantly as I read it).

    The question:
    How does anyone use Unity professionally? Is this in the core curriculum of those game dev schools? Unity 231: More Undocumented Hacks. Or do studios have support contracts where they email a Unity dev whenever they run into a problem? It seems insane that a mainstream development tool would have such terrible documentation.

    • Shamus says:

      “How does anyone use Unity professionally?”

      I wonder that myself. Maybe they just spend hours watching videos? Maybe the docs were better in the past? Maybe what I’m going through is just the normal Unity newbie initiation and everyone has to go through this? I don’t know.

      • Daemian Lucifer says:

        Wait…I followed this comment a minute ago and it was not displayed….Did….did the spam filter catch your comment?

        • Niriel says:

          Wait, you can subscribe to comments? I read this blog on my phone on the bus, I haven’t seen the pc version in years. Is there a button, or you do that with rss/atom, what’s your secret?

      • Olivier FAURE says:

        I’m guessing part of it is having senior developers around who can teach junior developers about the most obscure parts.

        • Chiller says:

          That’s exactly it. I’m a videogame dev and while I haven’t worked with Unity for professional development, every game engine I encountered came with its own annoying issues and surprising pitfalls, which were only mitigated by having someone else on-site who knew how to work around them.

      • Abnaxis says:

        It actually reminds me of my old job making web UIs for large machinery (think like internet of things for “things” as big as a house). There’s always a canned bit of software that does everything the designer thinks you’ll ever need to do with it, but leaves out an obvious thing that everyone wants to to. And if you want users to be able to use your interface to do (thing) you basically have to tear their code apart and fix it yourself or declare it impossible. Most people just declared these problems impossible, but I prided myself on winning quite a few loyal customers by managing the former.

      • Ilseroth says:

        I’m at least trying to use Unity professionally, but I also am not dealing with proc gen stuff and when I did proc gen for other projects, I did all of the generation during project runtime, and it was mostly fitting together pre-existing pieces and art, not creating new stuff.

        So my workflow for this project, if I was given it in a Game Jam, would probably be
        -Make the Base City Block pattern models (roads+ where buildings fit)
        -Code a way to fit them together without any seams/issues in random patterns
        -Set up a system of building generation in spots on the base city blocks that allow for certain building footprints per block (so you can get some different shaped buildings. As well as additional props (city lights, fire hydrants, ect)
        -Model/Texture a bunch of buildings, preferably getting at least a few per building footprint
        -Test, make sure it all works
        -If time allows, add modular additions to buildings (or just more buildings that are variants) that are randomized to decrease cookie-cutter effect.

        It wouldn’t be exactly the same thing you’re producing, but that would be my method of making a proc gen city builder in Unity.

      • Pylo says:

        I’m using it professionally (incidentally I spent most of the time on a mobile city builder game) and I pretty much went through the same thing you are going now. Unity offers a LOT of features and every single one of them is booby-trapped with these terrible design choices that you have to hack around. But the sad truth is that most development tools out there are crap and we just don’t have the time to build everything from the ground up so we take what we can get and be glad we don’t have to program by punching holes into cards anymore.

      • thesomethingcool says:

        Well, it helps to be in an environment where you can just ask a more experienced colleague for advice, rather than spend an afternoon divining the answer through the mess of tutorials and documentation. Plus, I’m pretty sure most game dev involves making ugly hacks to get around flaws in a byzantine system anyway, so the pros must feel right at home with Unity!

    • Redingold says:

      Isn’t “mini blogs” just what twitter is for? A quick tweet might be helpful if you get stuck on something like this for an extended period, and I certainly check my twitter more frequently than I check this blog for updates.

    • Olivier FAURE says:

      I never used Unity professionally, but as someone who tried a few game engines and is planning to write my own, here’s my guess:

      The major reason is that there are very, very few usable game engines out there. If you want to create a game with graphics remotely approaching AAA level (of 5+ years ago) without having an AAA budget, your choices boil down to Unity or Unreal Engine. Or Godot3d (open-source), but most people don’t know about that one.

      If you’re ready to code the physics, sounds, etc part yourself, you can maybe use Ogre3D (open-source), but its documentation is even worse than Unity.

      Or you can write your own game engine, in which case, unless you’re doing 2D, you’re in for a few years of doing nothing *but* your engine. You need to write or find 3D effects, physics, optimizations, input handling, GUI, sound management, AI management, an asset pipeline, a level editor, documentation (unless you’re doing a one-man project), etc. Each of which must work multiple graphic cards, consoles, Android, iOS, etc. Also, good luck having an asset store with a community as massive as Unity’s.

      Now, Unity’s implementation of graphics, physics and multi-platforming is amazing, and its implementation of everything else I mentioned is subobtimal or downright mediocre, which is part of why you see many games with great-looking graphics and bad [everything else] on Steam these days.

      But unless you’re willing to spend years trying to do better (and you’re not going to do better), then Unity is the best of a bunch of crummy options, so people work around its defects.

    • Xeorm says:

      As someone that did use Unity in school classes, I can say it was like most tools. Give a short powerpoint/tutorial on how to do the things you needed to do in class, followed up with projects/homework that used what you learned. If you had questions you’d explore different options. Ask the teacher or other students, check online, etc. There’s a lot of “informal” knowledge out there, and it’s hardly like Unity is special in that regard.

      Documentation in general tends to be something that’s skimped on. Unity isn’t what I’d call a mature program yet.

    • Matt Downie says:

      Ways to cope with the problems of using Unity professionally:

      (1) Go through the usual rigmarole of searching for hacky solutions to the problem on the internet; make up for the lost time through the things Unity does well.

      (2) Do only simple things of the sort that the Unity developers expected. Most projects don’t require you to destroy objects programatically while editing the game. You have professional artists making the city.

      (3) Find an ‘alternative’ method of doing things. If I couldn’t figure out how to auto-destroy objects once I’d created them in the editor, I could probably:
      – Create them while the code is running; most of the editor tools should work just fine from within the game.
      – Create them all within a single parent object that I can delete manually with a couple of clicks.
      – Turn it off and on again every time. (Once I got into a situation where Unity would crash 50% of the time whenever I stopped running the game. I couldn’t fix it, but I got used to it. Reloading Unity is quicker than compiling and running a typical console game.)

      • Olivier FAURE says:

        – Create them all within a single parent object that I can delete manually with a couple of clicks.

        Yeah, that was my first thought as well. Doesn’t work if you want to create complex hierarchies, but good enough for 99% of cases.

  8. Paul Spooner says:

    I’m doing a similar Voronoi diagram kind of thing, except in 3d. http://peripheralarbor.com/gallery/v/CG+Art/scripts/crystal/
    The code is significantly more complicated:
    But it can also do weighting, so some points are weighted more highly than others, which offsets the boundary lines. You can also do gradual point distortion and sub-division, like so: http://peripheralarbor.com/gallery/v/CG+Art/Elseinct/Elseinct_Chamber08.jpg.html?g2_imageViewsIndex=1

    A decent way to get evenly spaced centers is to place them on a grid or matrix of some sort, and then shift them with a small random offset. I know Spore used some sort of uniform noise model that placed objects randomly but semi-uniformely in space… but I’m running into the same I-don’t-know-what-it-is-called-so-I-can’t-find-out-about-it-on-the-internet problem as you were with Voronoi charts.

    • Redingold says:

      You can use a Poisson disc distribution to get something that’s randomly distributed while still being evenly spaced.

      They use Voronoi cells for shatter physics, but it always looks fake, because the cells are always convex, unlike real debris. I wonder if you could make a more realistic looking shatter effect by breaking an object up into Voronoi cells and then randomly joining some adjacent cells together so you had at least some non-convex pieces?

      • Droid says:

        If the object in question isn’t brittle but can be deformed by force without breaking, another idea would be to deform the Voronoi cells by sampling points on their boundary, and moving all points a bit towards or away from the center, with some small smoothing in-between to make it look jagged, but like one big force did this, instead of N random ones. So something like normal- or even Cauchy-distributed random variables X_n (n = 1, …, N), and

        boundary_new = boundary_old + [X_1, X_2, …, X_N] * (center_point – boundary_old).

        Assuming your language can handle an instruction of the form “a point minus a set” and pointwise multiplication of sets (of the same size).

        If you’re in 3D, maybe even add another such deformation with only positive random variables and a point of origin of the force instead of the center point of the cell.

    • thesomethingcool says:

      I have nothing to contribute, I just want you to know your crystal project is cool as heck.

    • Noumenon72 says:

      Really cool project and cool idea for a D&D challenge.

      Can I suggest where you have

      # If it is ever “None” something is wrong,
      # probably the starting planes are non-water-tight.

      That you replace it with

      if these_points is None:
      raise AssertionException(“No edge points found — probably the starting planes are non-water-tight.”)

      It seems like continuing through the loop ignoring planes will just confuse you later when a plane vanishes because it has no edge points for some other reason. Or if you do want to continue through the loop anyway, change the comment to reflect that this is a normal case and nothing’s really wrong.

      # Skip cases with no edge points, for example, ones whose starting planes are non-water-tight.

  9. James says:

    I know the point of this post wasn’t really this particular problem, but still: this is a really weird problem to run into. Destroying stuff in the editor with DestroyImmediate in response to a button press should work just fine, no work-arounds required. I just tested it out in Unity 5.6 (which is a few versions back now, but not too far) with this editor script:

    public class SpawnerInspector : Editor
    public override void OnInspectorGUI()

    if (GUILayout.Button(“Cleanup and Spawn”))

    private void CleanupAndSpawn()
    var spawner = target as Spawner;

    // Destroy all children, then spawn new ones.
    for (int i = spawner.transform.childCount – 1; i >= 0; –i)
    if (spawner.prefabToSpawn != null)
    for (int i = 0; i < Random.Range(1, 100); ++i)
    Instantiate(spawner.prefabToSpawn, new Vector3(Random.Range(0f, 100f), Random.Range(0f, 100f), 0f), Quaternion.identity, spawner.transform);

    It doesn’t throw any errors for me. I guess there might be something going on with the actual objects you were spawning that could’ve been throwing it off? Like maybe if they had some OnValidate scripts or something that were still running for some reason, though that seems unlikely. Weird. I wonder what freaked it out?

    (Argh, don’t know how to format the code correctly in a comment.)

  10. Matt van Riel says:

    Shamus – Go to your plugins, add new, search for ‘click to show’ or variations. There’s a good few plugins that do what you want, using shortcodes you can embed code within and the like.

  11. Legendary Teeth says:

    Since you are building a city, a lot of the math concepts you are looking for (like the voronoi diagram) can be found under the umbrella of GIS, or geographic information systems. In particular that example of it being used in the Broad Street pump (see the excellent Extra History series of you haven’t) can be thought of the inception of GIS.

  12. John says:

    The Museum of Science & Industry in Chicago has some interactive Voronoi diagram displays. They’re like–wait, scratch that–they are giant touch screens, each with a bunch of center points and the associated regions. As you drag the center points around, the display re-draws the regions in real time. The displays are part of a “shapes and patterns found in nature” exhibit, along with other concepts like the Fibonacci sequence.

    • Paul Spooner says:

      Oh man, I use the Fibonacci sequence (and it’s limit, the golden ratio) all the time in design. One of those little secrets of math that you don’t even know that you needed, let alone what to call it.

      • John says:

        There’s an interactive Golden Ratio display too. You stand in a designated spot while a computer uses some kind of Kinect-like camera to identify your head, feet, hands, hips, elbows, knees, and so forth. Then the computer produces a giant (as in wall-size) stick-figure display of your body and compares ratios from your body to the Golden Ratio.

        • Kathryn says:

          *takes notes for upcoming trip to Chicago*

          I’m also planning to hit the Field Museum and see Sue. Maybe the Shedd Aquarium too. Hopefully there will be neither Kemmlerites nor Denarians around.

          • John says:

            Any relationship between the fictional Chicago of the Dresden Files and the actual Chicago is purely coincidental. The least believable thing in the books isn’t the magic, it’s the assertion that a teacher could afford a house in Wicker Park.

  13. Olivier FAURE says:

    Oh god, the voronoi diagram.

    A few months ago, I worked on a small Unity project with a friend, and he *absolutely* wanted to integrate his voronoi implementation into the game. Even though we were making a lane-based tower defense game, and procedural generation didn’t really bring much to the game, and we hadn’t even implemented the engine yet.

    I mean, I get why he wanted it (he coded a cool thing and he wanted to use it) but man was that an unnecessary source of friction.

  14. Riley Miller says:

    Unity’s problems come from two main sources.

    1: Attracting investors > supporting devs. Unity Technology isn’t a publicly traded company (yet) but it has done a number of fundraising rounds to the tune of hundreds of millions of dollars. Unity Technology doesn’t make games internally and because of that fixing bugs and long standing issues like terrible documentation is lower priority than adding shiny new features. When an engine is adding PBR pipelines and a job system but has an input system bordering on barbaric and a bug ridden UI you have a problem.

    2: The asset store. Unity actually makes money off of being unfinished. Suppose, like me, you are making a local multiplayer Unity game that can support mouse and keyboard, xbox, and dual shock controllers. The default input system is totally unable to cope with this seemingly reasonable situation so you have two options. You can either do what I did and spend days writing a layer between Unity’s input system and your game, or you can pony up $45 and get the Rewired package. Unity gets a cut of that sale.
    Before Text Mesh Pro was acquired by Unity you had a similar situation. The engine’s default text rendering was absurdly limited and a third party asset stepped up to fill the void. When Unity did buy Text Mesh Pro and make the asset free you could argue they did it against their business interests.

    To be clear I’m not saying that games made with Unity are necessarily bad nor am I claiming the Unity devs are lazy. But the business incentives of the company do not line up with making stable and mature software.

    Unity makes easy things easier and hard things harder. If you want to slap together a 3d prototype there is no better place to do it. But if you want to release a polished stable product? You’re in for a rough time.

  15. Paul Spooner says:

    Typo alert: “which what I did” needs an “is” or something.

  16. Daemian Lucifer says:

    Unity is really powerful. You can do amazing things with it. Stuff that might take hours on another platform can be done in seconds. But then you’ll run into something that should be trivial and ends up being insurmountable.

    But isnt that basically true for any programing tool?Or any computer tool in general.

    • Paul Spooner says:

      It’s always nice to have the right tool for the job. Some tools are right for a lot of jobs, and some are only right for a few. Then there’s the wieldiness of the tool, and the skill floor, and the cost.
      But no. Not all tools are as oddly shaped as Unity.

    • Olivier FAURE says:

      Ideally, you want tools that are modular, with clear demarcations between what the tool does well and what it’s not made for, and easy way to combine it with other tools to shore up its weaknesses.

      Unity isn’t really that; it’s meant to be the beginning and the end of your code pipeline. If there’s a part of Unity that doesn’t work well, your choices are to hack something together “manually”, to find something in the asset store that does it for you, or switch to a different engine entirely.

  17. Hector says:

    Forget Unity – Shamus, tell us what you think of Rage 2? WIll MegaTextures destroy the game? (Probably not.) Will is continue the story of the Single Most Boring Apocalyose Ever? (Probably yes.)

  18. ShivanHunter says:

    Obviously, you should scrap everything you have on the project and redo it all in Unreal ;)

  19. Kronopath says:

    Man, the transition between the first and second steps in the Voronoi diagram images really tripped me up. You have one image that generates a whole bunch of points, then you say that you should draw triangles that use those points as their corners, and then the next image… has a whole bunch triangles whose corners are completely new points and the red points from before are instead used as center points for the circumcircles. And so the explanation doesn’t really make sense with the diagrams.

    I think it would make a lot more sense if the black points were shown in the first diagram rather than the red points.

    • Philadelphus says:

      Ok, it’s not just me that got completely confused by that then. I thought it was about drawing circles through the red points too.

    • Mousazz says:

      What’s more, the second Voronoi diagram image (taken from Wikipedia? I see the datagenetics.com link has the same two images, except color-inverted) has the two red circumcenter points at the bottom-right so close together, they almost look like one point (and their (slightly thicker) circle looks like it encompasses all four points of the two bottom-right triangles as well, confusing me even more, since it breaks the rules of making the Delauney triangulation).

      • Droid says:

        If there happen to be four points that lie on the same circle, there is nothing to be done about that. It doesn’t break any rules. The rules only state the other points may not be within the circle. The border is fine. You’ll have to choose one of the segments for the Delaunay triangulation, but it doesn’t matter one way or the other, especially not for the Voronoi diagram.

  20. thesomethingcool says:

    At the risk of starting a flame war…
    I’m starting to think that Unity is the PHP of game engines :)

  21. Warclam says:

    I actually made a procgen city in Unity as a course project. We didn’t find it difficult, but that’s entirely because of our existing experience with Unity.

    I can confirm that even as a habitual Unity-user, I do in fact spend a lot of time looking up how to do stuff on forums.

  22. Kylroy says:

    I believe you meant to caption that picture “introspeción intensifie”.

  23. Anachronist says:

    Hmmm. When I saw the lead image in this post, I thought “oh, a voronoi image.” Having a background in physics, if I couldn’t remember the name, I would have searched for “crystal grain boundaries”. Take a shallow dish with a saturated solution of something, throw in a few nucleation sites (grains of sand or whatever), and as the liquid evaporates, crystals will grow uniformly outward from the grains and form voronoi boundaries where they meet. This assumes the growth is roughly circular from the nucleation sites.

  24. Page 12 of this presentation gives a clever approximation of a Voronoi diagram exploiting the z buffer:

  25. Daemian Lucifer says:

    I did this poll because Unity’s Mathf.Sign () returns 1 for 0, contrary to every other version of the same thing I’ve encountered elsewhere. It looks like this is UNUSUAL behavior, but not without some mathematic justification.

    Hmmm….That means that unity sees 0 as a positive number.Its mathematically wrong,but I can see how it would make sense from a programming perspective.

    • Shamus says:

      That one really tripped me up. I find Sign that returns -1 0 , or 1 to be immensely useful for figuring out “which way is this thing going” sort of problems. It’s good for movement controls. (Good for turning analog inputs into hard ones.) In this specific case I was applying it to the scrollwheel, because scrollwheel controls often count each “notch” as (say) 35 or so.

      But a Sign () that returns -1 or 1 by turning 0 into 1? I don’t know what I’d use that for.

      • Pylo says:

        I was similarly tripped by the Unity’s (and also standard C#) midpoint rounding convention.
        In C++ the midpoint numbers (like 3.5 or 4.5) are rounded “away form 0” by default, like so:
        round(3.5) -> 4
        round(4.5) -> 5

        In C# (and Unity) the default is to round to “nearest even integer”, like so:
        round(3.5) -> 4
        round(4.5) -> 4

        So in C# sometimes it rounds up, and sometimes it rounds down which caused some weird behaviour in our game. It costed us a couple of hours of bug hunting but we did learn something new in the end (apparently there are a lot of different midpoint rounding conventions).

        Also, just a note: there is a Unity Mathf namespace, but there is also a C# Math namespace that you can use. And Math.Sign (the standard C# one) works as you would expect:

        Not sure why Unity bothered to reimplement it, I guess it’s an optimisation because C# Math seems to only work with double values while Unity.Mathf works with float values.

Leave a Reply

Comments are moderated and may not be posted immediately. Required fields are marked *


Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun.

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>