CitiEz – Test 1

Citiez

Experiments in Procedural Streets


Preface

L-Systems are an ideal way to produce predictable growth, and have been used in recent years to generate entire cities. I have found that the process of using turtle logic is just like its name slow… and does not have very many options for the branches of the system to make intelligent decisions about their surroundings, maintain a object hierarchy that is transversable, or store any important variables. They are basically dumb and can be given pseudo intelligence. I started trying to work with the standard format for constructing a library for axioms and found that this was not a very robust way to make anything of value. I’m going to be honest tons of the stuff I see guys do with L-Systems is crazy, and I have a great amount of respect for it, but I still wanna kinda do things my way so yeah.

The basic idea is just like an L-System I will construct an “alphabet”. These characters though are just a naming convention for embedded functional objects, that can be constructed and then reference a rule with the same name type effectively making a dynamic and tailorable constructor class that is deployed on runtime. Inside a basic component of the system (a axiom or road) it holds all the basic data that is going to be needed to construct our road map, these variables include path information and some other general information. Each Axiom contains a repo, that references other axioms in the library for when this branch is no longer valid, to spawn. Each Axiom works independently of the others and essentially has restrictions it tries to maintain, if all restrictions are out of limits then the thread terminates and sends a message to the main script to start the IO on another Axiom.

Right away I can see benefits to this system, as I can store street names, locations, elevations, spatial data, etc. Also in later version I will be looking to extend the Survey area to a larger zone, and have each block be processed with later optimization functions deciding the route and conditions. I see this being completely valid for the construction of real time procedural content, as all the calculations can happen on a sub thread and IO’s divided, with the detail slowly building up. This build up could also enable the options for LOD

Test – 1

In my first tests I did not include elevation calculations, the roads only scan their local North, South, East, or West points in the Survey. Population clamp is set to 0.65 or 255*0.65. The roads will stop if the hit a intersection or can not travel their primary direction and one initial alternate direction that is established on the first turn. This is a very simple model, but the effect is immediately noticeable.

 




Settings :

City Name
Origin:XY


N : 0

 

This is about 14 hours of development and conceptual work in, I am interested to see how it progresses, and will be introducing DAS_NOISE and BJS into the scope here at some point. I am also drafting up the concept of doing away with a by pxl method, and making a vector tracing system that will be much more modular, and have the ability to make decisions on if it should attempt to link up with an intersection, cross a road, or how steep it should make a turn.

Texture Syth

Texture Syth
An experiment in Texture Generation
Author: Andrew V Butt Sr. – Pryme8@gmail.com
http://pryme8.github.io/

Introduction

Texture Synthesis is method in 2d procedural generation that is quickly becoming and interest for several developers. Its capability can easily be be extended to 3d. This is an active investigation on how to teach a computer to output generated content from sample input. The general basis is discussed HERE

Abstract

I will attempt to make different methods of generation based with and without my Das_Noise Library and will later include research on this topic in GLSL. The eventual goal is to create a robust texture synthesis library for javascript and use this product to aid in the deployment of TERIABLE.
The initial test will be loosely based on the documentation and will be my own spin on the approach. Later I with lessons learned will attempt to deploy more popular methods.
The outcome of these test I am unsure of but will document both the approach and the results and provide an example.

Test 1

The first test was trying to not deploy a base noise to reference the sample texture against. I stopped working on this test after i started noticing shortcomings in the colors being produced.

Base SampleA few terms that are used while using a texture synthesis method are:

  • Texton
  • Neighborhood
  • Vector
  • Noise

Constants in our Examples will be:

  • R – Reference Image
  • P – Base Sample Target Point
  • nP – Neighboring Target Point
  • N – New Texture Being Generated
  • Np – New Texture targetPoint
  • np – New Texture Neighboring targetPoint

 

In my first test, I decided for the first step, was to generate my textons from R, which I did not do a very good job of. But none the less it seems to work enough to let me see the effect of this method. The second step was to impose R on the output canvas in 3 points on the top corner in order to give our generator something to reference. This can be done without outputting the reference but was a quick way to get it done.
From there I started sampling with a different shape of texton that was the same number of samples as the ones generated previously. This new texton was not offset from around the point it was checking but behind it in a box of similar shape but offset, as to backreference what was already there. Then I found the closest Texton from our first set and used its value to output to the canvas.
I could not for the life of me figure out why the colors were so washed out, though this effect was able to duplicate the pattern fairly accurately. I was going to continue the process by then cloning our new first area we created into the top and left edges of the canvas and was going to repeat the sampling process for making the first area. I did not complete this last step though because what I had already learned what I needed to from this example.
You can look at a live DEMO but the script is very sloppy and basically it boils down to I don’t know what I was thinking on my original script.
This method is… slow, plus with the bad color transfer I do not think is a valid method. Moving on…

Test 1 – Enter Noise

So after my first night of hacking away at this, while trying to get some sleep I thought of how to implement using noise to predict what color the cell will need to be.
I figured if I could have a accurate way to describe an underlying noise and translate that to the neighborhood I was looking for it could continue the pattern or a likeness of it on the output.
Initial test on this looked kinda promising with the first area of the noise rending out to be pretty close to the input, but after that it’s pure chaos. I think it may be with how I am measuring the differences.
What I need to do is some more reading and find out what other guys have done to solve this. The DEMO shows that this method could be possible but quite a bit of refinement is needed.
Also the computation speed is also very slow, and produces crappy output, I ran several different test with a range of noises, and tried to output by pxl as well as by neighborhood the results being:

