Abstract

This article is on how I could write a 3D engine using only excel formula, including following functionalities :
- infinite procedural generated maze map
- real time ray tracer rendering
- occlusion calculation
- basic illumination rendering
- illumination and compute shader
- natural displacement engine
- No macro at all used by the 3D engine,
    * to enjoy the game using key press, some macro trigger the displacements, using just one simple copy instruction.

In-game screen capture

You can freely download the file and test it by yourself !

Files

Demonstration

Context

A computer science teacher once told us "a given computation can be achieved with any programming language, even spreadsheet formula".

At first, as wise at it could have been, including Excel in the comparison sounded definitively stupid ...

Thereafter, while studying Turing machine, it then sounded correct, yet not very fulfilling.

Several years of experience with Excel, we will mostly remind Excel formula only are definitively limited with the lack of input/outputs.
But, the set of problems that can be simply solved with formula only remain impressive. 

Anyway, this work is not just some kind of performance ... There is was a good reason for me to do it.

Spreadsheet are a powerful tool that everyone has to learn to use for almost every business jobs.
Yet, when most people come to solve most complexes problems, they want to use VBA language, without even knowing why.
And once they started learning it, they try to use it for any kind of problem, even simple search or rendering.

Today, as an excel teacher, I'm trying to explain to these people why writing VBA macro for any problem while not being educated on computer programming is not only a real waste of time, but also a serious risk for their spreadsheet quality.
In a business environment, using formula rather than macro is :

Nota : these concerns mostly apply to procedure used as macro, while additional function written in VBA can increase the efficiency without lowering the quality.

This is how I came to write this game : an applied demonstration, that macro was not necessary at first, even for some of the most complex problems.

To be more precise, I found only 2 cases when VBA is required :

This said, now, I'll only focus on the rest of this article on how the spreadsheet actually works, for its different aspects.

The Map

The spreadsheet is meant to be a doom-like game, in a sort of maze environment.
It could have been a fixed, manually-constructed map, possibly looping on borders, but it would require storage, lookup, and an initial design.
In the meantime, using a procedural generated infinite map sounded much more worth of the effort.

To get a random generated map, we need it to be self-consistent over time, so rand() function could not be used, as we do not control the random seed.
The seeds for the random generator have to be the position (x;y) on the map, to get a different value for each position, and we cannot take the result of the previous random as seed for the next, or we would have to store all the map from the beginning.
While providing high quality random, usual hash functions are too expensive, so I needed to find an other one.
Trying to use fractal generator appeared to be also quite costly, and providing interesting result only for a small part of the map.
Then I found the middle-square method, which isn't very "random" when consecutive seed are used, but gave me the idea of taking decimal of any other calculation.
I found out that taking decimals of sin(x)+cos(y) finally provided nice decimals, without any visible pattern, and a computation time surprisingly short.
To get decimals, mathematical function mod() and floor() are much more efficient compared to text function substring mid()
Trying to get the map looking like a rat maze, I didnt made block of solid block, otherwise it would have looked like a cavern (minecraft style) rather than a maze.
So we needed thin walls, with 2 possible walls for each square. We can then take 2 blocks of digits among the same random value.
2 parameters controlling the density of walls.
Given theses rules, we can either display the maze, or test any wall given it's position for raytracing.
Note that the map is "flat", without any top/down. It would be possible to add relief using relief generator (diamond-square algorithm could apply, as it is possible to write it with a non-recursive function), but the solution of cutting holes in both ceiling and floor, with an additional level value would greatly ease the whole following process.

Ok, we're definitively in hell

Raycaster

The raycaster solution imply to determine for each pixel which face the ray would touch first, and retrieve some information from it, (distance, angle with light, color ...).
Raytracer also require additional ray to spread from this point (reflections, transparencies), with a direct massive increase on computation cost.

Occlusion

The first problematic will be to find the first object in the course of each ray.
Since the maze is actually flat, with horizontal walls, the nearest wall found will be the same for all pixels of a given column.
The process can then be simplified as an horizontal radar, on 1 dimension.
Then, there is no choice but testing for a wall on the first possible wall, then the second possible, until we find one.
It's only a trigonometrical problem to determine which wall are to be tested.
And as we have 2 kind of walls, we have to test both of kinds, and then keep only the nearer.
One of the limit in excel is that condition loop does not exist, and the loop body can only be skipped to save time. So we should cut the maximum checking distance, assuming there is no wall at all if not found until then.

Floor and Ceiling

To represent floor and ceiling, we just have to find where wall does stop.
A dedicated sheet mesure the distance of the floor or ceiling depending of the vertical angle.
Then, for each pixel, we decide if the wall is further or not than the ceiling of the floor, and decide the pixel color accordingly.
The comparison is made efficiently by using only the projection of the distance of both wall and ceiling/floor on the camera axis. The final distance is then obtained using the pre-calculated distance factor in the distance shader. The fixed pre-calculated is mean to save resources.

Illumination

