[MUD-Dev] Re: Hex-grid mapping

[Jon Leonard]

On Tue, Dec 01, 1998 at 07:51:24PM -0500, James Wilson wrote:
> On Tue, 01 Dec 1998, Jon Leonard wrote:
> >On Tue, Dec 01, 1998 at 02:42:18AM -0500, Matthew R. Sheahan wrote:
> >> i'm in the design phase for a project where i want to use hex-grid
> >> mapping, and this has led me to realize that i don't know any decent
> >> methodology at all for tracking coordinates on a hex-grid.  ideally
> >> i'd like something not very different from Cartesian coordinates, and
> >> which permits easy determination of what locations are adjacent to
> >> a given coordinate.  this seems like the kind of thing which has
> >> probably been solved to death, so i thought i'd ask around instead of
> >> reinventing the wheel.   does anyone have any suggestions, or resources
> >> to point me to?
> >
> >Treat it just like cartesian coordinates, except that instead of using
> >sqrt(x*x + y*y) for distance, use sqrt(x*x - x*y + y*y).
> >
> >That gives a coordinate grid that looks like this:
> >
> >                      /   \   /   \   /   \   /   \   /   \   /   \   
> >                    |  0,5  |  1,5  |  2,5  |  3,5  |  4,5  |  5,5  |
> >                  /   \   /   \   /   \   /   \   /   \   /   \   /
> >                |  0,4  |  1,4  |  2,4  |  3,4  |  4,4  |  5,4  |
> >              /   \   /   \   /   \   /   \   /   \   /   \   /
> >            |  0,3  |  1,3  |  2,3  |  3,3  |  4,3  |  5,3  |
> >          /   \   /   \   /   \   /   \   /   \   /   \   /
> >        |  0,2  |  1,2  |  2,2  |  3,2  |  4,2  |  5,2  |
> >      /   \   /   \   /   \   /   \   /   \   /   \   /
> >    |  0,1  |  1,1  |  2,1  |  3,1  |  4,1  |  5,1  |
> >  /   \   /   \   /   \   /   \   /   \   /   \   /
> >|  0,0  |  1,0  |  2,0  |  3,0  |  4,0  |  5,0  |
> >  \   /   \   /   \   /   \   /   \   /   \   /
> >
> 
> this isn't a hex grid. It's a warped square grid. A hex grid has the useful
> property that any cell has six neighbors, which is often a better fit for
> tactical simulations than the square grid's four-with-four-diagonals neigbors.
> For instance, diagonal motion makes a lot more sense in hexes than in squares
> (assuming one move equals the traversal of one border). 
> 
> You can't tweak your equation to give them six neigbors, so don't try. (The
> number of neighbors of each cell is a topological invariant, i.e. you can warp
> space in any smooth way and each square will still have
> four-with-four-diagonals neighbors.)

Would you have been happier if I'd drawn my hexes like this?

        / \   / \   / \   / \
       /   \ /   \ /   \ /   \
      | 0,2 | 1,2 | 2,2 | 3,2 |
      |     |     |     |     |
     / \   / \   / \   / \   /
    /   \ /   \ /   \ /   \ /
   | 0,1 | 1,1 | 2,1 | 3,1 |
   |     |     |     |     |
  / \   / \   / \   / \   /
 /   \ /   \ /   \ /   \ /
| 0,0 | 1,0 | 2,0 | 3,0 |
|     |     |     |     |
 \   / \   / \   / \   /
  \ /   \ /   \ /   \ /

Those are really hexagons...  And the six neighbors have the coordinate
deltas I specified.  The fact that they don't look pretty in ASCII graphics
says little about the math.

That they're best stored in memory as a two dimensional array doesn't change
how the geometry works.  Two of the "corner" diagonals are as adjacent as the
"sides", and the other two diagonals are farther away than with a square
geometry.

The underlying mathematics are that if you try to do coordinate geometry with
axes 60 degrees apart, the distance function changes to d=sqrt(x*x-x*y+y*y),
and the lattice points wind up being the centers of packed hexagons.

This is convenient for certain kinds of programming, such as Matthew's
original question.

Displaying this kind of map has a couple of challenges, like that the
screen x&y don't scale equally with the map x&y.  It's not too bad, though,
and my code to do this both runs correctly and looks right...

Why can't I do this, again?

Jon Leonard