Strategies

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 random() and noise(). This week we are changing focus to high-level planning. To create more complex systems you must develop a clear understanding of your goal, 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 particular goals. Strategies are specific to their goals, and not highly reusable.

Strategies are composed of tactics.

Tactics
Tactics are low- to mid-level concrete approaches to solving common problems. Tactics include algorithms, data structures, design patterns, and other reusable components that can be applied to a variety of problems.

Tactics are composed of 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 hidden from your program’s frame of reference.

Primitives are atomic: they are the smallest units of composition and cannot be 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.

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

If you want to dig deeper, this is a very simple explicit numerical integration of motion. It is 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 fairly common and they all names. 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.

This week we’ll look at 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 area 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 shouldn’t overlap because when beads of water touch, they join into a bigger bead. Scratches are more likely on raised, exposed parts of the ship that might 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 banging up a spaceship. They could be adapted to arranging points on lines or in 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.

What’s the Difference?

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

  • How does each example compare to the others?
  • What characteristics could be used to group similar examples?
  • What applications might each placement pattern have?

overview

strategy_workshop.ai

Placement Tactics

Placing the Points

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 areas a little more or less dense.

Grid Placement

Place points on grid squares. One way to do this is a nested loop. This approach guarantees a perfectly even 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.
  • Each dot will be placed near the last as the values change in the noise cloud.
  • This technique allows you some control over the proximity of successive points.
// 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 already exist and a fourth is being considered. Three possible values are shown. One is too close and one is too far, so they are rejected. The third location is okay, and a fourth point is added at that location.

cull placement 1 cull placement 2 cull placement 3

This tactic is essentially unoptimized Poisson-disc sampling. Poisson-disc sampling is great when you need evenly distributed points without pattern artifacts.

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

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 can be used to roughen up a rigid arrangement like grid placement produces.

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

Noise Displacement

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

  • This technique allows for nice control over displacement.
  • Can be used to create wave-like effects.
x = x + noise(i * frequency, 0) * amount;
y = x + noise(i * frequency, 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 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.

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 (dark). This results in patches or islands of dots.

Tactics Match

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

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

overview

strategy_workshop.ai

Point Placing Demo

Study Examples

Basic Grid Placement

Basic Random Placement

Stored Grid Placement

In-class Challenge

Explore the code examples above by completing the following challenges in order.
Don’t skip any.

Time Comment
< 11 in 20 Minutes You need to put in some extra work to strengthen your understanding of these topics.
11 in 20 Minutes Good.
All 14 in 20 Minutes Great.

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 each circle.
  3. Draw a little “pine tree” at each point: a green triangle on a brown square.
  4. Remove the noLoop(). Does this introduce any problems?

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 to make them 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 little random offset to each circle.
  2. Change the setup to use random placement and place 100 points.
  3. This example doesn’t need noLoop(). Why?

Challenging Challenges

Continue with the stored random placement code you made above.

  1. Draw about 75% of the points as trees and 25% as snowmen.
  2. Make sure the points don’t switch between trees and snowmen every frame.
  3. For each draw() move the snowmen a random step left, up, right, or down.
bl.ocks.org: Poisson-Disc, Poisson-Disc II
Poisson Disc description, visual explanation, and sample code by Mike Bostock.
Devmag.org: Poisson Disk Sampling
Longer article on implementing and applying Poisson Disk Sampling
Random Points on a Sphere
Nice, interactive demo of three strategies for placing points on a sphere.
Leena’s Inception Overworld Overview
A description of the strategy used to create the main map in Lenna’s Inception.
Game Programming Patterns
An online book that looks at design patterns commonly found in games.