Showing posts with label javascript. Show all posts
Showing posts with label javascript. Show all posts

Friday, November 1, 2013

Compile and execute a code snippet from your C# program

The problem

Every so often I find myself creating little command line programs that:
  1. Gather a list of items from somewhere
  2. Perform some user-controllable operation on each item
My problem for today is in that user-controllable operation. Somehow I often end up designing and implementing a little mini-programming language.
    > ChangeDocuments "UserName = Frank" "Set RetentionPolicy=30y"

    > ChangeDocuments "Today > ExpirationDate" "Add State=Expired"
The first parameter to this ChangeDocuments program is a quite regular search query that I can feed into the system I am programming against. The system is well designed, so I can feed nicely complex search queries into it:
    RetentionPolicy = 30y AND (ExpirationDate = Null OR AnyOtherField = AnyValue)
When I am testing my little ChangeDocuments program I can clearly see that the query language was designed by people that know that sort-of stuff and parse search queries for a living.

Unfortunately that doesn't apply to me. Which means that the second parameter, the one that I have to implement myself, turns into a mini programming language that gets uglier with every step.

    Set RetentionPolicy=30y
    Add State=Expired
    Clear RetentionPolicy
    Set ExpirationDate=TodayPlus30Years()
Ouch? Did you see that last one? Not only is it ugly, but I'll have to find a way to parse that function call out of there and implement the function. And what if they want a different number of years. Sure, I could write a proper parser for that and implement function calls, call stacks, contexts and all that. But I also need it to be done today and to feel slightly more wieldy then the way I'll end up implementing it. Besides... aren't there enough people that implement programming languages for a living already?

So what I'd really prefer to do, is execute a snippet of C# code. So that the above examples can turn into something more regular, like:

    Set("RetentionPolicy", "30y")
    Add("State", "Expired")
    Clear("RetentionPolicy")
    Set("ExpirationDate", DateTime.Now + TimeSpan.FromDays(30 * 365))
Note that this is still not an ideal language. I'd prefer to have symbols like RetentionPolicy and State to be available like named variables. But short of implementing my own domain-specific language, this is as close as I could get with C# in a reasonable time.

Walkthrough

When I first dynamically compiled code in .NET, I was shocked at how simple this is.

Let's start with this code snippet:

    DateTime.Now + TimeSpan.FromDays(30 * 365)
For the moment, we'll put it in a variable:
     var snippet = "DateTime.Now + TimeSpan.FromDays(30 * 365)";
We'll be compiling the code using .NET's built-in C# compiler. The C# compiler can only handle full "code files" as its input, so the type of thing you'd normally find inside a .cs file.

So we'll wrap our snippet in a little template:

    using System;
    public class Snippet {
        public static void main(string[] args) {
            Console.WriteLine(CODE SNIPPET GOES HERE);
        }
    }
In code:
    var template = "using System;\npublic class Snippet {{\n\tpublic static void main(string[] args) {{\n\t\tConsole.WriteLine({0});\n\t}}\n}}";
    var code = string.Format(template, snippet);
Note that for now we simply write the result of the expression to the console. We'll see other ways to handle this later.

Next up is the bulk of our operation: compiling this code into an assembly.

    var provider = new Microsoft.CSharp.CSharpCodeProvider();

    var parameters = new System.CodeDom.Compiler.CompilerParameters{ GenerateExecutable = false, GenerateInMemory = true };

    var results = provider.CompileAssemblyFromSource(parameters, code);                                                

    if (results.Errors.Count > 0) {
        foreach (var error in results.Errors) {
            Console.Error.WriteLine("Line number {0}, Error Number: {1}, '{2};\r\n\r\n", error.Line, error.ErrorNumber, error.ErrorText);
        }
    } else {
        var type = results.CompiledAssembly.GetType("Snippet");
        var method = type.GetMethod("main" );
        method.Invoke(null, new object[] { new string[0] });
    }
That is really all there is to it.
    10/25/2043 1:21:04 PM
There are tons of additional parameters you can pass to the CSharpCodeProvider, but this minimal set tells it to:
  • generate an assembly, instead of an executable
  • keep the generated assembly in memory, instead of putting it on disk

Complete code

This is the complete code snippet that we constructed so far:
    var snippet = "DateTime.Now + TimeSpan.FromDays(30 * 365)";
    var template = "using System;\npublic class Snippet {{\n\tpublic static void main(string[] args) {{\n\t\tConsole.WriteLine({0});\n\t}}\n}}";

    var code = string.Format(template, snippet);

    var provider = new Microsoft.CSharp.CSharpCodeProvider();

    var parameters = new System.CodeDom.Compiler.CompilerParameters{ GenerateExecutable = false, GenerateInMemory = true };

    var results = provider.CompileAssemblyFromSource(parameters, code);                                                
    if (results.Errors.Count > 0) {
        foreach (System.CodeDom.Compiler.CompilerError error in results.Errors) {
            Console.Error.WriteLine("Line number {0}, Error Number: {1}, '{2};\r\n\r\n", error.Line, error.ErrorNumber, error.ErrorText);
        }
    } else {
        var type = results.CompiledAssembly.GetType("Snippet");
        var method = type.GetMethod("main" );
        method.Invoke(null, new object[] { new string[0] });
    }
I normally run this type of code snippet in LINQPad, which does something quite similar (albeit likely a lot more elaborate) internally. But if you just paste the above into the main of a command line program in your Visual Studio project it'll also work of course.

Possible changes and considerations