In the last example I did not want to wait for it to finish, as it was going per pxl and using the textons average value. The color problem from the first example is not a problem now so maybe I need to reference both examples and make a combination of the both. Till then I think it’s time to do some more reading, and write down some of the ideas from what I learned here to create a procedural dungeon (maybe).
 

To be continued…

DungeoNear?

Experiments in Procedural Level Creation


Introduction

After working on doing some texture synthesis, a method for creating dungeons and other content kinda just smacked me in the face. I have been itching for about two days now to get a chance to do this. The night I thought it up the write up went as follows:

A Zone (Z) is defined as a area of set units that is divided into a set amount of Cells (C). For this deployment I will be dividing the
Z into a 3 by 3 grid with the labeling of each cell as follows starting from the top left; n10, n00, n01, m10, m00, m01, s10, s00, s01. Because I am spliting it into thirds to keep things simple I will define the size of the zone always to something divisible by 3, for general purposes I will always use a Z size of 60 by 60 making each cell 20^2 pxls. Because we will be averaging the black and white value of the cells we limit the size of the zones to be as small as possible but still large enough to have defined details. The larger our Zones the larger the calculation overhead.

Once my Zone method and size is established and I have defined the cells for it, I have to calculate every possible state of the Zone and output that to a human readable jpg. This is achieved by looping through combination sets of the cells, and creating a single array of all states, then use that information to generate a canvas with the correct cells displayed as black and white on or off state.

After the human readable jpg is produced, reload our now created Zone map into the program and associate each zone’s location information on the map and cell state information into a referenceable and searchable array or object.
At this point I can start choosing my method for a base noise, because each Zone will only be 60 by 60 I believe my Worley2D noise from my Das_Noise library will work just fine, if there is a calculation lag on the generation of the zones due to the noise, I will see about moving to a modified SimpleX. Starting from the top left of the visible stage, we calculate the values for the base noise by passing it to our zone object and averaging the values of each cells black white ratio due to the noise, and round to 0 or 1 effectively converting the noise to a Zone similar to the ones I generated earlier. Loop through the map object,
and find out which zone matches the closest to the new noise zone.

The point of first creating a human readable image instead of just having the noise be manipulated is that after we get a look for the base layout that we want, an artist can use the human readable image as a template to draw a secondary reference image that has the same dimensions as our reference map. I could then load image data into the map object from the secondary reference image and output the fancy tiles instead of just black and white. This process could also be extended to use secondary noise calculations to establish and simulate different biomes and altitudes, changing what tile map is referenced.

This is all theory but it sounds about right so I’m gonna give it a shot.

The Reference Map

Diving right in I think the smartest thing to do will be to create my first reference map, or the human readable map I described earlier. The first day I thought of this I tried to make it by hand in illustrator and got about 32 combinations in before I realized that was dumb, and it was time to make canvas go to work.

First we need to calculate the combinations of the cells and make something that we can use to output a physical reference map. What I mean by combinations is if we had an input of [1, 2, 3] the output would look like =>123,213,132,232,312,321…. There are lots of ways to do this, but I will try to keep it simple. Because order does not matter, we do not have to worry about permutations (the same combination in a different order).

This script to make it happen is as follows:

dungeon = function(args){
    args = args || {};
    args.zSize = args.zSize || 60;
    args.zDiv = args.zDiv || 3;
    this.zSize= args.zSize;
    this.zDiv = args.zDiv;
};

dungeon.prototype._createRefMap = function(){
    var cells = [];
    var pCount = this.zDiv * this.zDiv;
    
    function perm(s,c){
        if (c == 0) {
        cells.push(s);
        return;
        }
        perm(s+'0', c-1);
        perm(s+'1', c-1);
    }
    
    perm('',pCount);
    
    var last = cells.splice(cells.length-1,1);
    cells.unshift(last+'');
    console.log(cells);    
};

Just creating a new dungeon and then calling the prototype now outputs all of the permutations for a total of 512, on a side interesting note, is it also the could be looked at as every possible combination of a binary set of 9. Looking at the structure I already know that my two most common ones I am shooting for will be all states on and all states off, so I think it would be best to take the first record and move it to the front of the array to save on calculation time once we start looping through our state array.

Zone Object

Now it is time to make a Zone Object, this will be the basis for our mapping of the noise, this makes a object that we can put in an array, and compile the states of the cell as a searchable string. After that we will look at making a readable image.

dungeon.Zone = function(size, div, state){
    this.size = size;
    this.div = div;
    this.searchString = state;
    this.state = state.split('');
    this.cells = [];
    for(var i=0; i < div*div; i++){
        this.cells.push(0);
    }
    for(var i=0; i < state.length; i++){
        var sID = parseInt(state[i],10);
        this.cells[sID] = 1;            
    }
    return this;    
};

I then modified my pre-existing script to the following:

...
    var map = [];
    for(var i = 0; i < cells.length; i++){
        map.push(new dungeon.Zone(this.zSize, this.zDiv, cells[i]));    
    }
    this.map = map;    
    console.log(map);

This gives us an array on the main dungeon object that contains set of Zones with a searchable string for referencing later. I now need to create a new function to compile the physical map and set values for where the zone object is on the output map. This step is only necessary so that at a later time an artist can create a secondary reference map at a later time, if I just wanted black and white pxls to display I could effectively skip this step but that is not the final product I want.

I also went ahead and allocated the memory for each of the zone objects to have image data as well, even though I’m just using the map image and not an artistic tile image do to the fact of 512 tiles is quite a bit of content to come up with, just for an example. Using this function I generate my reference map that I will use as both a way to look up / store tiles and their properties; it also creates the ability for me to output a canvas with the tiles on it to make a human readable map.

