Chapter 1.3:
Constraint programming

In map generation, we talked about the Wave Function Collapse algorithm for generating tile maps by specifying a set of possible tiles, together with restrictions on what combinations of tiles were could be next to one another.  It's used in a number of commercial games, such as Townscaper (see image above).

WFC is a constraint satisfaction system: it specifies a problem in terms of a set of choices to make, together with restrictions on what combinations of choices are allowable.  In the case of Wave Function Collapse, the choices were what tile to put in each location and the constraint was that you could only have certain pairs of tiles adjacent to one another.

The typical terminology used in constraint satisfaction refers to the choices to be made as variables and the restrictions on their combinations constraints.  The menu of options for a given variable is known as its domain.  A set of choices that satisfies all constraints is referred to as a solition or a model.

For example, we could describe the problem of generating an NPC for an “F20” style game¹ in terms of the following variables:

• Name, whose domain would be some list of possible names in the story world
• Class, whose domain would be something like: fighter, magic user, cleric, etc.
• Various stats (numbers), such as STR (strength), DEX (dexterity), CON (constitution), INT (intelligence), WIS (wisdom), and CHA (charisma).

The constraints might be something like:

• The sum of all the stats must not be more than some number (e.g. 27)
• Stats should be sensible for the character's class:
  • A fighter should have a strength of at least 6
  • A magic user should have an intelligence o f at least 6
  • etc.

The set of solutions to this are valid characters who have all the necessary attributes and are sensible in the sense that they are neither over-powered nor under-powered for their class.

These kinds of constraint satisfaction problems are generally described using the language of either set theory or formal logic.  However, we'll begin by showing you a language that lets you describe constraint problems without needing to know logic or set theory.

Endnotes