Modelling Puzzles using Graph Theory

If we want to talk about choice in interactive systems in a technical way it might be useful to have a shared understanding of graph theory. Graphs are a useful tool for understanding interactive systems as they can be used to model the possible states of the system and the possible state transitions at each step in a generic non-game specific way. The aim of this article is to introduce everything one would need to know to understand one very simple generic model that will describe a single player puzzle. The specific puzzle we will use is a simple maze. We know a maze is a pure puzzle as it fits the definition, an interactive system with a goal.


From Wikipedia “In mathematics graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another.”

Graphs Formally

Basically a graph is just dots with some lines connecting them. We can formally specify a graph as a set G=(V,E) where V is a set of vertices and E is a set of edges. An edge always connects two vertices so we can label our edges by stating the pair of vertices that we want the edge to connect. The edge e1=(v1, v2) is an edge going between vertex v1 and vertex v2. The following is a graph we will call G,

Graph Example.PNG

We can modify this graph definition to create what is known as a directed graph. The only difference between an undirected and directed graph is that the edges in a directed graph have ‘direction’. In an undirected graph the edge relationship is symmetric, in a directed graph the relationship only goes one way. As we will later be using this to describe game states and the possible transitions between them we can think of a directed graph as only allowing a move forwards and not backwards.

graph-example

Paths Formally

A path in graph theory is a series of edges that connect a series of vertices which are all distinct from each other. Another way of putting it is that for a series of vertices to be a path we can’t have the path go over the same vertex twice. Formally, for any series of vertices Vpath=(v1, v2, […], vn)in V where n is a natural number (0, 1, 2, 3, 4, …), for that series of vertices to be a path in that order there must exist some series of edges e1, e2, […], e(n-1) such that e1=(v1, v2), e2=(v2, v3), […], e(n-1)=(v(n-1), vn) and for any two vertices vx and vy in Vpath, vx is not the same vertex as vy.

path-example

Trees Formally

A special subset of graphs are called trees. A tree is any undirected graph that has “no loops” and is fully connected, meaning there is only one path between any 2 vertices. Stated formally, for graph G=(V,E), for any two v1, v2 in V there exists a path Vpath=(v1, […], v2) and for any two Vpath1=(v1, […], v2) and Vpath2=(v1, […], v2), Vpath1=Vpath2. This is just saying the path between any two nodes v1 and v2 must exist and if there are two paths from v1 to v2 they must just be the exact same path.

Tree Example.PNG

Rooted Trees Formally

A rooted tree is a tree where we choose one of the vertices to be a “root vertex”. For an undirected tree the choice of root vertex is arbitrary. As our graph is a tree, each path to the root vertex will be unique. We will say that the distance of a vertex from another vertex is the number of edges in path between them. We will also refer to the distance between any vertex and the root vertex the ‘depth’. For any pair of vertices, if the distance between them is 1 then we shall say the vertex whose depth is smaller will be the ‘parent’ of the further away one, and the greater depth one is the closer’s ‘child’. For any vertex, the parent of that vertex is also called an ‘ancestor’. Further, the ancestors of a vertex’s ancestors are also that vertex’s ancestors. In this awkward recursive way, the root vertex is the ancestor of every other vertex. The reverse relationship of ancestors will be ‘descendants’; the child of a vertex is that vertex’s descendant and the descendants of a vertex’s descendants are also that vertex’s descendants . Any vertex with no children is known as a leaf vertex. An important term for later discussions is the ‘branching factor’ which refers to the average number of children that some set of vertices have. When talking about the branching factor of a tree on the whole we tend to ignore the fact that the leaf vertices have no children.

For our purposes we will be interested in a particular type of graph very similar to an undirected rooted tree. Ours will be a directed rooted tree, where edges are directed from the root vertex down towards the leaf vertices while having a unique path from the root vertex to all others.

rooted-tree-example

In these diagrams the root vertex is red, the internal vertices are black and the leaves are blue. We will be using this special form of tree as our first simple model of game states and choices in our puzzle.


Now that we have the graph theory out of the way we can turn to look at how we can apply it to model a simple puzzle. For a maze, the goal is to get from the starting location, through the maze and out the exit. This goal definition is awkward because it makes it hard to compare the properties of mazes to other forms of puzzles like Sudoku or the Parking Lot game. Are these different puzzles meaningfully different or is Sudoku equivalent to a large maze? If we could come up with some more generic description of a maze maybe it would become easier to compare its properties to other puzzles and interactive systems. This is where the model comes in,

puzzle-example

Now we have a tree that fits this maze, can we form some rules to follow to produce a tree given any maze? Well if we look at the maze and the tree together can see we could make the tree by following these rules: the starting point is the root vertex, the forks in the path are internal vertices and the dead ends and exit are leaves. Next time we will be investigating some more puzzles, the ways we can model them, and the similarities and differences we find.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s