About the ArticlesThe 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 ConnectionHere 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.
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.
Charles River Media, 2005.
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.
IntroductionIntroduction and reference on graph theory.
Brent Gulanowski, "What are Videogames?"
Wikipedia: Graph theory
Reinhard Diestel, Graph Theory textbook
ApplicationsA few uses of graph theory.
Journal of Graph Theory
AlgorithmsAlgorithms to solve some graph problems.
The Stony Brook Algorithm Repository
Journal of Graph Algorithms and Applications
SoftwareSoftware and implementation of graphs.
Graph Template Library
Oracle Tip: Solving directed graph problems with SQL, part 1
PortalsOther sites with links on graph theory.
Mongoose Metrics, Graph Theory Resource Page (links to lessons and interactive examples) http://www.mongoosemetrics.com/phone-articles/graph-theory-resource-page.php
Graph Theory: Textbooks and Resources
The Mathematical Atlas: Graph Theory
About the author
Site Copyright 2004-2005 David Ethan Kennerly