Thursday 21 February 2019

Three.js Overview, and Visualising Games ad Fractals

This month's London meetup had two interesting themes - an interesting way of visualising how games play out which results in fractal images, and an introduction to three.js, a leading javascript 3d library.


Ben's slides for visualising games is here: [PDF].

Carl's guide for threejs. is here: [PDF].
Carl's code and working demos are online: [glitch].


Visualising How Games Play Out

Algorithms and AI techniques for game play is one of Ben's interests. He's previously demonstrated his work and given a very brief talk but I wanted to give him more time to fully explain his work because I think it really deserves a fuller hearing.


Ben started by discussing the simple game of naughts and crosses. At the start of the game there is an empty 3x3 grid. We can label the cells 1-9, or 0-8 which is equivalent.

If the first player chooses to place a mark in the top left we can define the move as 0, because the cell filled is labelled 0. If the next player chooses to fill in the top middle cell labelled 1, the game sequence so far is 01. If the first player then chooses to fill the central cell labelled 4, the game sequence is 014.

Ben's slide illustrates this idea well.


If we wanted to visualise the game after one move, we could simply use a 3x3 grid. After the second move we can use a 9x9 grid because each cell in the 3x3 grid becomes a 3x3 grid itself for the next move. For simplicity we can ignore the fact that some cells will be excluded as they are already filled.

This provides the basis for visualising a game as it proceeds. If we use game data, or simulate games to completion, we can use the likelihood of winning from a position to colour a cell. The following shows that the chances of winning are highest if a player starts from the central cell. The corner cells are also advantageous, but not as much as the central cell.


If we start from the second move, the grid will be 9x9 as we've already seen. The colouring indicating likelihood of winning starts to show a fractal pattern.


Ben's blog shows how the pattern develops as the starting point progresses from 1 to 5.


Ben then talked about applying these ideas to other games such as Quarto and chess. In particular he looked at the 8 queens challenge, which is to see if a chess board can be set up with 8 queens that aren't attacking any other. He used simulation to see which starting positions led to solutions, and which led far but didn't succeed.


I find Ben's approach provides an insight into the dynamics of games and puzzles, revealing structure which itself reflects on either biases or advantageous positions in the game.

During the Q&A Ben mentioned that many games explode exponentially in terms of possible next states, and so a sampling is used to reduce the computational load.

Ben also pointed to a numberphile and a coding train video for wider applications of these ideas.

You can read more on Ben's blog posts:




Three.js Introduction

Carl developed a thorough tutorial introducing three.js, a popular javascript library for creating 3d scenes. Three.js itself works on top of the low level WebGL.

Instead of repeating the tutorial exactly, I will try to use his guide to develop a simple scene, step by step.

Three.js is a javascript library that can be included in a normal web page using the standard <script> tags, after which it can be used in subsequent javascript code.

We'll avoid messing about with source code files, and work on the web, using a site called glitch. After sign up for an account, we can create a new web page project. This creates a skeleton set of html, css and javascript files. The following shows the index.html file, which we will edit.


We add our reference to three.js using the standard <script> tags:

<!-- import three.js -->
<script src="https://threejs.org/build/three.js"></script>

The resulting index.html file now looks like this:


I've also removed the content of the <body> tags leaving it empty.

Glitch auto-saves changes, and the resulting web page can be viewed in a separate window or tab, updated live.

The style.css file, linked from index.html, is also adjusted to ensure the canvas fills the tab or window, and removes the scrollbar which can sometimes appear.

body { margin: 0; overflow: hidden; }
canvas { width: 100%; height: 100% }

The resulting style.css now looks like this:


This is a good point to open the live view of the web page which is rendered using these index.html, style.css and script.js files. Click the show live icon at the top, which has the spectacles logo attached.


You should see a new tab open. The page itself should look empty.

We can now start using three.js in the script.js file, also linked from index.html.

The first thing we need to set up is a scene, a camera and a renderer object.

var scene = new THREE.Scene();
var camera = new THREE.PerspectiveCamera( 75, window.innerWidth/window.innerHeight, 0.1, 1000 );

var renderer = new THREE.WebGLRenderer();
renderer.setSize( window.innerWidth, window.innerHeight );

A scene is needed for all three.js scenes, there isn't a choice about it.

There are different kinds of camera, here we've chosen a simple PerspectiveCamera. The options are, in order:

  • the field of view (FOV) which is 75 degrees here
  • the aspect ratio of the camera, here calculated from the size of the window
  • the near and far clipping points outside which scene objects are not shown


The renderer is the hardware accelerated WebGL renderer. Other options are available, but usually not used, and are there as fallbacks if the browser is old and doesn't have WebGL.

So far so good. We now need to attach something to the web pages's body so that it has a html element showing us something. In this case we attached the renderer to the body element.

document.body.appendChild( renderer.domElement );

Although not obvious, this actually adds a <canvas> element to the page, which you can check by using the "inspect element" or page source viewing tools in most browsers.

