Inferno Devlog


Here I describe some of the technical challanges and design choices I've dealt with when writing the game engine and designing the levels. The main goal for me was learning how to make a game engine from scratch. The final product would have looked much better going with an existing game-engine and openGL rather than CPU-rendering. I have a math background but very limited programming experience, I did some Python before but this is my first project in C/C++.

Design principles and goals

When starting out I had a number of things I wanted to achieve:
  • Code everything from scratch in C/C++, no external libraries
  • Over 100 puzzle levels
  • Serious tone to the presentation
  • Each puzzle should bring something new, no repeating puzzles
  • Puzzles shouldn't require massive trial and error to solve, the player should be able to find the idea to solve them
  • The setting of the levels (not the puzzles themselves) should follow Dante's poem pretty closely
  • Each circle of hell should bring some new mechanic
  • Each circle should have its unique color scheme, lighting scheme, textures
  • Each circle ends with a "boss puzzle" requiring mastery of the mechanic
  • Avoid puzzles requireing timing or fast inputs.
  • Minimal UI
  • Over 60fps on an average CPU
  • Playable without instruction
  • Playable with only keyboard or mouse
  • All level creation from an ingame editor
  • Coherent menu-system with many configurable options
  • Quotes from Inferno before every level
  • Colorize art for each section of the game
  • Steam integration with achievements

Python-Prototype

While experimenting with Python and pygame in I made what would be the prototype for this game, depicted to the left below. The game world is represented by a 3-dimensional array of blocks, vertices are projected to the screen and using pygame.gfxdraw.filled_polygon I could draw simple 3d world to the screen. All surfaces are a solid colored and there's no lighting engine. The game at this point ran with python at about 80fps. All movements are discreete, so the game is playable on a 10fps framerate at this point. Originally I used a fixed isometric perspective, but by keeping track of the projection of three basis vector it was possible to allow for rotation and zooming of the game-world allowing for any orthographic perspective (meaning an infinitely zoomed in view from infinitely far away, making all blocks look the same size regardless of the distance to the camera).
Above is a picture of the level containing the gate to hell in the python version (left) and an early version of the c++ version (right). The main differance is the lighting engine and that some blocks are textured. The c++ version still runs at a higher fps.

Graphics Engine

The first step when moving to C++ was to make the graphics engine, and to make it run fast. Using something highly optimized like OpenGL would give the best results here, but wanting to learn how things works I decided to write the engine from scratch.

Screen Buffer

The pixels that are drawn to screen every frame are stored in an array of size screen_width*screen_height. Each pixels is represented by an unsigned 32-bit integer. This corresponds to a color, if a pixel value is 10ff2a (in hex) this corresponds to an RGB-color value of (10,ff,2a)=(16,255,42). This uses only 24 of the 32 bits, but is still a good way to do this considering how sequential bits of memory are read.

Projection

All game objects are represented by 3d-vectors, with the basic block being of size 1x1x1. To draw these 3d objects on a 2d screen we need a mathematical projection formula pr: R3->R2. To do this I keep track of the projection of the game-world basis vectors E1=(1,0,0), E2=(0,1,0), E3=(0,0,1). Let e1,e2,e3 be the projection of these. For example, an isometric perspective corresponds to e1=(sqrt(3)/2,-1/2), e2=(-sqrt(3)/2,-1/2), e3=(0,1). Then since orthographic projections are linear we can simply define a function pr(x,y,z):=x*e1+y*e2+z*e3, and only recalculate e1,e2,e3 when the perspective is changed.

Drawing polygons

With the projection function in hand we can draw a block at (x,y,z) drawing its six surfaces as filled polygons. For example, the top surface of the block has corners in game world coordinates (x,y,z+1),(x+1,y,z+1),(x+1,y+1,z+1),(x,y+1,z+1), so by projecting these four points we get the corresponding polygon corners on the 2d-screen. We still need primitive functions to actually draw a solid-colored 4gon on the screen though. To draw a line parallell to the x axis, we simply loop through all the corresponding pixels in the pixel buffer and change the values to the appropriate color. A triangle on screen with one side parallell to the x-axis has corners in (x0,y0), (x1,y1), (x2,y2) where y0=y1. These can be drawn by drawing a line at each y-coordinate between y0 and y2, the start and endpoints being expressible in an algebraic expression in x0,x1,x2,y0,y2. Any triangle can be split into two trianges of the form above (split it with a line parallell to the x-axis through the vertex with y-coordinate between the other two y-coordinates min(max(y1,y2),y3)). Finally any 4gon can be split into 2 triangles (or generally, any n-gon can be split into n-1 triangles), so this allows us to draw block faces to screen.

