Implementing Bresenham's line algorithm

Discussion and feedback on Construct 2

Post » Thu Jun 12, 2014 7:23 pm

I am trying to create objects in a line between two points. I am trying to wrap my head around Bresenham's line algorithm in order to implement it in C2 for this purpose. I am not interested in a plugin to do it for me, I am trying to learn something here. I can't seem to find a plain english explanation of what the algorithm is actually doing online; the articles always get muddied up in how it was developed, how it's implemented in such and such language, etc. I feel I can implement it into C2 myself if I can just understand the concept. Can anyone explain this to me?
Thanks.
B
11
S
4
G
1
Posts: 159
Reputation: 1,803

Post » Thu Jun 12, 2014 7:43 pm

Whats the point?
The only way to represent the line would be to create 1 pixel objects. That could easily go into the hundreds, if not thousands of instances..
If all you want is a line then stretching a tiled bg to the distance() between the two points, and setting the object to point at the second position, would be far easier, and less intensive.
Not to mention all the sub-pixel stuff you have to deal with......
Image ImageImage
B
169
S
50
G
169
Posts: 8,286
Reputation: 108,216

Post » Thu Jun 12, 2014 7:53 pm

It doesn't get much simpler than this:

<For each x>, Bresenham's algorithm chooses the integer y corresponding to the pixel center that is closest to the ideal (fractional) y for the same x; on successive columns y can remain the same or increase by 1.


Source: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
ImageImageImage
B
71
S
21
G
231
Posts: 3,691
Reputation: 129,358

Post » Thu Jun 12, 2014 11:55 pm

@Newt "I am trying to create objects in a line between two points." + "I am trying to learn something here." = point. Rephrase: I am trying to understand the algorithm, and using the platform of C2 to experiment with it. This isn't a game project. I am having a brain block, and trying to clear it up.

@blackhornet Yeah, I went to that site already. Didn't help. The quote states what the algorithm does, but not how it does it. I would like to understand it on a level where I could do it on graph paper, step by step. I am not sure how else to put it.
B
11
S
4
G
1
Posts: 159
Reputation: 1,803

Post » Fri Jun 13, 2014 12:07 am

Yttermayn,
<For each x>, Bresenham's algorithm chooses the integer y corresponding to the pixel center that is closest to the ideal (fractional) y for the same x; on successive columns y can remain the same or increase by 1.

This is all you need, just iterate thru every X position of the screen
B
42
S
17
G
17
Posts: 2,247
Reputation: 17,461

Post » Fri Jun 13, 2014 3:18 am

This book here has a chapter on it that explains it pretty well as I recall.
http://www.drdobbs.com/parallel/graphic ... /184404919

The idea basically is to find a y position for each x position. It can be done with the equation of a line.
Y=m*x+b

Bresenham's algo differs in that it does it with no divisions among other things.
I haven't looked at it in a while but the implementation details are a big part of it.
B
92
S
32
G
107
Posts: 5,274
Reputation: 69,959

Post » Sat Jun 14, 2014 4:20 pm

@R0J0hound Thank you. After reading the relevant chapter, I went back and looked at the wikipedia entry's pseudocode and it made much more sense to me. Sometimes it just takes explaining things in a different way, I guess. Thanks for your replies, folks!
B
11
S
4
G
1
Posts: 159
Reputation: 1,803


Return to Construct 2 General

Who is online

Users browsing this forum: No registered users and 30 guests