Point Placing Strategies

Computational Form + Strategies + Tactics

Strategy without tactics is the slowest route to victory. Tactics without strategy are the noise before defeat.

Probably not Sun Tzu

So far we’ve been looking at low-level topics like how to use—and get the most from—random() and noise(). In the chapter, the focus is on the high-level structure of a program. To create more complex systems you must develop a clear understanding of your goal and create a plan to achieve that goal, divide that plan into sub-problems (decomposition), and create code to solve those sub-problems (implementation).

When planning and coding a project, I tend to think in terms of strategies and tactics.

Strategies

Strategies are high-level plans for achieving your unique, broad goals. Because strategies are specific to their goals they are not highly reusable.

Strategies are composed of tactics.

Tactics

Tactics are low- to mid-level concrete approaches to solving common problems. Tactics can include common algorithms, data structures, design patterns, and other reusable components. Tactics correspond to common problems and are highly reusable.

Tactics are composed of smaller tactics and primitives.

Primitives

Primitives are the programming building blocks provided by your language and libraries. These include control structures like loops and functions and built-in data types like variables, objects, and arrays. They may also include more complex tasks like rect() and random() when the complexity is encapsulated and you don’t have to think about how they work internally to use them.

Primitives are atomic: they are the smallest units of composition and are not further broken down.

Building a Toolbox

Becoming familiar with common tactics and being able to recognize the problems they solve is critical to creating more complex code. Tactics are powerful and useful because they are reusable and composable: the problems they solve appear over and over in a variety of contexts and you can combine tactics in different ways to solve different problems.

The trick is recognizing the abstract similarities between problems.

For example, compare this code that animates a bouncing ball:

to this code that “bounces” the color of a ball:

These two programs produce different effects, but structurally they are almost identical. The two problems have a similar “shape” and we can use a common tactic to solve them both. We could call this common tactic “bounce”. Bounce is fairly simple, but we can break it down further as a composition of smaller common tactics:

Line 20

A variable increment to animate the position/color. If you want to dig deeper, this is a very simple explicit numerical integration of motion using the Euler method simplified by assuming no acceleration and a constant time step.

Line 14 and 17

A very simple implementation of the collision detection tactic.

Line 15 and 18

A very simple implementation of the collision response tactic.

Line 10

This tactic relies on being run repeatedly in the game loop.

These tactics are all common in physics simulation and they all have established names. In other cases, you will find some tactics have several names and other tactics don’t have names at all. Naming tactics is helpful when communicating with other programmers about your code, but the most important thing is to recognize their essential structures.

Tactics can range from very simple—like using the average of two random() calls to center bias the result—to complex—linear congruential generators, noise generation, Brownian motion, L-systems, neural nets, turtles, Markov chains, Poisson-disc sampling, particle systems, fractals, meta-balls. We’ve seen some of these already and will explore others in the course of this class.

In this chapter, we’ll examine some tactics for a very common problem in procedural generation: arranging points on a square.

Where Should I Put Things?

Many procedural systems have to answer a fundamental question: Where should I put things?

This problem shows up all the time: putting trees on an island, putting beads of water on glass, putting scratches on a spaceship. In these situations, it is important to control the placement carefully to achieve an appropriate look. Trees tend to grow in groups and in certain areas where the conditions are right. They don’t tend to grow at high altitudes, in the water, or where there is no rain. Beads of water don’t overlap because when beads of water touch, they join into a bigger bead instead. A spaceship will have more scratches on raised, exposed parts that are more likely to collide with debris. Each situation has different requirements, and depending on your approach, you can determine how planned, chaotic, random, natural, or mechanical the placement feels.

The problems above are all specific instances of the general problem of arranging points. Below we’ll look at several tactics for placing and moving points on a square. These tactics can be combined in different ways to generate a wide variety of arrangements. These tactics can help with planting trees, beading water, or scratching up a spaceship. They could be adapted to arranging points on lines, filling cubes, or arranging events in time. You can find applications for these tactics in all areas of procedural generation any time you have things that need to be arranged.

Placement Tactics

If we want points arranged on a square, we’ve got to start by creating some points and assigning them initial positions. There are many, many ways to go about this: here are five relatively simple but powerful tactics.

Random Placement

Place each point at a random location on the square.

x = random() * width;
y = random() * height;

This is a quick, effective, and straightforward way to lay points down. In theory, since the placement is random, all of the points might be placed in a clump or on one half of the square. In practice, the points are mostly evenly distributed over the plane, with some clumps and some sparse areas. Random placement isn’t usually very pretty.

Grid Placement

