0
\$\begingroup\$

I had a question about how to do edge tracing for use in collision detection for a game - think 'Asteroids'. I couldn't frame the question clearly so I did some R&D. The question I had in mind was 'how can I detect the edges of non-geometric shapes in a way that is pragmatic, fast and simple'. The reading I did before I rolled up my sleeves seemed to be leading down the road of using a minimal bounding rectangle around whatever object is to be collision detected. I wanted more accuracy, and since my game will be using the HTML canvas....

I am posting this in case it is of use to other people and as an answer to my own question. I would be interested to know if this is a standard technique, which I am sure it must be, and if there are some standard ways to improve it.

The approach in this code is to copy the shape into a canvas, then grab the pixel array for the smallest bounding rectangle. The canvas pixel array is a continuous 1D array with slots 0,1,2,3 containing the R, G, B, and Alpha values for the pixel. So the array is 4 times the size of the w x h. That's not so important, but useful to know.

We traverse the array to run 4 line-scans scans, effectively running a finger along the canvas from left-right, top - bottom, right - left, bottom - top, looking for the edge pixels.

Say we are scanning left to right - we start on line 1 and inspect each pixels alpha value in turn. If the value is non-zero we know we have found a pixel on the boundary of the shape. We don't care about the details of the pixel colour or any pixels after this on line 1 so we move on to line 2 and repeat. If you do this left to right, right to left, top down and bottom up, the conclusion is a set of x,y points that represent a fair guess at the edges of the shape. It is not perfect as there is a 'shadow' effect as illustrated by the edge trace snippet (add square and star).

Negatives - clearly there could be a lot of pixels to scan, But on the positive side, you will only scan once, and you can store the results that you know are not going to change as part of your app data!

Consider an asteroids game - you could have 30 different asteroid shapes, well possibly really only 10 with the additional 20 being scaled versions of the 10. So you scan those and save the edge data. From there on, edge detection is a matter of rectangle comparison with some common sense techniques to avoid too much overhead.

Todo: For efficiency later the list of points needs to be sorted, and possibly collected into a tree structure, combined with a larger sector-grid and some code to identify which objects are in which sectors, and we need a process that works for when the objects are rotated.

The snippet lets you add some shapes to the left-hand canvas, and visualizes the edge trace on the right-hand side.

// add a stage
var s1 = new Konva.Stage({container: 'container', width: 800, height: 600});
var s2 = new Konva.Stage({container: 'container2', width: 800, height: 600});

// Add a layer and group to draw on
var l1 = new Konva.Layer({});
s1.add(l1);
var g1 = null;

// Add a display layer and group to draw on - only used to visualise what is going on
var l2 = new Konva.Layer({});
s2.add(l2);
var g2 = new Konva.Group({});

// this function is called from the buttons to throw some interesting shapes onto the canvas for tracing
var makeShape  = function(opts){

    var x = opts.x + opts.w;
    var y = opts.y + opts.w;

    // if the main group is not defined do it now.
    if (!g1){
      g1 = new Konva.Group({x: opts.x, y: opts.y, width: opts.w, height: opts.w});
      l1.add(g1);
    }

    // Draw the requested shape.
    switch (opts.type){

      case "circle":
        var c=new Konva.Circle({
              x: opts.x + opts.w, y: opts.y + opts.w,
              radius: opts.w/2,
              fill: 'white',
              stroke: 'black',
              strokeWidth: 4,
              listening: true
          });
          g1.add(c);      
          break;
        
      case "square":
        var r = new Konva.Rect({ x: opts.x, y: opts.y, width: opts.w, height: opts.w, stroke: 'black' });
        g1.add(r);        
        break;

      case "star":
        var star = new Konva.Star({
          x: opts.x + opts.w + 30, y: opts.y + opts.w,
          numPoints: 6,
          innerRadius: 40,
          outerRadius: 70,
          fill: 'yellow',
          stroke: 'black',
          strokeWidth: 4
        });

          // add the shape to the layer
          g1.add(star);
          break;
        
      case "blob":
        
        
        var blob = new Konva.Line({
            points: [23, 20, 23, 160, 70, 93, 150, 109, 290, 139, 270, 93],
            fill: '#00D2FF',
            stroke: 'black',
            strokeWidth: 5,
            closed : true,
            tension : 0.3
          });
        
        g1.add(blob);
        break;

        
      case 'rocket':
        var rocket = new Konva.Image({
        x: 50,
        y: 50,
        image: img,
        width: 106,
        height: 118
        });
        g1.add(rocket);
        break;        
    }
    l1.draw(); 
    // and lets draw it all 
    s1.draw()
}