Use an instance method In the above code we use a static main method. If you'd instead prefer to use a regular instance method, you'll need to instantiate an object and pass it to Invoke, like this:
    var type = results.CompiledAssembly.GetType("Snippet");
    var obj = Activator.CreateInstance(type);
    var method = type.GetMethod("main" );
    method.Invoke(obj, new object[] { new string[0] });
If you do this, I recommend that you name the method something else than main, since most people will associate main with a static void method. Pass parameters to the snippet The snippet operates in complete isolation so far. To make it a bit more useful, let's pass some parameters into it:

First we'll need to modify our template to do something with the new parameter:

	var template = "using System;\npublic class Snippet {{\n\tpublic static void main(string[] args) {{\n\t\tConsole.WriteLine(args[0], {0});\n\t}}\n}}";
So we just use the first parameter as the format string for Console.WriteLineargs[0], {0}). Then we pass a value for this parameter when we invoke the method:
    method.Invoke(null, new object[] { new string[] { "Expiration date = {0}" } });
And now the snippet will print:
    Expiration date = 10/25/2043 1:21:04 PM
Make the script return a value However interesting writing to the console is, it is probably even more useful if our snippet would return its value instead.

To accomplish this, we'll change the template for the main method to this:

    public static string main(string[] args) {{\n\t\treturn string.Format(args[0], {0});\n\t}}
And the invocation now needs to handle the return value:
    var output = method.Invoke(null, new object[] { new string[] { "Expiration date = {0}" } });
    Console.WriteLine(output);
Note that the snippet itself has remained completely unchanged through all our modifications so far. This is a good design principle if you ever allow the users of your application to specify logic in this way: make sure that any changes you make to your code are backwards compatible. Whatever code the users wrote, should remain working without changes. The line numbers for errors are offset If there is an error in the snippet, the script will write the error message(s) that it gets back from the C# compiler.

So when we change the snippet to:

    var snippet = "DateTime.No + TimeSpan.FromDays(30 * 365)";
We'll get this output:
    Line number 4, Error Number: CS0117, ''System.DateTime' does not contain a definition for 'No';
The error message itself is correct of course, but the snippet we provided is one line, to the line number is clearly wrong. The reason for that is that our snippet is merged into the template and becomes:
    using System;
    public class Snippet {
        public static string main(string[] args) {
            return string.Format(args[0], DateTime.No + TimeSpan.FromDays(30 * 365));
        }
    }
And indeed, this C# contains the problem on line 4.

The solution for this line number offset is to either subtract the offset from the line number in the error message or simply not print the error message. In a simple case such as this the latter option is not as bad as it may sound: we only support short snippets of code, so the line numbers should be of limited value. But then again: never underestimate the ability of your users to do more with a feature than you ever thought possible. Make the wrapper class more complete Probably the most powerful way you can extend the abilities of your snippet-writing users is by providing them more "built-in primitives".

  • Any method you add to the Snippet class, becomes like a built-in, global function to the snippet author. So the Set, Add and Clear methods of my original snippets could be implemented like that.
  • You can also make the Snippet class inherit from your own base class, where you implement these helper functions.
  • Any variables that you define inside the main method before you include the user's snippet, will become like built-in, global variables to your snippet authors.
  • I've had great success in the past with making utilities such as a log variable available like this.
Allow importing more namespaces and referencing more assemblies The template above imports just one namespace and only binds to the default system assemblies of .NET. To allow your snippet authors to use more functionality easily, you can either expand the number of using statements in the template and add additional references to the ReferencedAssemblies of the CompilerOptions.

Alternatively you can give the users a syntax that allows them to specify their own namespaces to import and even assemblies to reference. In the past I got some pretty decent results with this syntax:

   <%@ Import Namespace="Path.Of.Namespace.To.Import" %>
Use VB instead of C# There is also a compiler for Visual Basic code. If you'd prefer to use that, you can find it here:
    var provider = new Microsoft.VisualBasic.VBCodeProvider();

Sunday, January 20, 2013

Handling asynchronicity in an API

Designing a good API is one of the more difficult tasks when it comes to software development. Unfortunately it is also one of the important tasks, since it is really hard to change an API after it's been made public. Well OK, maybe it is not hard for you to change the API, but it is hard on the users of your API: they have to update all their client programs if you decide to make changes.

Nowadays many APIs deal with asynchronous operations, especially when an API bridges the gap between a client-side web application and a server-side back-end. Whenever a web application needs some additional data from the server, it needs to initiate a (XMLHttpRequest) call to the server. And since such a call can take a significant amount of time it should (in almost all cases) be handled asynchronously.

Checking if the title is loaded

Here is how I recently saw this done in a JavaScript API:

    function displayTitle(object) {
      if (object.isLoaded()) {
        document.getElementById('title').innerText = object.getTitle();
      } else {
        function onLoaded(object) {
          object.removeEventHandler('load', onLoaded);
          document.getElementById('title').innerText = object.getTitle();
        }
        object.addEventHandler('load', onLoaded);
        object.load();
      }
    }

To display the title of the object, we first have to check if the data for the object has been loaded from the server. If so, we display the title straight away. If not, we load it and then display the title.

That is quite a lot of code, for what is a quite common operation. No wonder so many people dislike asynchronous operations!

Use a callback for the asynchronous operation

Let's see if we can simplify the code a bit.

For example, the event handler is only used once here. And although registered event handlers can be useful for things that happen all the time, clearly in many cases people will want to check if the object is loaded in a regular sequence of code - not respond to whenever the object is (re)loaded.

