# Good algorithm to generate pixels for thick line?

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?

• Why not just check during movement that a player is not crossing between the corners of two obstructing pixels? That is similar to the movement rules in most 2D top-down games (video-game or table-top). – Sean Middleditch Sep 13 '15 at 18:44
• Because such rule would cause other bugs - for one there's nothing wrong with giong parallel between 2 other lines no matter how close they are. Making the line thick simply fixes the problem without adding more vulnerable logic that would break later on. – Tomáš Zato Sep 13 '15 at 21:15
• That reasoning makes no sense to me. Adding the logic for diagonal movement does not "cause other bugs" with movement between parallel surfaces. Widening your lines, however, will have tons of otherwise unnecessary consequences on your game grid and movement. :) – Sean Middleditch Sep 13 '15 at 21:28
• So to help you with getting sense I have drawn this picture: i.stack.imgur.com/EyeNX.png As you can see on the second screen, several valid pixels would raise false positive error. Not mentioning the performance aspect - this check would need to be performed for every single pixel being "claimed". – Tomáš Zato Sep 14 '15 at 12:25
• With "thicker lines" that second case wouldn't be able to happen reliably, either. And the performance impact of the diagonal checks will be negligable; literally, they won't even show up on a profile of your game (and it's not like using a more complex line drawing algorithm would be better in that regard...) :) – Sean Middleditch Sep 14 '15 at 23:33

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

• But what would those tangents do? Should I fill the areas they define? If so, how to do that for non-rectangular areas? – Tomáš Zato Sep 13 '15 at 18:21
• Tried to add more pictures but I need more rep to do so :( – RobM Sep 14 '15 at 12:11
• So make triangles from points A,B,C and then B,C,D then C,D,E etc – RobM Sep 14 '15 at 12:11
• Oh wow, this is pretty smart. I'll start thinking how to implement it, thanks. – Tomáš Zato Sep 14 '15 at 12:26
• Note that this comes very close to remove the 'pixel' logic that you turned down in other answers. Still this answer seems to be a good approach, it enables you to do line intersection tests etc. For your game going a 'vector' way may benefit you in the long run. The analytic geometry could be derived from a bitmap where the pixels serve as point nodes in the geometry. Pixelmapping for games may create potential issues; for example what if a player/object goes faster than 1 pixel per frame? – Felsir Sep 14 '15 at 13:48

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.

• Nope. I am not even planning to use analytic geomethry for this - in future I want to add more obstructions, weird shapes and stuff... What I see on screen is no sampling, that's just whole bunch of rectangles that I generate based on gaming map. This all is actually specified by the very sentence you quoted. – Tomáš Zato Sep 13 '15 at 14:38

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!
...

• I disputed this idea with following image already: i.stack.imgur.com/EyeNX.png – Tomáš Zato Sep 14 '15 at 13:17
• sorry, missed that. Updated – dnk drone.vs.drones Sep 14 '15 at 13:33
• I get your point but this is still flawed - which is why I am not trying to solve this problem using algorithm but by changing the game map. Anyway, try to think about it, maybe you'll figure out what's the problem here until I get time to make another picture. – Tomáš Zato Sep 14 '15 at 13:36

If you store which line claimed which pixel, then you can differentiate for sure left and right cases of the picture http://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.