Place points on grid squares. One way to do this is a nested loop. This approach provides a perfectly even, mechanical distribution.

for (row = 0; row < grid_rows; row++) {
	for (col = 0; col < grid_cols; col++) {
		x = (row + .5) / grid_rows * w;
		y = (col + .5) / grid_cols * h;
        ...
	}
}

Noise Placement

Place each point at a location determined by a noise lookup.

• Because noise is center-biased, the results will be center-biased.
• Because noise fields are continuous, each dot will be placed near the last if you use samples in the noise that are near each other.
• By controlling your sampling frequency, you can control how close the points are to their neighbors.

// loop with _i_
x = noise(i * frequency, 0) * w;
y = noise(i * frequency, 1000) * h;

Proximity Cull Placement

Place points randomly, but reject a point if it is too close to an existing point or too far from all existing points. In the example below, three points have already been placed and a fourth point is about to be added. Three possible locations are shown. One is too close and one is too far, so they are rejected. The third location is okay, and a point is added at that location.

This method scatters points evenly across the square, but without the clumps and sparse patches produced by simple random placement. The results can take longer to place dots in this way if you are not careful but the results are prettier.

Poisson-disc sampling is a common and efficient algorithm for quickly achieving this effect.

Stamp Placement

Create predefined arrangements of points by hand or generatively. Copy these arrangements onto different locations.

This technique allows mixing of handmade and procedural design.

This tactic is used for map generation in many rogue-lite video games, which create random layouts of hand-designed rooms.

Moving the Points

These tactics can be used to move existing points. Many effects can be created by combining these with the placement tactics above if in different ways.

Random Displacement

Given a set of points, offset the location of each point by a random amount. This is often used to “roughen up” a rigid arrangement like grid placement produces.

x = x + random();
y = y + random();

Noise Displacement

Displace each point by an amount determined by a noise lookup.

• This technique allows for more control over displacement.
• This is also a good way to “roughen” up grid placement, but creates more of a natural effect.

x = x + noise(x * scale, y * scale) * amount;
y = x + noise(x * scale, y * scale, 1000) * amount;

Relaxation Displacement

Find pairs of points that are near each other. Move them towards or away from each other by a small amount. This technique is often applied several times in a row with very small movements, which avoids the problem of pushing a point away from one point, but into another.

• This technique can be used to push points apart to some minimum distance.
• This technique can also be used to pull points together if they are near each other.
• This technique simulates attractive or repulsive forces acting on the points and can be used to loosely simulate natural phenomena.

Noise Culling

Sample noise based on the location of the point. Use the sampled value to determine if the point should be culled (discarded).

In the example above, points are removed if the corresponding noise value is too low. This results in patches or islands of dots.

Point Placing Demo

This code implements the tactics described above, and demonstrates the effect of combining the tactics in different ways.

Study Examples

Basic Grid Placement

This example places dots on a grid using a nested loop. This is a very common and reusable tactic in generative coding, and is well worth studying until you understand it completely.

Basic Random Placement

This example places 100 dots at random positions. This is a simple starting point that can be adjusted and tuned in many ways.

Stored Grid Placement

Like the Basic Grid Placement example above, this example places dots on a grid. Rather than drawing immediately, this example stores the locations as an array of simple data objects [{x: ?, y: ?}, {x: ?, y: ?}, ...] and draws them separately. This allows the code to separate concerns—placing and drawing—and is a better foundation for multistep, iterative, and interactive effects.

Properties of PCG System

When designing a procedural generation system there are several properties to consider. The following properties are discussed in Chapter 1 of Procedural Content Generation in Games.

Speed

• How fast does your program need to run?
• Is it okay if it takes a very long time to complete?
• Many times a faster-running program is harder to code and understand.
• A frame of VR content needs to be rendered in under 10ms, and a short pre-rendered animation may take days to render.

Reliability

• Does your program need to produce a good result every time?
• Are results shown directly to your audience, or will you have the opportunity to edit?

Controllability

• Does your program expose any user parameters?
• Do you want to explore the parameter space manually?
• Do you want to have tight control over the results or should everything work automatically?

Expressivity and Diversity

• How much apparent range does your system have?
• Does everything look same-y?
• Is it okay for your output to be completely wild or does it need to satisfy some constraints?
• If you are exposing parameters, do they allow for meaningful control?

Creativity and Believability

• Do you want your results to look natural or hand-made?
• Is it okay for them to look “computer-y”?
• If your system is generating variations on something that already exists, how closely do you want to copy the original?

Repeatability

• Do you need the ability to generate the same result more than once?

Explore