I'd like to present a handful of programming concepts that I find incredibly
useful, all of which can be implemented in under 20 lines of code. These
techniques can be used in a wide range of contexts, but here, I'll show how
they can all build off of each other to produce a full physics engine in just
75 lines of code.

Continue reading...

Noise functions are a way to produce continuous pseudorandom values across one
or more dimensions. The simplest example is a one-dimensional noise function
that makes the y-value wobble up and down smoothly, but unpredictably, as you
move along the x-axis. It's also possible to produce 2-dimensional noise, where
the amplitude of the noise depends on the x,y coordinates you're sampling.

This can be used to create hilly terrain in a video game, or more generally,
it's used in computer graphics for procedurally generating textures or making
bumpy surfaces. The original version of Minecraft used a 2D noise function to
generate heights for terrain as a function of (x,y) coordinates, and later
versions used a 3D noise function to generate terrain density as a function of
(x,y,z) coordinates to produce overhangs and caves, as Notch describes
here.

Continue reading...

Consider this problem: You have a list of items and a list of their weights.
You want to randomly choose an item, with probability proportional to the
item's weight. For these examples, the algorithms will take a list of weights
and return the index of the randomly selected item.

Continue reading...

Contour lines, also known as
isolines, are lines drawn along along paths of constant elevation. They are
often used when drawing maps to indicate the slope of hills and mountains:

But they can also be used to visualize functions that map (x,y) values to z
values, or to find the boundaries of implicit
surfaces. One of the common
algorithms for finding contour lines is Marching
Squares. The algorithm assumes
that you have a set of elevation data points spaced out at regular intervals on
a grid, and generates contour lines for each square of the grid. A simpler
algorithm exists, called Meandering Triangles, and it divides the data points
into triangles, rather than squares, to reduce the number of cases the
algorithm has to handle. Here, I'll give a full explanation of how the
Meandering Triangles algorithm works, with some examples to show it in action.

Continue reading...