Networked Games -- Graph Theory for Game Design

Hunt Graph

To all of you guys, graph is not a new thing. There are vertices, and there are edges. Two vertices connected by an edge are called adjacent vertices. A vertex may or may not have a label.

Directed graph is used very often. They are called digraph, just imagine a street map composted solely of one-way streets. In a digraph, an edge is called an arc. A path is a sequence of adjacent vertices.

Here, a directed path of 4 vertices is referred to as DP4. The following is a simple example:

            a ---> b ----> c ----> d

In on-line multiplayer games, most common activities can be classified as either hunting or gathering. With hunting, you loot resources from mobile objects, aka mob. A mob can be anything such as a monster, villain, aliens, and ... Basically, a mob has some resources like minerals, crops, magical components that a player can take. Gathering is exactly the same as hunting, except the resources are collected from static objects.

Both kinds of activities can be represented very well with a digraph.

                 S  <--  W
                 ^  \    ^
                 |   \   |
                 L  <--  G    

You start from S, searching for a goal, the mob or static object. You perform an activity. On victory, you go to W, otherwise go to L. Of course, within this graph, there are many different DPs, including those with infinite lengths. In fact, if the game is finite or turn-based, the above graph can be refactored into subgraphs in the form of a tree, with the root of the tree as a reference point. The tree will only contain out-going edges, and hence called out-tree.

                 G --> W
                 |
                 v
                 L

Edge weights are typically used to represent the time it takes to complete an activity. With each vertex, a value is often assigned to define payoff, usually in the form of experiece points (xp). For instance, we can say t(g,l) = t(g,w) = 3 minutes , and the reward for winning is pi(l) = 1 xp and for losing, it is pi(l) = -10 xp . In this example, we are penalizing losing in a big way.

Because an online multiplayer game is meant to exist for a long period of time, it is very very important to analyze the above graph for extreme cases. Although it is highly likely for anyone to continue losing for an hour, in our scenario this is bound to happen as the number of samples approaches infinite. Taking a close look, we see that twenty plays can be played in an hour. So one can lose 200 xp/hour in the worst case, whereas a best case says one can win at most 20xp/hour. Usually, for gathering pi(L) = 0.

Whether extreme conditions as above are acceptable is totally designers' choice. Just that you need to be very sure about your decision. One thing you can do for instance is to have individual scores be averaged over an entire group, for instance.

Mission Graph

Till now, you have just seen the graph representing a single activity. How about putting together a story. A straightforward way is to use a narrative structure depicted as a mission as a complete graph, Kn with n being the number of vertices. We have all seen complete graphs before. One thing that we might not have noticed though is how quickly the complexity of Kn goes up as n increases. Indeed after a certain point, just adding one more node would be a great pain, because you need to debug for all possible paths in the graph. That is on the order of O(n!).

No way we can expect to write anything dependable if manual twiddling is needed. Unfortunately, if you are designing the story for a game, that's a frequent need.

How about taking a different approach, such as composing narratives. Here is what to do. First, you make your missions/activities linear like below. Let's call a, b, c and d subsequent stages.

            a ---> b ----> c ----> d

            s ---> g ----> l ----> s
            s ---> g ----> w ----> s			

Note, you are still creating a very very complicated graph by composing narratives. Always remember to check for the minimum spanning tree of your resulting graph. What do you looking for? You want no surprises in the MSP. Every path in the MSP must be intended. If not, you might be looking at a loophole in your game design right there.

Zone Graph

To scale up in number of users and servers, and also to borrow on intuition in real world, proximity and visibility must be considered. Just like how we cannot see who is in the next room or throw a football and hit someone in Florida. This concept greatly simplifies our problem and makes the overall implementation practical.

A common tecnical approach in this venue is range graph, or zone graph which is very similar. The idea is to first organize the virtual world (mostly 2D or 3D) into very manageable structures. For instance, let's organize the overall global map into a grid. Each grid point is referred to as a neighborhood. In a neighborhood, we connect to it a hunt graph or mission graph specific for that location. Each player must be connected to a grid node as well, hence the server knows who is where and know what those folks can do. Moving from one location to another would understandably be a slower process, which provides a natural interface to partition among servers.

A more tailored range graph is the zone graph. Range graph would uniformly partition the overall game space. But that may not be the more efficient or suitable choice. If you are designing a online game of street gangs, probably you don't need any grid points in our neck of the woods.

Zone graph is better used to represent territories. With nodes being locations/neighborhoods, and edges represent two territories sharing a common border. Note here that territories can be of varying scales. It could be as large as a state, or as small as a room (where borders become portals).

Career Path

Hunt, mission and zone graphs codes up the mechanisms for gameplaying. In order for players to engage in long-term strategices, they must "choose" what job to play and how to advance, etc. For that, we need yet another kind of graph - a job graph.

A job graph is usually in the form of a complete tree, with each ascending level composed of smaller number of nodes. Recall what we discussed about 3 30's, a player must be able to change in a good story (he doesn't have to, but should be able to). Your job graph is the intrinsic control over that part.

At first, the game would let a player decide what role to pick up first, be it to heal wounds, or deliver damage or to augment damage delivery, or to absorb, degrade or produce new resouce/tools. This job graph should be used to identify a potential set of mission/hunt graphs for each player to do in any neighborhood. For teams, players assuming different and complementary roles by all be present before any group activities can embark. However, groups typically don't progress towards a higher "class", except being more or less powerful due to strength and synergy of the members in every group.

Trading Graph

In-game trade is a significant activity that is only possible in online multiplayer games. Other games either lacks the persistency or a community, hence a market, of players.

Trade graph records a creation, transfer and consumption/destruction of new resources. For each resource, there is hence a source and a sink. Note that trading graph is not typically a mechanism of gameplaying, but instead of profiling tool for the designer to fine-tune/lubricate the "economy" after the launch of a game. What is in question is the flow, and particularly whether the observed flow is desirable. For instance, hoarding is usually consider bad. Designers can then adjust the production rates and use of a resource, and probably adjust price vs. interest, etc.

The key design issue in this regard is two-fold: your design must allow collecting such information, and should allow adjusting the key attributes of the fodder at runtime.

There are other types of graphs used for post-launch analysis of game designs. Since we are primarily just interested in implementing one this semester, let's leave those out of the scope for the time being.