This blog post refers to an easter egg that’s hidden on my website. If you’d like to try finding this for yourself, now’s your chance to do so, as the rest of this post will contain “spoilers”.

Hint: Look for a constellation

An aversion to algorithms

For the first few years of my career I thought that “writing algorithms” was a special type of programming and required a unique skillset.

My experience with programming consisted mostly of taking things that other people had built and connecting them together in new ways. The open source community publish functions and libraries for doing all sorts of things, from parsing YAML to unattended typesetting, and by stitching these together you can achieve a lot. I thought that these functions I was stitching together were written by “algorithm developers”, people on a fundamentally different level to me.

I had a full time job, and I considered myself a fairly good programmer. But I’m self-taught, and at the time I didn’t think I’d ever be able to write algorithms. I thought you had to go to university to learn that skill. I also thought that I’d never need to, since I was already doing alright for myself without.

But it turns out that algorithms aren’t actually so scary. This is the post that I wish I could send my past self. Here I am trying to write the post that I wish I could have read at that time.

The problem

When I was just getting started with the HTML5 Canvas API, one of the early things I worked on was a twinkling star field.

View toy

The effect was very basic, but I was happy with the result, and I thought it would make a nice background for my website. But I also knew that I wanted to add some easter eggs to my website, and the space theme gave me an idea.

Asteroids is a classic arcade game, but I always found it somewhat unsatisfying. The way that shooting an asteroid spawns two smaller, faster asteroids never felt to me like the asteroid was being believably destroyed. Additionally, I thought the way that the asteroids simply respawned after they were all destroyed was a bit anticlimactic.

I wanted to build a game inspired by Asteroids where your weapon (a laser) would cleanly slice the asteroids along your line of aim. There was just one problem: how would I actually build something like this?

A mental block

At the time that I was trying to build this small game, I had not written anything that I would consider an “algorithm”. What did “algorithm” mean to me at the time?

Looking back, I guess the distinction to me was that problems where I had an idea of where to start and what would be involved in solving them were normal programming. Problems where I had no idea where to even begin approaching them required “algorithms”. Arthur C. Clarke said “any sufficiently advanced technology is indistinguishable from magic” and to me “algorithm” was a word that represented that magic.

The closest I’d come to writing an algorithm was porting existing algorithms, such as when I implemented the pseudocode from Wikipedia’s minimax article in C#.

But I really wanted to build this Asteroids knock-off. Nowadays if you Google “splitting a 2D polygon” you’ll find numerous helpful results, but back in 2017 I wasn’t able to find anything like this. (And believe me, I tried every combination of search terms I could think of.)

In desperation, I wondered: could I build it myself?

Designing an algorithm

Where do you start when designing an algorithm? I needed to start with one polygon and a ray, and from these produce multiple polygons that somehow represented the cut segments of the first polygon. This was overwhelming. I had no idea how to approach this.

In order to visualise the problem, I drew a simple asteroid shape on a piece of paper.

An irregular polygon which might charitably be described as "asteroid shaped".

How would you cut this in half on paper? The most obvious way is to simply draw a line through it.

The same polygon, but with a line drawn over it, bisecting it.

But has this really divided the shape in two? Or is it the same shape, but just with a line drawn over it? In your imagination perhaps it is the former, but if a computer follows these steps the result will most certainly be the latter.

Philosophy time: What really defines if an illustration of a shape has been cut? For my purposes, it’s the ability to move each piece individually. To move the two shapes around in paper, I’d need to break out the scissors. But obviously I can’t expect players to physically slice their monitors, so that’s not a good representation of the problem.

In order to be able to move the two shapes independently on the computer, all I needed to be able to do is draw them independently. So my new goal, how would I go about redrawing the two chunks of my asteroid apart from one another?

Two distinct polygons, representing the polygon divided along the line.

How could I do this? What steps should I follow? To make things easier, let’s consider what the process would look like to redraw one section of the asteroid on some tracing paper. Remember that the point here is to think very explicitly about something you’d usually do without thinking. So it’s good to go slow, break things down into small steps, and try to explain any thought processes along the way.

Where do I even start? I guess anywhere is as good as anywhere else for now. I could start by picking a random location and tracing along the initial shape. But as I trace, if I get to a point where my pencil touches the line, I’ll stop tracing the initial shape and start tracing the line instead. Then, when my pencil travels far enough along the line to touch the shape again, I’ll switch back to tracing along the shape.

A diagram depicting the process of tracing one part of the earlier polygon.

Then all I need to do is keep going until I get back to the starting point.

This is a great start, I can trace out one sliced fragment of the shape. But how can I guarantee that I trace out every fragment? In order to reason about this, let’s consider a more complex shape.

[aside] | Initially I thought that a good start would be to group the vertices of the asteroid based on which side of the cutting line they appear on. But after playing with this idea for a bit, I couldn’t think of what to do next. Splitting the points in this way had not actually helped me at all, it didn’t get me closer to the goal. So I scrapped this idea. | | When you’re trying something new, you won’t always nail it first time. Sometimes writing algorithms involves knowing when an idea isn’t working.

An S-shaped irregular polygon. No matter how charitable you are, you could not describe this as "asteroid shaped". A red line has been drawn across the polygon.

Previously when I traced the fragment, I started at a random point. But in order to make things a little more predictable, what if I instead find all the intersection points between the cutting beam and the asteroid, start at the first intersection point, and set out in a clockwise direction.

A diagram showing the same irregular polygon and line. Orange dots have been added at each point that the line intersects the polygon. The process of tracing the first part of the polygon has been started. The point at the first intersection is green to show that it's been used.

