### Speculative Physics

## Mathematics of Game Design: Finite Structures

**by Mendel Schmiedekamp**

Aug 29,2003

## Mathematics of Game Design: Finite Structures

Finite structures are an essential element of game design. Without these structures, any game becomes essentially unplayable chaos. However, in RPGs these structures are repeatedly abandoned and regained. Due to the unbounded nature of an RPG, the game situation will often take a departure from its structure, returning due to decisions made by its players (GM included) to that structure when feasible. Even so-called free form games possess these structures, albeit on a simpler scale than most RPGs. This application is referred to as *prescriptive*, defining the game by describing it in a finite structure.

Finite structures also provide a model for the interactions inside RPGs. While behavior during games is technically unpredictable, with some accepted error, it is reasonable to provide a model for this behavior which closely resembles the behavior. This application is referred to as *descriptive*, describing the game by defining a finite structure that closely resembles it.

*Note for the Technically Inclined:* What I'm referring to as finite structures are more explicitly finitely described structures. Obviously this is not an exhaustive list, I'm merely attempting a short list of useful structures, and their properties.

### Finite Control

**Aliases:** Finite Automata, State Machines

**Core Elements:**

**States** - These are the positions of the finite control. Over time the control passes from one state to another. Typically this is all the information from which the machine works. It doesn't matter if this is the first or the hundred and first time the machine has been in this state, it will behave exactly the same.

**Transition Function** - This is a set of rules that describes how the finite control's states change. Often the change is based both on input the machine receives and the current state of the machine. These rules attach the states to the outside world, allowing them to reflect some feature present in the game at large.

**Advantages:**

A finite control is an excellent way to describe the dynamics of a game. By describing these dynamics as a finite control, it's possible to break down states that are equivalent. This helps condense and simplify both mechanics and models. Also finite controls are surprisingly intuitive. They can be encapsulated in flowcharts, procedure diagrams, and even simply one or two line rules. At the same time they incorporate a large amount of structure.

**Disadvantage:**

The primary danger with a finite control is locality. Most people do not make decisions entirely based on the local information. Typically people will choose or expect based on information not directly related to the situation. This causes dissonance with the finite control. Often people need to train themselves to think in the focused terms in which a finite control operates. Fortunately the fluidity of RPGs makes this less of a problem than it could be.

**Examples:**

**Combat Sequences**(*prescriptive*) - A good example of a cyclic control, many RPGs, especially those closer to wargaming roots, had different parts of combat for different activities. Sometimes a mini-round would commence to manage one element or another, indicating a "spur" structure in the finite control.

**NPC Relations**(*descriptive*) - Often the relationship of an NPC to a PC is very similar to a finite control. The NPC passes through simple states of interaction: uncertain, duped, friendly, hostile, vengeful, etc. More often or not, some key event causes these changes, making it reasonable to simulate these changes in a finite control, based off different types of events: betrayal, declarations, defeat, victory, stand-offs, etc.

**Variants:**