If we allow the onLoaded function to be passed into the load() call, things clean up substantially:

    function displayTitle(object) {
      if (object.isLoaded()) {
        document.getElementById('title').innerText = object.getTitle();
      } else {
        object.load(function onLoaded(object) {
          document.getElementById('title').innerText = object.getTitle();
        });
      }
    }

The nice thing about this change it that you can add it to the existing API after releasing it:

    MyObject.prototype.loadAndThen = function(callback) {
      function onLoaded(object) {
        object.removeEventHandler('load', onLoaded);
        callback(object);
      }
      this.addEventHandler('load', onLoaded);
      this.load();      
    };

This is mostly a copy of the code we removed between the first and second fragments above. But now instead of everyone having to write/copy this plumbing, you just have to write it once: in the prototype used for the object in question.

Note that I named the function loadAndThen, to avoid conflicting with the existing load function.

Assume asynchronicity

But when I started using the Firebase API a while ago, I noticed how natural their way of handling asynchronous operations feels. If we'd apply their API style to the above example, the displayTitle function would become:

    function displayTitle(object) {
      object.getTitle(function (title) {
        document.getElementById('title').innerText = title;
      });
    }

Since the title might have to be loaded from the server, they require you to always pass in a callback function. And they will simply call that function once the title is loaded.

Now I can see you thinking: "but what happens if the title is already loaded?" That is the beauty of it: if the title is already loaded, they simply invoke the callback straight away.

