Bressenham's line algorithm on rectangular grids

[jack]

Introduction

Suppose you want to draw a straight line using a grid of pixels. I say "suppose"; of course, almost all of my friends and acquaintances do so daily[1]. I'm now going to describe a classic method to get it straight in my mind. (Most techie friends likely know this already, and those who've done any graphics programming a lot more, but this is a necessary precursor to the sequel on hex grids.)

Part I

Suppose we divide the plane into 1x1 sqaures:

 0 1 2 3 4 5 6
 1 # # # # # #
 2 # # # # # X

Each number, dot, and X represent a 1x1 box, and we want to fill in some of the boxes to draw a line from (0,0) to X at (6,2). Eg. we might fill in 01 on the first row, 234 on the second row, and 56 on the last row. How can we calculate that deterministically?

One of the oldest tricks is referred to as Bresenham's. Don't worry about calculating it yet, just imagine each 1x1 box on the plane and wonder which ones you'd like to fill in. Lay a ruler at an angle from the centre of box (0,0) to the centre of box X and sketch that line. For now we'll assume the line is drawn further right than it is down, and assume we fill in one box in each column.

Which boxes should those be? Well, now it seems obvious. Look at the centre of the column. Where does our diagonal line cross the centre? Whichever box that's in, fill in that one. (AKA, if there were a pixel in the centre of each box, light up the one in each column that's vertically closest to the diagonal line.)

Aside

There's even a neat side effect. Pedantic people are probably asking themselves "Which box? What if it's on the edge between two boxes? Well, that was implicit in our original assumption. Imagine:

A # #
# # B

And draw a line from the centre of A to the centre of B. It passes right through the middle of the edge between the middle two boxes. We can stick to our "one in each column" rule, and colour the top one. Or the bottom one. (This will be represented in our algorithm by choosing between >= and >) It will just look a lot neater if we always choose the SAME one if we have to choose multiple times.

Alternatively, colour in both. That probably makes the line look wonky, though.

Part II

How do we calculate this? Well, fortunately (AKA, why this algorithm is well known), it's really easy. Let DX be the centre-to-centre distance horizontally, and DY the centre-to-centre distance vertically. Then the slope of the line is to move vertically DY/DX for each 1 we move horizontally.

Move across horizontally in steps of 1 box. Keep a running tally of how far vertically our diagonal line should have moved by the middle of that column -- since we know the desired slope, this is just incremented by DY/DX each time. When this offset is below the bottom of the first row, the next box should be coloured in the second row, etc.

But we're incrementing by DY/DX each time, and comparing to 1. We're dealing with integers, so it's a lot easier to instead increment by DY each time, and compare to DX. We don't care how many times, we can just measure when we've overshot. We assume we're moving further X than Y, so we know which coord to increment. And we're starting from the centre, so we want to start our offset from DX/2 rather than 0. (If DX was odd, multiply both DY and DX by 2.)

while (...) {
   x += 1; // Increment by one, next pixel draw one to the right of previous pixel
   offset += DY; // Increment current position of diagonal
   if (offset>DX) offset-=DX, // Reduce it so it always stays between 0 and DX (NB: DY<DX)
                  y += 1;     // Next pixel also on next row (diag of previous pixel)
   draw(x,y)
}

There's a number of small but fiddly details in making the algorithm work in any direction, and seeing when you are done. You can look them up on wikipedia if you need to implement it.

Aside

That's not the sum of my knowledge of drawing lines, but I'm no expert. There's lots more that could be said. And please correct any typos above.

This is probably most relevant for drawing things. AFAIK lines-of-sight, eg. in rougelike/nethack games or with roleplaying miniatures, which squares are visible from which, are a bit different. But I'm using this algorithm for that anyway, because it's simple and widely available.

Footnotes

[1] I'm referring to using a computer, which even if you don't implement the algorithm yourself, if you're using any program, draws lots and lots of lines on the screen. However, that's probably not actually true; most programs and operating systems deal with rectangles and bitmaps most of the time. But in principle, you're likely to want to represent a line by lighting up some pixels but not others.

References

cf. http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Comments

[alextfish.livejournal.com]