**Probabilistic** - This variant is very common in RPGs, by adding a random decision between two possible states, the result can be more chaotic and interesting, while keeping a basic structure (that's what makes it chaotic and not just random). This is sometimes called a Markov model.

**With Memory** - By adding another finite structure, the finite control can become much more complex, containing more information than just the current state. A good example of this is the control sequence of the game Magic when applied to the spells on the Stack (which is as expected a stack structure).

### Stacks

**Aliases:** Pushdown Stack, First In Last Out (FILO)

**Core Elements:**

**List or Contents** - A stack consists of a list of elements, whether they be papers, procedures, or plates. There is essentially no upper limit to how many things can be in the list, allowing the stack to avoid the limited nature of the finite control.

**Stack Head** - Elements are added and removed from the stack from only one location, the stack head. This is located at one end of the stack. Removing something from this end is often called a Pop, and adding something is likewise called a Push.

**Advantages:**

A stack has two major advantages. First, it can hold a large amount of information without being concerned with more than a small piece of it at a time. Second, a stack mimics the strategy of breaking a problem down into pieces. By storing larger parts of the problem for later perusal, the most immediate portion remains on the top of the stack, allowing it to be dealt with first. It is this later feature that explains why nearly every programming language uses a stack to manage procedure calls.

**Disadvantage:**

While a stack is simple, it is fairly limited. Using a stack tends to cause a certain short-sightedness, since early information is essentially inaccessible. Also the fact that a stack reverses the order that most people expect causes some confusion when using a stack. While often simpler, the stack will not always seem so, especially to the average person. Lastly, a stack alone is often of little use, and typically requires the addition of other structures to be of real use.

**Examples:**

**Magic: the Gathering's Stack**(*prescriptive*) - This game mechanic is precisely a stack, functioning in much the same way as the run-time stack on a computer does. This mechanic grew out of a more intuitive idea of acting and preempting. Eventually the preemptions grew so complex that a structure was required to handle them, the stack is the simplest choice.

**Roleplaying Frames**(*descriptive*) - During roleplaying players approach the game in different levels. Often this immersion will vary during game, each deeper layer built on the previous one. This pattern can be easily described by a stack, allowing the rising and falling of the frames, and the encapsulation of the information which accommodates them.

**Variants:**

**Counters** - Sometimes a stack is too complex to be used for a given application. In those cases a simpler version exists. This is the counter, where only the length of the list is relevant.

**Peeking** - On the other hand, sometimes a bit more information is needed. Having a stack usually means that the earlier information can't be touched, but in many contexts it's possible to cheat this fact. By adding a peeking functionality, the imbedded information can be accessed, even if it can't be removed.

### Queue

**Aliases:** Lines, First In First Out (FIFO)

**Core Elements:**

**List or Contents** - This is exactly the same sort of list as with a stack. The key difference between a stack and a queue is how the elements are added and removed.

**Head and Tail** - Like the stack, the queue has a particular end where items are removed, and one where they are added. Unlike the stack, these are opposite ends of the list. Respectively those are the head and the tail.

**Advantages:**

A queue is in many ways the most intuitive data structure. It succinctly manages a group of people waiting for their turn, and unlike the stack, preserves the order of any sequence it is given. In addition there exists a mathematical theory dealing with the dynamics of queues, appropriately called queueing theory.

**Disadvantage:**

While simple and intuitive, a queue rarely acts as more than a delay on some sequence of requests. Some variants avoid this problem, but lose the intuition of a line rapidly in the process. Also, if there is a significant mismatch between requests and services then the queue will spend almost all of its time growing rapidly, or being empty. This, while indicative of some broad features, prevents real consideration of the more subtle features of the model.

**Examples:**

**Combat Rounds**(*prescriptive*) - Most RPGs delineate combat rounds as waiting for your turn. This naturally describes a combat round as a queue of actions. Most of the variations that can be added to this are related to different variants of queues (see below), usually priority queues.

**GM requests**(*descriptive*) - Usually when a request is made to the GM it is handled immediately. However, this is not always possible. The resulting structure can often be modeled as a queue, one which ideally will not become too long. This also allows describing preferential responses as a priority queue (see below).

**Variants:**

**Priority Queues** - These are essentially queues with an added option for "jumping in line". Different items in the list have different priorities, and based on their distance from the top and their priority may be removed before the head item is. This variant produces all sorts of preferential behaviors, and is often used in computer science for this reason.

**General Lists** - Technically a list structure is related to both stacks and queues, but it tends to act more closely to a queue. A list structure is a queue where the position where items are added and the one where they are removed can be moved along the list. This permits a significant range of manipulation for the items in the list.

**Next Month:** More Finite Structures of Game Design

### What do you think?

Go to forum!\n"; $file = "http://www.rpg.net/$subdir/list2.php?f=$num"; if (readfile($file) == 0) { echo "(0 messages so far)"; } ?>

### Previous columns

- Testing the Boundaries II - Putting Things Together by Mendel Schmiedekamp, 28dec05
- Testing the Boundaries I - Taking Things Apart by Mendel Schmiedekamp, 29nov05
- Need for Speed by Mendel Schmiedekamp, 21oct05
- Groups Redux by Mendel Schmiedekamp, 23sep05
- Two for One by Mendel Schmiedekamp, 19aug05
- Death of Culture by Mendel Schmiedekamp, 27jul05
- Zero Sum by Mendel Schmiedekamp, 17jun05
- Technobabble by Mendel Schmiedekamp, 17may05
- Constrained by One Another by Mendel Schmiedekamp, 22apr05
- Patterns and Play by Mendel Schmiedekamp, 18mar05
- Role, Play, and Game by Mendel Schmiedekamp, 18feb05
- Symbols and Machines: Formal Languages and RPGs by Mendel Schmiedekamp, 21jan05
- Form and Meaning: Computational Languages and RPGs by Mendel Schmiedekamp, 23dec04
- Growing Games: Natural Language and RPGs by Mendel Schmiedekamp, 19aug04
- Speaking in Tongues by Mendel Schmiedekamp, 21jul04
- Planning for Failure by Mendel Schmiedekamp, 20may04
- Between the Steps by Mendel Schmiedekamp, 23apr04
- The Road Once Traveled by Mendel Schmiedekamp, 24feb04
- Seeds of Enlightenment by Mendel Schmiedekamp, 30jan04
- Mathematics of Game Design: Probability and Statistics by Mendel Schmiedekamp, 23dec03
- Mathematics of Game Design: Game Theory and Related Concerns by Mendel Schmiedekamp, 31oct03
- Mathematics of Game Design: More Finite Structures by Mendel Schmiedekamp, 24sep03
- Mathematics of Game Design: Finite Structures by Mendel Schmiedekamp, 29aug03
- Homeworld Project 2: Modes, Grains, and Journeys by Mendel Schmiedekamp, 28may03
- The Homeworld Project by Mendel Schmiedekamp, 30apr03
- Desk Juggling: Designing Players and the Statistical Metagame by Mendel Schmiedekamp, 26mar03
- Juggling Desks: Balance and Dice by Mendel Schmiedekamp, 29jan03
- Fuzzy Alchemy by Mendel Schmiedekamp, 30dec02
- The Opposition Rests by Mendel Schmiedekamp, 27nov02
- A Brief Introduction by Mendel Schmiedekamp, 28oct02

### Other columns at RPGnet

TQo0~^DҒt< ek&Ǿ$\۵ZFȃuwݝIŃU QYir2HR2.u3MFoعq]4#A`pP5(b&)b)ⰾp7(i<[-2gL#5[f g?*rVGf8*)s'+20ϟ̑F}KB<7wSL\gbvm9WiRބYŜvdy0'p2I_Fc2>#oA )VL[Qk?3`)<У[(*W.JH ?tXCt谙 X:@ \0w~LqĤE-rFkYj4q 5AQ6[AxG [>w|?( fХθY䝛$c=_qNĦoǸ>O_|&/_Mi7"宥CЧk0dӷLh;TmuCGU-!Ul{ h<\bQX.~"O2*yPcz!Gg