// This is what this is all about !
function scanForEdges(){

  // get the imageData
  var c = l1.getCanvas();
  var ctx = c.getContext();
  // Now we have the inageData - this is a one-D array with a four-step sequence
  // where 1=R, 2=G, 3=B and 4=A. So positions 1-4 give RBBA values of pixel 1.
  // A lot of examples walk the entire array to flip colours, but we need to walk 
  // a line-scan to find the outer edge of the shape by looking for any of the A 
  // values not being zero. This is because A=0 is invisible 
  // and all other values ARE a visible pixel. We only need to scan left to right 
  // until the first hit, then right to left the same, then the top & bottom scans. As 
  // long as the rect we select is not overly gappy around the shape then it 
  // 'should' be quick.

  // Get the width and height of the box to scan,
  var gsz = g1.getClientRect();
  var x = 0, y = 0, w = gsz.x + gsz.width, h = gsz.y + gsz.height;

  // get the pixel data for that box
  var imgData = ctx.getImageData(x, y, w, h);
  var data = imgData.data;


 // console.log('h=' + h + ' w=' + w + ' data len=' + data.length);

  var pxWidth = w * 4, xStep = 1, yStep = 1; // steps > 1, like 3 or 7 can speed up the scan but they can miss edges of squares.

    // you can set these false to see the effect of each scan - all true for live.
  var doWEScan = true, doEWScan = true, doNSScan = true, doSNScan = true;
  var plotRects = []; // this is where we collect the boundary points

  if (doWEScan){ 
    // walk the Alpha pixels West to East.
    for (var y = 0; y < h; y = y + yStep){
      for (var x = 0; x < w; x = x  + xStep){
        pxNo = (y * pxWidth) + (x * 4) 
        if ( data[pxNo + 3] > 0){    
          xStep1 = xStep  
          plotRects.push({x:x, y: y, w: 4, h:4, pxNo: pxNo});
          break;
        }
      }
    }  
  }


  if (doEWScan){   
  // walk the Alpha pixels East to West.
    for (var y = 0; y < h; y = y + yStep){
      for (var x = w; x >=0; x = x  - xStep){
        pxNo = (y * pxWidth) + (x * 4) 
        if ( data[pxNo + 3] > 0){    
          plotRects.push({x: x, y: y, w: 4, h:4, pxNo: pxNo});
          break;
        }
      }
    }
  }

  if (doNSScan){ 
    // walk the pixels N to S.
    for (var x = 0; x < w; x = x  + xStep){
      for (var y = 0; y < h; y = y + yStep){
        pxNo = (y * pxWidth) + (x * 4) 
        if ( data[pxNo + 3] > 0){    
          plotRects.push({x: x, y: y, w: 4, h:4, pxNo: pxNo});
          break;
        }
      }
    }
  }


  if (doSNScan){ 
    // walk the pixels S to N.
    for (var x = 0; x < w; x = x  + xStep){
      for (var y = h; y >= 0; y = y - yStep){
        pxNo = (y * pxWidth) + (x * 4) 
        if ( data[pxNo + 3] > 0){    
          plotRects.push({x: x, y: y, w: 4, h:4, pxNo: pxNo});
          break;
        }
      }
    }
  }

  // So now we have the results stored in plotRects[] - we are going to visualise then on another canvas 
  // but in live use you would use this array for hit-detection processing.
  // clear the visualisation group & layer
  g2.destroyChildren();
  g2.destroy;
  s2.clear()

  // Addrect just...adds rects !
var addRect = function(x,y,w,h){
  w=1;h=1;  
  var r = new Konva.Rect({
    x: x, y:y, width: w, height: h, strokeWidth:0.1, stroke: 'red', fill: 'red'    
  });
  l2.add(g2)
  g2.add(r);  
}

var c2 = l2.getCanvas();
var ctx2 = c2.getContext();
ctx2.putImageData(imgData, 0, 0);
ctx2.drawImage(c2._canvas, 0, 0);

for (var i = 0; i < plotRects.length; i = i + 1){
  var r = plotRects[i];
  addRect(r.x, r.y, r.w, r.h)
}
l2.draw();

//console.log('Done - calculated ' + plotRects.length + ' pts')

  
}

// Events for the buttons
$('.addShape').click(function(e){
  
  var type = $(this).prop('id');
  
  makeShape({w:120, x: 4, y: 4, type: type});
  
  scanForEdges();
  
})