The game also has primitive functions for drawing 3d-lines, spheres, cones, and cylinders - the projections of these consist of basic elements like circles, ellipses, lines and triangles.

Textures

Textures are stored in a single atlas.bmp image, which is loaded on boot into a pixel buffer. A simple struct keeps track of location and size of a texture within the atlas, as well as animation meta-data. A texture is typically a 32x32 square which will be projected onto a block surface. To achieve this, when we have projected the four corners to the screen we get four screen coordinates. Let us assume the first corner is (0,0), otherwise we can apply a simple translation. If the corners of the 4-gon are (0,0),(x1,y1), (x2,y2), (x1+x2,y1+y2), we note that the linear transformation
f:(x,y)->x*(x1,y1)+y*(x2,y2)

maps the unit square [0,1]x[0,1] to the given polygon, so its inverse f-1 maps the polygon on screen to the unit square, and 32*f-1 maps a point inside the polygon to the corresponding pixel in the texture, this lets us set the pixel color correctly when drawing the 4-gon (here one has to be careful about rounding issues). This operation is what takes up most CPU time in a regular level.

Some early experiments with textures.

Optimizations

Drawing textures this way using the CPU is expensive and lowers fps significantly, on the other hand this looks a lot better than solid colored blocks. A first optimization is achieved by noting that in any orthographic projection of a block, we only need to draw the three surfaces that face the camera. To do this one need only to keep track of which octant the camera is in (meaning the sign of the x,y,z coordinates of the camera). This halves the cpu required. Another thing to note is that in a typical level, many blocks are obscured and will not need to be drawn. Although its complicated to compute exactly which blocks are completely obscured, we note at (x,y,z) is definitely partly obscured if there are blocks at (x+1,y,z), (x-1,y,z), (x,y+1,z),.. and so on. Ignoring such block sides saves a lot of cpu-time on levels containing large chunks of land, lika mountains.

Blocks, shapes, and physics

The basic element of the game is the "Block" - a 1x1x1 solid shape. It has integral (x,y,z) coordinates, and textures or colors on each side. Blocks also has attributes, they can come as solid, static, floating, destructible. Some blocks can be keys or doors, some have ladders attached. A collection of blocks can be stuck together forming a "Shape", like a tetris piece. Blocks are structs stored in an array, a Shapes is simply a container of pointers to such blocks. The game needs to handle pushing shapes, this is handled by a recursive algorithm that checks wheather adjacent blocks in the push-direction are blocked or free to move.
If a block is about to move, all blocks on top of it should also slide along if they are not blocked. This leads to some dilemmas on how to define movement, for example, if a shape rests on two other shapes and one of those shapes move, should the top shape move along? In the end I decided that the answer should be yes, it looks unrealistic in some cases but I would prioritize consistency of game mechanics over absolute realism.

Left:Recursive search through the tree of adjacent blocks. Since one of the blocks in the push-direction is blocked by a wall, nothing will move. Right: Dilemma when the blue shape is pushed, clearly the magenta-colored shape should slide along, but should the red?

There's also gravity, blocks fall down quickly if there is no supporting block under them. This also leads to some problems, for example, two shapes can support each other, like two connected C-shaped blocks.

Above a level from the Circle of Heresy is shown. The five tetris Shapes has to be puzzled into place to allow the bridge to move.

Draw order

A major difficulty is the order in which blocks and game elements are drawn on screen. An advanced engine like openGL has algorithms running on the GPU to compute intersections of polygons. For me I cannot split polygons into distinct drawable objects. Luckily, as long as blocks are kept to a grid, given any two blocks overlapping on the screen, one will always be in front of the other. This is more complicated for shapes consisting of several blocks. For example three long shapes A,B,C parallell to the three coordinate axii respectively could be arranged in such A>B>C>A (where > means "is in front of").

Three shapes where none of them is in front of both the others - which one should be drawn to screen first?

For reasons such as this, shapes are drawn block by block. Although all movement is on a discrete integer grid I added a sliding animation to make it look smoother, this causes some major problems in the draw-order of blocks. In the end the final algorithm works roughly like this when the camera is in the first octant:

Lighting Engine