dungeon.prototype._calculateMap = function(){
    var map = this.map;
    var cvas = document.createElement('canvas');
    var ctx = cvas.getContext('2d');
    
    var X = 0, Y = 0;
    var cellSize = this.zSize/this.zDiv;
    
    cvas.width = 20*this.zSize;
    cvas.height = Math.ceil(map.length/20)*this.zSize;
    
    for(var i = 0; i < map.length; i++){
        var x = 0, y = 0;
        for(var j = 0; j < map[i].cells.length; j++){ if(map[i].cells[j] == 1){ ctx.fillStyle = "#FFF"; }else{ ctx.fillStyle = "#000"; } ctx.fillRect(x+X,y+Y,cellSize,cellSize); x+=cellSize; if(x > this.zSize-cellSize){
                y+=cellSize;
                x=0;
            }
        };
        
        ctx.strokeStyle = "rgba(255,0,0,0.2)";    
        ctx.strokeRect(X,Y,this.zSize,this.zSize);
        
        var imgData = ctx.getImageData(X,Y,this.zSize,this.zSize);
        
        map[i].imgData = imgData;
        map[i].x = X;
        map[i].y = Y;
                
        X+=this.zSize;
        if(X > cvas.width-this.zSize){
            Y+=this.zSize;
            X=0;
        }
    };
};

Now it’s time to start generating a noise, and see if we can kick this thing into gear and output a dungeon like structure. Later I will research into making the ability for you to draw on the base noise and see the overlay tiles update accordingly, this would be cool for later development I think, but is something that is down the road a little bit.

Also CLICK HERE for an Example of the Reference Map

Enter Das_Noise

Ok so now the next step will be to generate a base noise map to start sampling, and outputting out maps imageData in the correct areas and see what kind of output I can get. I’m assuming this should go without much hitch and with a well set up noise will structure itself to resemble a dungeon right of the bat (I hope).

I want to use a good sized chebyshev style Worley Noise to start because I believe this will have a good look to it once overlaid, and will guarantee that most if not all the rooms connect. If you are not familiar with my Das_Noise library you can check it out here: http://pryme8.github.io/Das_Noise

To test the noise I am going to output on a 600 by 600 pxl canvas the noise till I get something acceptable. When I go to use it, i will not have to create the noise to any sort of output, but rather just check its values at certain locations then parse that how ever is needed to see what cells are active or not in that zone.
Already looking at this noise, we can visualize what the dungeon will look like if the calculations have been set up correctly. The next step is to identify the what each zone on the noise matches up to on our reference map, to see this in action click the link below to do one zone at a time on our canvas to the left.

Generate Zone

*UPDATE – I went ahead and added a basic tile map to reference, to show how that would work… you can look at the code to see how I did that, but after seeing it deployed I have three options, rework the tilemap to be cleaner and work a little better, make some sort of comparison script to see what the other tiles next to it are, and if there is a flat edge, have caped variations to use, or make everything procedrual… I think given the fact it took me two and a half hours to make 512 tiles im going to go with the last option here at some point.

Ohhh yeah, that works! Ok so I think I will wrap it up on this, but first here is a look at how I ID the zone of the noise.

Here is and example of the same process, with the noise of the same seed, but set to Simple2 and a scale of 100.

dungeon.prototype._idNoise = function(x,y,noise){
    if(typeof noise ==='undefined'){
    noise = this.noise;    
    }
    var cellSize = this.zSize/this.zDiv;
    
    var string = '';
    var self = this;
    var ctx = (document.getElementById('noise-canvas')).getContext('2d');
        ctx.fillStyle = "red";
        
        var cX = 0;
        var cY = 0;
    
    for(var i=0; i<this.zDiv*this.zDiv; i++){
        var t = 0;

        for(var pY = 0; pY < cellSize; pY++){
            for(var pX = 0; pX < cellSize; pX++){
                t+=noise.getValue({x:(pX+(this.zSize*x)+(cellSize*cX)),
                                   y:(pY+(this.zSize*y)+(cellSize*cY))});
                                    
            }
        }
        
        t/=(cellSize*cellSize);
        if(t<0.45){ string+=0+""; }else{ string+=1+""; } cX++; if(cX>this.zDiv-1){
        cX=0;
        cY++;
        }
    }

    for(var i=0; i<this.map.length; i++){
        if(this.map[i].searchString == string){
            return this.map[i];
        }
    };
};

Conclusion…

This was all literally done in one day intermittently while I cleaned the house… so yeah I think this is a valid and good approach for what I want to achieve. I will have to experiment with different noise types styles and scales and then come up with a nice tileset for it (I will prolly jack RPG maker resources for now). I think once this is deployed a little more the possibilities will be extensive.

I will be posting a simple Canvas Game based on this principle at some point!

Resources and References : None… I just made this crap up… if you have any questions Pryme8@gmail.com.

Web Workers Experiment 1

Web Worker Experiments

An investigation into how web workers operate.

Introduction | Getting Started | Part I | Part II | Part III | Part IV | Part V

 

A phrase I’ve been hearing used a lot lately, “Web Workers”.  What is a web worker?  What can I do with one?  Through this tutorial I will have you follow along with me while I go through some steps to understanding what a Web Worker is and how we can use these in actual situations.  Prior to this I have no knowledge whatsoever as to what they are used for and what they are capable of, but hopefully by the end of this I will!

First let’s get our basic template for our page setup, you can download the template HERE, or you can set up whatever basic index page is most comfortable to work in.

What does developer.mozilla.org say about Web Workers?