As it happens, about six months ago I did a lot of thinking about Bresenham's algorithm. I was after a version of line-of-sight for a tactical game, where I want to establish whether two units can see each other across a landscape that may have other items in. I'm allowing sight in 360 degrees for the purposes of this particular criterion, and crucially, I need the algorithm to be symmetric: if A can see B then B can also see A. (It's representing being able to set up a data link between units A and B.)

It'd also be very nice if the precise squares through which the line of sight passes don't change if you rotate the grid and everything on it by 90 or 180 degrees.

Between them, I believe these criteria exclude every line-drawing algorithm that chooses either < or <=. I think that any algorithm satisfying my criteria above will have to at least sometimes "colour in both". I'd love to hear other people's thoughts on this.

(An example: suppose the grid looks like

A . # . .
. . . . B

In this situation, a line drawn from A to B by a conventional algorithm like Bresenham will either hit the wall # or pass through the dot below it. Most versions of Bresenham give the same result from B to A as from A to B. However, if you rotate the grid 180 degrees to end up with

B . . . .
. . # . A

then most normal algorithms will now return the opposite result. And it seems very inelegant that if units A and B stand on a north-facing battlefield with a tree at the #, they can set up a data link, but if the battlefield's facing south then they can't.

[cartesiandaemon.livejournal.com]

Ah, that's interesting! As I say, I heard Bressenham wasn't necessarily the best for this, but don't know if there's any received wisdom other than that. (I don't know what, eg. rougelike games do. I did find someone who'd made their own rules for line-of-sight on a hex, but that included facing.)

I automatically assumed that there should be no hidden information in the sort of game I imagined, that what happens shouldn't depend on which way round the map is, or which order the objects are instantiated. I think most existing games, even really good ones, mostly gloss over this: if you're tracing the path of zombies to hero, it doesn't really matter what configuration the rear zombies end up in if they're obstructed.

When I'm dealing with zombies with two choices of which way to move, or a choice of which of two zombies to move into a particular square, when it really does have to be one or the other, I thought choosing clockwise/anticlockwise consistently was the best choice.

For line of sight, I think (but am not sure) that the algorithm gives a consistent choice of the spacing of the vertical steps, other than for the =/>= question when the diagonal passes through the centre of a side.

There's also the question of corners like

A .   and   A #   and  A #
# B         . B        # B 

For a line, the diagonal is ok, but for line-of-sight you probably need at least one of the diagonal squares to be empty.

In both cases you're faced with a square on either side of the line, and do you need either or both? One solution is to require both. If you're always traversing the line the same direction, you can choose always the clockwise or anticlockwise side of the line.

My suggestion was to keep a running tally of both sides, and mark the line-of-sight valid if EITHER all the >= squares OR all the > squares are clear.

Simon improved that by saying it should be able to switch over, eg.

A # . 
. . B . .
    . # C # .
        . . D

A would be able to see B (DOWN) and C (DOWN, UP) but not D (DOWN, UP, DOWN). He hypothesised that this would be equivalent to saying "Suppose each square is full, and you're looking from a small circle size epsilon in the centre of one square to a small circle of size epsilon in the centre of the other square. Is there an unblocked line." (It's a little different for hexes because of the jutty corners, but I think ok.)

This seemed to fit my intuition of what ought to be possible, though I haven't stress-tested the idea yet.

FWIW, I think DND miniatures say if you can trace a LoS from any corner of A to any corner of B, but I don't remember how that deals with corners.

It sounds like that might be applicable to your question too. Did you conclude anything at the time?

[alextfish.livejournal.com]

Roguelikes, from the reading I did when I was looking into this, don't care about making these things symmetrical: it's vitally important whether the player can see the monster, but they often gloss over whether the monster can see the player.

An extension suggested in the second post here, which deals with the corners suggestion, actually separately records whether each square's centre, left edge and bottom edge are visible (assuming you're looking up and to the right).

Yes, I've heard about miniatures saying "LOS from any pint on A's base to any point on B's base". Personally, I'd prefer it if my algorithm didn't have to cope with switching over once... and I don't think simon's hypothesised equivalence holds, either, assuming the #s are assumed to extend all the way into the corners of their squares.

For my problem, I concluded that I'd have to put up with the lines passing through multiple squares at a time:

A x x . .
. . x x B

I generate this line by an algorithm that I believe is equivalent to Bresenham-plus-reverse-Bresenham: I only step through the xsteps once, but I effectively keep two running counts, one that uses > and one that uses >=, and I think they start at floor(dx/2) and ceil(dx/2) as well.

[simont]

I don't think simon's hypothesised equivalence holds, either, assuming the #s are assumed to extend all the way into the corners of their squares

I agree that it doesn't work in this particular example with the square grid. When I proposed it on Thursday I was actually thinking of a different example on a hex grid (namely, two hexes such that the line between their centres went straight down the dividing lines between a few pairs of other hexes), and in that situation it does work :-)

[cartesiandaemon.livejournal.com]

Yeah, that's interesting. Your solution and algorithm sound sensible.

I don't think simon's hypothesised equivalence holds, either, assuming the #s are assumed to extend all the way into the corners of their squares.

You're right, I think it works in the case we were thinking about (directly along an edge in a hex grid), but I overgeneralised. I think the same might be relevant for corners in a square grid, though I'm not positive.

In fact, even on a hex grid, the straight line for a 4x1 step

A . O
 . O . B

passes through both "O" squares. But I think it's right for my purposes to treat it as the 1x1 step

A .
 . B

and require either of the squares to be free. It looks like you ought to be able to see :) But I don't know what rigorous condition, if any, it corresponds to :)

[cartesiandaemon.livejournal.com]

It was a bit of a faff trying to it though! I've no idea if I've got it right yet. The iterator class is initialised with beginning and ending coordinates, and has a ->tile pointer, and an ->alt pointer. Normally the ->alt pointer is zero and the ->tile pointer points to successive squares on the map. But when there's a choice, the ->tile pointer points consistently to one side of the line[1], and the ->alt pointer to the alternative tile on the other side.

The 'isvisiblefrom' function uses the iterator to walk the map from A to B, and at each choice, keeps a running total of whether each diagonal is still free, and if it has "crossed over" yet. If any non-choice tile is blocked it blocks any of the possibilities. And at the end, if any of the diagonals are still vis, the line marked ok.

[1] In theory "clockwise side", but currently just arbitrary.