$('#reset').click(function(e){
  g1.destroyChildren();
  g1.destroy()
  g1=null;
  l1.clear();
  s1.clear();
})


// fluff to get the svg image into the canvas.
var svg = document.querySelector('svg');
var img = document.querySelector('img');
// get svg data
var xml = new XMLSerializer().serializeToString(svg);
// make it base64
var svg64 = btoa(xml);
var b64Start = 'data:image/svg+xml;base64,';
// prepend a "header"
var image64 = b64Start + svg64;

// set it as the source of the img element
img.src = image64;

setTimeout(function(){
  // something to get is started
  $('#rocket').trigger('click');
  },
  500
  )
p
{
  padding: 5px;
  
}
.container
{display: inline-block; 
width: 250px; 
height: 300px; 
background-color: transparent; 
overflow: scroll; 
border: 1px solid red;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

<script src="https://cdn.rawgit.com/konvajs/konva/1.6.5/konva.min.js"></script>
<div>
  <button id='square' class='addShape'>Add square</button>
  <button id='circle' class='addShape'>Add circle</button>
  <button id='star' class='addShape'>Add star</button>
  <button id='blob' class='addShape'>Add blob</button>
  <button id='rocket' class='addShape'>Add rocket ship</button>
  <button id='reset'>Reset</button>  
</div>

<div id='container' class='container'></div>
<div id='container2' class='container'></div>

<p>
  <span id='text'>Issue: Shadowing effect.</span>
</p>



<div style='display: none;'>
<img />
<svg  id='rocketship' version="1.1" id="Capa_1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px"
	 viewBox="0 0 309.133 309.133" style="enable-background:new 0 0 309.133 309.133;" xml:space="preserve" width='200' height='200'>
<g>
	<path d="M30.078,172.934c23.695-34.108,37.633-56.082,47.795-72.321c-39.053,3.454-76.486,52.048-76.486,52.048l25.777,25.776
		C27.912,176.531,28.867,174.68,30.078,172.934z"/>
	<path d="M130.723,281.997l25.76,25.759c0,0,48.592-37.43,52.047-76.482c-16.234,10.158-38.201,24.091-72.32,47.792
		C134.484,280.264,132.644,281.242,130.723,281.997z"/>
	<path d="M91.549,268.678c-4.422,1.787-8.768,3.686-13.299,5.2c-12.102,4.045-24.566,6.778-37.203,8.522
		c-5.297,0.731-10.643,1.351-15.998,1.757c0.051-0.661,0.1-1.323,0.156-1.983c1.105-12.876,3.064-25.685,6.229-38.223
		c1.525-6.051,3.471-11.933,5.56-17.807c1.299-3.652,2.92-7.147,4.555-10.642l-2.834-2.832c-6.303,4.234-11.785,9.584-16.437,15.637
		c-6.887,8.963-12.049,19.117-15.658,29.817c-3.877,11.489-6.189,23.657-6.549,35.787c-0.051,1.704-0.168,3.445,0.096,5.136
		c0.34,2.184,1.299,4.251,2.74,5.926c1.426,1.657,3.303,2.908,5.383,3.579c1.746,0.563,3.502,0.573,5.313,0.559
		c11.012-0.092,22.195-2.005,32.736-5.137c19.279-5.728,38.742-16.504,50.15-33.532l-2.758-2.756
		C93.008,268.026,92.283,268.359,91.549,268.678z"/>
	<path d="M306.004,3.149c0,0-0.002-0.001-0.004-0.003c-2.006-2.005-4.725-3.128-7.555-3.128c-0.07,0-0.141,0.001-0.211,0.002
		c-34.41,0.675-119.307,7.111-164.393,52.199c-20.467,20.467-27.119,31.121-41.699,54.469c-10.5,16.81-24.875,39.835-51.147,77.649
		c-2.951,4.25-2.438,10.003,1.221,13.66l68.928,68.929c2.068,2.069,4.807,3.133,7.564,3.133c2.119,0,4.248-0.628,6.096-1.911
		c37.828-26.278,60.844-40.65,77.648-51.146c23.346-14.579,34.002-21.233,54.473-41.702c45.166-45.168,51.557-130.009,52.205-164.39
		C309.187,8.007,308.057,5.205,306.004,3.149z M226.187,133.206c-13.877,13.876-36.373,13.876-50.25,0
		c-13.879-13.877-13.877-36.372,0.002-50.248c13.875-13.877,36.371-13.879,50.248-0.003
		C240.06,96.831,240.062,119.331,226.187,133.206z"/>
</g>
</svg>
</div>

\$\endgroup\$
  • 1
    \$\begingroup\$ If you want to post an answer to your own question, you should post it as an answer, not embedded inside the question itself. \$\endgroup\$ – DMGregory Feb 24 '18 at 12:40
  • 1
    \$\begingroup\$ Why don't you just start with a bounding rectangle to quickly eliminate most of the shapes? Then you can do more expensive edge detection on the one or two shapes that overlap your bounding rectangle. \$\endgroup\$ – Kyy13 Feb 25 '18 at 2:41
  • 1
    \$\begingroup\$ Also you only need to scan the area of the bounding boxes not the entire canvas. \$\endgroup\$ – Kyy13 Feb 25 '18 at 2:50
  • \$\begingroup\$ As you suggest, I see this as the deepest part of a sequence of overlap detection with the board broken into cells like a chess board, then for any objects in the same cell a bounding rectangle check and finally the most expensive edge intersection check based on the line-scanned edge matrix. I would do the edge tracing once at game start or even store and load as game data. \$\endgroup\$ – Vanquished Wombat Feb 25 '18 at 10:15
1
\$\begingroup\$

I am a hobby enthusiast and I made my 'clone' of 'Space Invaders'. Here is its Codepen link: GalactiX. I was thinking slightly different about sprite-sprite collision. I test all interactions between actors.

First step: those too far apart gets filtered out: distance between their center points being larger than preset constant (larger side of the biggest sprite in the game).

Second step: classic rectangle overlapping; if yes, then:

Third step: only overlapping parts of both sprites are checked for nontransparent pixels. If the nontransparent pixels are found on the same coordinate in both sprite, function immediately returns true.

All sprites I am using are trimmed (have no transparent lines around). So the collision is either quickly found, or at least the overlapping areas are fairly small.

Relevant method from game:

collision: function(actor1, actor2) {
    var X = Math.abs(actor1.x - actor2.x);
    var Y = Math.abs(actor1.y - actor2.y);
    if (Y >= INI.COLLISION_SAFE) return false;
    if (X >= INI.COLLISION_SAFE) return false;
    var w1 = parseInt(actor1.width / 2, 10);
    var w2 = parseInt(actor2.width / 2, 10);
    var h1 = parseInt(actor1.height / 2, 10);
    var h2 = parseInt(actor2.height / 2, 10);
    if ((X >= w1 + w2) || (Y >= h1 + h2)) return false; //no rectangle overlapping 

    var act1 = new Vector(actor1.x, actor1.y);
    var act2 = new Vector(actor2.x, actor2.y);
    var SQ1 = new Square(act1.x - w1, act1.y - h1, w1 * 2, h1 * 2);
    var SQ2 = new Square(act2.x - w2, act2.y - h2, w2 * 2, h2 * 2);

    var x = MAX(SQ1.x, SQ2.x);
    var y = MAX(SQ1.y, SQ2.y);
    var w = MIN(SQ1.x + SQ1.w - x, SQ2.x + SQ2.w - x); 
    var h = MIN(SQ1.y + SQ1.h - y, SQ2.y + SQ2.h - y); 

    var area = new Square(x, y, w, h);
    var area1 = new Square(
                area.x - SQ1.x, 
                area.y - SQ1.y,
                area.w,
                area.h
    );

var area2 = new Square(
  area.x - SQ2.x, 
  area.y - SQ2.y,
  area.w,
  area.h
);
    var CTX1 = LAYER.temp;
    var CTX2 = LAYER.temp2;
    ENGINE.draw("temp", 0, 0, SPRITE[actor1.name]);
    ENGINE.draw("temp2", 0, 0, SPRITE[actor2.name]);
    var data1 = CTX1.getImageData(area1.x, area1.y, area1.w, area1.h);
    var data2 = CTX2.getImageData(area2.x, area2.y, area2.w, area2.h);
    var DL = data1.data.length;
    var index;
    for (index = 3; index < DL; index += 4) {
        if (data1.data[index] > 0 && data2.data[index] > 0) return true;
    }
    return false;
},

Even with all sprite-sprite interaction testing, the game runs smoothly on current version of Chrome and Firefox.

\$\endgroup\$
  • \$\begingroup\$ Great game - I was there in the back of the record shop in my old home town, 12 years old. Happy days. Thanks for the code looks useful. \$\endgroup\$ – Vanquished Wombat Mar 1 '18 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.