Mathematics for Game Designers

I was just thinking about when a graph is appropriate to use when thinking about the design of a game and when it isn't.

Now, it's obvious (at least to me) that you could always use a graph to model a game (at the very least, each unique positioning of elements in the game can be classed as the game state, and can represent a node in the game, connected to all states it is possible to reach from there), but this isn't always useful - for example, if you used this 'state graph' representation for Go or Chess, you end up with a huge graph that isn't very useful (it's too computationally expensive to derive any useful info from the graph).

Now, you could find a more suitable graph representation of a game. For example, you could model just the movement of pieces as graphs. On some board games, this is quite boring (monopoly, for example, is an extremely simple graph - 36 vertices each of degree 2) and on others this again gets quite complicated (e,g, with chess, you would need a separate graph for each piece with different connections and it would keep on changing depending on the positioning of the other pieces). However, I believe there is a 'sweet' spot in this view where you have games with more complicated movement that monopoly but simpler than chess where graphs are a much more suitable tool for thinking about the game. Some thoughts in this area lead me to the games of Cluedo and Arkham Horror. In the case of cluedo I'd anticipate simplifying it down a bit to remove the hallways to make a useful graph. With Arkham Horror (a very niche game based off the Cthulhu mythos) there is a much more direct graph transaltion - the entire playing board is a graph with city streets connected to each other and 'play areas' and the graph is updated through the game with new connections as portals open to other dimensions. There are also some areas connected to all the streets (e.g. the Sky) and some that aren't connected at all (the outskirts). Even movement in the game isn't done by dice rolls, but by a character specific set amount of 'nodes' that you can move in a turn. To me, looking at this game as a graph is extremely sensible for this game, but for some others it is less of a useful thought process.

Now, in the case of video games, things become a lot more complicated. Many of these are trying to mimic real-time continuous gameplay, and graphs are inherently discrete rather than continuous (unless you want to deal with infinite graphs with each discrete element being an infinitesimal amount of continuous gameplay... nah, I don't want to do that either :) ). But there are places where graphs are a useful simplification of smaller portions of the game. E.g. path finding used to be done with a graph of 'waypoints' on a map. Some games did straight-line travel between these points, other more sophisticated ones did proper route finding (the simple versions had enemies falling off cliffs at times, if the graph node was just slightly off position).
Also, a graph (or rather tree) can be constructed of the space in the game. In a 2d game, you can construct a quad-tree, where the entire map is divided into 4 sections, then each of those is divided into 4, and so on down until you have a way of referring to parts of space and traversing the tree in a more useful manner than if it was just a simple grid. This can be expanded into the 3d case, where you instead construct an octtree and divide each 3d region into 8 sub-regions, and so on down hierarchically.

Also, at a meta level, the entire game can be considered a simple state graph. The game goes from an initial 'loading' state to a 'menu' state. From this the graph can go to different menus, or to the game, or quit the game. Within the game, there is also a paused state, from which you could reach some menu items, or you can leave the game and go back to the main menu, or quit.

I guess the main thing I'm driving at here is what other people think of as useful times to visualise some game behaviour as a graph. Maybe with that in mind, we can start looking at these specific graphs and working out if they have anything in common, or if there are categories within them, and getting useful maths for the various categories.

Or maybe others can think of ways of making what I class as unwieldy graphs (e.g. the state graph of chess) more useful :)