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

<iframe title="3D engine on MS Excel - without vba" src="//www.youtube.com/embed/iCeOEQVUWZ0?enablejsapi=1&amp;origin=https%3A%2F%2Fwww.gamedeveloper.com" height="360px" width="100%" data-testid="iframe" loading="lazy" scrolling="auto" class="optanon-category-C0004 ot-vscat-C0004 " data-gtm-yt-inspected-91172384_163="true" id="631389177" data-gtm-yt-inspected-91172384_165="true" data-gtm-yt-inspected-113="true"></iframe>

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.