Web Workers provide a simple means for web content to run scripts in background threads. The worker thread can perform tasks without interfering with the user interface. In addition, they can perform I/O using XMLHttpRequest (although the responseXML and channel attributes are always null). Once created, a worker can send messages to the JavaScript code that created it by posting messages to an event handler specified by that code (and vice versa.) This article provides a detailed introduction to using web workers.

Ok, so this sounds really promising! What I am getting out of this is that Web Workers can simulate multithreading and could also serve as a pseudo response server for more dynamic content.

Also the thought of nesting certain calculation functions inside another script could allow more dynamic animations on a canvas element, or any other intensive calculation.
A few points about scope, if we create a web worker thread it creates a new thread outside of the scope of the window. If at any time we would need to refer to the ‘window’ that called the worker thread we would instead of using window use self. *dont quote me on this part

Other Key Points:

  • A dedicated worker is only accessible from the script that first spawned it, whereas shared workers can be accessed from multiple scripts.
  • You can’t directly manipulate the DOM from inside a worker, or use some default methods and properties of the window object.
  • Functions and classes available to workers
  • Workers can spawn new workers, those workers must be hosted within the same origin as the parent page.

I would recommend reading the mozilla page, as most of this tutorial will be based off the information served there.

Web Worker detection and setting up our first thread.

Now that we have an idea of what one is, let’s go ahead and jump right to the main.js file and start making some changes.

window.onload = function() {
    if (window.Worker) {
         document.body.innerHTML = "We Have Ignition";
    }else{
         document.body.innerHTML = "Lame sauce... no Web Workers...";
    }
}

If you have ignition, then you are good to go! If not then, yeah something is wrong because pretty sure most modern browsers have these… geez guy/gal.

From this point we need to actually do something with a web worker so the first step in that will be to go to our js folder and create a new script called “worker1.js” and then edit both the main script and the worker script accordingly.

window.onload = function() {
    if (window.Worker) {
         var newWorker = new Worker("./js/worker1.js");
        
              newWorker.postMessage([1,"Two"]);
              console.log('Message posted...');
            
            newWorker.onmessage = function(e) {
                  result = e.data;
                  console.log(result);
            }

    }else{
         document.body.innerHTML = "Lame sauce... no Web Workers...";
    }
}
onmessage = function(e) {
  console.log('Message received from main script');
  var workerResult = 'Result: ' + (e.data[0] + e.data[1]);
  console.log('Posting message back to main script');
  postMessage(workerResult);
}

What is happening here is first we are creating our instance of the worker on our main script. Then we are using the built in method .postMessage which will be the main basis for communicating with out worker. Then we have the worker listen for a message by defining the onmessage function, do whatever we want with the data and then pass it back! If everything is set up right when you refresh the page nothing amazing happens, but when you look in the console you will see the desired output hopefully. If you are having trouble or just feel like skipping this step you can download it HERE

Implementing and Creating Our First Project!

Now that we have this set up, what is something we could make? Hmmmm, I know how about Pong. We will get to learn how to use the Web Worker to do all the calculations and just have the main page update the canvas. If we do things right we could perhaps have one worker for calculating what is happening and the other calculating the output to the canvas. This may not be ideal or even the correct thing to do, but this is open research so I have no shame.

Because we don’t have another person and I don’t feel like going over AI for this tutorial, lets make a game that we can play with ourselves (ha). So to get things rolling let’s make these changes to our index.html, main.js and main.css

Web Workers Step 2

 

@charset "utf-8";
/* Web Workers Tutorial */
html, body{
padding:0; margin:0;
min-height:100%;
height:100%;
}

#score{
    position:absolute;
    top:1em;
    left:1em;
    font-family:"Lucida Console", Monaco, monospace;
    font-size:18px;
    font-variant:small-caps;
    opacity:0.5;
}
window.onload = function() {
    cvas = document.getElementById('cvas'); //Lets make it Global ^_^
    var context = cvas.getContext('2d');
    var score = document.getElementById('score');
    score.innerHTML = "Score: 0";
    function resize(){
        cvas.setAttribute("width", window.innerWidth+'px');
        cvas.setAttribute("height", window.innerHeight+'px');
        drawBall();
        drawPlayer();
        return    
    }
    resize();
    window.onresize = resize;
    
    
    //Lets just Draw our ball for now and paddles for now.
      function drawBall(){      
      var centerX = cvas.width / 2;
      var centerY = cvas.height / 2;
      var radius = cvas.height / 40;
      context.beginPath();
      context.arc(centerX, centerY, radius, 0, 2 * Math.PI, false);
      context.fillStyle = 'blue';
      context.fill();
      context.lineWidth = 1;
      context.strokeStyle = 'blue';
      context.stroke();
      }
      
      function drawPlayer(){      
      var centerX = cvas.width / 2;
      var centerY = cvas.height - 20;
      var width = cvas.width / 10;
      var height = 10;
      context.fillStyle = 'red';
      context.fillRect(centerX - (width*0.5) ,centerY,width,height);
      }
    
    
    if (window.Worker) {
         var newWorker = new Worker("./js/worker1.js");
        
              newWorker.postMessage([1,"Two"]);
              console.log('Message posted...');
            
            newWorker.onmessage = function(e) {
                  result = e.data;
                  console.log(result);
            }

    }else{
         document.body.innerHTML = "Lame sauce... no Web Workers...";
    }
}

If you’re all set up things should look like this.

Ok, so basically all we did was set up a resize listener, and some basic function to figure out how we are going to draw the objects

Now that we got some basic things set up its time to get to core structure of our program. You can download step 2 if you feel like skipping to this point or are having trouble.

