FABRIK Algorithm (2D)

The FABRIK algorithm is an amazingly clever solution to the Inverse Kinematics problem – how to adjust the joints of an arm to reach a target location.

In this tutorial, I go over how the core algorithm works in 2D, building up from simple concepts.

Read More

Polygon Clipping (Part 2)

My previous polygon clipping tutorial dove into the Greiner-Hormann clipping algorithm. Unfortunately, this algorithm fails at common cases… so let’s revist the problem and try again.

The F. Martinez 2008 algorithm handles coincident edges (unlike Greiner-Hormann), but it still has some minor goofiness. Let’s solve this problem once and for all.

Read More

Polygon Clipping (Part 1)

Polygon clipping is an interesting problem: how do you intersect, union, or diff two polygons?

My first attempt was a failure:

Polygon Clipping - Part 1 (Greiner-Hormann)

So I researched and developed another algorithm, which handles every case:

Polygon Clipping - Part 2 (Modified F. Martinez 2008)

Read More

Genetic Algorithms

Using computers to simulate breeding to search for optimal fitness.

This article discusses the basic strategy I used to create breeding bunnies, in my Ludum Dare 31 entry, Bunnies!

Read More

Shunting Yard (Part 3)

Let’s continue adding to our Shunting Yard code base.

In Part 2, we created operator precedence. This allowed us to delay application of operators indefinitely, using a stack. Next, we’ll focus on adding parentheses, so that the end-user can manually override precedence.

Series: Part 1, Part 2, Part 3, …

Read More

Shunting Yard (Part 2)

Let’s continue building a general purpose Shunting Yard algorithm.

We left off with bare-bones skeleton that implements a shunt to delay building of the abstract syntax tree (AST). Our skeleton left a lot to be desired. For this article, we’ll implement operator precedence.

Please read Part 1 first, since the code here builds directly on the source from that article.

Series: Part 1, Part 2, Part 3

Read More

Procedurally Generated Planet Textures

Using Perlin noise to generate planets.

When creating Odyssey, I used this basic technique to generate unique planet textures for every level.

(Much cheaper than hiring an artist 😛)

Read More

Shunting Yard (Part 1)

A magical algorithm for parsing expressions.

Read More

Two-Dimensional Bin Packing

Given a collection of different sized images, how can you efficiently pack them into one big image?

Brute-forcing the problem is too expensive - so here we come up with a simple heuristic that works pretty well.

Read More

How to Fix Banding in Gradients

Photoshop’s gradient algorithm can have banding artifacts when drawing subtle gradients. The fix: dithering.

Read More