Created in 10 days for Scream Jam 2020.
This is a short horror game based on a well-known analogy from mathematical optimization for describing certain local search algorithms (notably gradient descent and hill climb). If our goal is to minimize the value of a cost function, then we can imagine that the objective is like a foggy mountain range and that our search process is a mountaineer trying to get down. Because of the fog the mountaineer's vision is limited, and so they have to make their decisions about which direction to move in based solely on their immediate surroundings.
This scenario struck me as one rife with horror potential, and I thought it would be kind of funny to try to make a horror game based on mathematical concepts. To help flesh things out there are also a few other... things... to discover on the mountain, based on a couple of local search-based metaheuristics that I've used during my doctoral research.
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.
The general problem considered in mathematical optimization is to find a set of inputs (possibly subject to some constraints) that minimize (or maximize) the value of an objective function. Optimization is a major part of applied mathematics and operations research, where it can be used to intelligently plan decisions. It is also a topic with which I have some personal familiarity.
Discrete optimization is a subset of optimization where the objective function is defined over a set of discrete decision variables, such as integer variables or binary (yes/no) decisions. As with many other areas of discrete mathematics, at first it might seem like placing this sort of restriction on a problem would make it much easier since there are far fewer values to consider for the decision variables, but in general the discrete version of an optimization problem tends to be much harder than its continuous analog. For a problem with hundreds of decision variables, there is generally not much hope of being able to efficiently find an exact solution outside of a few special cases. Many continuous optimization techniques rely on the use of the objective function's gradient, but discrete functions have no such thing, and so require a completely different approach.
One major class of discrete optimization algorithms is based on the idea of local search, which relies on the idea that similar solutions should have similar objective values. The exact definition of "similar" varies by application, but if our variables are integers, then a common approach is simply to say that two solutions are "neighbors" if they differ by exactly 1 unit in exactly 1 decision variable (or if they differ by a single ADD, DROP, or SWAP move). This idea of the algorithm's "limited visibility" is what gives rise to the analogy of navigating downhill in a thick fog. In the simplest possible implementation of local search, we begin with an initial solution and then look at all of the neighboring solutions. If one of the neighbors has a better objective value, then we move to it and repeat the process, always looking at our current solution's neighbors to see if any offer an improvement on our current objective value. Eventually we will reach a point where no neighboring solution is better than our current solution, at which point we have achieved local optimality.
You may already be able to see the problem with this approach. While it can guarantee local optimality, it cannot guarantee global optimality, meaning that our search algorithm could get trapped at a locally optimal solution and never be able to find better solutions that exist outside the space it has explored so far. If we only ever allow local moves that improve the objective value then we may miss out on non-monotonic paths that could lead us from the initial solution to the global optimum. One way to try to fix that issue is to apply a metaheuristic, or a general search strategy that typically produces good objective values without requiring information specific to the particular problem. There are lots and lots of metaheuristics, many of which are based on natural processes such as ant foraging, bird flocking, and biological evolution.
This game includes mechanics based on two of the most commonly-used local search-based metaheuristics, although in order to avoid spoilers I will not say exactly how: simulated annealing and tabu search, both of which I've used in my research, and which I've written brief introductions for. Both are similar in that they essentially consist of a modified local search that occasionally allows suboptimal moves in order to escape from local optima, but they differ significantly in how they achieve this.
Simulated annealing does this by introducing randomness, always moving to neighbors that improve the objective value but also moving to neighbors with worse objective values with a certain probability. That probability decreases the longer the search goes on according to a parameter called the temperature, so early in the search when the temperature is high it tends to make a lot of random moves, and late in the search when the temperature is low it tends to favor locally optimal moves. If the temperature is reduced slowly enough then the search will stabilize around the global optimum, although for practical purposes it is impossible to know how slow is "slow enough" or how long we will have to wait, and so like most metaheuristics we simply cut off the search process after we get tired of waiting.
Tabu search is significantly more varied in how it can be applied, but in its simplest form it involves defining certain moves as tabu and disallowing them from being made for a limited amount of time. The tabu moves are meant to prevent the search from revisiting the same set of values too often, which can force the search to escape from a local optimum if the solutions too close to it are all tabu. Tabu search can be significantly more sophisticated in the types of memory structures it uses and how it drives the algorithm through periods of intensification around locally optimal solutions and diversification to explore the search space.
Is it telling that my first instinct when looking for horror ideas was to think back to my doctoral research?
This was the first game jam that I had participated in, and it is the first in what I hope will become an annual tradition of making a mathematical horror game around Halloween. This was something that I had wanted to do for a while, and it allowed me to combine three of my greatest loves: horror, independent game design, and mathematical optimization. The entire game, including all assets and code, was developed in 10 days, which is not especially short as game jams go, but I think that the time constraints definitely show, and I am not completely happy with how some of the systems turned out. My source code is as always freely available in case anyone is interested, but it is quite kludgy and in fairly dire need of refactoring.
This project changed quite considerably from my first conception of it, due mostly to time constraints but partly because of my evolving ideas about how to place the player within a combinatorial optimization setting in a way that would lead to interesting gameplay. Originally I wanted to have the player decide a set of instructions to give to a group of explorers, which would then go out to cover the ground by following various metaheuristics. That might have been more directly informative as to how metaheuristics work, and as a result I may very well make a demonstration like that in the future, but it would not be very fun or scary, and so I opted to have the player directly take on the role of a single character.
I also went back and forth for quite a while about whether to have the goal of the game be to travel uphill or downhill. Uphill seems more natural within a horror game, since it could be explained in terms of gaining the high ground over enemies, and higher altitudes are more naturally associated with the light. However, downhill travel is more directly tied to the analogy that this game is based on, as well as the terms "gradient descent" and "steepest descent". Due to a combination of wanting to use the word "descent" in the game's title and my ideas for the ending, I decided to go with the downhill version.
Gameplay-wise I regard this project as something of a failure. Part of this is due to the muddy visual design which makes it unclear what is going on, but it is mostly due to the fact that I was not able to tune the game parameters enough to encourage the player to exhibit the sorts of behaviors that would mimic those of metaheuristics. In particular I would have liked for the gameplay mechanics to lead to the emergent strategy of alternating between intensifying around a local optimum and diversifying to search other areas, but in the final game there is not much reason not to make a beeline towards the goal. I could have perhaps included more false exits, but that seemed like it would lead to frustrating gameplay.
I really need to stop working on games that rely on enormously complicated systems under the hood that are never really seen by the player and are not very evident to anyone whom doesn't look through the code. In this case, the first few days of development time went to the terrain generation and storage systems. The main gameplay loop of Steepest Descent revolves around the player exploring and revealing a tile-based level with limited visibility. It would be inefficient to generate the entire level at once since most of it will end up being unexplored, and so the level is generated dynamically as the player moves, with explored tiles loading and unloading as they move on or off screen. The level is potentially infinite as a result and more terrain will be generated as the player continues to walk in any given direction. In order to accommodate this, the level size does not actually correspond to the room size. The player is actually fixed in the middle of the room, and the terrain is moved around them to create the appearance of movement, with tiles being loaded as they near the screen and unloaded as they leave.
To generate the terrain for each level, the game defines a few slightly randomized noise functions which are added together to define the altitude of each tile. The standard go-to noise that most games use to generate natural-looking terrain is Perlin noise, which is mathematically interesting but somewhat involved to generate, and so what I settled on was a combination of Gaussian functions, sinusoidal functions, and white noise. As I do with most of my game projects, I prototyped the terrain generation process in Mathematica before implementing it in-game since it makes testing mathematical algorithms so much faster and easier.
All altitudes are positive integers, but are treated as being negative by the game's graphics and text, where the goal presented to the player is to reach the lowest possible tile. The main underlying "base terrain" is a slightly randomized set of Gaussian peaks. Several small peaks are defined to create local optima, while the global optimum has both a thin peak (to ensure that it is taller than anything around it) and a shallow, wide peak (so that general direction of travel towards the tallest peak can be seen from the player's starting position).
Next come the sinusoidal functions, to give the terrain more of a generically hilly appearance and to introduce many more random local optima. The main lesson that I learned through experimenting with terrain generation is the importance of including many different scales of noise, to give the pattern a somewhat fractal appearance. Including only a few sine functions with similar frequencies makes it far too easy to see periodicities in the peaks and valleys that form.
Finally a layer of white noise (as a random integer between -2 and 2 generated for each tile) gave the terrain a bit of roughness.
One aspect of the programming that I am actually somewhat proud of, although in the final build it does not actually end up mattering, is the deterministic generation of each tile's elevation. I had originally intended for the entire game to consist of one very long level, and for the player to be able to save their game during the level. This could potentially lead to an excessively large save file if the entire array of generated tiles had to be stored, so instead I wanted to be able to calculate the elevation of any given tile based solely on the level's random seed and the tile's grid coordinates, meaning that the entire level could be re-generated from only the seed and a list of explored tiles. This was accomplished by using a pairing function to associate a unique integer with every grid coordinate, which was then used alongside the global seed to define a tile-specific seed for each tile's randomization.
There is a tendency among independent game developers, especially for solo projects and game jams, to rely heavily on pixel art. I can attest to the fact that it is very easy to make bad pixel art. Good pixel art certainly exists, but I am not currently capable of producing it. That being said, for as simplistic as the sprites, themselves, are in this game, I think that some of the animations actually look pretty good.
Because the game is seen from an orthogonal view, the difference in elevations between different tiles had to be communicated entirely through shading. Tiles on the player's levels are gray, with higher tiles being colored lighter and lower tiles being colored darker. The game defines a "darkest possible" shade of gray and a "lightest possible" shade of gray, and at any given moment the tiles visible on screen are colored so that the lowest among them gets the darkest shade while the highest among them gets the lightest shade. As a result, the colors of the tiles around the player may change as the player moves. A similar system is used for the highlighted tiles in the player's neighborhood.
Unfortunately I think that the visuals are still to muddy to really make out at a glance which tiles represent ascent and which represent descent, which is why I added a text display to explicitly state which is the case. Moreover, some of the visual effects that get added later in the game get in the way of this shading scheme, and are, themselves, difficult to visually discern in their different states. Considering that the primary gameplay loop involves gauging the elevation of nearby tiles, this is the aspect of the game that I consider to be most in need of additional tuning.
Any fan of horror will tell you that sound design is one of the most crucial aspects, and I have certainly found that to be the case. If you try turning off the music to this game you will immediately see how much heavy lifting the drone soundtrack by Kevin MacLeod is doing. There are also a few ambient forest sounds thrown in for good measure.
As a hint about which direction to move in, the level exits emit a sound that gets louder as the player gets closer. The sound is an auditory illusion called a Shepard tone, which seems to decrease in pitch endlessly despite looping forever. The tone is actually a combination of tones, each separated by an octave, which all descend simultaneously with lower tones being subtly phased out while higher tones are phased in, leading to the illusion of infinite descent. I knew that I wanted to include Shepard tones in the game since I first game up with the idea, and the level goals (plus one other occasion) seemed like the perfect place to include them.
As usual most of the sounds in the game came courtesy of freesound. I think that most of the nature sounds are fairly self-explanatory, but a couple of the more interesting ones include the damage sound (which is a sheet of paper being torn) and the player death sound (which is an orange being squeezed).