The Long Haul… Core Changes

So the first thing on the chopping block, is let’s get a ASYNC loop set up with a throttle on it so we’re not just calculating for no reason on the draws. Then move the functions for drawing on the canvas onto the worker and see if it all still works. I’m not sure if this can all happen on the worker, but I have a sneaking suspicion that it will work just fine as long as we make sure we set up the correct scopes.

That means we will be editing the worker1.js file.

newGame = null;
onmessage = function(e) {
  console.log('Message received from main script');
  var type = null;
  if(e.data.length){
      type = e.data[0];
  }
    switch(type){
    case "init" : newGame = new pong(e.data[1]);
    break;
    
        console.log('new Game');
    }
}

pong = function(cvas){
    this.score = 0;
    this.run = false;
    this._cvas = cvas;
};
if (window.Worker) {
         var newWorker = new Worker("./js/worker1.js");
        
              newWorker.postMessage(['init', cvas]);
              newWorker.onmessage = function(e) {
                  result = e.data;
                  console.log(result);
            }

    }else{
         document.body.innerHTML = "Lame sauce... no Web Workers...";
    }

If we try to run this we get that the error: “DataCloneError: The object could not be cloned.” I believe this is because of instead of passing a reference of the object to the worker script it tried to make a clone of it, which is evidently not permitted with a canvas element (we could pass the imageData as a Buffer or Array though, but kinda overkill in this situation). So our work arounds will be to try to pass the context of the canvas, or just have the main script do the canvas manipulations but have the worker thread do the calculations. I’m not sure if this is even a correct use for a Web Worker but we will find out.

So I guess we should actually set up the structure for the game on the main thread, so on the main.js we add all the constants and containers for the game. As of right now we will do a simple 30Hz interval loop to process what needs to be put onto the canvas. Later we will make this loop more customizable and put in a way to set our FPS. The concept that we will be testing is having the physics be calculated on the worker, and have it push the updated hits and other properties to the main thread to be processed. Initially here we will set the main and worker thread to work at the same frequency, but later will prolly crank up the main thread to 60Hz and see how that affects performance.

SCALE = 1;
CENTERX = 0;
CENTERY = 0;

Entity = function(id, pos){ //pos is an array(3) with [x,y,angle];
      this.id = id;
      this.pos = pos;
      this.velocity = [0,0,0]; // X,Y,ROTATION
      
}

Entity.prototype.update = function(state) {
      this.pos = state.pos;     
}

Entity.prototype.draw = function(ctx) {
      ctx.fillStyle = 'black';
      ctx.beginPath();
      ctx.arc(this.pos[0]+CENTERX , this.pos[1]+CENTERY , 2, 0, Math.PI * 2, true);
      ctx.closePath();
      ctx.fill();
}

Ball = function(id, pos) {
      Entity.call(this, id, pos);
      this.body = {
          type:'circle',
            radius : SCALE,    
      }
}

Ball.prototype = new Entity();
Ball.prototype.constructor = Ball;

Ball.prototype.draw = function(ctx) {
      ctx.fillStyle = 'blue';
      ctx.beginPath();
      ctx.arc(this.pos[0]+CENTERX, this.pos[1]+CENTERY, SCALE, 0, Math.PI * 2, true);
      ctx.closePath();
      ctx.fill();      
      Entity.prototype.draw.call(this, ctx);
}

player = function(id, pos) {
     this.body = {
          type:'box',
            points : [
          [-(10 * SCALE)*0.5, -SCALE*0.5], //TL
          [(10 * SCALE)*0.5, -SCALE*0.5], //TR
           [-(10 * SCALE)*0.5, SCALE*0.5], //BL
          [(10 * SCALE)*0.5, SCALE*0.5] //BR
          ]    
      }
      Entity.call(this, id, pos);
}
    player.prototype = new Entity();
    player.prototype.constructor = player;
    
    player.prototype.draw = function(ctx) {
     ctx.fillStyle = 'red';
      ctx.fillRect((this.pos[0]+CENTERX)-((10 * SCALE)*0.5),
                   (window.innerHeight -20),
                   (10 * SCALE),
                   1 * SCALE);
    
     
}

pong = {
    ent_stack : [],
    gravity : [0,0.2],
    _init : null        
}


window.onload = function() {
    cvas = document.getElementById('cvas'); //Lets make it Global ^_^
    var ctx = cvas.getContext('2d');
    var score = document.getElementById('score');
    score.innerHTML = "Score: 0";
    pong.ent_stack.push(new Ball('b1', [0,0,0]));
    pong.ent_stack.push(new player('player1', [0, window.innerHeight - 20 ,0]));
    
    function resize(){
        cvas.setAttribute("width", window.innerWidth+'px');
        cvas.setAttribute("height", window.innerHeight+'px');
        SCALE = cvas.height / 40;
        CENTERX = cvas.width / 2;
        CENTERY = cvas.height / 2;
        reDraw();
        return    
    }
    
    function reDraw(){
        for(var i=0; i<pong.ent_stack.length; i++){
            pong.ent_stack[i].draw(ctx);
        }
    }
    
    resize();
    window.onresize = resize;
    
    
    if (window.Worker) {
        console.log("Worker Go!");
         var newWorker = new Worker("./js/worker1.js");
        
              newWorker.postMessage(['init']);
            
              /*newWorker.onmessage = function(e) {
                  var result = e.data;
                  if(result[0]=='update'){
                
                }
                
            }*/
            
            setInterval(function(){
              ctx.clearRect(0, 0, cvas.width, cvas.height);
              reDraw();   
            },1000/30);

    }else{
         document.body.innerHTML = "Lame sauce... no Web Workers...";
    }
}

