Editor’s note: This is a guest post by Thomas Coudray, Amaury de la Vieuville, and Ahmed Bougacha. Thomas, Amaury, and Ahmed attended the Google Apps Script Hackathon in Paris, and in this post they are sharing their creative use of Google Apps Script to render a 3D scene in a Google Spreadsheet. -- Jan Kleinert
Recently, we heard about the Google Apps Script Hackathon arriving in Paris, France. We did not know much about Apps Script - heck, even JavaScript! Perfect occasion to learn something. We spent most of the event hacking around with the ever-growing collection of Google APIs. As a tribute to the folks over at id Software, we settled on one of the most fun (however useless) ways to use it: rendering a 3D scene in a spreadsheet.
The rendering is done using a technique called ray-casting, made popular by the 90s id Software game Wolfenstein 3D. Ray-casting is a really brilliant and straightforward algorithm:
First, we render the background: color the upper (sky) and lower (floor) halves of the screen in different colors. We store the pixel colors in a matrix, the screen buffer:
screen = new Array(SIZE_Y); for (var lin = 0; lin < SIZE_Y; lin++) { screen[lin] = new Array(SIZE_X); for (var col = 0; col < SIZE_X; col++) { screen[lin][col] = colorToString((lin < MID) ? UPPER_BG_COLOR : LOWER_BG_COLOR); } }
Note that we draw the screen only once the buffer is fully colored, to avoid the overhead of coloring cells individually.
Then for each column of the screen:
The trick is in the drawing: the upper and lower halves of the screen are symmetrical in shape, and the only computed value is the display height of the wall. The screen really is just a fancy formatting for an integer array of columns.
The camera is represented using:
We store these 3 values at the bottom of the sheet, to ensure persistence (else, each refresh would bring us back to the start location!).
function Camera() { this.x = CAMERA_X; this.y = CAMERA_Y; this.theta = CAMERA_THETA; this.saveToSheet = function(sheet) { // The player state has to be saved between each frame sheet.getRange(STORE_LIN, 1, 1, 1).setValue(this.x); sheet.getRange(STORE_LIN, 2, 1, 1).setValue(this.y); sheet.getRange(STORE_LIN, 3, 1, 1).setValue(this.theta); }; this.readFromSheet = function(sheet) { this.x = sheet.getRange(STORE_LIN, 1, 1, 1).getValue(); this.y = sheet.getRange(STORE_LIN, 2, 1, 1).getValue(); this.theta = sheet.getRange(STORE_LIN, 3, 1, 1).getValue(); }; ... }
The map is a logical matrix, thus limiting us to discrete boxes for walls: for every cell, there either is (1), or is not (0), a wall:
// starting 10x10 map var S = 10; var map = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 0, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1, 1, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 0, 1, 1, 0, 1, 0, 1], [1, 0, 0, 0, 1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 1, 0, 0, 1, 0, 1], [1, 0, 1, 1, 1, 1, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ];
It is also possible to modify the map in real-time: write a character in the boxes you want to swap, then hit Refresh map.
Moving involves adding (or subtracting for backwards movements) to the xy coordinates, using basic trigonometry, but only after checking the validity of the move (i.e. that it will not collide with a wall):
function Camera() { ... this.move = function(distance) { // return whether valid move or not x = this.x + Math.cos(this.theta) * distance; y = this.y + Math.sin(this.theta) * distance; if (isValidPos(x, y)) { this.x = x; this.y = y; return true; } return false; }; } function moveUp() { readMapFromSheet(sheet); // Retrieve the map from the sheet var camera = new Camera(); camera.readFromSheet(sheet); // Retrieve the camera state from the sheet camera.move(0.5); raycast(camera); }
Turning left (respectively right) is even simpler, adding (respectively subtracting) small constants to the camera angle (mod 2 PI):
function Camera() { ... this.rotate = function(alpha) { this.theta = (this.theta + alpha + 2 * Math.PI) % (2 * Math.PI); }; } function lookRight() { readMapFromSheet(sheet); var camera = new Camera(); camera.readFromSheet(sheet); camera.rotate(-0.25); raycast(camera); }
Actual actions (moving/turning) are shown in a menu:
spreadsheet = SpreadsheetApp.getActiveSpreadsheet(); var subMenus = [ {name:"Reset",functionName:"onOpen"}, {name:"Refresh map",functionName:"refresh"}, {name:"Move forward",functionName:"up"}, {name:"Look left",functionName:"left"}, {name:"Look right",functionName:"right"}, {name:"Move backward",functionName:"down"}, {name:"Turn around",functionName:"turn"}, ]; spreadsheet.addMenu("Sheetcaster", subMenus);
The ray is cast as follows:
/* * Given a value on the x axis (screen column), * return the ray that will be cast */ function getRay(camera, x) { var cos = Math.cos(camera.theta); var sin = Math.sin(camera.theta); // from -1 to 1: 0 being when x is the middle column var k = ((SIZE_X / 2) - x) / SIZE_X; return new Vector_( cos / 2 - k * sin * K_FOV, sin / 2 + k * cos * K_FOV ); }
Moving the ray is the most involved step:
while (!hit) { // Next potential wall is on the x axis if (dist.x < dist.y) { // Distance from the camera, delta: / Distance between each horizontal wall along the ray dist.x += delta.x; // step.x is either 1 or -1, depending on the ray direction mapCoord.x += step.x; hit = readMap_(mapCoord.x, mapCoord.y); } else { // Next potential wall is on the y axis dist.y += delta.y; mapCoord.y += step.y; hit = readMap_(mapCoord.x, mapCoord.y); } }
The height of the drawn column is nothing fancy: the further the wall, the smaller-looking the wall, hence the smaller the height of the column.
Again, nothing really complicated. However, the simplicity of this wall-height technique is the reason behind its major caveat: there is no clean way to look up or down: you can only turn left or right, and move forward or backward.
Displaying the rendered image is done using a spreadsheet. Each cell becomes a small square pixel, its color being the background color of the cell. We pass our scren buffer matrix to the handy setBackgroundColors:
sheet.getRange(1, 1, SIZE_Y, SIZE_X).setBackgroundColors(screen);
As you probably noticed, the low display density makes the sharp, jagged, edges really visible. Fear not, reader, for we also implemented anti-aliasing!
The anti-aliasing algorithm is even simpler:
When the runs are really small (< 5 columns), we attenuate the gradient intensity, as it would only add another pixel above (below) the column, thus rendering the antialiasing utterly useless.
Real-time was not an objective, the main problem being controlling the player/camera. Scripted movements should however be quite easy to implement with a fixed duration loop, restarting itself using an Apps Script recurrent time-driven trigger (a minute-long loop, repeated every minute). This is left as an exercise to the reader.
Please feel free to copy the script and walk around this Apps Script virtual world.
