INFORMATION NOW

Sheetcaster 3D in Apps Script

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:

1. Cast a ray
2. Move along the ray until hitting a wall, calculate the distance to that wall
3. Draw a column whose height is inversely proportional to that distance

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:

• Its (real-valued) x/y coordinates in the map plane
• Its angle relative to some predefined direction

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:

• Its origin is the cameras 2D coordinates in the map plane
• Its direction is calculated off the cameras and the column index (the center column will have the exact same direction as the camera; the other columns directions depend on the field of view parameter)

/*
 * 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:

• Calculate the distance to the next vertical and horizontal borders
• Move to the closest border

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:

1. Accumulate the length of runs (successions of same-sized columns)
2. Draw a gradient, from the background (wall and floor) to the wall, above (and below) the columns

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.

Thomas Coudray Thomas is interested in low level computing and application security.

Amaury de la Vieuville Amaury is passionate about algorithmic problem-solving and software engineering.

Ahmed Bougacha Ahmed is interested in kernels, compilers and theoretical computer science.

Posted by Unknown at 7:45 AM

Email ThisBlogThis!Share to TwitterShare to FacebookShare to Pinterest

Labels: 3d, apps, in, script, sheetcaster