A light-source is a struct having several attributes. The basic are (x,y,z) position, color, and intensity. But lights can also pulsate with different colors and intensity, they can rotate around a point (allowing for fireflies, or a night and day cycle for example). Some lights are directed, meaning they only shine in a cone, and some lights are ambient, meaning that they only take into account distance to surfaces, not direction of the lightbeam relative to the surface normal, allowing for smoother light, and some light sources has a lens-flare effect. Normal lights illuminate surfaces with intensity proportional to the inverse square of the distance to the light source (as in the real world). Some lights are special, where this square can be modified to any real number (in reality this could be observed if there is fog or dust in the air). Lights can also be attached to blocks, allowing players to carry lamps etc. The game looks a lot better with this engine, but it is quite cpu-costly. Early versions saved the lighting levels of blocks to reduce cpu drain, but current versions update all lighting every frame which looks a lot better when lights are moving.

Early experiments to make sure that distance and angles interacts properly with the different colored surfaces.

Being able to quickly change light intensity and colors makes it very easy to change the look and feel of a level. Some design decisions also had to be considered - for example, I wanted the whole circle of Fraud to be fiery red - should the blocks themselves be red (meaning they only reflect red light) or should they be lit only with red colored light? In the end I went with the latter, the end result looks a bit muddy since Dantes purple clothes will look brownish in the red light, but to me it looks more realistic.

The same level when changing the color of the sun.

Lens flare

Light sources are typically invisible points in space, often far outside the level to give smooth lighting. For some levels, especially in the circle of wrath I want the player to know exactly where a source of light is. For this I added lens flares - appearing as a smooth circle around the light source. The flare consists of a number of opaque circles of the same color as the light, the radius of the circle is related to the intensity of the light source, so pulsating lights will give pulsating flares. A problem is when in the draw-order to do the flare. The idea is that the flare is an effect in the camera observing the scene, so the full circular corona-effect should be visible on screen when the light sources center is visible. For this I used an algorithm that steps from the light-source to the camera until it exits the level. I added opimizations to deal with light-sources far outside the level, like "suns".

A light attached to Minos' key in the circle of lust (left), and testing how lens flares interact when being obscured.

Saving Levels

In the early python version I used a pickle-library to quickly serialize game objects and store them into files, which was quick and easy. Here I had to write my own serialization algorithms. The choice stood between binary or text format. In the end I went with text-files since it is easier to debug errors when you can read exactly what is in the file. There is some problem when saving shapes consisting of several blocks as one has to keep track of this tree-like relationship when saving and loading. The map-file consists of several keywords, for example here is a few lines from a level file:

shape 1 1
0 0 0 0
block 0 0 0 0 0 0 0 2105408 2105408 2105408 2105408 2105408 2105408 0 0 0 0 0 0
block 0 1 0 0 0 0 0 2105408 2105408 2105408 2105408 2105408 2105408 0 0 0 0 0 0
end_shape

 This corresponds to a shape which is unpushable, and unaffected by gravity. It consists of two blocks with coordinates (0,0,0) and (0,1,0) respectively, there are no ladders on either block, and all sides are colored rather than textured, the color of each side corresponds to the value 2105408 when translated to hex. So roughly there is one line for each block of the level, making files of about 2000 blocks on average. The game also saves data about the lights, weather effects, and some metadata, and the poem-text associated to the level in a similar formats. Most level files are around 100kb, which can be loaded by the deserialization algorithm almost instantly. One could argue that we dont need to save all this information for most blocks, like static background blocks that never move, and blocks inside a mountain that are never seen. But I like the idea of all blocks beeing equal, and that there is real dirt beneeth the grass. Also it allows for some cool effects on level load:

One of the several intro/outro effects I tested.

Level editor

In order to be able to make 100 levels I wanted to make an editor which was very user friendly and which didn't require modification of files outside the game. It took a long time to make this editor, making sliders, buttons, positioning everything consistently, and dealing with bugs. The editor is still not perfect and I do not plan to include it in the release version as it still uses a console for some text inputs. The thing that really sped up the level editing speed was the addition of being able to click on a surface with the mouse. This allowed rectangular selection and quick drawing of textures on surfaces. The problem is that the mouse position on screen typically overlaps several surfaces, so the game constructs an inverse to the projection function that computes a set of all possible surfaces clicked on, then it returns the one closest to the camera. Here is what the editor looked like some time into development:
There are five modes, selecting multiple positions by drawing rectangles, selecting by clicking, the paint-modes to paint surfaces or full blocks, and Light edit mode. In block-paint-mode, the clicked or selected blocks are pained the same as the surfaces of the pre colored fold-out cube in the center left, which you can edit before painting. There are also buttons for merging blocks into shapes, setting shapes as pushable, adding text and so on. In light edit mode most of the menu changes.

