NaN-Boxing

How do dynamically typed languages hold any data type in any value?

One way is NaN-Boxing. This technique crams a payload into a signaling NaN value.

Polygon Clipping

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)

C Tricks

I update this document with different C tricks I come across that I find useful.

Maybe you'll find some of these tricks useful too.

Kong's Garbage Collector

Garbage collectors can seem magical, but their essence is quite simple.

Here I discuss and walk through some of Kong's garbage collector code.

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!.

Shunting Yard

A magical algorithm for parsing expressions.

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 :-P)

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.

How to Fix Banding in Gradients

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