Random direction in 2d

Randomness adds an extra flavor to games by injecting some unpredictability, something that can surprise the player. It also makes the game less mechanical and more organic. In the game prototype I posted earlier, bots always initialized their look directions to (1, 0). So every time a level starts all bots looks in this direction after which they start to behave randomly. This may seem like a smally but as a matter of fact it’s kind of disturbing also it gives the player the handicap of always knowing in what direction the bots will look at startup. Thanks Maurycy Zarzycki for pointing this out.

Generating a random direction, three different algorithms

When I was going to implement this I noticed that I didn’t have any central code to create a vector in a random direction. This is something I use frequently so I decided to do a proper implementation.

Randomizing a direction can be done in many ways, but be aware: some intuitive approaches are simply wrong and doesn’t provide a uniform distribution.

Wrong: normalizing random points in a square

The first time I was doing this, I didn’t realize this until a code review. The reviewer asked me if I was aware that my code generated biased directions. It all seemed random in my testing, I replied. I guess my first draft of the code looked a bit like this:

private function createRandomDirBad():Vec2
{
	const u:Number = 2 * Math.random() - 1;
	const v:Number = 2 * Math.random() - 1;
	const l:Number = Math.sqrt(u * u + v * v);
	return new Vec2(u / l, v / l);
}

Can you see why this is skewed? This generates a random point in a square which is normalized to have length one – this means that diagonal directions will be biased because points outside the circle are “pushed” inside. The image below illustrates this bias. (Points are drawn in the circle rather than on the outline to demonstrate this)

Discarding points outside of the circle

I was quickly convinced and changed my code. I fixed it by discarding all randomly generated points outside of the circle (x*x + y*y > 1). This requires more iterations but gives an uniform distribution of points within a circle. See distribution B below.

private function createRandomDirSquare():Vec2
{
	var p:Vec2;
	while (true)
	{
		const u:Number = 2 * Math.random() - 1;
		const v:Number = 2 * Math.random() - 1;
		const s:Number = u * u + v * v;
		if (s > 1 || s < Vec2Const.EpsilonSqr) continue;
		const l:Number = Math.sqrt(s);
		p = new Vec2(u / l, v / l);
		break;
	}
	return p;
}

Here is the distribution within the circle (on the circle surface it's uniform - but not over the area):

Using trigonometry

Another method for random generation of points in a circle is to use trigonometric functions. This perhaps the most straightforward way, we just grab a random angle and create a vector in that direction:

private function createRandomDirTrigonometry():Vec2
{
	const rads:Number = Math.random() * Math.PI * 2;
	return new Vec2(Math.cos(rads), Math.sin(rads));
}

This will put points uniformly along a circle outline.

No square roots, no trigonometry

While looking around, I found a method attributed to Von Neumann. This trick allows us to generate a random direction without any use of square roots or trigonometry which can be useful if those are slow.

public static function createRandomDirKnuth():Vec2
{
	var p:Vec2;
	while (true)
	{
		const u:Number = 2 * Math.random() - 1;
		const v:Number = 2 * Math.random() - 1;
		const l:Number = u * u + v * v;
		if (l > 1 || l < EpsilonSqr) continue;
		p = new Vec2((u * u - v * v) / l, 2 * u * v / l);
		break;
	}
	return p;
}

Final note on performance

The difference from the three methods is very small, today sin and cos are mostly hardware accelerated and as it turns out in my measurements this is the fastest way to do this. So perhaps I would recommend using the one with sin and cos, if not for its performance for its simplicity.