Point Placing Strategies

Overview

Building a complex procedural generation system requires analyzing your problem and creating a strategy for solving it. Explore tactics and strategies for placing points on a square.

Tools

p5.js

Computational Form + Strategies + Tactics

Strategy without tactics is the slowest route to victory. Tactics without strategy is 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.

If you are already familiar with the idea of design patterns, my use of the term tactics will sound familiar. The book Design Patterns: Elements of Reusable Object-Oriented Software largely popularized design patterns, and describes them as “descriptions of simple and elegant solutions to specific problems in object oriented software design” and notes that that “point of view affects one’s interpretation of what is and isn’t a pattern.”

I am using the term tactics to talk broadly about reusable approaches to solving reoccuring coding problems and tasks. Design patterns would fall into this category, as would smaller and larger ideas that others may not think of as patterns.

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.

Points on a Square

Consider the image below. How might you make something like this?

tighten_relax

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.

The Drive Home, 2017
Martijn Steinrucken
The Drive Home, 2017
Realtime procedurally generated view from a windshield in the rain.
Don't Starve, 2013
Klei Entertainment
Don't Starve, 2013
Don't Starve's procedurally generated maps included carefully placed trees, bushes, and shrubs.
StippleGen, 2012
Evil Mad Scientist Laboratories
StippleGen, 2012
StippleGen was created in Processing to turn photographs into pen-plottable drawings.
No Man's Sky, 2016
Hello Games
No Man's Sky, 2016
No Man's Sky populates its vegetation on the three-dimensional surface of its planets.
Mutant Garden, 2021
Harm van den Dorpel
Mutant Garden, 2021
This project implements a breeding strategy that creates colorful geometric shapes.

What’s the Difference?

Analyze each of the examples below. Carefully consider their similarities and differences.

overview

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.

random placement

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

grid placement

Noise Placement

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

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

noise placementlow frequency sampling

noise placementhigh frequency sampling

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.

cull placement 1

cull placement 2

cull placement 3

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.

cull close beforeproximity cull

random placementrandom placement

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.

stamp placement 1

stamp placement 2

stamp placement 3

This tactic is used for map generation in many rogue-lite videogames, 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() * width;
y = y + random() * height;

noise placement

Noise Displacement

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

x = x + noise(i * frequency, 0) * amount;
y = x + noise(i * frequency, 1000) * amount;

noise placement

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.

relax displacement 1

relax displacement 2

relax displacement 3

Noise Culling

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

noise cull 1

noise cull 2

noise cull 3

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

Tactics Match

What tactics might have been used to get each result below?

Place Move
Random Placment Random Displacement
Noise Placment Noise Displacement
Grid Placment Relaxation Displacement
Proximity Cull Noise Cull
Stamp Placment  

overview

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 loops. This is a very common and reusable tactic in generative coding, and 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 seperately. This allows the code to seperate concerns—placing and drawing—and is a better foundation for multistep, iterative, and interactive effects.

Coding Challenges

Explore this chapter’s example code by completing the following challenges.

Modify the Basic Grid Placement Example

  1. Change the grid to 10 x 20, 20 x 20, and 100 x 100.
  2. Add a little random offset to the position of each circle.
  3. Remove the noLoop(). Does this introduce any problems? ••
  4. Draw a little “pine tree” at each point: a green triangle on a brown square. •••

Modify the Basic Random Placement Example

  1. Change the code to place only 10 points. Try placing 1000 points.
  2. Use middle biasing when placing points so they’re more likely to appear near the center. ••
  3. Draw a little “snowman” at each point: three white circles, stacked. •••
  4. Remove the noLoop(). Does this introduce any problems? ••

Modify the Stored Grid Placement Example

  1. Add a random offset to the position of each circle.
  2. Change setup code to use random placement to place 100 points.
  3. This example doesn’t need noLoop(). Why? ••
  4. Draw about 75% of the points as trees and 25% as snowmen. ••
  5. For each draw() frame, move the snowmen a random step left, up, right, or down. •••

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

Reliability

Controllability

Expressivity and Diversity

Creativity and Believability

Repeatability

Take Home Challenge

This is the last chapter of the “Foundation” section. The challenges in the chapters so far—random, noise, parameters—have been open ended. They suggested general themes, but left the specifics up to you.

The challenges this week are much more specific, challenging you to recreate a specific effect. Recreating existing effects presents different challenges than open ended sketching, and forces you to contend directly with any problems you run into. Both this type of work and open ended exploration are good ways to study creative coding and mixing them is particulary effective.

Solving these two challenges will require strategic planning:

Challenge 1: Dots

Challenge Goal

Challenge Start Code

Challenge 2: Line

Challenge Goal


Challenge Start Code

Explore