Jump to content
  • Advertisement
aptpatzer

Optimizing a scrolling view

Recommended Posts

I have an html5 canvas providing a view into a world with a bunch of points. The user can click and drag around to pan the view.

I'd like to know if my method here is horribly inefficient and could possibly be optimized another order of magnitude. It's currently a little laggy for me with a million points.

jsfiddle: https://jsfiddle.net/3oc1mnu6/2/

HTML:

<canvas id="myCanvas" width="960" height="540" style="border:1px solid #000000;"></canvas>

Javascript:

//world dimensions
var worldWidth = 4000;
var worldHeight = 3000;

//mouse down bool
var mouseDown = 0;

var canvas = document.getElementById("myCanvas");
var context = canvas.getContext("2d");

//point class
function point(x, y){
  this.x = x;
  this.y = y;
}

//some key points
var camera = new point(1000, 1000);
var cameraLocationWhenMouseClicked = new point();
var mouseDownLocation = new point();

//the mass of points
var numPoints = 1000000;
var points = [];

for (var i = 0; i < numPoints; i++){
  points.push(new point(Math.random() * worldWidth, Math.random() * worldHeight));
}

//mouse event handlers
canvas.addEventListener("mousedown", mouseDownEventHandler);
canvas.addEventListener("mousemove", mouseMoveEventHandler);
canvas.addEventListener("mouseup", mouseUpEventHandler);

//on mouse down
function mouseDownEventHandler(e){
  mouseDown = 1;

  //update mouseDownLocation
  mouseDownLocation.x = e.offsetX;
  mouseDownLocation.y = e.offsetY;

  //store where the camera was when mouse down occurred
  cameraLocationWhenMouseClicked.x = camera.x;
  cameraLocationWhenMouseClicked.y = camera.y;
}

//on mouse move
function mouseMoveEventHandler(e){
  //if mouse is down
  if (mouseDown == 1){
    //adjust camera location
    camera.x = cameraLocationWhenMouseClicked.x + (mouseDownLocation.x - e.offsetX);
    camera.y = cameraLocationWhenMouseClicked.y + (mouseDownLocation.y - e.offsetY);
  }
}

//on mouse up
function mouseUpEventHandler(){
  mouseDown = 0;
}

function drawScreen(){
  //draw canvas
  context.fillStyle = "white";
  context.fillRect(0, 0, canvas.width, canvas.height);

  //draw points
  context.fillStyle = "black";
  for (var i = 0; i < points.length; i++){
    //only draw if in view
    if((camera.x < points[i].x)&&(points[i].x < camera.x + canvas.width)&&(camera.y < points[i].y)&&(points[i].y < camera.y + canvas.height)){
      context.fillRect(points[i].x - camera.x, points[i].y - camera.y, 1, 1);
    }
  }
}

window.setInterval(drawScreen);

 

Share this post


Link to post
Share on other sites
Advertisement

You are currently looping through every point to see if it is visible, this could probably benefit from a space partition. For instance, instead of having, a single array with all the points spread over the entire area, you would have a series of smaller arrays representing smaller areas. You would then check which of these smaller areas is visible, and loop through their points if visible. Look into space partitions such as quadtree.

You could have a 2-d array. Where each element of the array is a series of points contained in area (x,y)-(x+w, y+h), where x and y are array indicies but also associated with locations in space. With this method you could easily find if an entire group of points is likely to be visible. Space Partitioning: method to make fewer spacial comparisons given the camera only looks at  a specific area of space. 

Edited by h8CplusplusGuru

Share this post


Link to post
Share on other sites
On 11/18/2017 at 10:14 AM, h8CplusplusGuru said:

You are currently looping through every point to see if it is visible, this could probably benefit from a space partition. For instance, instead of having, a single array with all the points spread over the entire area, you would have a series of smaller arrays representing smaller areas. You would then check which of these smaller areas is visible, and loop through their points if visible. Look into space partitions such as quadtree.

You could have a 2-d array. Where each element of the array is a series of points contained in area (x,y)-(x+w, y+h), where x and y are array indicies but also associated with locations in space. With this method you could easily find if an entire group of points is likely to be visible. Space Partitioning: method to make fewer spacial comparisons given the camera only looks at  a specific area of space. 

This immediately strikes me as feasible and very interesting. Thank you for the suggestion. It's definitely something I will try to implement. I have an idea involving a pair of binary searches (one per dimension)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!