Good algorithm to generate pixels for thick line?

Question

I am not really making some drawing as of picture manipulation but I use line function to calculate "claimed" pixels in my line race game (demo here):

The actual rendering is apart from the game algorithm which uses map of integers to remember which line "claimed" which pixel. I intentionally do the game logic based on pixels, not line intersections, because in future I want to add all kinds of shapes and analytic geometry would make that pain to implement. Instead, I'll use raster map and eventually make it look smooth on the rendering side.

The problem I have right now is that under special occasions, one line can cross another - and this is not an algorithm error but concept error. The problem happens because sometimes, the lines look like this:

As you see, there's no pixel collision - and this is not as unlikely as it seems. Making the line thicker would fix this and probably also make the game look better, but it has a flaw too - the line will now "claim" pixels it has already claimed last iteration. The current "thin" algorithm is basically just copied from wikipedia:

/**
 * Returns array of points that form line between x1,y1 and x2,y2. The array looks like this:
 *  [x,y,x,y,x,y...]
**/   
Line.straightPoints = function(x1,y1,x2,y2) {
  var result = [];
  // Define differences and error check
  var dx = Math.abs(x2 - x1);
  var dy = Math.abs(y2 - y1);
  var sx = (x1 < x2) ? 1 : -1;
  var sy = (y1 < y2) ? 1 : -1;
  var err = dx - dy;
  // First coordinates are not being added - it's assumed they were added in the last
  // iteration
  // Main loop
  while (!((x1 == x2) && (y1 == y2))) {
    var e2 = err << 1;
    if (e2 > -dy) {
      err -= dy;
      x1 += sx;
    }
    if (e2 < dx) {
      err += dx;
      y1 += sy;
    }
    result.push(x1);
    result.push(y1);
  }
  // Return the result
  return result;
}

But anyway, I need a trick to get this algorithm generate thicker line and I have no idea what to change. Should I generate circle of points for every point?

Answer 1

One way would be to generate tangents of a certain length and use them as coordinates to generate a triangle list.

So if the red dots are your points. You make a line to join the points ( in white ) and then generate a tangent to the white line ( in green ) of a defined length. You can then use the endpoints of the tangents to create a triangle list.

It does kind of depend on your original coordinate space. For the example here the red dots have distance between them.

If you label the endpoints of the tangents with letters A-F And so create triangles to join them up. So here, make a triangle using points A,B,C

Answer 2

The actual rendering is apart from the game algorithm which uses map of integers to remember which line "claimed" which pixel.

What you see on the screen is actually a sampling of the geometric line. The line equation is continuous contrary to the samples you see on the screen.

You need to perform an intersection ray/line segment test before sampling (before generating the points). once you perform a ray/line test, you can change the generation direction in case there is an between the ray and the line within specific distance. This way you can avoid intersecting lines.

Answer 3

If you add this logic to collision check ? (using color as ID)

...
   if (nextpixel.x != currentPixel.x && nextpixel.y != currentpixel.y)
        //next and cur pixel are diagonal
        if (screen[currentpixel.x,nextpixel.y].Color ==
           screen[nextpixel.x,currentpixel.y].Color )
               COLLISION!
...

Answer 4

If you store which line claimed which pixel, then you can differentiate for sure left and right cases of the picture https://i.stack.imgur.com/EyeNX.png

In the left example the diagonal pair of pixels belongs to the same line, while in the right - to different lines.