This is a minimalist puzzle game that explores a variety of graph coloring problems. The goal of each puzzle is to color the given graph according to a particular set of rules. The game is meant to be accessible to everyone and does not require any mathematical background.
A graph (also known as a network) is a mathematical object used to represent pairwise relationships. We encounter graphs constantly in our everyday lives, and they can be used to represent an endless variety of physical and abstract structures ranging from social connections to infrastructure networks to biological pathways to digital data structures to symmetric systems of sets, just to name a few.
The game is divided into several sections, each of which follows a different set of rules regarding which elements can be colored and what criteria must be met in order to solve the puzzle. Part of the challenge lies in figuring out what, exactly, the rules are in each of these sections, which will require observation and experimentation.
This game was developed in GameMaker Studio 2. It is available for free at my itch.io page, and the source code is available under the MIT license at my GitHub page. Please feel free to modify it in any way you wish.
This is a spoiler-free discussion of the game's mathematical background. If you have already completed the game (or you do not care about spoiling puzzles for yourself), you can read about the backgrounds for some of the specific puzzles here.
Graphs are great. In the same way that numbers represent the fundamental unit of information for describing quantities, graphs represent the fundamental unit of information for describing relationships. A graph (or network) is defined with a pair of sets: a set of vertices (or nodes), which represent the objects we are interested in talking about, and a set of edges (or arcs), which are made up of pairs of vertices that are related to each other. Any system that involves interrelated things (which includes pretty much any system you can imagine) can be modeled using a graph. A few common examples include social networks (with people as vertices and edges representing pairs of acquaintances), road networks (with locations and intersections as vertices and edges representing road links between locations), and assignment problems (with employees and jobs as vertices and edges connecting employees to the jobs for which they are qualified), although countless more (and more abstract) applications exist.
A large part of this game revolves around exploration and discovery, and so I would rather not go into too much detail about the specific graph theory problems contained within it for risk of spoiling the experience. As described above much of it revolves around the concept of graph coloring. There are many variants of the graph coloring problem, but in its simplest form the goal is to apply a color (or a label) from a limited palette to each vertex so that adjacent vertices are always colored differently (such a coloring is called a proper coloring). Obviously this is always possible when we have enough colors, and so the goal is generally to complete the coloring with as few colors as possible or with a limited number of colors, which is in general a computationally hard task.
Graph coloring problems have important applications throughout operations research, and are generally used for allocation and planning while avoiding some type of conflict. One particularly well-known example is classroom scheduling. For example, suppose that we have a list of classes, each taking place within a set time slot, and our goal is to assign a room to each class. Obviously we should not assign two classes to the same room if their time slots overlap, however classes taking place at different times could conceivably take place in the same room. We could model this problem as a graph coloring problem: we define a vertex for each class, we define a color for each available room, and we define an edge between two vertices if their corresponding classes overlap. Coloring this graph corresponds to assigning each class to a room, with the color of each vertex representing the room assignment for the class. Because we defined vertices to be adjacent if and only if the corresponding classes overlapped, a proper coloring of this graph corresponds to a room schedule that is free of conflicts. This basic modeling technique can also be used for other related problems for which we wish to avoid conflicts of some sort.
I strongly believe that an introduction to graph theory belongs in every elementary school classroom. Not only are graphs an incredibly important tool for modeling real-world phenomena, they also provide the opportunity to explore the side of mathematics that revolves around structure rather than quantity, which can go a long way towards dispelling the common misconception that math is only about performing calculations with numbers. This, plus my doctoral research, is a large part of the reason why graph theory is so close to my heart. As a bonus, a lot of common graph theory problems look and feel exactly like puzzles and games and are inherently visual in nature, which makes graph theory incredibly accessible for children.
As with many of my personal projects, the origins of this game can be traced back to my Dungeons & Dragons campaign. For years before I began running my first D&D game I had been accumulating ideas for particular puzzles and gameplay sequences that I thought would be interesting. I knew that I wanted my campaign to reflect my own interests, and so I wanted to make a point of introducing a variety of mathematical concepts into it. I tend not to think very highly of the puzzles that generally show up in RPGs, which often consist of terrible riddles or simplistic lever pulling or the like. Not only that, but it is difficult to convey instructions for a puzzle in a way that seems natural within the game world, particularly if the in-game mechanism is meant to be based on some piece of arcane and unknown technology. This prompted me to explore possibilities for designing interesting puzzles whose rules would not have to be explicitly explained. My first attempt at implementing such a puzzle, which I included in the players' first mission, was mapped out like this:
The puzzle consisted of a set of ten pressure plates on the ground with lines drawn on the floor between certain pairs to define a graph. The goal of the puzzle was to have the five players stand on the correct combination of pressure plates to open a door to the next area. The door was sealed with five metal bars, which retracted one-by-one as the players got closer to the solution, but which slid back into place as the players got further from it.
What I did not tell the players (and what was their job to figure out through experimentation, which to their credit they did rather quickly) was that this was an independent set problem. The solution was to have everyone stand on pressure plates that were not adjacent to each other. Because figuring that out through pure trial and error would take far too long on its own, the puzzle also included some instant feedback in the form of the metal bars, with the number of retracted bars corresponding to the number of players standing on pairwise nonadjacent plates. By observing which actions caused the bars to retract and which caused them to return the players were able to figure out the rules for the puzzle, and then the correct solution which fit within those rules.
I regard this puzzle as a success, and it is an example of a broader puzzle design style based on inductive logic, where figuring out the rules of the puzzle is part of the puzzle. This design philosophy is central to some of my favorite puzzle games. Particularly for this project I was inspired by World of Goo and The Witness, both of which do an excellent job of getting the player to figure out, for themself, how their puzzles work, and then gradually building up to more and more complex tasks (they also happen to both be games about graphs, in a way, but that is purely a coincidence).
Chromagraph essentially represents my attempt to create a complete gameplay experience to get the player to explore and teach themself a variety of graph theory concepts. Originally the game was going to cover a much broader array of graph theory problems, but for simplicity I decided to include only problems based on graph coloring (and things that can be stated in the language of graph coloring, such as graph partitioning and labeling). The inductive logic aspect of the game was central to the design, and informed many other aspects of the game such as the minimalist interface, the complete lack of written instructions, and the immediate visual feedback regarding which elements of the solution are invalid.
The visual design was very much informed by the game design goals. I knew that I wanted the game to be as free as possible from direct instructions, and so I made efforts to avoid having to use text wherever possible. Besides the credits there are only a few instances of text within the game (including explanations of the controls and save functionality), and they occur only where I thought it would be impossible to convey important information purely visually.
This design principle extended to the choice of puzzles to include, and thus also to the decision to base the entire game on graph coloring and related problems. I tried to choose only puzzles whose solutions could be submitted purely by clicking on portions of the graph, and whose rules could be communicated purely by experimenting with the graph, itself. In particular I wanted to choose puzzles for which it would be easy to give immediate visual feedback if any aspect of the solution was invalid (for example, indicating when a pair of adjacent vertices used conflicting colors). Originally I had planned to include some puzzle types that would require meters and additional graphics to the side of the graph in order to display things like budgetary constraints. These were cut from the game in order to preserve a consistent design aesthetic, although I have plans to use them in a future project.
I think that the inductive logic design approach works particularly well for puzzles which, in-universe, are meant to represent ancient, alien technology that the player is discovering for themself. I attempted to make the puzzles seem as if they are carved into stone, as if the player is an archaeologist exploring newly-unearthed mechanisms. The specific graphics and sounds are meant to hint at a vague story for what the player is doing, but I would prefer to leave the story of the game up to the player's interpretation.
In any puzzle game there is the risk of the interface looking too static and boring, since the player is likely to have to stare at the same screen for extended periods of time while deciding which action to take. As a result I wanted to ensure that everything on the screen would have some subtle motion, without distracting from the important elements of the puzzle. This was achieved by applying some atmospheric particle effects to the entire screen while making the puzzle elements slowly pulsate and rotate.
Early in development the vertex colors were represented in the obvious way by simply changing the graphical color of the vertex. However, eventually I added a puzzle type based on vertex labeling for which the numerical labels of the vertices were actually significant. For this reason, as well as for providing colorblind support, I needed to establish some sort of numerical labeling system for the vertices. In order to fit in with the rest of the game's design aesthetic I wanted to avoid using any easily-recognized number system such as Arabic numerals or Roman numerals. Some of the alternatives that I considered included drawing numbers as complete graphs, as arrangements of dots based on figurate numbers, the Mayan numeral system, and the Kaktovik Iñupiaq numeral system (which is probably my favorite numeral system). Eventually I decided to use arrangements of dots based on circle packings, partly because their rotational symmetry makes them work well with the rotating vertex graphics, but mostly because I liked the idea of hiding an additional, unrelated mathematical concept in the game. The numbers 1-18 are represented as the following:
The sound effects for this game were made using a combination of assets from freesound and sounds recorded on my own microphone. I think that most of them are fairly recognizable, but you might be curious about a few of their sources. The sound that plays when cycling the color of a vertex is a compressed recording of me exhaling, with its pitch modulated according to the vertex label. The looping rumbling sound that plays whenever there is an invalid solution is the slowed sound of a train screeching. There are also various soft tapping sounds used throughout the game, which are made from the sound of stone grinding and the sound of me knocking on my desk.