Mitchell's Best Candidate Algorithm for Sprite Placement?

Get help using Construct 2

Post » Thu May 26, 2016 4:17 pm

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:
Code: Select all
/*

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')));
B
7
S
1
G
1
Posts: 9
Reputation: 560

Post » Thu May 26, 2016 5:40 pm

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
Image ImageImage
B
170
S
50
G
179
Posts: 8,379
Reputation: 113,427

Post » Thu May 26, 2016 5:43 pm

B
94
S
33
G
113
Posts: 5,356
Reputation: 73,273

Post » Thu May 26, 2016 6:09 pm

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
B
78
S
23
G
69
Posts: 1,353
Reputation: 44,005

Post » Thu May 26, 2016 11:37 pm

Thanks for the quick replies.

R0J0hound wrote: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.
B
7
S
1
G
1
Posts: 9
Reputation: 560

Post » Fri May 27, 2016 3:20 am

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.
B
94
S
33
G
113
Posts: 5,356
Reputation: 73,273

Post » Fri May 27, 2016 2:44 pm

R0J0hound wrote: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.
B
7
S
1
G
1
Posts: 9
Reputation: 560

Post » Fri May 27, 2016 3:40 pm

I'm imagining a function that returns an array of acceptable coordinates, given arguments:
Code: Select all
var array = function mitchellBC(numDesiredCoordinates, kSamples, minDistance, canvassDimensions, canvassOffsets)


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
B
7
S
1
G
1
Posts: 9
Reputation: 560

Post » Fri May 27, 2016 7:56 pm

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.
B
94
S
33
G
113
Posts: 5,356
Reputation: 73,273

Post » Fri May 27, 2016 8:07 pm

It always escalates to trig....

Course now I'm wondering what formula C2 uses for pick closest.
Image ImageImage
B
170
S
50
G
179
Posts: 8,379
Reputation: 113,427

Next

Return to How do I....?

Who is online

Users browsing this forum: brunopalermo, Google [Bot], Yahoo [Bot] and 65 guests