The final light is obtained from a light shader representing a torch light, in the direction of the camera (and weapon sight).
Some reflection is also added, when a surface is exactly horizontal to the light ray.
Only wall can be horizontal (if a pitch is added, it would only displace the screen pane up and down, not turning the camera)
For each angle of the radar, we get the angle between the ray and the nearest found wall.
Then, the reflection factor is a basic function of this angle.
In the end, the light is the product of a factor function of the distance, the ceiling/floor or wall resolution, the reflection factor, and the light shader factor.

Display

The effective display is made from conditional formatting - gradient of color based on the value of the cell.
Hiding the value is achieved by cell formatting.

Wall collision

The player is not supposed to move through wall, or it would defeat the idea of a maze.
Wall would not either stuck the player as he reach them. The movement should slip unless he reach a corner.
In addition, a minimum distance should be kept from the player to avoid graphical issues, and make wall have some width.

It appeared to be particularly tricky to manage all the possible cases of wall, and positions of the player compared to this wall.

The 2^5 possibilities were studied, and the 3 potentials outcome (for each displacement axis) where mapped to get the result within fewer possible tests.

While appearing one of the smaller, the displacement tab was one of the most complex to realize. (10 times more than the map, twice as much as the wall detection)

Enemies

The bad guy

Graphical rendering

The challenge for enemies was to obtain a shape that could be easily added before wall, easily rendered at any distance, and who would be more interesting than a simple cube.

A complete tab is dedicated to calculation of the shape of spheres, considering the horizontal radius, and vertical height of the ovoid. The height/width ratio is used to animate the creature.

The wall and ceiling rendering only used the gradient on 1 color, while excel allow 2 successive (not merged) gradient. Then, the enemies can be displayed in an other color. The value range bellow 0 can be used for this gradient, the value 0 being black.

The progressive transparency appeared to be not harder than the smooth rendering of a sphere surface. The ray is getting the thickness of the sphere, the thicker making the pixel more colored.
On the border of the sphere, the low thickness is only keeping the default value of the wall behind, with a negative factor to turn it on the color of monster. The light color filter providing a transparency on the border of the sphere.
Once again, calculation are made on the horizontal plane, and the maximum calculations are prepared before finalizing the 3d calculation for each pixel.

Enemies behavior

In order to avoid a complex and unsatisfying procedural behavior, enemies does not react to the player action. Their position is determined only by the time, on a complex trajectory designed to provide no explicit pattern.

To keep the position, speed, and all acceleration continuous (so the movement is fluid), the trajectory is a sort of finite fractal of a big circle, and small circular variations added on it. Ratio factor between circle (and even x/y ratio) are random an non-natural, so the trajectory never loop on itself. A separate sheet was made to display the trajectory to achieve a good random generator of deterministic trajectories.
Since the trajectories cannot take account of walls, the ability of monster to go through walls is forced.

Several trajectories are then computed at each instant. The entire maze is populated by the same 10 enemies repeated on a grid with a sufficient distance so the player cannot see 2 instances of the same enemy.

The repetition grid can be zoom in/zoom out to decrease/increase the enemy density. This should be made while taking great care of excessive resulting displacement of the monster, and effective speed due to scale.

Then, we have a limited number of enemies to manage, these being copied everywhere in the maze.

Enemies attacks

The animation of the enemies is made using the radius/height ratio. Since the attack of the enemy should be clearly visible, and yet, slow enough for the player to be able to react, enemies simply increase in radius wether they have the player in sight. The grow follow an exponential function to simulate an explosion.

Light of sight is calculated for each enemy in the radar tab, considering walls.

Then, the player simply get damage if it turn to be inside the radius of an enemy. It works the same is the player goes on purpose inside the enemy.

This make the damage effect on the player a simple effect of negative color on the entire screen.
An other effect is to cancel the rendering of any other enemy when the player get damaged.

The life of the player is one of the element of its status, which managed though steps like its position.

Player attacks

Each enemy get a status value, defining either its remaining life and attacking phase. For some values, enemies are simply not displayed, for some other, the enemy slowly regenerate, and the last one make the enemy explode.

This simplified model allow the player to prevent attack by decreasing the life of the enemy.

To increase the challenge, the player will have difficulties to aim a small enemy by staying at long range, and the ammunition will require reload action after a while.

On kill, the enemy simply turn into a slow regeneration state of inactivity. Since there are few enemies repeated everywhere, there cannot be a definitive elimination of one of them. 

Death and rebi.. restart

Once the life of the player goes bellow 0, most of its actions are frozen, and the game-over screen appear.
This screen is rendered using an other light shader, and a negative effect is made on color to keep with the idea of damage.

The progressive display of the "game over" message is achieved with small factor, which are elevated with an exponential function. This allow future pixels to stay hidden before appearing once the exponent is big enough.

Then, the slide down is a simple displacement of the light shader, which include some other message, like high score and restart.

The score have to be written using pixels, with a very low resolution font.

The restart generate new starting parameter, and send the player elsewhere at an other instant to avoid the player to meet the same enemies.