Now let's create an actual 3d object for our scene. Let's start with a cube.

var geometry = new THREE.BoxGeometry( 1, 1, 1 );
var material = new THREE.MeshBasicMaterial( { color: 0x00ff00 } );
var cube = new THREE.Mesh( geometry, material );
scene.add( cube );

The term geometry is a little misleading. In the world of three.js geometries can be thought of as 3d objects of certain type - like a box, or a sphere, or a cone, or a pipe, and so on. Here we create a box geometry, which is given a width, height and depth of 1. because all the sides are the same this box is a cube.

We also create a material, which is given a green colour. The MeshBasicMaterial is the simplest, and doesn't interact with light, which means it has no reflections and doesn't show shadows.

We then combine the geometry and material into a Mesh object and it to the scene.

Because our cube is located at the origin, we need to move out camera back so we can see a wider view of the scene.

camera.position.z = 5;

If we look at the live view of this scene, we don't see anything. That's because we need a render or animate loop, as they're often called.

function animate() {
renderer.render( scene, camera );
requestAnimationFrame( animate );
}
animate();

This looks a bit ugly! We call a function called animate() which we've defined just beforehand. That function uses requestAnimatonFrame with animate() as the callback which is called whenever the browser is ready to draw the next frame of an animated scene. Not that clean looking but it's apparently better than what came before. You can read more here, and here.

Finally we can see the cube.


The cube doesn't do anything because we've not told it to yet. Let's now rotate it with ever animation render frame. We simple adjust the x and y rotations by a small amount with every frame.

function animate() {
  cube.rotation.x += 0.01;
  cube.rotation.y += 0.01;
  
  renderer.render( scene, camera );
  
requestAnimationFrame( animate );
};

Every time the animate() function is called to draw a new frame, the cube's orientation will be changed a bit.


That worked - we can see an actual 3d rotating cube.

This didn't work in Safari, which is known to have WebGL issues, but did work in Chrome and Firefox.

Let's change the material to better show the 3-d nature of the cube.

var material = new THREE.MeshNormalMaterial();

This material uses the normals of the surface to decide the local colour.


That's a much clearer rendering of a 3d object.

Carl then introduced the idea of manual controls to orient the object. We include another library from three.js called OrbitControls.js.

<script src="https://threejs.org/examples/js/controls/OrbitControls.js"></script>

In our javascript we add the controls linked to the camera:

var controls = new THREE.OrbitControls(camera);

We remove the cube rotation from the animate loop and instead set the orientation using these control library.

controls.update();

We can now control how we view the scene by effectively moving the camera.

Now let's use the power of code to create lots of objects.

Let's replace the code that creates a single material and cube with a loop that creates many, padding each to an initially empty list.

var boxes = [];
var numBoxes = 9;
for (let x = -numBoxes; x <= numBoxes; x++) {
  for (let y = -numBoxes; y <= numBoxes; y++) {
    var material = new THREE.MeshNormalMaterial( );
    var cube = new THREE.Mesh( geometry, material );
    cube.position.x = x * 1.1;
    cube.position.y = y * 1.1;
    boxes.push(cube);
    scene.add(cube);
  }
}

To keep each cube independent, each needs a new instance of a material. The loop counters x and y are used to set the location of each individual cube.

The following shows the array of boxes this loop creates.


Let's now modify these. Inside the animate function we can adjust the positions and rotations of each of these cubes individually.

// work through each box
for (var box of boxes) {
  
  var x = box.position.x;
  var y = box.position.y;
  
  box.position.z = Math.abs(x) + Math.abs(y);
  
}

Here we've pulled out the x and y position of each cube and used it to set the z position. The calculation uses the Manhattan distance, which results in an arrangement that looks like this:


That's pretty effective!

Carl demonstrated other kinds of manipulation such as offsetting each cube using wavy trigonometric functions.


A key idea he did introduce was the use of a pseudo-timer to calculate box positions. The pseudo-timer variable, which we can call step,  is created in the main javascript code.

var step = 0;

It is updated inside the animate loop, incrementing it by 0.0001 with each call to animate().

// work through each box
for (var box of boxes) {
  step += 0.0001;
  
  var x = box.position.x;
  var y = box.position.y;
  
  box.position.z = Math.sin(step + Math.sqrt(x*x + y*y));
  
}

Here we set the z position of each box using a sine function that depends on the distance of the box from the origin, and also the step pseudo-timer.


That's a rather pleasing effect! The key point is the use of the pseudo-timer to adjust the positions of the boxes in the animate loop.

You can explore the code on glitch:



Carl proceeded to look at more advanced ideas such as setting colours dynamically, adding additional lighting, and also grouping objects so they could be rotated together, or even adjusting the vertices of each object. Do look through his tutorial to explore these ideas in more detail.


The group enjoyed Carl's tutorial and we reflected that his introduction took away most of the initial barriers to trying a new technology. Several said they'd go home and continue to explore three.js.



No comments:

Post a Comment