Now the break down on this is as follows. One, we set up some global variables that will hold things that determine our size of our entities being drawn on the canvas. We make them global because at any point the user may resize the document and we want everything to remain the same. Right now we will disinclude the scale into the physics calculations, but later we will have to make sure we apply the scale to the physics as well so that the velocities and gravity etc stay proportionate.

Next we define our basic Entity Object, and its prototypes. This will be the basic container for whatever other objects we want to render on the screen. We give the Entity Object a draw prototype that should give us a center point. If you want to use the center point you must make sure that if your not spawning whatever entity at the center of the canvas, you need to translate the context prior to the output otherwise the dot will not be on the center of the new entity (not important we only using it on the ball which spawns in the center).

Then we define different Constructors for the Entity Object so that we can call different shapes. This is a very basic prototype/constructor layout and should be fairly straightforward to understand. After we have our Constructors ready we need to define a global container for everything. In this global container “pong”, we can define some constants as well. Once the DOM has loaded, we create the new entities and push them to a stack on our global container. Modify our all so important resize function, and then create a new function to call the draw method on all active entities. You could at this point put and enabled disabled flag on the Entities to toggle them on or off, but we’ll save that for later.

If in your interval loop, we stick the argument pong.ent_stack[0].pos[1]+= 0.25; You will see the ball move, which means we are on the right track.

After some more changes to the main script, we go back to the worker1.js, it is here that we start defining the structure for these workers to do physics calculations and post updates back to the main thread. We might as well take advantage of the number of threads available to us, and future proof a little bit with a navagator function that might not be supported in all browsers so we have a fall back.

// Step 3
engine = null;
onmessage = function(e) {
var type = null;
  if(e.data.length){
  	type = e.data[0];
  }
	switch(type){
	case "init" :  engine = new physics(e.data);
	break;
	}
}

physics = function(data){
	this._core = data[1];
	this.gravity = data[2];
	this.stack = [];
	var parent = this;
	this._init = setInterval(function(){parent._run()},1000/30);
}

physics.prototype._run = function(){
	console.log("Worker on Thread "+this._core+" Fired!");

};

We also need to make some changes on the main.js file to accomidate the thread structure.

