9

I'm looking for a fast algorithm that draws lines with a certain thickness. The lines don't have to be antialiased, speed is priority. Something fairly simple like this would suffice:

The use case is a Javascript game where worms leave trails. (HTML5 Canvas obviously draws lines, but getImageData() is very slow and so is collision detection)

I couldn't find anything that does this for the last 2.5 hours. And yes, I'm aware that there are almost identical questions on SO, quite a lot of them in fact, but not a single one has a working solution. The only solution I currently have is to draw circles along a Bresenham line, which is not very efficient.

Some code (pseudo-code, JS or at least a link to an article) would be great.

blade
  • 10,419
  • 7
  • 34
  • 36
  • 1
    Seems a bit rich to insist on being given code when you haven't done so yourself... – YXD Nov 16 '13 at 18:33
  • 2
    Line drawing is usually done using the Bresenham algorithm: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm. It should be rather straight forward to draw thick lines with this approach, too. – PMF Nov 16 '13 at 18:38
  • I think Canvas is the way to go. You can use DOM-elements and rotate them, but this will be way inferior especially performance-wise. Collision detection can be done with Canvas and JS-objects quite performant. What do you want to use `getImageData()` for? – Max Nov 16 '13 at 18:41
  • 1
    I didn't include any code as I'm only using Bresenham's algorithm - found here http://stackoverflow.com/a/4672319/388994 The problem is - it doesn't draw thick lines. At least I can't find any way to do so properly. – blade Nov 16 '13 at 18:41
  • 1
    @81403 just draw bigger squares (rectangles) instead of individual pixels. – Pointy Nov 16 '13 at 18:43
  • @Max getting just a single pixel from a ~HD canvas with getImageData() is very slow - see http://jsperf.com/getimagedata-complexity/2 . This would be the easiest way, but unfortunately is too slow. – blade Nov 16 '13 at 18:44
  • @81403 I'm aware of that. I just don't exactly see the reason you need it in the first place. How is the game built so far? – Max Nov 16 '13 at 18:47
  • @Max The game just draws rounded line for each worm into canvas that persists throughout one match. That works great until you're dealing with collisions - get one pixel ahead of each worm and 1 on both sides. With 8 players being maximum, this makes 24 reads.That's why I wanted to make an invisible array where I would manually draw the lines and get collisions from there. – blade Nov 16 '13 at 18:52

1 Answers1

13

http://members.chello.at/~easyfilter/bresenham.html

check at the bottom. It is an anti-aliased line, but should be easy enough to mod to non-anti-aliasing.

PlugTrade
  • 742
  • 10
  • 18