I’ll mark each of the intersection points that I’ve passed through as “used”. Then, once I finish drawing the first enclosed fragment, I’ll proceed to the next unused intersection point.

A diagram showing the tracing of all the parts of the polygon that lie on one side of the line. The intersections have been turned green as they have been used. The parts of the polygon that lie on the other side of the line have not been traced, but there are no unused intersections left for them.

You’ll notice that this has only captured the fragments on one side of the line, but all the intersection points are marked as used. What if I tweak the process so that I only mark an intersection point as used if I start on it, or if I move from tracing the line back to tracing the asteroid. When I move from tracing the asteroid to tracing the line, I will not mark that intersection point as used.

A diagram showing the step-by-step process of tracing each part of the polygon. Every part of the polygon has been traced.

Alright! That seems promising! Now the true test is whether I can convert these steps into code.

interface Vec2D {
	x: number;
	y: number;
}
type Polygon = Array<Vec2D>;
interface PolygonIntersection extends Vec2D {
	lineStartingPointIndex: number;
}

function splitPolygon(intersections: Array<PolygonIntersection>, polygon: Polygon): Array<Polygon> {
	const testedIntersections: Array<number> = [];
	const newPolygons: Array<Polygon> = [];
	for(const [i, startIntersection] of intersections.entries()) {
		// Start at the next intersection that hasn't already been used
		if(testedIntersections.indexOf(i) !== -1) {
			continue;
		}
		
		const currentPoly = [];
		newPolygons.push(currentPoly);
		
		let currentPointIndex = (startIntersection.lineStartingPointIndex + 1) % polygon.length;
		while(true) {
			// Trace along the existing polygon, adding each point to the new polygon
			const currentPoint = polygon[currentPointIndex];
			currentPoly.push({
				x: currentPoint.x,
				y: currentPoint.y
			});
			
			const foundIntersectionIndex = intersections.findIndex(i => i.lineStartingPointIndex == currentPointIndex);
			if(foundIntersectionIndex !== -1) {
				// If the current line contains an intersection with the ray...
				const foundIntersection = intersections[foundIntersectionIndex];
				const targetIntersectionIndex = foundIntersectionIndex + ((foundIntersectionIndex % 2 == 0) ? 1 : -1);
				const targetIntersection = intersections[targetIntersectionIndex];
				
				// trace until the intersection,
				currentPoly.push({
					x: foundIntersection.x,
					y: foundIntersection.y
				});
				// trace along the ray until the next intersection,
				currentPoly.push({
					x: targetIntersection.x,
					y: targetIntersection.y
				});
				
				// mark the second intersection as used,
				testedIntersections.push(targetIntersectionIndex);

				// and then continue tracing along the polygon from the location of the second intersection.
				currentPointIndex = targetIntersection.lineStartingPointIndex;
				
				// If we have arrived back at the intersection we started at, stop tracing...
				if(startIntersection.lineStartingPointIndex == targetIntersection.lineStartingPointIndex) {
					break;
				}
			}
			
			// and repeat for the next intersection.
			currentPointIndex = (currentPointIndex + 1) % polygon.length;
		}
	}

	return newPolygons;
}

And there it is, now it’s in code.

In order for this algorithm to work, I need to supply it with all the points where a line intersects with a polygon. I can obtain such a list by looping over each segment in the polygon and testing if that segment intersects with the line. In order to achieve this I need a way to find if a line intersects with a segment. And so it’s algorithms all the way down.

Is this all algorithms are? Just finding ways to break down complex problems into smaller ones, until we arrive at problems small enough that they can be represented by primitive operations? Hang on, we’re just… chaining together existing functionality in novel ways? Wouldn’t that mean that it’s not just algorithms all the way down, but it’s algorithms all the way up too?

Testing and iteration

Writing code is all well and good, but you also need to make sure that the code actually works. For the purposes of easy reading I have skimmed over this and included the working algorithm above. But my first attempt didn’t work so well.

Testing isn’t the main subject of this post, so I’ll keep this section fairly brief. But there are two things which I think are crucial to testing algorithms.

The first thing is the data that you’re testing with. You shouldn’t immediately try to test your algorithm in the wild. You should carefully create test data with a predictable result. (After all, if you don’t know what your algorithm should be outputting, how are you going to know if what it does output is correct?) Start simple with the test data (I started by trying to split a single square), and then build up to more complex data that tests edge cases and outlier situations. Once you’re confident that its working how you expect, that’s when you should start testing it against real data.

The second thing is a stepping debugger. If you do not know how to use your language’s stepping debugger, learn. You will not regret this. The stepping debugger will be your best friend.

Closing thoughts

They say that the word “algorithm” just means that the programmer doesn’t want to explain what they did. What I realised during this process is that the word algorithm doesn’t refer to any specific style of code. Writing algorithms doesn’t require a distinct skillset. All programming consists of writing algorithms, just at varying levels of abstraction. There are nitty-gritty bit manipulating algorithms, and there are algorithms to orchestrate the deployment of infrastructure.

We tend to use the word to refer to complicated logic, or maybe logic that we’re particularly proud of. But I think this can make them seem inaccessible to newer developers, who might see the word algorithm and assume that it refers to magic that they could not possibly understand, much less write themselves.

I hope that this post might help some people to break out of the mystical thinking that surrounds algorithms.

Perhaps reading through my thought process above you were thinking “oh yeah, that seems obvious”. A lot of algorithms are like this when you finish them, in hindsight they look easy. For many algorithms the hard part is just finding one insight which you can then use to get some leverage on the rest of the problem.