To tie together a few of my previous posts, I wanted to talk about the proof of concept I built in Node.js. I will come back and discuss the outstanding issues in a later post.
Given my preference for the Mandelbrot set as a prototype in client-side languages, I wondered how I could develop a Mandelbrot solution that used the server as little as possible, so I hit upon the idea of creating a zero-install grid computing solution, similar to SETI@Home, where every browser that logged on would be computing a small piece of the whole, and the job of the server would be to coordinate the clients, and maintain the shared state of the current progress.
I’m not affiliated with Numberphile, I’m just a fan, but for those of you who don’t know about the mathematics of the Mandelbrot Set, it’s worth having a look at this video to understand it.
The way my implementation works, in order to satisfy the map-reduce behaviour I was looking for, is as follows:
- Create a grid of points to represent each un-escaped pixel
- Note, the proof of concept used a fixed grid to ensure an upper bound on the number of points that the server needs to store.
- The proof of concept used a sparse grid of points here as I originally planned to do a flood-fill of the outer regions, but changed my mind and didn’t refactor.
- For each point, store the current iteration, value and whether it has stabilised (initially false). These points are indexed on the complex number co-ordinates rather than canvas co-ordinates.
- When a new client connects, open two connections. The first asks for the currently valid list of points to output to its own canvas, and the second ask for the next bit of work.
- The server picks an unescaped point at random, and sends it to the client, as well as sending the current list.
- When the client receives a point to work on, it performs up to 50 iterations on that point. If the point escapes, the client stops and reports the iteration that it escaped on, otherwise, it increments the iteration count by 50 and updates the z values to be the most recently computed for that point. It also renders that point to its own canvas
- The server receives the value, updates its cache, then sends the next point down to the client.
Of course, there’s a lot more to it than that, but I’ll talk about how I solved some of those issues in future posts.
For now, if you want to jump ahead, and check out the code yourself, grab Node.js (or a Cloud9 or Codio development environment) and grab the NMandelbrot Node.JS sample from Bitbucket.
If anyone wants to fork it to Github, please let me know and I’ll add a link to that here too.