...
pong = {
	ent_stack : [],
	gravity : [0,0.2],
	_init : null,
	cores : navigator.hardwareConcurrency || 4,		
}
...
	if (window.Worker) {
		
		workers = new Array(pong.cores);
		wID = 0;
		for(c=0; c<pong.cores; c++){
			workers[c] = new Worker("./js/worker1.js");
			workers[c].postMessage(['init', c, pong.gravity]);
		}
		
  			/*newWorker.onmessage = function(e) {
  				var result = e.data;
  				if(result[0]=='update'){
				}
			}*/
			
			pong._init = setInterval(function(){
      		ctx.clearRect(0, 0, cvas.width, cvas.height);
      		reDraw();   
    		},1000/30);
....

If when you run the page and look at your console, you should see all the threads sending out information to the console! So now that we have our threads firing, and creating a new function called physics, its time to pass some Entites to the now unbuilt physics engine.

Part 3.2 – Physics B***h!

So how are we gonna handle this? Why dont we just use some other library? Why have you not used jQuery yet? Yeah well… the whole point of this is to expand your and my know how and just deploying a library is easy. Plus how much better are you going to be at your favorite engine if you understand some of the basic components?

Right away, we are only dealing with 2 dimensions so the natural inclination would be to go with a Array(2), and prototype some functions into the Array Object, but why not tailor things for what we are doing. So instead lets do an Array(3) with it representing [POSX, POSY, ROTATION], the same concept then can be used for the velocity vector. We would need a few things to happen for the engine to actually work:

  1. Check state of Object, if it turned off even in the stack ignore calculations on it.
  2. Apply Gravity to velocitys, with account for an objects mass.
  3. Apply any resctrictions
  4. Pre Check for Hits
  5. If its going to hit restrict the objects position to the point of impact and do inertia return calculations
  6. Convert Velocites to Units of messure of some kind
  7. Send Message back to main thread.

Now as I was doing this, I got all the way to having the objects pushed to their thread, then I realized… there would be no way to actually do a hit test on any object because simply enough there is no effective way to communicate between threads. Now there are shared workers but thats a whole other monster we will try to tackle at some other point. So instead of bogging you down with the script that does not work we will move right on to a single sub thread model.

// Step 3
var engine = null; //Does not need to be global.
onmessage = function(e) {
var type = null;
  if(e.data.length){
  	type = e.data[0];
  }
	switch(type){
	case "init" :  engine = new physics(e.data);
	break;
	case "AddObj" : engine._addObject(e.data[1]);
	break;
	}
}

physics = function(data){
	console.log("TREAD "+data[1]+" STARTED!");
	this._core = data[1];
	this.gravity = data[2];
	this.stack = [];
	var parent = this;
	this._init = setInterval(function(){parent._run()},1000/30);
}

physics.prototype._run = function(){
	for(e=0; e<this.stack.length; e++){	
		if(!this.stack[e].on){continue}
		
		var tempCalc = this._calc(this.stack[e]);
		
		/*
		var hit = false;
		for(h=e+1; e< this.stack.length; h++){
		if(!this.stack[h].on){continue}
		if(hit){return}
			if(physics._hitTest(e,h)){
			
			}else{
			continue	
			}
		}
		*/
		this._apply(tempCalc, e);
		
	}
	

};

physics.prototype._addObject = function(obj){
	obj.pos = obj.intPos, obj.velocity = obj.intVel;
	this.stack.push(obj);
	console.log("Thread "+this._core+": Added Obj - "+obj.id+" to its stack");
}

physics.prototype._hitTest = function(a,b){

return false;
}

physics.prototype._calc = function(obj){
		
	var response = {
		stackID : obj.stackID,
	};
	response.newVel = [
		obj.velocity[0] + (obj.mass * this.gravity[0]), //X
		obj.velocity[1] + (obj.mass * this.gravity[1]), //Y
		obj.velocity[2]	// ROTATION
	]
	response.newPos = [
		obj.pos[0] + response.newVel[0], //X
		obj.pos[1] + response.newVel[1], //Y
		obj.pos[2]	//ROTATION
	]
	
	//console.log(response);
	return response;
}

physics.prototype._apply = function(calc, id){
	this.stack[id].pos = calc.newPos;
	this.stack[id].velocity = calc.newVel;
	postMessage(['apply',calc]);
}

With these changes to the worker script, we have enabled the ability to start calculating basic physics into our scene. To enable it we need to modify the main script now. We can get rid of the thread count on the pong object as we are going with a single sub thread now, and then we have to change our script around to be a single worker instead of the 4 we had set up.

...
if (window.Worker) {
		
		worker = new Worker("./js/worker1.js");
		worker.postMessage(['init', 0, pong.gravity]);

		
		function addObj(obj, stackID){
			worker.postMessage(['AddObj',
			{
				id : obj.id,
				body : obj.body,
				mass : obj.mass,
				intVel : obj.velocity,
				intPos : obj.pos,
				stackID : stackID,
				on : true				
			}
			]);
	
		}
		
				
		
		for(var i = 0; i < pong.ent_stack.length; i++){
			addObj(pong.ent_stack[i], i);	
		}
		
  			worker.onmessage = function(e) {
  				var result = e.data;
  				if(result[0]=='apply'){
					var calc = result[1];
					pong.ent_stack[calc.stackID].velocity = calc.newVel;
					pong.ent_stack[calc.stackID].pos = calc.newPos;
				}
			}
			
			pong._init = setInterval(function(){
      		ctx.clearRect(0, 0, cvas.width, cvas.height);
			reDraw();   
    		},1000/30);
...

If your following along and have everything set up correct, when you refresh the page the ball should now drop like graviity is being applied to it. This set the stage for us to start making some more dynamic effects, the things we have to consider now is how we are going to handle our Collison detetions. The most simple model will be for us to use a projection and impulse system where we test if our object is going to collide find out the position where this is happening and then modify our velocity and position to stop the objects from penitrating. We will keep the model simple, but will include things like restitution and friction.

Collisions, Collision, COLLISIONS!

How does one actually do a collision test? Well in concept it is easy, first you have to establish what kind of collisons you need to calculate for, are they simple shapes like rectangles and cirlces only? Are the axes of the rectangles always the same? What kind of shapes we need to test will decide our approch. For this model we need to track at least circles and off axis rectangles. I want to include off angle rectangles even though the paddle will never change its angle, because there may be a reason to place other objects in the scene that do not have flat axial value. Oh man, I just realized how quickly this is becoming a math lesson… my bad, anyways to achive our goals lets first go over some vocabulary. Also for these examples I am writing them out for any length vector, which is useful in normal situations but with how we are storing our stuff it might not be the best idea. So I have one of two options, pass more variables that are standard vec2’s and numbers instead of our vec3 that has rotation with it as well, or redo these functions to only handle 2 units of the vector we hand it. The smartest I think would be to follow convention, and drop the vec3 that we were using and have a seperate value for the rotation so that way when we do our vector calculations they are correct.

  • normalization

    Normalizing a vector is scaling it so that its length totals 1. To normalize the vector, we divide each of its components by the length of the vector:
    function normalize(vec){
    var l=0;
    for(var i = 0; i < vec.length; i++){
    l+= (vec[i]*vec[i]);
    }
    l = Math.sqrt(l);
    for(var i = 0; i < vec.length; i++){
    vec[i]/=l;
    }
    return vec
    }
  • dot product

    Think of it as the relative orientation of a and b. With a negative dot product a and b point away from each other; a positive dot product means they point in the same direction.
    function dot(a, b){
    var t = 0;
    for(var i=0; i < vec.length; i++){
    	t += (a[i]*b[i]);
    }
    return t;
    }
  • projection

    A formula to find the shortest length vector that an object must travel to be out of the collision and using this to detect if a object is collided or not.
    function project(a, b){
    var proj = new Array(a.length);
    var  bt = 0;
    for(var i = 0; i < a.length; i++){
    bt+= (b[i]*b[i]);
    }
    for(var i = 0; i < a.length; i++){
    proj[i] = (dot(a,b)/bt)*b[i];
    }
    
    return proj
    }
  • Perpedicular Product

    How to return the vector perpendicular to the input. Every 2D vector has two normals: the right hand and left hand normal. The right hand normal points to the right of the vector, and the left hand normal points to the left.
    function perproduct(vec2){
    var rN = [-vec2[1], vec2[0]];
    var lN = [vec3[1], -vec2[0]];
    return dot(vec2,rN);
    }

With these basic functions we are going to be able to run a whole array of 2d comparisons. So to solve our 2D overlap test using a series of One Dimensonal Tests. Each query tests if the two shapes overlap along a given axis. If one of the Axes we test fails then we know that the objects are not intersecting, and we can stop our test to save on overhead. If we run a test and find that the objects overlap along all of the possible axes, they are definitely overlapping each other. From this point we need to figure out the projection vector, which we will use to seperate the objects.

The last step would be to find which axis has the smallest amount of overlap between the two objects. The “Push” we are looking for or the projection vector is the same as the axis direction with the length of the projection vector equal to the size of the overlap. To acomplish this we need to know first the position of the object and all of its axes, along with our target object and the same. But Wait? What about circles, or triangles or or… ok fine lets do some drawings.

 

Separating Axis Theorem

In 2D games to represent moving objects we make an axis-aligned
bounding box, or AABB. An AABB is defined by a position and two vectors xw and yw that represent half widths of the object. The concept is the same as testing the radius of circle, but these are aligned to the world axis and are then defined in a specific direction and distance.
Well that all sounds cool… but how does it work? I think maybe the simplest way will be to make a real quick mock up canvas for you. After the first example, we will go over more shapes and the methods for testing them. I know this was supposed to be a webworker tutorial, but for real though we need something decently intensive to even have a nessesity for them. Collision testing I think meets that bill, so please stay with me or skip ahead.
In the next example what we will see happen when you click run, is the red box should move to the right and once it collides with the other box well start it all over.

START/STOP
This is a SUPER simplified model, which works only if the two objects faces are perfectly aligned and thats something that is kinda weak for what we are looking to do. So what happens when its a polygonal shape or a off angle square? Back to the drawing boards.

 

This is where the method for seaperating axes comes into play. If you
look at our diagram on the right you will see two polygons. Both of these shapes are called as Convex Shapes. A Convex shape is any polygon that can be defined by a set of points, that if you were to draw a straight line anywhere on the shape from one point to anouther on the polygon, the line will never travel outside of the shape. Anyways these two Convex polygons are in a non intersecting state.

The value for the seperation is positive and so we know that the shapes are not touching, if it was negitive the shapes would be overlapping and if it was 0 the shapes are just touching. With this kind of hit detection there would be three kinds of possible contact, edge to edge, vertex to edge, and vertex to vertex. If we were to draw a line between the two polygons and we pretend the seperation line continues to infinity and we draw a line perpedicular to this line, that is our speration axis.
Anouther thing we need to start identifying is the “normal” angle of and edge. This is not to be confused with our normalization meathod discussed earlier, but is a way to establish heading of our edge. When we define our shapes, we need to follow a convention that assumes the shapes points are orderd on a clockwise direction, this is so when we loop through our edges it stays consitant on the output no matter the shape. You could proccess the shapes counter-clockwise but this would effectivly reverse your edge normals.





I think the easist way to visualize all this is to make some more diagrams… lets see if I can mock up some canvas elements to demonstrate.

If you look at the diagram on the right, you will see a Convex Polygon with its center point represented by the black dot. The red dots are the points of the polygon, the green are the edges and the blue arrows are the normal vector or perpendicular axis to the face. If you drag one of the polygons you will see that the normal for that face changes.

What we need to establish now is the most extreme points on the polygon. We do this by simply looping through the points and of the polygon and find the most extreme points, then project the max and min points onto the perpendicular normal lines. If all of the projections overlap we know we have a contact.

To make this simpler to understand lets extend out projection axis for each normal out farther. If you were to select any of those lines that extend from the face of the edge, you would look at both the current polygon and the opposing one and figure out what points on those polygons are at the min and max points for that projection line.

 


In the case of projection line a1 we see that the most extreme point on the polygon that falls on that projection axis is the same as the edge itself, both points that make up that edge would have the same value effecivly when projected on that line so our min value for the projection of polygon A to axes A1 is equal to the projection value of point 0 || 1 (remember we go clockwise and when I constructed these I started at the top left). We then look for the max using the same method and in this instance the max value of polygon A is the projection value of the point between edge a2 and a3, or point 3. We now know where on this axis the polygon A is located so we do the same to polygon b (still looking at the a1 axis). When we follow the same process we fine that the min of B is point 1 and the max of B is point 3. If you remember I diagram on the top this is what we were representing. You can in your mind draw line from these points to perpedicular the projection axis and you can easily see if the two polygons are overlapping in that instance. If at any point we discover that any of the axes do not overlap then we do not have to continue our calulations and can then interpolate the response.
Now I can continue to beat this concept into the ground and do a bunch of implementation to show you how we would calculate a whole gambit of physics stuff, but this is supposed to be a web socket tutorial so lets just get back to doing that.

Back to the Game.

Ok I know I was talking all sorts of good stuff about, lets include curved shapes and blah blah… but this is starting to take up way to much time and I have to get back to some other projects. That means its time to wrap this up.

We are going to just worry about making the ball bounce around hit the paddle and stay on the stage, get some controls working and output a score. After that Ill leave it up to you to extend these ideas and make something really cool!

First a little bit of restructing is nessirary to make this a little less redundent on our object constructors and make them a little more diverse on their arguments. Then we will just place the player in the scene and attack some kind of controler to allow the user to have input. Then we will use the same constructor as to make some walls, but they will only be there as a level constraint. After we get the walls and the paddle in place we will script a simple version of the hit testing and see if we can get a “bounce” back off the walls with the paddle. After all that we will add the ball back into the stack, and make sure that we have the hit detection identifying the shapes body and running the approriate tests.

To be Continued…

Also this was taken from my older website and may have some broken links, and scripts that may now work as of yet on the new site!

Refrences:

MethodOfSeparatingAxes.pdf

New Site!

New site is launched! There will be some errors in the links of some of the articles I assume. As time goes on here they will be fixed. I will continue to post content on this site as I create it and am hoping to get in the habit of just working on here instead of my localhost o_O…