Mathematics of Game Design: More Finite Structuresby Mendel Schmiedekamp
Mathematics of Game Design: More Finite Structuresby Mendel Schmiedekamp
Mathematics of Game Design: More Finite Structures
Aliases: Trees, Nets, Webs
Vertices - A Vertex is a point or node on the graph, they are connected to other vertices via edges. Usually a vertex is related to some fixed quality, such as location, mental state, or progress in time.
Edges - An Edge is a link between two vertices. Usually there can only be one edge between any two vertices, although using labels or direction (see below) this can be changed. Edges are usually related to a transition, such as travel, a critical event, or a level of progress reached.
Directionality - Normally edges are considered undirected, simply being a link between two vertices. An alternative is to treat some or all edges as directional. This indicates that the edge is only considered to link its starting vertex to its ending vertex, not vice versa. This option best describes a relational map of a dungeon, where some areas can be traversed both directions, while other routes are one directional (down a cliff, through a shute, or using a collapsing staircase).
Labels - Labeled edges are again possible, to indicate particular kinds of links between nodes. This is especially relevant if labels are repeated. Thus similar transitions can permit access to different parts of the graph based both on the edge and position. This approach can be equivalent to the finite automata mentioned last month, especially if the graphs are made directed as well.
Cycles - Cycles, where a chain of edges and vertices returns to its starting vertex, occur in many graphs. In fact, unless all the edges are directional this occurs in every graph. Often for descriptive graphs these cycles indicate important behavior pattern. However in some cases cycles are problematic. Most notably a graph that lacks a cycle has the advantage that an end or leaf vertex, one with no edges leaving, will eventually be reached. This allows the maximum number of edges traversed to be bounded. This is especially useful for decision graphs.
Connectedness - One question which is often required to evaluate a graph whether all the vertices can be reached from each other. If this is not the case, then it can be asked which vertices can be reached from a given vertex. This collection of vertices is then a type of subgraph, and the entire graph can be treated as just this subgraph once that vertex is reached. Usually for a decision graph we want there to be a vertex from which all other vertices can be reached. Likewise we want the graph to lack cycles. The resulting kind of graph is called a tree, and in this case a decision tree.
Graphs are well geared towards describing relationships between things, whether they be people, places, or events. Graphs are also easily extensible, allowing the addition of new regions and the combination of different graphs is often as easy as connecting them with an edge or a vertex.
Graphs are complex things. Unlike the previous finite structures a graph contains a great deal of information and can be extended to a significant size quite easily. This means care must be taken to ensure the desired properties of the graph, like connectedness, lack of cycles, and standardized label schemes.
Populated Maps(prescriptive) - Populated areas on maps are usually connected by a network of roads and trade routes. These connections act much like a graph, and in most situations can be reduced to one. These networks grow like graphs, with a small number of new edges (routes) being formed when new vertices (settlements) occur.
Requirement Based Character Building(descriptive) - Many systems use a strict requirement system to allow character advancement. One example is D&D with its prestige classes and other requirements for different abilities. The general options of characters can then be described as a graph, where some vertices are closer and more accessible than others. Likewise early choices will ultimately bias how accessible certain options are. One concern about this graph is the balance between different regions. There is a risk of imbalance causing the character building to tend other than the designer intended.
Trees - While trees are technically just one type of graph, they are used in their own right often enough to distinguish them. In particular a tree is a directed graph, with no cycles, and at least one vertex which is connected to all other vertices. This vertex is called the root. One advantage of trees is that at each vertex the vertices still connected to it form a tree of their own, a subtree. This lends the tree to being broken down into smaller and smaller pieces to make it more manageable than a general graph would be.
Neural Nets - Neural nets are a very odd variant of a graph, a graph where each vertex has a state. Each edge relates the vertices together, so that if one state changes the next will sometimes be altered as well. Whether the change occurs in the next vertex is based on some trigger value. If the states all around a vertex reach a given level then that vertex changes state as well. This allows the net to remain stable with a few changes, and then suddenly under go a significant change, albeit built of a long series of events. Often this sort of behavior is very desirable, and a neural net is often the simplest way to bring it about.
Aliases: (None generally)
Elements - The elements of a group can be anything which mutually interacts. Whether it can be numbers which add together, movements which combine to form an entire new position, or adjustments which modify an object or a person, these elements must combine to form new elements, and so on. For the moment use letters for elements.
Binary Operation - The operation of a group is a method by which two elements can become a third element. This can be addition, multiplication, composition, or something less common. For the moment use + as this operation.
Axioms - To be a group, three rules need to be fulfilled.
(1) One of the elements must be the identity element, e, where with any element a, a + e = e + a = a. Essentially this is the zero of the group.
(2) Each element has another element which is its inverse, so that if a and b are inverses, then a + b = b + a = e. This means that each use of the operation can be reversed. Sometimes we don't want this, in those cases we have a semi-group (see below).
(3) The operation is associative, (a + b) + c = a + (b + c). This means that the order of performing the operation doesn't matter, although the order of the elements could.
Commutativity - Some groups also have the rule that the order of elements can be switched, a + b = b + a. This means that in general the only thing that matters is how many of each element has been put into the mix. One good example of this sort is addition, where 1 + 2 and 2 + 1 both equal 3.
Generators - Many groups have a small number of elements which can be used to generate the rest of the elements by simply applying the operation to those elements some number of times. Addition is another good example of this, where all the integers can be generated by adding 1 or -1 enough times. The major advantage of generators is they can simplify a large or even infinite group (making it back into a finite structure). One nice property of generators, is that the axioms need only be verified for generators to ensure that the generated elements form a group.
Finite - Some groups have only a finite number of elements. Obviously addition isn't a good example of this. On the other hand, the group of rotations on which retain the symmetries of a cube is such a group, since there is only a finite number of orientations the cube can have.
Groups are structures that can possess an amazing amount of complexity, and are easy to handle, since they can usually be described fairly easily by a few generators. Groups are typically the best structure to describe systems which resemble arithmetic in some way or have a small, but complete set of interacting options. Another advantage of groups is that they often contain smaller subgroups with group structure as well. This means that it is often possible to examine these small parts to understand larger structures of the group.
Unfortunately the rules which give groups a great deal of power, also make it more difficult to apply in some cases. Often a system is close to a group, without quite fitting all the requirements. This can cause confusion if the system is incorrectly treated as one.
Multiplier Addition(prescriptive) - One common problem in systems is cumulative multipliers often cause an exponential growth, while a geometric one is preferred. By using an additive scheme this problem can be remedied. As such the multipliers are treated as members of an additive group, rather than the multiplicative one in which they naturally appear.
Metagame Prestige(descriptive) - Modeling the rating of a given player's prestige in an RPG is a complex task. Prestige can easily be treated as additive, but different modes of prestige exist, from bringing snacks to effective characters. Each of these modes could be a different generator for a prestige group. One of the questions in building this model is whether prestige in different modes are independent, making the group commutative, or do they interact in some way, implying that order of prestige gaining events does matter.
Semi-groups - A semigroup is a group without elements having inverses. The most common examples of semi-group are strings, which are basically long collections of letters. This sort of structure is best suited to situations where the element generated is always increasing or staying the same length, in terms of generators.
Rings - A ring is a group with another group lying on top of it. The simplest example is the way addition lies underneath multiplication. This means that a ring has two operations, both of which are group operations, and these operations distribute in the expected way. These sorts of systems are useful for more complicated arithmetic and developing multiple level patterns.
Next Month: When a game is a game.