A million interactive circles

[danpaulsmith]

Hi, I'm new to game development, but have been visualising data for a while (SVG & HTML as opposed to Canvas & graphics).

 

I'm trying to make a universe map of up to a million interactive circles and I've narrowed down my approach to using 2D WebGL

 

- PixiJS and Phaser interest me due to their interaction and optimisation features.

- The circles are generated dynamically on the fly, and are different colours and different sizes.

- I've found that faster rendering = less interaction & slow rendering = high interaction.

- Drawing a million circles seems to be too expensive as opposed to using images, but zooming on textures causes pixelation (any nifty ways of allowing scaling of a million sprites?)

 

Drawing circles using primitives seems too expensive.

 

I've tried using cached SVG circles, canvg'ing them onto a canvas, generating textures from them and adding them as sprites. Performance is good, but they become pixelated as they are scaled. Used code from here: http://bl.ocks.org/pjanik/5238326

 

Spritebatches look good regarding performance, but they sacrifice all interaction unless I used coordinate mapping I guess?

 

Scaling a DisplayObjectContainer to scale all circles inside it works, but their co-ordinates need to change with the scale level too. Iterating over 1 million circles and updating their co-ordinates and scale is too slow.

 

Aiming for:

- circles of varied colours and sizes

- fluid scaling of the circles, as opposed to zoom "levels"

- clipping, so if the stage contains 10 circles, we don't need to render the other 999,990.

- hovering and clicking

 

What makes me think this is possible is this demo:

http://www.html5rocks.com/en/tutorials/webgl/million_letters/million_letters.html

 

Does anyone here have an opinion of a route I should go down and what combination of techniques I should be looking to use? Sprites, textures, shaders, buffers are all new to me so I don't know if any of them can help me solve this problem.

 

I've contemplated a tile server serving pre-rendered images, but like I said, these circles are created on the fly, and you can't interact them as images.

 

Thanks

Dan

[rich]

You could never actually display 1 million circles at once anyway, so the real question becomes: How many do you need to display simultaneously?

[Deban]

-Circles of varied size.

 

If you don't have unlimited zoom:

One way is to use a circle of the maximum possible size at the maximum possible zoom and then scale it down.

Another is to have circles of different sizes (in a png) and and use the one that need the less scaling. This way you will have minimum difference when scaled (up or down).

Or use vectors. http://www.goodboydigital.com/pixijs/examples/13/

 

-Circles of varied colours.

For the colour this will probably be useful: http://www.goodboydigital.com/pixijs/examples/17/

If you want to colour the outline, use a different sprite (one for the inner colour and one for the border) and put both inside a container (DisplayObjectContainer in Pixi) that way you only move your container.

 

To learn about graphics you can use the examples from Pixi: http://www.pixijs.com/examples/

It goes from basic to advance.

 

-Fluid scaling.

There are two types of graphics: vectors and raster (pixels, pngs).

Vectors is what you want, they can be scaled however you want and remain perfect, but the performance is not really that good. For a vector the computer has to process all the points in real time, per frame. With 10 circles it can be done, it's possible. But I don't think you can do something like 1.000.

Raster graphics are a lot faster (in Pixi you can use approximately 170.000 sprites) but are really bad at scaling. Commonly raster graphics are used and different zoom levels are hacked to look like a better scaling. This is having an image for 0.25 size, another for 0.5, 1, 2 4 and 8 for example. This images are done in you normal graphic editor and are pre-render, so you can edit them as you like. Then you use the image that is closer and will have the less distortion when scaled.

 

-Clicking.

This is pretty easy: http://www.goodboydigital.com/pixijs/examples/6/

For better performance you can take away the interactivity when the circle is clipped.

 

-Hovering.

I don't know if you want to hover with the mouse or the keyboard.

For the mouse: use the functions for mouse down and mouse up. When the mouse is down hovering = true. When it's up hovering = false; And then you can calculate the speed of hovering by distance moved.

This is a good example: http://www.goodboydigital.com/pixijs/examples/8/

For the keyboard: it's almost the same, when keydown you say that key is down, when it's up you do down = false for that key. Then if a key is down you can set the speed in the direction of that key, and even an acceleration while it's still down. There is no example of this so here you go:

