6 Useful Snippets

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

Hill Noise

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

A Faster Weighted Random Choice

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

Meandering Triangles

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:

A contour map

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