Randomly generate objects in canvas without duplicate or overlap

Question

How do I generate objects on a map, without them occupying the same space or overlapping on a HTML5 Canvas?

X coordinate is randomly generated, to an extent. I thought checking inside the array to see if it's there already, and the next 20 values after that (to account for the width), with no luck.

var nrOfPlatforms = 14,
platforms = [],
platformWidth = 20,
platformHeight = 20;
var generatePlatforms = function(){
  var positiony = 0, type;
  for (var i = 0; i < nrOfPlatforms; i++) {
    type = ~~(Math.random()*5);
    if (type == 0) type = 1;
    else type = 0;
    var positionx = (Math.random() * 4000) + 500 - (points/100);
    var duplicatetest = 21;
    for (var d = 0; d < duplicatetest; d++) {
      var duplicate = $(jQuery.inArray((positionx + d), platforms));
      if (duplicate > 0) {
        var duplicateconfirmed = true;
      }
    }
    if (duplicateconfirmed) {
      var positionx = positionx + 20;
    }
    var duplicateconfirmed = false;
    platforms[i] = new Platform(positionx,positiony,type);
  }
}();

I originally made a cheat fix by having them generate in an area roughly 4000 big, decreasing the odds, but I want to increase the difficulty as the game progresses, by making them appear more together, to make it harder. But then they overlap.

In crude picture form, I want this

....[]....[].....[]..[]..[][]...

not this

......[]...[[]]...[[]]....[]....

I hope that makes sense.

For reference, here is the code before the array check and difficulty, just the cheap distance hack.

var nrOfPlatforms = 14,
platforms = [],
platformWidth = 20,
platformHeight = 20;
var generatePlatforms = function(){
  var position = 0, type;
  for (var i = 0; i < nrOfPlatforms; i++) {
    type = ~~(Math.random()*5);
    if (type == 0) type = 1;
    else type = 0;
    platforms[i] = new Platform((Math.random() * 4000) + 500,position,type);
  }
}();

EDIT 1

after some debugging, duplicate is returning as [object Object] instead of the index number, not sure why though

EDIT 2

the problem is the objects are in the array platforms, and x is in the array object, so how can I search inside again ? , that's why it was failing before. Thanks to firebug and console.log(platforms);

platforms = [Object { image=img,  x=1128,  y=260,  more...}, Object { image=img,  x=1640,  y=260,  more...} etc

Answer 1

You could implement a while loop that tries to insert an object and silently fails if it collides. Then add a counter and exit the while loop after a desired number of successful objects have been placed. If the objects are close together this loop might run longer so you might also want to give it a maximum life span. Or you could implement a 'is it even possible to place z objects on a map of x and y' to prevent it from running forever.

Here is an example of this (demo):

//Fill an array with 20x20 points at random locations without overlap
var platforms = [],
    platformSize = 20,
    platformWidth = 200,
    platformHeight = 200;

function generatePlatforms(k) {
  var placed = 0,
      maxAttempts = k*10;
  while(placed < k && maxAttempts > 0) {
    var x = Math.floor(Math.random()*platformWidth),
        y = Math.floor(Math.random()*platformHeight),
        available = true;
    for(var point in platforms) {
      if(Math.abs(point.x-x) < platformSize && Math.abs(point.y-y) < platformSize) {
        available = false;
        break;
      }
    }
    if(available) {
      platforms.push({
        x: x,
        y: y
      });
      placed += 1;
    }
    maxAttempts -= 1;
  }
}

generatePlatforms(14);
console.log(platforms);

Answer 2

Here's how you would implement a grid-snapped hash: http://jsfiddle.net/tqFuy/1/

var can = document.getElementById("can"),
    ctx = can.getContext('2d'),
    wid = can.width,
    hei = can.height,
    numPlatforms = 14,
    platWid = 20,
    platHei = 20,
    platforms = [],
    hash = {};

for(var i = 0; i < numPlatforms; i++){
  // get x/y values snapped to platform width/height increments
  var posX = Math.floor(Math.random()*(wid-platWid)/platWid)*platWid,
    posY = Math.floor(Math.random()*(hei-platHei)/platHei)*platHei;

  while (hash[posX + 'x' + posY]){
    posX = Math.floor(Math.random()*wid/platWid)*platWid;
    posY = Math.floor(Math.random()*hei/platHei)*platHei;
  }

  hash[posX + 'x' + posY] = 1; 
  platforms.push(new Platform(/* your arguments */));
}

Note that I'm concatenating the x and y values and using that as the hash key. This is to simplify the check, and is only a feasible solution because we are snapping the x/y coordinates to specific increments. The collision check would be more complicated if we weren't snapping.

For large sets (seems unlikely from your criteria), it'd probably be better to use an exclusion method: Generate an array of all possible positions, then for each "platform", pick an item from the array at random, then remove it from the array. This is similar to how you might go about shuffling a deck of cards.

Edit — One thing to note is that numPlatforms <= (wid*hei)/(platWid*platHei) must evaluate to true, otherwise the while loop will never end.