Font

It turns out that it is hard to make a good looking font from scratch. I wanted a mono-spaced font to make things easy. I started by making a minimal font where each letter consisted of 7x4 pixels forming capital lettesr. This is used only in the editor and when displaying compact data such as fps. Here each letter is simply an array of 7*4=28 bits corresponding to pixels. Theres also a draw function for simply multiplying the size by an integer, which makes it easy to make large but terrible-looking letters. I then used the same idea to make a larger font of size 15x20 which is used for the in game menu and for the lines of Dante's poem. The font still looks jagged and weird without kerning so there's room for improvement.

Background blur

Originally the background was always black which looked pretty good. My idea was to instead have the background follow roughly the same color scheme as the level itself. I ended up designing a background similar to how some photos and videos with black borders are filled up: by using a very blurred version of the image itself. To do this I wrote a gaussian blur filter which uses three box-blurs in the x and y direction respectively. This is far to slow to do every frame, so on level load the level is zoomed in to cover most of the screen, the filter is applied, and the pixeldata is saved in a secondary buffer which is copied into the main buffer every frame, this all happens in about 20ms on level load and is invisible to the user. I like the look of this blur effect, but the black color had a certain simplicity to it, so I kept it as an option.

Game Menu

I wanted the game menu to be easy to use, many things should be configurable, and the effects should be clearly visible or demonstrated when changing options. The options menu looks like this:
Here the text on the top of the screen explains what the hovered option does. Clicking fancy backgrounds will immediately set the background to black so the user can decide what to use without leaving the menu. Since the menu is overlaid upon the game, I wanted the text to have good contrast. Therefore the menu text changes depending on the Circle of Hell. In the picture above we are in the Circle of Fraud which has a red theme, therefore the color scheme of the menu is set in orange-yellow.

There is also a level-select screen. Here I wanted to use thumbnails rather than names to make it easy for the user to recognize and find an old level.
This image is generated by an algorithm that sequentially loads all levels, zooms out a lot, and copies the miniature level into the corresponding position of a pixel buffer, and saves this image as a bmp. This algorithm takes a couple of seconds to run so it is only done before publishing new versions of the game.

Music

Music is the one thing I did not do myself, instead I use around 60 tracks of royalty free music found online. Each circle of inferno has its own collection of 5-10 songs trying to match the general mood of the scenes. Typically songs get more tense and oppressive the deeper you go.

Sound Effects

I made these myself which was a lot of fun. I used a Röde microphone. The sound for breaking a block comes from crushing a piece of clay, the basic step-sounds is me squeezing a sand-stuffed toy, pushing a block is me pushing a big plant on my desk, while picking up keys and opening doors is recordings of me doing just that. Using the same sound for the step sounded very monotone, so I recorded a number of similar sounds and choose randomly between them when the player moves.

Art

Throughout the ages artists have made depictions of scenes from Dante's Inferno. Luckily most of these are old enough to be in the public domain. My favourit are Gustave Dore's wood engravings. Since these are black and white I decided to color them for the game. I used the Krita software to draw a color layer and combined it by the "multiply" which was surprisingly easy. Still it took many hours, and in total I colored around 50 of these images. Being able to chose colors also had the benefit of letting me match the colors to the actual colors of the levels in the game.

Above is a picture of the original Dore-engraving (left), my color layer (middle), and the merged result (right). A surprisingly good result considering what I added.

Dante and Virgil in Limbo (left) where they meet the people who neither picked the side of good nor evil. And in the Circle of Treachery (right), where the sinners are permanently stuck in the ice. Dante is usually depicted wearing red clothes (which was an indicator of wealth since the pigment was expensive). Since many levels of hell are red I decided to go with purple clothing for my Dante.

Level design

Creating levels is a time-consuming process and it can be hard to come up with an ideas for good and interesting levels. My philosophy here has been to "get it right the first time" since it is frustrating to go back and delete or rework a level I was not happy with. I mostly used graph paper (which is hard for levels with verticality) for coming up with the ideas before implementing them and tweaking them in the engine.

