Poisson Disk Sampling
This article originally appeared in Dev.Mag Issue 21, released in March 2008. One way to populate large worlds with objects is to simply place objects on a grid, or randomly. While fast and easy to implement, both these methods result in unsatisfying worlds: either too regular or too messy. In this article we look at an alternative algorithm that returns a random set of points with nice properties: the points are tightly packed together; butno closer to each other than a specified minimum distance. Figure 1 shows an example of such a set, which is called Poisson-disk sample set. Poisson disk sampling has many applications in games: random object placement;sampling for graphics applications;procedural texture algorithms; andmesh algorithms. In this article we will look mostly at object placement and briefly at texture generation. Figure 1 Implementation There are several algorithms for producing a Poisson disk sample set. Here are the details: Here is how all this look in pseudo code: Figure 7
How to Use Perlin Noise in Your Games
(Originally appeared in Dev.Mag Issue 20, released in February 2008.) Perlin noise is the foundation of many procedural texture and modelling algorithms. It can be used to create marble, wood, clouds, fire, and height maps for terrain. Edit 19 June 2011: The examples were originally given in pseudo-code. Edit 19 May 2012: I always thought the cloudy noise described in this article is called Perlin noise. Real Classical Perlin noise, and simplex noise, can also be combined, just like the “smooth noise” is combined in this article, to give cloudy noise. Implementation Written in its concise mathematical form, the Perlin noise generation seems daunting, but it is actually easy to implement. Generate a number of arrays containing “smooth” noise. That’s it! Figure 1 Generating Smooth Noise First, you need to create an array with random values between 0 and 1. The following pseudo C snippet shows how the kth octave is generated. Note that the line: is not the same as Blending the Arrays Textures
Getting More out of Seamless Tiles
We have used tiles to decorate our living spaces for more than 4000 years . Tiles have several properties that make them attractive for use: they can be mass-produced; they are easy to build with (because of their geometric properties); and combinations of tiles lead to a huge number of decorative options. Early game makers recognised that these advantages of tiles also apply to tiles in computer graphics, and using tiles was (and still is) a popular way to make game graphics. In computer terms, here are the advantages of a tile system: it is efficient, it is easy to program, and a few tiles give you a huge number of possible game maps. The last point is really the one that makes tiles shine, and it really comes to its full with procedural content generation. But tiled games can also suffer from some defects: the geometric regularity of tiles might be less appealing than organic design; and the repetition can be jarring. Tiles Some Tile Basics Grids Penrose tiles A Few Definitions Symmetries Blur
Bézier Curves for your Games: A Tutorial
(Image source) We all know what a curve is. Here are some examples. A Bézier curve is a type of curve that is easy to use, and can describe many shapes. In games, Bézier curves are sometimes useful to describe paths: the racing line in a racing game, or the line in line-drawing games such as Flight Control, or the looping butterfly that enlivens an RPG. Bézier curves are popular because their mathematical descriptions are compact, intuitive, and elegant. In this guide, I give you the instructions necessary to implement algorithms for using Bézier curves in your games. Mathematical Description Let’s start with the mathematics. The value t can range from 0 to 1. Here is an example of the simplest type of Bézier curve, a line-segment: [x, y] = (1 – t)P_0 + tP_1 This is shorthand notation for the two equations that give the coordinates separately (see Vector Fundamentals): x = (1 – t)P_{0x} + tP_{1x} y = (1 – t)P_{0y} + tP_{1y} The points P_0 and P_1 are the control points. Here is the formula: Cases
Bézier Path Algorithms
In the article Bézier Curves for your Games: A Tutorial, I introduced Bézier curves and Bézier paths. In this tutorial I provide some algorithms useful for working with Bézier curves: determining the length of a piece of curve; interpolating a set of points with a Bézier path; and reducing a large point set to a smooth Bézier curve. (Image by snuffyTHEbear). Calculating curve length Assuming that the line segments we use for drawing are a reasonable representation of our curve, we can estimate the curve length by summing the lengths of the segments. A more complicated strategy is necessary when we need the length of only a part of the curve, and not the complete curve. First, we must cache the accumulative length of segments when we update the drawing points. Then, we can use a simple subtraction to find the length of the piece of the curve (assuming, for a moment, that we need it only between points that coincide with the drawing points). Note that we subtract 1 from the smaller index.
