Webs Within Webs

Graph Theory for Designers - Appendix
David Ethan Kennerly

About the Articles

The first article, "Games within Games," introduces graph theory and demonstrates how mechanics in any game can be modeled by a mathematical graph (A mathematical graph is basically a well-defined network). Then graphs are modeled for common activities in massively multiplayer games: hunting, gathering, missions, and spatial navigation. Several case studies are analyzed, in which graph theory is used to expose exploits and suggest improvements in Anarchy Online, Ultima Online, City of Heroes, and others.

The second article, "Worlds within Worlds," extends graph theory to model the economy and community in a massively multiplayer game. The economy is modeled by graphs of transactions, and the community is modeled by graphs of chatting, team participation, friendship, guild membership, and faction relationships. Examples of economic and community design are given from several online games, such as Dark Ages, Final Fantasy XI, EverQuest, and World of Warcraft.

Making the Connection

Here is an online appendix to a pair of articles that introduces the mathematical concepts of graph theory for use by massively multiplayer (MMP) game designers. Since this article deals with connections, it is appropriate that an online presence connect it to sites for further exploration. You will find a glossary of terms defined in the article and links for algorithms and further study.

Ethan enjoys direct feedback and discussing the topic further.

Model

Massively multiplayer (MMP) games are complex. The following figure models one suggested approach for learning about the fundamental mechanisms and systems in MMPs. The figure may be loosely interpretted as a system of prerequisites, like classes in a college degree. Each vertex (labeled point) may be considered as a type of graph. Each arc (directional line) depicts the prerequisite knowledge for subsequent graphs.


In the above figure, an activity graph depicts the relationship of the new concepts. In this graph, a vertex represents a particular kind of graph, such as a hunt graph. An arc between two vertices represents that the concept of the target depends on comprehending the concepts of the source. For example, to understand a mission graph, the reader must first comprehend the hunt graph and the gather graph.

The above figure loosely categorizes the massively multiplayer systems as: game systems, economic systems, and communal systems. So, in this model, the fundamentals of the game mechanisms enable the designer to appreciate the economic mechanisms. And with the addition of communication (such as a chat graph), many of the mechanisms of the community may be analyzed.

Articles

For explanation and examples of the use of these concepts, read the articles "Games within Games" and "Worlds within Worlds" in Massively Multiplayer Game Development 2 (ISBN 1-58450-390-4) published by Charles River Media, 2005.

Glossary

The pair of articles introduce several new terms, which a reader may find convenient to refer to in a single glossary.

    chat graph: A graph whose vertices represent players. Edges represent mutual chat message transmittal during a given period.

    economy graph: A graph whose vertices represent abstract containers of goods and whose arcs represent valid transferral of a good from one container, including a player, to the next. A vertex is a source if and only if it has no incoming arcs. A vertex is a sink if and only if it has no outgoing arcs.

    faction graph: A signed graph whose vertices represent coalitions. Negative edges represent enmity and positive edges represent alliance.

    friend graph: A graph whose vertices represent players. Edges represent mutual listing on respective friend lists during a given period.

    game graph: A graph whose vertices possess payoffs and whose edges possess time values.

    gather graph: A game graph whose vertices represent states in gathering or harvesting.

    guild graph: A graph whose vertices represent players, and a distinguished vertex represents a guild. An arc from a player represents membership in a guild.

    hunt graph: A game whose vertices represent states in hunting.

    job graph: A graph whose vertices represent a job. An arc represents a valid decision to advance or change jobs.

    mentor graph: A graph whose vertices represent players. An arc represents a relation of a novice to a mentor, as formally defined by the massively multiplayer game.

    mission graph: A type of game graph whose vertices represent essential states in a mission.

    payoff cycle: A path in a game graph that starts and ends on the same vertex, usually with a nonzero payoff value for the complete path.

    range graph: Vertices are adjacent if and only if the occupants of those vertices are within range of each other, usually meaning proximity and line of sight.

    role graph: A signed graph whose vertices represent an abstract role that a player or job may have. Arcs represent influence the role has on other roles.

    tactical role graph: A role graph whose vertices represent the roles in combat and arcs represent influence on the outcome of the combat.

    team graph: A graph whose vertices represent players. An edge represents membership to the same team or group during a given period.

    trade graph: A graph whose vertices represent players. An arc represents transference of a good.

    trade network: A trade graph with a source and a sink and arcs are weighted by flow.

    room graph: A range graph for a MUD or other game that divides space into encapsulated rooms.

    zone graph: A graph whose vertices represent a single zone and whose edges represent travel between zones.

Links

The following are useful links for game designers who wish to apply graph theory.

Introduction

Introduction and reference on graph theory.

Applications

A few uses of graph theory.

Algorithms

Algorithms to solve some graph problems.

Software

Software and implementation of graphs.

Portals

Other sites with links on graph theory.

Resources

About the author

Return to Fine Game Design


Site Copyright 2004-2005 David Ethan Kennerly