Mitchell's Best Candidate Algorithm for Sprite Placement?

I was searching for a method to place a relatively small N number of (identical square) sprites within the scene via random seed, such that the sprites maintain a minimum distance from each other and have a more natural looking distribution.

This link is the nearest and clearest example of such I could find. (You can edit values and rerun.) In my case, a sprite would be centered at each dot (rather than dot drawn), and the "dotRadius" would that of a circle containing the sprite plus padding.

I was curious as to whether this would be a suitable solution for Construct 2 and how one might implement it. Below is the code from the above link:

/*

Inspiration: http://bl.ocks.org/mbostock/d7bf3bd67d00ed79695b

Amazingly, even with high numbers of dots and high levels of smoothing,
finding the ideal position for a new dot never takes takes longer than
a millisecond. I was sure the brute-force approach would lag and I'd 
have to implement a quadtree or something.

*/

(function (canvas) {
    'use strict';

    var ctx = canvas.getContext('2d'),
        cw = canvas.width,
        ch = canvas.height,
        twoPi = Math.PI * 2,
        dotRadius = 32,
        dotColor = '#0AA594',
        dotCount = 30,
        samples = 50, // candidate dots attempted, higher is better
        placedDots = [], // a dot is represented as [x, y]

        initialize = function () {
            var dotsDrawn = 0,
                interval = setInterval(function () {
                    // var elapsed = (new Date()).getTime();
                    placeNewDot();
                    // elapsed = (new Date()).getTime() - elapsed;
                    dotsDrawn++;
                    // console.log('Dot #' + dotsDrawn + ' drawn in ' + elapsed + 'ms.');
                    if (dotsDrawn === dotCount) clearInterval(interval);
                }, 20);
        },

        generateRandomPosition = function () {
            return [
            Math.round(Math.random() * cw),
            Math.round(Math.random() * ch)];
        },

        getDistanceToNearestDot = function (dot) {
            var shortest;
            for (var i = placedDots.length - 1; i >= 0; i--) {
                var distance = getDistance(placedDots[i], dot);
                if (!shortest || distance < shortest) shortest = distance;
            }
            return shortest;
        },

        getDistance = function (dot1, dot2) {
            var xDistance = Math.abs(dot1[0] - dot2[0]),
                yDistance = Math.abs(dot1[1] - dot2[1]),
                distance = Math.sqrt(Math.pow(xDistance, 2) + Math.pow(yDistance, 2));
            return Math.floor(distance);
        },

        generateBestDot = function () {
            var bestDot, bestDotDistance;
            for (var i = 0; i < samples; i++) {
                var candidateDot = generateRandomPosition(),
                    distance;
                if (!placedDots.length) return candidateDot;
                distance = getDistanceToNearestDot(candidateDot);
                if (!bestDot || distance > bestDotDistance) {
                    bestDot = candidateDot;
                    bestDotDistance = distance;
                }
            }
            return bestDot;
        },

        placeNewDot = function () {
            var dot = generateBestDot();
            placedDots.push(dot);
            drawDot(dot);
        },

        drawDot = function (dot) {
            ctx.fillStyle = dotColor;
            ctx.beginPath();
            ctx.arc(dot[0], dot[1], dotRadius, 0, twoPi);
            ctx.fill();
        };

    initialize();

}(document.getElementById('canvas')));[/code:2j133ne4]

You could use pick nearest with distance()

Create object at random(maxwidth), random(maxheight)

-While object.count is less than value.object max

->set ranx.value to random(maxwidth), rany.value to random(maxheight)

->object pick closest to ranx, rany

-->distance(object.x,object.y, ranx,rany)<value.mindistance

--->create object at ranx, rany

Here's one way to do it:

https://dl.dropboxusercontent.com/u/542 ... ibute.capx

Example 2 updated : based on r0j0's 200 repeat.

did a capx example of what you shown ... however is not picking distance is that what you need?

its basically spawning at a radius space for each row and cell in the width/height divided by 10 so if you have a 300 width height then its 30 rows at 10 radius each... and if a sprite is spawned in the same position as another one then the new one is destroyed.

edited:

seeing r0j0s example is much faster you should try that one depending how you understand it better.

on my example you need to check if sprite.count = 200 then stop spawning

Thanks for the quick replies.

Here's one way to do it:

https://dl.dropboxusercontent.com/u/542 ... ibute.capx

Sorry, I'm still a bit unfamiliar with events. Is the 200 repeat for drawing 200 sprites? I assume that's the case, but changing it to a smaller number had no visible effect. It's also still trying to draw new sprites after a number of seconds. (Just looking at it in debug mode. I may well be misunderstanding it though.)

I think in my case it may be more beneficial to create this sprite distribution in the editor (via a plugin, I assume), though on the fly creation also has application for me as well. (These 12-24 sprites I envision will serve as portals to other levels, so each will have unique properties.)

Btw, here (pdf) is another, related method described without code.

It's following what the code you posted does.

aka take a number of random points and find their distance to a closest other point. Finally just keep the closest of them all.

In the capx it just creates a bunch of sprites, and destroys all but one.

It's following what the code you posted does.

aka take a number of random points and find their distance to a closest other point. Finally just keep the closest of them all.

In the capx it just creates a bunch of sprites, and destroys all but one.

Sorry, but I'm not seeing that it does. In your example (viewing in IE), if I change 'Repeat 200' to 'Repeat 24', I'm still seeing ~200 objects, and if I further change the project window size to 1280, 960, I'm seeing over 800 dots which are still spawning after over a minute. This isn't a behavior I understand, expect or want.

The code I posted returns the furthest candidateDot of var "sample" = 50 randomly generated dots from the nearest placed dot 'control' (in placedDots [ ]). I'm of the opinion that building (and saving) that placedDots array first, then drawing/spawning from it lastly (or separately, later), might be a better approach than creating/destroying sprites.

FYI for anyone interested, an example of Bridson’s poisson-disc sampling method I linked to in last post. Supposedly more efficient and tightly-packed.

I'm imagining a function that returns an array of acceptable coordinates, given arguments:

var array = function mitchellBC(numDesiredCoordinates, kSamples, minDistance, canvassDimensions, canvassOffsets) [/code:oh0lkr4g]

in which canvassDimensions [x,y] and canvassOffsets [x,y] allow for the return of an array of coordinates within a defined space (rather than scene-wide- a bit more control).

I could probably write that function in javascript (since most of it is in my link), but I'm not sure how to integrate with event sheet using the SDK, and I don't know how to build the function using only the event sheet (which seems more confusing than just figuring out the javascript code, honestly- think I could better follow a hybrid approach to events).

A bridson function would also be nice, that I could compare

I made up an example for that paper since it looked cool growing from one location:

https://dl.dropboxusercontent.com/u/542 ... bute2.capx

That said it is not simpler than the first example. Which tries 200 times per frame to find a good spot. Also it can be made to stop if enough dots are made.

It always escalates to trig....

Course now I'm wondering what formula C2 uses for pick closest.

newt

It just calculates all the distances and picks the closest.

I imagine as a for each that might slow things down.

I'm just wondering if we should have an expression to get the closest value from a list.

Sort of like min(), or max()

closest(value(a,b,c,d....)) or something like that.

That way you wouldn't have to rely on distance(), or objects.

Of course I'm not sure how that would work with xy coordinates either.