jack: (Default)
[personal profile] jack
Assume we are drawing down and to the right again, and that our grid is numbered thusly:
 0 1 2 3 4
  1 # X #
   2 # # #
    3 # # #
The numbers along the top represent the x coordinates. The numbers along the left represent the y-coordinates. Notice that it's not symmetric any more. All the numbers down the left have coordinates x=0, but in real life, are further across. However, this does let us number each hex in a nice, easy, systematic way.

A hex down-and-to-the-right is offset by (+0,+1). A hex down-and-to-the-left is offset by (-1,+1). Fixing up this algorithm to work in any direction will be a bit more fiddly, and I won't bore you with it.

For now we'll assume that our line is from (0,0) to the right and down, and further right than it is down. Eg. from (0,0) to (2,1) or to (4,1).

On a rectangular grid, successive pixels followed a simple pattern: they were either to the right of the previous pixel, or diagonally to-the-right-and-down of the previous pixel. What does it look like here?

Eg. fill in hexes from 0 to X. These would be hex 0, hex 1, the # to the left of X, and X. Successive hexes are either to the right of the previous hex, or right-and-down. Except that unlike before, BOTH these next hexes would touch the previous one.

The change in coordinates for these successive hexes are (+1,+0) and (+0,+1).

When do we want to make them? Well, imagine sliding all our rows of hexes left so the left column lines up vertically. They don't tessellate any more, but they're easier to think about lines on. I won't try to imagine it, but lets just ignore the hexes and use the same algorithm from the rectangular grid to colour the (x,y) coordinates!

This tells us how to colour one hex in each "column". (Columns have are diagonally down and to the right eg. all hexes with x=1.) Will that do?

Nearly. The only problem is that it makes diagonal moves, eg. from (0,0) to (1,1), but in our coordinate system that jumped a hex. You need (0,1) or (1,0) to fill in the gap.

WHICH hex? Well, look at our diagonal line. At some point between the middle of the previous "column" and the middle of this "column" it crossed from one "row" of "boxes" to the next "row". If the cross-over was nearer the left "column", it spent most of the time in the lower row so colour the lower hex. If it was nearer the right "column", it spent most of the time in the higher row, so colour the "higher" hex.

If it was exactly in the middle, our notional line must pass exactly along the dividing line between two hexes. For lines of sight, we do something cool and freaky simont and I agreed on in the pub, but just consistently choosing one or the other would do.

That may not make any sense to anyone else without my diagrams, but I'm pleased to have worked it out. I'm not sure if it's isomorphic to something simpler.

Date: 2008-09-20 12:51 pm (UTC)
From: [identity profile] alextfish.livejournal.com
As my comment on your other post implies, I'm interested in line-of-sight algorithms. Would I be able to ask for a brief summary of what you and simont agrred in the pub?