A puzzle from the Circle of Lust where locks and keys are introduced. Initial idea on paper, implementing it in engine, adding colors and textures, and finally lighting and additional decorations.

Level design using wooden cubes.

For each circle I typically had one or two levels to introduce a new mechanic, and then the players progressively learns to apply it to different situations and to mix it with previously learned mechanics. Most circles end with a "boss puzzle", where the player has to combine what they learned to beat a hard puzzle (this does not necessarily mean there's physical "boss" in the puzzle). There are also some levels that are only there for the atmosphere, where the player just moves through, such as a level going down a set of stairs between two circles of Hell to give the feeling of actually descending into the earth. Such walk-through levels doesn't count towards my 100 level goal though. At the moment of writing this there are about 133 levels, 108 of which are puzzle levels.

Dictionary

The old Longfellow translations of Inferno - though charming - may be to hard to understand for some audiances. Therefore I added a dictionary containing over 600 words and phrases. Users can hover words in the level intro to read an explanation. The dictionary also provides short info on the historical and mythological persons Dante meets on his journey, like Virgil, Cleopatra, Minos, Cairon, Trisan, count Ugolino etc.

The start of the game and the first epic lines of Dantes poem.

Undo moves

The player can hit Z to undo a move. Since the game has things like destructible blocks and moving npc's it is not so simple to reverse a move. Instead the level state is saved every time the player clicks a movement button, and then loaded on undo. This works just like the quicksave - with the main difference that it only saves positions of active blocks (pushable, breakable, npcs, light sources etc). In a normal level there are around 10-20 such blocks, but some levels have over 100. Instead of saving to a file I save each such state as a string and store them all in a vector. There are effectively unlimited undo's, but I set an artificial limit of 1000 undos to avoid potential memory issues. If you watch somebody else play and they click undo it looks really strange, like the player jumpp backwards. Therefore I added a small poof-effect to give feedback that the undo key was pressed.

Rain and particles

Some levels have rain, firestorms, dust, snow, and hail. let's just call it rain. The level meta-data contains information about the rain, it has a direction, speed, length of streaks, color, number of particles (0-500). Rain is not drawn on top of the level as in some games, but individual particles are sorted into the draw-order and drawn at their exact position, this is relatively cheap CPU-wise. This also makes the rain-direction independant of the viewing angle. The rain particles can be distracting for some players, so there's an option to turn it off. Levels with rain also has wind in the rain-direction, so Dante's mantle will move.

There are also some particle-effect when breaking blocks. When a block breaks, a the texture on 3 of the blocks sides are used to create the particles. These particles are also effected by gravity.

Random numbers

The standard c++ library contains a rand() function yielding a random integer between 0 and some high limit RAND_MAX. One problem is that you might need several independant generators that you can reseed without effecting the others. I wrote a very simple such generator: It starts with a nonzero unsigned integer, say 331 and every call to rand() it multiplies this number by a fixed high prime, say p=324294301 and returns the result (bit-shifted and turned into an int). When the unsigned integer overflows it is automatically reduced modulo the maximum unsigned int. Since p is prime the period of this generator will be maximal, meaning that that it will go through all unsigned integers before returning to 331 (or whatever starting value you choose). You can also seed the generator by setting its current number to some integer (but one has to avoid 0 here).

This rand function is fast, relatively well distributed, and easy to use, for example, to get an integer on some interval [a,b] one can do a+rand()%(b-a+1), and for a 3 decimal float on [0,1] one can do (rand()%1000)/1000. I use this generators for a few things - one intro effect has blocks randomly appearing on screen, and raindrops are generated at random positions.

Steam Integration

I decided to add some light steam integration after finishing the game. Currently there are twelve progress-achievements, one for each circle, but I may add some more interesting achievements later, like solving a level in a certain number of moves to add a bit of replayability. Using the steam library does mean including another library, but on the other hand this doesn't really effect gameplay.
Unfortunately the Steam overlay is not compatible with a custom graphics engine like mine, so the achievements doesn't pop up on screen when achieved. I fixed this by adding my own custom-achievement popups:

The first twelve achievements viewed on Steam.

Custom popup achievement when reaching the second Circle with a Dante-quote from the Circle. The small thumbnail is of Francesca and her lover, this is a small section of a larger painting that the player will find later.

Contact

Feel free to contact me If you have any questions, suggestions, or feedback!

infernopuzzle@gmail.com
@inferno_puzzle on twitter




Back