• Create Account

### #ActualBrother Bob

Posted 23 September 2012 - 08:01 AM

the number of tiles is max(abs(x2-x1), abs(y2-y1)).

How does that work? Wont that just get the number of tiles in one of the two directions? (only the change in X or only the change in Y)?

Xanather.

Look at the picture you posted and count the pixels, and think of how moving one of the points one or two steps to the left or right affects the outcome. There are 10 red squares, and there are 10 pixels difference in the Y-direction. Moving, say, the top point one or two points to the left or to the right will just change how the 10 points are distrubuted along the X-axis. It's only when the end point is 11 pixels or more away from the start point in the X-direction that you have to add more points in the X-direction, but then the X-direction has become dominant and that is taken care of by the max() function.

Bresenham's algorithm as TrickyLogic linked to is a perfect example demonstrating this. Bresenham's works by looping over each discrete step in either the X or the Y direction, and calculates the other direction by error accumulation. It generates exactly as many pixels as the greatest distance along the either X or the Y direction.

### #1Brother Bob

Posted 23 September 2012 - 08:00 AM

the number of tiles is max(abs(x2-x1), abs(y2-y1)).

How does that work? Wont that just get the number of tiles in one of the two directions? (only the change in X or only the change in Y)?

Xanather.

Look at the picture you posted and count the pixels, and think of how moving one of the points one or two steps to the left or right affects the outcome. There are 10 red squares, and there are 10 pixels difference in the Y-direction. Moving, say, the top point one or two points to the left or to the right will just change how the 10 points are distrubuted along the X-axis. It's only until the point where the end point is 11 pixels or more away from the start point in the X-direction that you have to add more points in the X-direction, but then the X-direction has become dominant and that is taken care of by the max() function.

Bresenham's algorithm as TrickyLogic linked to is a perfect example demonstrating this. Bresenham's works by looping over each discrete step in either the X or the Y direction, and calculates the other direction by error accumulation. It generates exactly as many pixels as the greatest distance along the either X or the Y direction.

PARTNERS