If we'd like to implement such an API on top of our example, we could implement getTitle like this:

    MyObject.prototype.getTitleAndThen = function(callback) {
      if (this.isLoaded()) {
        callback(this.getTitle());
      } else {
        function onLoaded(object) {
          object.removeEventHandler('load', onLoaded);
          callback(object.getTitle());
        }
        this.addEventHandler('load', onLoaded);
        this.load();      
    };

Like before I gave the function a suffixed name to prevent clashing with the existing getTitle function. But of course if you end up implementing this in your own API, you can just stuff such code in the regular getTitle function (which probably reads the title from a member field of this).

If you think this is a lot of code to add to your framework, look back at our first example. If you don't add the code to your framework, every user will end up adding something similar to their application.

Conclusion

By assuming that certain operations are (or at least can be) asynchronous, you can reduce this code:

    function displayTitle(object) {
      if (object.isLoaded()) {
        document.getElementById('title').innerText = object.getTitle();
      } else {
        function onLoaded(object) {
          object.removeEventHandler('load', onLoaded);
          document.getElementById('title').innerText = object.getTitle();
        }
        object.addEventHandler('load', onLoaded);
        object.load();
      }
    }

To this:

    function displayTitle(object) {
      object.getTitle(function (title) {
        document.getElementById('title').innerText = title;
      });
    }

The biggest disadvantage I see in the second example is that users of your API are more directly confronted with closures. Although I hang around on StackOverflow enough to realize that closures are a real problem for those new to JavaScript, I'm afraid it is for now a bridge that everyone will have to cross at their own pace.

Tuesday, August 25, 2009

JavaScript Particle Systems part 2: adding some life

The frame below shows a demonstration of the particle system we are about to build. Move your mouse through it to have some fun. If it doesn't work for you, click this link to open the same demo in a popup window.

Introduction

A few months ago I wrote an article that demonstrated how to create a very simple particle system in less than 50 lines of JavaScript code. That article has slowly been finding its way into the Google search indexes and by now it's becoming obvious that I'm not the only one who thinks particle systems deserve more attention and JavaScript is the perfect language to experiment with them. Back then I was quite pleased with being able to implement a fully functional particle system in less than 50 lines of (quite readable) JavaScript code. But I think we can agree that the particle system was not very exciting. Although the system contained all three required ingredients, the end result was a bit "static". From games and other places where particle systems are used, we are used to them being a lot more "alive". So that's the goal for this article: to add some life to our previous particle system, while still keeping it small. In this case I've increased my self-imposed limit to a 100 lines. A generous doubling from our previous system, so we'd better have some real interesting "life" to show for the increase. We'll add three behaviors to the particle sytem.
  • Gravity
  • Grow then shrink
  • Mouse control
Lot's of work to do, so let's get started with gravity straight away.

Gravity

In our first particle system, the particles would fall at a constant speed. The fall speed of each particle was determined at random when creating the particle.
      dy: Math.random() + 0.5
And then we just updated the y position every time:
      particles[i].y = particles[i].y + particles[i].dy;
I always find it very interesting to add some gravity-like behavior to systems I create. So how about making the particles fall at an increasing speed?
      p = particles[i];
      p.y += p.dy;
      p.dy += 0.1; // simulate gravity
So we increase the particle's y velocity every time we update its position. I realize that to make this work like real gravity I'd have to know the particle's mass and do a multiplication. But for this simple example just increasing the dy is already convincing enough. Since the particle will now drop at an ever increasing speed, it is nice to make it go up a bit at first:
      dy: -1 + Math.random()
So the particles will first move up a bit and then start falling down at an increasing speed. If all goes well, they'll move in a nice arc-like pattern. Again there is no real math or physics reason for these values, these just looked best to me. If you feel the need to make the system more physically correct, just download the source and go ahead. Let me know if you find an interesting combination.

Grow then shrink

Another thing I wasn't too happy with in the original particle system is the static size that the particles have. Each particle is created to be 3px in width and height. By the way: there was a bug in the original code such that the sizing didn't work in Internet Explorer. As my team often tells me: "you need to test more with IE Frank!" My bad. Let's hope I got it right this time. I changed the code to shrink the particle a bit in each update:
      p.s -= 0.1
This of course requires the particle to have a size when we create it:
      p.s: 3.0
With this setup the particle will slowly shrink from 3 pixels width and height to 0. Once the size of the particle reaches 0, we can kill it:
      if (p.ttl-- > 0 && p.s > 0) {
         updateParticleElement(p);
This leads to a working particle system, but somehow it's still a bit boring when all the particles start and shrink at the same speed. So let's make the size change random and instead of just shrinking, let's make the particles grow at first and then shrink until they die out. For the initialization the change is simple:
      p.ds: Math.random()+0.1,
This gives the particle a growth speed that is guaranteed to be positive. So instead of adding 0.1 each time we update the particle, we add the ds:
      p.s += p.ds;
If we leave this unchanged, the particle will grow forever - or at least until it's time to live runs out. To ensure the particle also starts shrinking at some point we give it a maximum size:
      if (p.s > 5) p.ds *= -1;
When the particle reaches its maximum size, we just flip the sign of the growth speed - so it becomes a shrink speed. After this the particle will keep shrinking until it reaches size zero at which point it dies out. By now I'm not really sure if the ttl property is still needed, as the particles already have an implicit time to live and get their randomness from the growth/shrink speed. But I left the ttl in as a safeguard against my own mistakes when manipulating the size. I wouldn't want to end up with an infinitely living and growing particle by mistake. If you would reconstruct the particle system at this point it is already quite lively and dynamic. Particles seem to be attracted by the bottom of your screen and particles seem to have a real life cycle, where they grow and shrink to die out. But this particle system is still a spectator sport. Let's see what happens when we give the user some control over what happens on screen.

Mouse control

As our last feature we want to give the user some control over the behavior of the particles. Specifically I want to accomplish two things:
  1. particles originate close to the position of the mouse cursor
  2. particles move roughly in the direction that the mouse is moving
To accomplish this we need to add four variables to the system.
      mx and my - the position of the mouse
      dmx and dmy - the direction and speed of the mouse's movement
These variables are global to the script, so they are not stored for each particle. These variables are updated whenever the user moves the mouse, by hooking the onmousemove event of the window. The mousemove handler is a bit tricky to read at first. But since the behavior of the particles only depends on the four variables mentioned here, I will not explain the mousemove handler of the code further. Now how do we use these variables when creating and updating a particle? The variables are actually only used when we create a new particle:
      x: mx,
      y: my,
      dx: dmx + Math.random(),
      dy: dmy + Math.random() - 1,
As you can see the code remain quite similar to how it was. We've just substituted our new "mouse dependent" variables for the previous hard coded and random values. We still make the dx and dy a bit random, since otherwise all particles would go in the same direction. The updating of the particles doesn't have to change for this behavior. The mouse just allows the user to control the position and the direction of the initial movement. After its creation each particle behaves as the rules of our system dictate, which ensures the particles still behave similar even with al their differing properties.

Summary

So in the first article we created a simple particle system in less then 50 lines of JavaScript code. The system was fully functional, but felt a bit static after you'd been looking at it for a while. In this second article we've added life to our particle system by adding by:
  1. making the environment a bit more "physical" with our simple gravity emulation
  2. making the life cycle of the particles more complex, by making them grow and then shrink and die out
  3. allowing the user to control the particles, by hooking their position and movement up to the mouse movement
All in all our particle system has now gotten quite complex. But weighing in at 90 lines, it is still well under my self-imposed limit of a 100 lines of code. I did my best to keep the code readable again and even added some constants to make it easier to change and debug the particle system. Now go ahead and play with the system. I find it's great fun to see how far up you can throw the particles. Remember: this is controlled by moving the mouse, so start pushing and pulling your mice!

The code

// constants
var NUM_PARTICLES = 50;
var FPS = 20;
var PARTICLE_LIFETIME = 4; // in seconds
var ANIMATION_LIFETIME = 300; // in seconds

// global variables
var container;
var particles = [];
var framecount = 0;
var mx = 20; // default origin, will be set to mouse position once the mouse moves
var my = 20;
var dmx = 1.0; // default movement, will be set to mouse movement once the mouse moves
var dmy = -1.0

function onMouseMove(e) {
 var IE = document.all?true:false
 var nmx, nmy;
 if (IE) { // grab the x-y pos.s if browser is IE
  nmx = event.clientX + document.body.scrollLeft
  nmy = event.clientY + document.body.scrollTop
 } else {  // grab the x-y pos.s if browser is NS
  nmx = e.pageX
  nmy = e.pageY
 }
 dmx = (nmx - mx) / 4;
 dmy = (nmy - my) / 4;
 mx = nmx;
 my = nmy;
}

function createParticle(container) {
 var p = {
  elm: createParticleElement(),
  x: mx,
  y: my,
  s: 0.0, // size
  dx: dmx + Math.random(),
  dy: dmy + Math.random() - 1,
  ds: Math.random()+0.1,
  ttl: PARTICLE_LIFETIME*FPS
 };
 container.appendChild(p.elm);
 updateParticleElement(p);
 return p;
}

function createParticleElement() {
 var elm = document.createElement('span');;
 elm.style.border = '1px solid blue';
 elm.style.position = 'absolute';
 return elm;
}
function updateParticleElement(p) {
 p.elm.style.width = p.elm.style.height = p.elm.minWidth = p.elm.minHeight = Math.floor(p.s) + 'px'; // doesn't work on IE
 p.elm.style.left = Math.floor(p.x) + 'px';
 p.elm.style.top = Math.floor(p.y) + 'px';
}

function updateParticles() {
 for (var i=particles.length-1; i >= 0; i--) {
  var p = particles[i];
  p.s += p.ds;
  if (p.s > 5) p.ds *= -1;
  p.x += p.dx;
  p.y += p.dy;
  p.dy += 0.1; // simulate gravity
  if (p.ttl-- > 0 && p.s > 0) {
   updateParticleElement(p);
  } else {
   container.removeChild(p.elm);
   particles[i] = createParticle(container);
  }
 }
 if (framecount++ < ANIMATION_LIFETIME*FPS) {
  setTimeout('updateParticles()', Math.floor(1000 / FPS));
 } else {
  alert("All done. Reload to watch again.");
 }
}

window.onload = function() {
 container = document.getElementById('particles');
 for (var i=0; i < NUM_PARTICLES; i++) {
  particles[i] = createParticle(container);
 }
 
 setTimeout('updateParticles()', Math.floor(1000 / FPS));
 document.onmousemove = onMouseMove;
}
Download it here. And the corresponding HTML:
<html>
    <head>
        <title>JavaScript Particle System</title>
        <script type="text/javascript" src="particles2.js"> </script>
    </head>
    <body>
        <div id="particles" style="width:640px; height: 480px; overflow: hidden"> </div>
    </body>
</html>
Download it here.

See also

Saturday, May 16, 2009

Particle systems in JavaScript

Particle systems have always held some magic for me. Or maybe I should explain it more clearly: anything that resembles physics in a game-like fashion has always held some magic to me. In this post we'll look at how to create a simple particle system in JavaScript.

Pod racers


A few years ago when I wrote a small 3D pod racer for my own amusement. If you don't know what pod racers are, have a look at this video:



My game looked nothing like that of course. I'm a developer, not an artist. And besides I spent lots of time playing with the physics of the pod: where are the thrusters on my pod? How much force do the thrusters give? Does the force get exponentially bigger when the pod gets closer to the track? Fun stuff.

I also added a particle system to my pod. After all, those thrusters are bound to give off some exhaust fumes and this was a great way to give an indication of speed. And of course it was a great way for me to get started on particle systems.

As it turns out particle systems are really quite simple things. I had a blast playing with the parameters and figuring out how to create a most interesting effects.

Of course the pod racer was never finished and the source code has long been lost. That's why today we'll create a completely new particle system. In less than 100 lines of JavaScript. Granted it will only be 2D this time. But believe me, I've already been staring at the flow of particles longer now than it took me to write the script.

parts of a particle system



Let's get started with the three things that make up a particle system:

  1. an array of particle data structures

  2. a function that updates all particles each frame

  3. some form of lifetime management for the particles


Parts of a particle


First comes the particle data structure. What makes up a particle? If you've ever seen a particle system in its bare essentials, you'll have noticed that it consists of multiple small elements on your screen that each move on their own account, yet in a predictable and similar way.

This already means quite a few things. A particle apparently has a location on the screen. And since it moves, it must also have a direction.

var particle = {
x: 0.0,
y, 0.0,
dx, 0.5,
dy: 0.5
}

So this is a particle that is at position (0,0) and moves half a pixel to the right and bottom every time.

Creating an array of these objects is of course really simple.

function createParticle() {
return {
x: 0.0,
y, 0.0,
dx, 0.5,
dy: 0.5
}
}

var particles = [];
for (var i=0; i < 10; i++) {
particles.push(createParticle());
}

But of course these are really boring particles. They're all the same. Let's make the particles unique by adding a bit of randomness:

function createParticle() {
return {
x: 0.0,
y, 0.0,
dx, Math.random() + 0.5,
dy: Math.randon() + 0.5
}
}

var particles = [];
for (var i=0; i < 10; i++) {
particles.push(crateParticle());
}

So this creates 10 particles. They all start from the same location on the screen, yet move out in a different directory.

With that out of the way, let's move on to the behavior of the particles.

Particle behavior


As I said in the previous section, particles move in a predictable way. So we'll need a function that updates the position of each particle every frame.

function update() {
for (var i=0; i < particles.length; i++) {
particles[i].x = particles[i].x + particles[i].dx;
particles[i].y = particles[i].y + particles[i].dy;
}
}

And of course we'll need to call this function periodically:

setInterval("update()", 50);

Calling the update function every 50ms results in a 20 frames per seconds. This will give us quite smooth animation, without being too taxing for todays browsers/PCs.

lifetime management


We're almost done here. But if we would start this particle system now, the particles would just move away from each other indefinitely. That won't be very interesting to look at.

What we need to add is some way for the particles to die and for new particles to be born. The simplest way to do this for now is by giving each particle a lifetime counter at birth and just decrease that with every update.

Let's first update our createParticle function:

function createParticle() {
return {
x: 0.0,
y, 0.0,
dx, Math.random() + 0.5,
dy: Math.random() + 0.5,
ttl: Math.floor(Math.random()*50) + 50 // time to live in frames
}
}

We now defined that each particle will live between 50 and 100 frames. With a framerate of 20 frames per second, that will give the particles a lifetime of between 2.5 and 5 seconds.

Let's use this new property in our update function:

function update() {
for (var i=0; i < particles.length; i++) {
particles[i].ttl = particles[i].ttl - 1;
if (particles[i].ttl > 0) {
particles[i].x = particles[i].x + particles[i].dx;
particles[i].y = particles[i].y + particles[i].dy;
} else {
particles[i] = createParticle();
}
}
}

See the nice little trick we do here? We don't delete the particle, we just replace it with a new one. Of course the new particle will start at the origin again and will have its own direction and speed.

This way we will always have the same number of particles in our system.

visualize the particle system


I was not completely honest at the start here. There is actually one more step we have to take before we can see our particle system in action. After all what good is a particle system if you can't see it.

Up until now the particle system we've created is completely agnostic to the output system. If you use JavaScript for scripting your DirectX game, you might render these particles onto a DirectDraw surface. If you feel really "Linuxy" you might render them onto a 24x40 character display. But for our purposes here, we'll render the particles using HTML.

I'll just show the modified fragments here. For the complete script, refer to the end of the article.

We visualize each particle as a simple HTML span with a blue border:

function createParticle(span) {
return {
elm: span ? span : createParticleElement(),
...
}
}
function createParticleElement() {
var elm = document.createElement('span');
elm.style.border = '1px solid blue';
elm.style.position = 'absolute';
elm.style.width = elm.style.height = '3px';
container.appendChild(elm);
return elm;
}

When updating the particle, we also have to update its span. When the particles dies, we re-use the span for the new particle:

if (particles[i].ttl > 0) {
...
particles[i].elm.style.left = Math.floor(particles[i].x) + 'px';
particles[i].elm.style.top = Math.floor(particles[i].y) + 'px';
} else {
particles[i] = createParticle(particles[i].elm);
}

demo


The frame below shows a demonstration of the particle system we just built. If it doesn't work for you, click this link to open the same demo in a popup window.

next steps


As you can see this particle system is about as simple as it can be. Real particle systems in games and simulations are of course much more complex. But the basic ingredients stay the same:

  1. an array of particle data structures

  2. a function that updates all particles each frame

  3. some form of lifetime management for the particles


If there is interest in it, I would like to make this post the first of a series where we investigate particle systems. If that is the case, the next step will be to make the particle system a bit more interesting by adding some "physics-like" behavior to it.

the finished script


This is the complete script needed to run this particle system. If you count them, you'll see that it is only 47 lines of code. So you can create an (admittedly simple) particle system in less than 50 lines of code.

var container;
var particles;

function createParticle(span) {
return {
elm: span ? span : createParticleElement(),
x: 0.0,
y: 0.0,
dx: Math.random() + 0.5,
dy: Math.random() + 0.5,
ttl: Math.floor(Math.random()*50) + 50 // time to live in frames
}
}

function createParticleElement() {
var elm = document.createElement('span');
elm.style.border = '1px solid blue';
elm.style.position = 'absolute';
elm.style.width = elm.style.height = '3px';
container.appendChild(elm);
return elm;
}

function update() {
for (var i=0; i < particles.length; i++) {
if (i == 0) console.log(i+' '+particles[i].ttl);
particles[i].ttl = particles[i].ttl - 1;
if (particles[i].ttl > 0) {
particles[i].x = particles[i].x + particles[i].dx;
particles[i].y = particles[i].y + particles[i].dy;
particles[i].elm.style.left = Math.floor(particles[i].x) + 'px';
particles[i].elm.style.top = Math.floor(particles[i].y) + 'px';
} else {
particles[i] = createParticle(particles[i].elm);
}
}
}

window.onload = function() {
container = document.getElementById('container');
particles = [];
for (var i=0; i < 10; i++) {
particles.push(createParticle());
}

setInterval("update()", 50);
}

Download it here

The corresponding HTML:

<html>
<head>
<title>JavaScript Particle System</title>
<script type="text/javascript" src="particles.js"> </script>
</head>
<body>
<div id="container" style="width:320px; height: 200px"> </div>
</body>
</html>

Download it here

Sunday, March 2, 2008

Finding primes using a grid of browsers

It's been a few months since I talked about my idea of combining the power of a lot of browsers into a so-called computing grid. Since writing that post I've been working on such a browser based grid. Progress has been slow, but steady. And I'm learning a lot in the process, so I'm not complaining at all.

My current prototype grid software has a server-side and a client-side part. Tasks and results get distributed over clients as needed. It's actually pretty cool to see one node start a task and another node finish it. But one thing that my grid lacks is a data storage service. Until I add such a service (in a scalable way) I am stuck with a grid that can only handle tasks like finding prime numbers. But even from such a classic task, there is still a lot to be learned.

For example one of the problems we'll need to solve for a browser based grid is the fact that the nodes in the grid are not dedicated to being part of the grid. Whereas people that download SETI@home at least consciously decide to contribute their computer cycles to the project, for a browser based grid this decision is less explicit. Of course this is part of the beauty of a using the web for this grid: it becomes very easy for people to join the grid. But it also means that we can't do certain things. Like eat up all available CPU cycles...

So how do we find prime numbers without eating up too much CPU time? As you probably recall from school: a prime number is a number that can only be divided by 1 and by itself. So the simplest possible algorithm to determine if a given number is a prime is something like:


function IsPrimeNumber(number) {
for (var i=2; i < number-1; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}

As you can see this is quite a literal translation of the definition of primes we all learned. And although there are plenty of optimizations you can do to this algorithm, we'll stick to to this very simple version for now.

What happens if we execute this function on a node? It'll work fine for small numbers. But once the number goes beyond a certain threshold, the loop will start eating up quite some time. And since executing JavaScript in the browser is unrestricted but single-threaded, this means the script will eat up all CPU cycles for a noticeable amount of time. As I said before, that is something that I simply don't want to happen on this grid.

So we need to modify our algorithm to not eat up all CPU time. We could optimize it by for example skipping all even numbers above 2. But that would only double the maximum number we can check with this function before the user starts to notice. What we need is something that will make this function work without noticeable effect on the CPU for any number.

My approach to this has been to split the task into many sub-tasks. So instead of having one loop like in the version above, we split it into multiple loops that each run over a smaller range. Let's say we have the following helper function:

function IsDividableBySomethingInRange(number, start, end);

This function will return true if number can be divided by one of the numbers in the range [start, end>. With this helper function, we can rewrite our original IsPrimeNumber function to use ranges.

function IsPrimeNumber(number) {
var CHUNK_SIZE = 1000;
for (var i=0; i < number; i += CHUNK_SIZE) {
if (IsDividableBySomethingInRange(number, Math.max(i, 2), Math.min(i + CHUNK_SIZE, number-1)));
return false;
}
}
return true;
}

Now if we leave the algorithm like this, we are still executing the work in one go. To actually remove that problem we need to convert the IsDividableBySomethingInRange calls into sub-tasks, which can be executed on the grid separately. The IsPrimeNumber function/task then just has to wait until all its sub-tasks have completed.

The splitting of a task into sub-tasks that can be executed separately and independent of each other is a typical fork operation that I learned back in my college days. We would fork off some work to separate sub-threads, so it could be completed in parallel instead of executing each one in turn. Waiting for the sub-tasks is called a join operation. By creating a fork/join algorithm we're not just making task execution more deterministic, we're also improving parallelism by allowing the sub-tasks to run independently from each other.

So what we really wanted to create all along is a fork/join version of our IsPrimeNumber function/task.

Let's say that we have a fork operation that we can call to somehow fork off a function into a separate sub-task. And let's say that whenever such a sub-task is completed, it will call back into the original task with the result:

class IsPrimeNumber {
var number;
var result;
function IsPrimeNumber(number) {
this.number = number;
this.result = true;
}
function forkSubTasks() {
var CHUNK_SIZE = 1000;
for (var i=0; i < number; i += CHUNK_SIZE) {
fork IsDividableBySomethingInRange(number, Math.max(i, 2), Math.min(i + CHUNK_SIZE, number-1)));
}
}
function joinSubTask(subtask) {
if (subtask.result == true) {
this.result = false;
}
}
}

This is a grid-enabled fork/join version of our IsPrimeNumber task. When we execute this task with a very large number on a grid of nodes, the task will be forked into sub-tasks and each of those sub-tasks can be executed on any of the nodes. When a sub-task is completed its result can be joined back into the IsPrimeNumber, which will assure that the combined result is correct.

IsPrimeNumber(2137)
forkSubTasks
|
|--------->IsDividableBySomethingInRange(2137, 2, 1000)
| |
|------------------+-------------->IsDividableBySomethingInRange(2137, 1000, 2000)
| | |
|------------------+---------------------+---------------->IsDividableBySomethingInRange(2137, 2000, 2136)
| | |
joinSubTask | | |
| | | |
|<-----------------+ | |
| | |
|<---------------------------------------+ |
| |
|<---------------------------------------------------------------+
|
true<--------+

If you know a bit about Google's Map/Reduce algorithm (or the open-source Hadoop implementation of it) you will probably see the similarities between join and reduce.

There is still many things that we can improve here (not swamping the grid with all sub-tasks at once, keep track of the number of missing sub-tasks, etc). But essentially we now have a grid-enabled way of determining whether any given number is a prime.

Sunday, December 30, 2007

Grid computing - using web browsers

Grid computing is one of those areas that seems to have a magic appeal to software developers. There is something very attractive about taking some relatively simple computers and wielding their combined power to perform seemingly infinitely large computing tasks within reasonable times.


I've also always been attracted to grids. But as many developers, I too thought this type of power was not within reach for me. Only since Google started documenting the "cloud of commodity PCs" that power their vast computing power, does it suddenly seem quite feasible for even just "large" companies to have their own computing cloud.


But my problem remains the same. I don't work for Google, Yahoo or IBM and I'm not a large company myself. So I don't have access to a set of commodity PCs that I can combine into a grid. So for years I decided that I'd never get a chance to work on a grid, unless I'd start working for one of those big boys.

Recently I've been thinking about an alternate setup for a grid computer, more along the lines of the SETI@Home project and all its successors. Those programs all allow home PCs of users all over the world to take part in a giant computer network - a global grid in essence. So the people creating these programs get a lot of computing power, yet they don't have to manage the hardware. A powerful setup.

But such setups already exist. And they have one downside that keeps them from even more mainstream adoption: they require the user to install software to put their computer into the grid. And although the threshold isn't very high, it's still too high for many people. So a lot of potential computing power is not used, because the barrier of installing software is too high.

Now that got me thinking: is there an existing platform on modern PCs that we can just embed our own grid applications in? Preferably a platform that's been around for a few years, so all its quirks are known. And it would be nice if the platform comes with built-in internet connectivity.

Here's the idea that popped into my head: web browsers! They used to be nothing more than HTML viewers, but those days are long gone. Nowadays our browsers are hosting more and more complete applications, like GMail, PopFly and Yahoo Pipes. These applications prove that there is a lot of computing power in the web browser. Is it possible to use the web browsers that people have open on their PCs all the time and turn those into nodes in the grid?

It is a very simple concept: every browser that has a certain URL open is a node in the grid. For a computer to join the grid, they just surf to the URL. To leave the grid again, they navigate away from the URL. It doesn't get much easier than that, right? No software to install, just a page you have to visit. Put it in your favorites in the office, open it every morning when you boot your PC and that's one more node in the grid. From even my own limited reach, I know of at least 5 machines that I could "grid enable" in this way. Those are all PCs and Macs that are on for a large part of the day, just waiting for me or my family to use them. Or that's what they used to be... now I can't stop thinking about them as being nodes in my "web based grid".

If you're a software developer reading this, than your mind probably started wandering while reading the last few paragraphs. Is this possible? How would the nodes get their tasks? How would they report their results back? How would you manage the nodes in the grid? Where do you keep the data that is needed for/generated by the nodes? How do you handle XSS issues? Wouldn't the nodes quickly overload the server that manages them? The list of challenges is seemingly endless and definitely too much for me to deal with in one go.

All I know is that ever since this idea popped into my head, I can't stop thinking about it. And for every problem, I can see at least a few potential solutions. I have no idea whether they'll work or which one is best, but the only way to figure that out is to actually start building the platform.

Oh man... I really need to make this my 20% project. Or more likely... I really need a lot of people to make this their 20% project. Help?

Sunday, June 10, 2007

Incremental search using JavaScript

Aside from this blog, I am also the webmaster (and one of the contributors) on two photo blogs(one in English, the other in Dutch). I wrote the software for maintaining these photo blogs myself, because nothing at the time seemed to do exactly what I wanted. The upside of writing your own software is that it does exactly what I want. The downside is that if I want any new feature, I have to write it myself.

This weekend I added a simple incremental search feature to the administrative interface of the photo blogs. Nothing fancy, but just an easy way for the contributors to check for example when the last post on diaper cakes was or when we had the theme week on chocolate.

My solution is completely client-side using this JavaScript:

  • var TEXT_NODE = 3;
    var TIMER;
    var SKIP_ROW_COUNT = 2;
    var SEARCH_INPUT;

    function instrument(input, skipRows) {
    SEARCH_INPUT = input;

    if (skipRows) {
    SKIP_ROW_COUNT = skipRows;
    }

    // listen to changes to the input
    input.onkeyup = input.onchange = startTimer;
    }

    function startTimer() {
    // start (or re-start) the timer, only once it expires will we start the search
    if (TIMER) {
    clearTimeout(TIMER);
    }
    TIMER = setTimeout("search()", 500);
    }

    function search() {
    var term = SEARCH_INPUT.value.toLowerCase();
    var rows = document.getElementsByTagName("tr");
    // skip first few rows (optional author book, commands and header)
    var i;
    for (i = SKIP_ROW_COUNT; i < rows.length; i++) {
    var tr = rows[i];
    // hide row if it doesn't contain the search term
    tr.style.display = (term == "" || doesNodeContain(tr, term)) ? "" : "none";
    }
    }

    function doesNodeContain(node, term) {
    if (node.nodeType == TEXT_NODE && node.nodeValue.toLowerCase().indexOf(term) >= 0) return true;
    return true;
    }
    var child = node.firstChild;
    while (child) {
    if (doesNodeContain(child, term)) {
    return true;
    }
    child = child.nextSibling;
    }
    return false;
    }
As you can see it is pretty basic stuff. Set up some event handlers on the input, start a timer whenever the user enters some text and then do the search once the timeout expires. The search itself is done using some recursive DOM scanning. There's probably a cheaper way to do this and once I find that I'll update the script. But until then, this simple script will do just fine.

You hook this up in the HTML using:
  • <input onfocus="instrument(this, 2)" type="text">
The second argument to the instrument function is the number of rows from the top that the search should ignore. I tend to have some extra rows at the top that unfortunately don't all use th's, so this is the easiest way to exclude those from the search.

I know that putting inline JavaScript in the HTML is not very Web 2.0 and makes the site inaccessible. But since this is the administrative interface for the contributors and not the front end of the website, I think I can live with myself for not making it accessible.

Friday, March 23, 2007

iframe.onload doesn't fire for ActiveX controls

Last week I had a few very frustrating days with the web interface of a new application we're building. The web application is basically allowing you to navigate websites as they were at a given moment in time.

The web application is built up from some panels with additional information and a main iframe hosting the actual web page. You type the URL of the page you want to see and presto, there you have it. On the side we'll show you all the other versions of that page we have available. Clicking on one of those versions will bring it up in the iframe.

So far, so good. The problems started when allowing the user to click links in the page that is showing in the iframe. We use a mix of rewriting the HTML before it's shown and intercepting the requests on the server, so that following links actually takes you to the destination as it was at the time that you were looking at. It might sound a bit complex, but it feels a but like time traveling. Imagine the wayback machine, with links working historically.

To update the information in the local panels we hook the onload event of the iframe. And that's where the problems started. Because on some of our systems, the onload event doesn't seem to fire when we open a PDF. It seems to only happen on IE, but not consistently on all our IE systems. A workaround with periodically inspecting the iframe also doesn't work, because somehow we can't even get the URL for the PDFs. And before you ask: yes, the PDFs are served from the same domain as the rest of the page.

It's really frustrating, because when the onload doesn't fire it breaks our UI logic. And the workarounds we've had to do are not pretty and slow the UI responsiveness way more than we'd like.

I've done some searching to see whether other people also had this problem. But of all the questions being posted on iframes, this doesn't seem to be a common occurence. That's why I post it here. Has anyone had the same problem? And if so, what was your solution?