window.addEventListener('keydown', onKeyDown, false);window.addEventListener('keyup', onKeyUp, false);

When you have the movement speed. Move your "camera" with the speed. With no clipping that would be having all inside one container and moving that container, with clipping it's a different story.

 

 

Now your biggest problem is the logic part, knowing if something is inside or outside of screen and moving 1 million circles at real time.

 

I put them together because... well, they are pretty tight together. You clip a circle if it's outside and it moves outside when it moves.

 

The obvious way is to look all circles and if they are outside your boundaries hide their image (image.visible = false;).

But of course you need to look all the 1m circles.

 

function MoveCircle() {    this.posX += this.speedX;    this.posY += this.speedY;        if(this.posX < lowerBoundaryX || this.posX > upperBoundaryX ||        this.posY < lowerBoundaryY || this.posY > upperBoundaryY) {                if(this.image.visible) this.image.visible = false;            } else {        if(!this.image.visible) this.image.visible = true;    }}

 

 

A better but really more complex way is doing separation of your space. A grid is the most common one and simple one. One circle can be in one cell at a time, and the cell is bigger than the maximum circle.

Then if a circle moves outside of you boundaries you clip it.

 

The grid would be a 2 dimensional arrays, or an array that contains inside another array. Each cell would be an object (to contain different circles and properties).

 

The code in circles remain almost the same, the real difference is that you update your circles based in the distances that they have to your camera.

var gridWidth = 100;var gridHeight = 100;var maximumRadius = 20;var maximumSpeed = 40;var cellSize = 50;var currentTopLeftCell = {x: 0, y: 0};var currentBottomRighttCell = {x: 0, y: 0};var borderCellsThickness = 5; //Around your camera is a border made of cells, this represents how much cells you want that border to befunction Cell() {    this.listOfCircles = [];        this.framesToSkip = 0;        this.framesSkiped = 0;}function GameLoop() {    HandleInput();    MoveCamera();    for (var x = 0; x < gridWidth; x++) {        for (var y = 0; y < gridHeight; y++) {                        var cell = grid[x][y];                        if(cell.framesSkiped === cell.framesToSkip) {                cell.framesSkiped = 0;                var list = cell.listOfCircles;                for (var i = 0; i < list.length; i++) {                    list[i].update(cell.framesSkiped);                }            } else {                cell.framesSkiped++;            }        }    }}

 

The framesToSkip can be calculated inside the GameLoop or inside the panning / hovering function. It depends in what happens more often, if the camera is moved once in a while it's better to be in the panning function, if the camera is mover a lot it's better in the GameLoop (travel the grid only once).

 

The code will be something like this:

function UpdateCellsDistance() {    for (var x = 0; x < gridWidth; x++) {        for (var y = 0; y < gridHeight; y++) {            var cell = grid[x][y];            var distanceX;            if (x < currentTopLeftCell.x) {                distanceX = (currentTopLeftCell.x - borderCellsThickness) - x;            } else {                distanceX = x - (currentBottomRightCell.x + borderCellsThickness);            }            if (distanceX < 0) distanceX = 0;            var distanceY;            if (y < currentTopLeftCell.y) {                distanceY = (currentTopLeftCell.y - borderCellsThickness) - y;            } else {                distanceY = y - (currentBottomRightCell.y + borderCellsThickness);            }            if (distanceY < 0) distanceY = 0;            var cellsDistance = Math.sqrt(distanceX * distanceX + distanceY * distanceY);            cell.framesToSkip = Math.floor(cellsDistance * cellSize / maximumSpeed);        }    }}

 

It calculate the distance of the current cell to the closest point of your camera, if it's inside the camera or it's borders there is no distance. Then it uses that distance to see how many frames it will take to a circle in that cell to arrive to the camera at maximum speed.

That is how it's determined how often it should be updated, basically it's updated only if it could enter the camera boundaries.

 

 

The code is a mess, is just to give you an idea. I don't even know if it works.

 

 

There are a lot more optimizations that could be done, but I think that the update (and clipping) of circles was the main bottle neck.

 

Good luck.