Relevant contributions

Procedural generation

The core of this game resides in the procedurally generated maze. Specifically, three aspects of the maze are generated:

• The base layout
• The static obstacles
• The dynamic obstacles

The base layout

To enable the use of complex obstacles in a sensible positioning in relation to the surrounding environment, I decided to build the maze as a composition of simple square rooms I will refer to as ChunkPieces. The possible layouts for each ChunkPiece have been chosen so that it is impossible to generate a closed shape. This guarantees the maze generated will always be fully explorable. The specific shapes I chose can be seen in this note I took early on during the design phase:

The main algorithm generating ChunkPieces is based on Wave Function Collapse and works on a grid of ChunkPieces I will refer to as Chunk. WFC works associating a subset of possible states to each tile and choosing for them randomly a single state in this subset (collapsing the tile in it). Each state is characterized by local constraints that are used to update the possible states of the adjacent tiles, treating thus the procedural generation like a Constraint Satisfaction Problem.

Tipically the constraints are propagated forward: whenever a tile is collapsed into one state, its costraints are propagated to the adjacent tiles. In this game the layout of a Chunk is conditioned by the layout of the adjacent Chunks, thus using a forward propagation approach during the creation of a Chunk would mean creating the adjacent ones beforehand. This could lead to the accumulation of a lot of useless data belonging to "phantom" Chunks. This is because the number of "phantom" Chunks is linear to the number of Chunks effectively visited by the player.
Therefore, I decided to use a backward propagation approach: each time the algorithm wants to assign a state to a tile, its possible states are computed checking the costraints of the adjacent tiles. This way there is no need to create extra data and the system only takes care of the "real" Chunks.

The static obstacles

As for the static obstacles, my goal was to place spikes and bumpers in a sensible but not repetitive way, to provide an entertaining experience. I drew inspiration from the deeply documented procedural generation system used in Spelunky, specifically from the algorithm generating the rooms' layout. Each room in Spelunky has a number of different templates to choose from and each one of these is a grid of tiles represented by characters.
Certain characters represent static tiles: if that character is in a certain position, the corresponding tile will be there. Other characters represent probabilistic tiles: if that character is in a certain position, the corresponding tile will be there with a set probability. This guarantees that a single room template will never appear the same to the player and was exactly what I was looking for. Additional informations about the (quite more complex) system used by Spelunky can be found here.

I then wrote a template for each of the possible layouts for ChunkPieces, obtaining JSON files like this one describing the T shaped layout:

{
   "layout": [[1,1,1,1,1,1,1,1,1,1,1,1],
              [1,1,1,1,1,1,1,1,1,1,1,1],
              [1,1,1,1,1,1,1,1,1,1,1,1],
              [2,2,2,2,2,2,2,2,2,2,2,2],
              [0,0,0,0,0,0,0,0,0,0,0,0],
              [0,0,3,0,0,0,0,0,0,3,0,0],
              [0,0,0,0,0,0,0,0,0,0,0,0],
              [0,0,0,0,0,3,3,0,0,0,0,0],
              [2,2,2,0,0,0,0,0,0,2,2,2],
              [1,1,1,2,0,0,0,0,2,1,1,1],
              [1,1,1,2,0,0,0,0,2,1,1,1],
              [1,1,1,2,0,0,0,0,2,1,1,1]],
    "spawnPoint": true
}

As you can probably imagine, "0"s and "1"s are static tiles (respectively empty spaces and blocks), while "2"s and "3"s are probabilistic tiles (respectively spikes and bumpers). Each Chunk can be created in easy, medium or hard mode and the probability associated to the tiles is proportional to this difficulty property, granting more obstacles in harder Chunks. It is important to note that this data driven approach has been used also to infer the costraints associated to each layout, computed verifying which sides of a template are blocked off by "1"s.

The dynamic obstacles

As for the dynamic obstacles, the procedural generation algorithm is quite simple. Each layout is associated to a series of possible obstacles and, based on the Chunk's difficulty, a number of them is chosen and generated. To enhance variety, each obstacle can be chosen with some random characteristics and is placed in the ChunkPiece randomly within a room of sensible spots. Furthermore, many obstacles exist in an "automated" mode or a "free" mode. Whereas "automated" obstacles are characterized by a motor that makes them move in a pattern, "free" obstacles move with the world's gravity, following the tilt of the player's device. The majority of dynamic obstacles are made of blocks and spikes connected by joints.

Consistency and optimizations

The procedural generation in this game presents a key factor to be considered: a player can always backtrack to previously visited Chunks and, since we can't save the whole maze in memory, they have to be generated every time in a consistent manner. Tipically this problem is solved using a set seed, guaranteeing consistency in the random number generator used. Unfortunately, the algorithm for layout generation I programmed takes into account the constraints derived by adjacent Chunks, thus even working with a set seed, the order in which Chunks are explored would result in an overall different maze layout.

To bypass this problem, each time a Chunk is collapsed into a layout, it is permanently saved, guaranteeing its consistency. This isn't particularly space consuming, since a layout ultimately is nothing other than an integer (or to be precise a reference to a static layout object). All the other characteristics of a ChunkPiece, such as static and dynamic obstacles, are generated each time using a set seed, since they aren't influenced by external factors.

Furthermore, since there can be quite a few objects on screen, only the ChunkPiece currently navigated by the player and its adjacent ones are rendered on screen and simulated. Specifically, only the collisions in the central ChunkPiece are active, since they are the only ones the player can directly interact with. Each time the player moves from a ChunkPiece to another, the ones forward are immediately built and rendered while the ones behind are set to be removed. To prevent lag spikes, the ChunkPieces are not deleted in a single frame, but instead are marked and then deleted singularly per frame.

Finally, since this game is developed in Java, one of my goals was to keep the number of objects eligible for garbage collection as low as possible at all times. This, along with the need to avoid spawning large numbers of identical game objects such as blocks, spikes, and bumpers, led to the extensive use of object pooling.