# Mitchell's Best Candidate Algorithm for Sprite Placement?

Get help using Construct 2

### » 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/d7bf3bd67d00ed79695bAmazingly, even with high numbers of dots and high levels of smoothing,finding the ideal position for a new dot never takes takes longer thana 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

### » 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
B
178
S
50
G
206
Posts: 8,686
Reputation: 127,715

### » Thu May 26, 2016 5:43 pm

B
100
S
38
G
134
Posts: 5,556
Reputation: 85,325

### » 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
86
S
26
G
75
Posts: 1,440
Reputation: 47,810

### » 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

### » 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
100
S
38
G
134
Posts: 5,556
Reputation: 85,325

### » 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

### » 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

### » 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
100
S
38
G
134
Posts: 5,556
Reputation: 85,325

### » Fri May 27, 2016 8:07 pm

It always escalates to trig....

Course now I'm wondering what formula C2 uses for pick closest.
B
178
S
50
G
206
Posts: 8,686
Reputation: 127,715

Next