A 3D Engine Made of Excel Formulas

One of the Gamasutra’s community members has presented something outstanding. A developer known as C Bel has published an article on his 3D engine made of MS Excel formulas! Sounds crazy, right? The thing is that the engine supports real-time raytracing, occlusion calculation, basic illumination rendering, and more.

Here is a small piece of the article to get you excited:

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 :

Faster to write for anyone but professional analyst programmer
Easier to maintain for anyone but professional analyst programmer. (while macro are mostly unusable once the initial developer is gone)
A guaranteed quality, due to permanent value checking. (a forced Test Driven Development method)
More efficient in the long run, due to the “think before you write” process with formula design
And definitively, much better integrated in the overall spreadsheet tool, following the initial design pattern of the spreadsheet, while macro often appear like specific developments requiring extensive maintenance afterwards.

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 :

Adding specifics input or output (as I did here to get key events), while formula is always limited to change on the cell itself
Some complex problems (like optimization, try-and-check problems), those in which the computation time is too long, and/or taking too much space. But theses problems are quite rare in real business life.

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.