[Freeciv-Dev] (PR#7481) meta-ticket for hex maps

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=7481 >

A hex map is a map with hexagonal tiles.  These tiles can come in two forms:

   ____       /\
  /    \     /  \
/      \    |  |
\      /    |  |
  \____/     \  /
              \/

Which I will call hex and iso-hex.  We'll ignore iso-hex for now.

Whether hex tiles is something freeciv wants may be questionable.  I 
don't think there's much doubt that hex tiles make for good gameplay. 
But we don't really know how much work it will take.

When iso was implemented, it was done in two steps: first iso-view was 
implemented, then (years later) iso-maps became available.  This works 
because iso-view and ortho-view are more-or-less interchangable.  They 
can both be played on the same map.  But with hex tiles we will need 
both a hex-tiled map and a hex tileset to have anything that works.


I suspect that a hex-tiled map will be fairly easy.  The problem comes 
from adjacency relationships.  With current orthogonal and iso maps we 
have two different represtnations: native and cartesian coordinates. 
Native coordinates are chosen because they are compact; this works well 
for iteration and storage.  Cartesian coordinates (map coordinates) are 
chosen because they represent the local adjacency relationships 
accurately, so that operations like square_iterate and adjc_iterate are 
easy.  Of course we can convert between the two forms at will.

With hex maps the native representation is easy, but a cartesian 
representation is impossible using integer values.  The best we can do 
is probably a cartesian approximation with a few hacks to get things to 
work.  The natural representation is something like:

     X   X
   X   X
     X   X
   X   X
     X   X
   X   X
     X   X
   X   X

Which means the native representation (compressed) is probably (with 
adjacencies included):

   X-X-X-X
   |\|/|\|
   X-X-X-X
   |\|/|\|
   X-X-X-X
   |\|/|\|
   X-X-X-X

But this form makes adjacency relationships very hard.  Operations like 
DIRSTEP or real_map_distance become very hard.  For instance a vector of 
(1,0) is somethimes northeast and sometimes southeast, depending on the 
X value of the origin.


A cartesian approximation might therefore be

         X
        /|
     X-X-X
    /|/|/|
   X-X-X-X
   |/|/|/|
   X-X-X-X
   |/|/|/
   X-X-X
   |/
   X

which allows the use of DIRSTEP and an O(1) operation for 
real_map_distance (moving up-and-sideways takes 1 move, but 
down-and-sideways takes 2).  Invalid directions can be filtered out by 
the users of DIRSTEP (the biggest user is MAPSTEP).

In a hex map map_distance is equivalent to real_map_distance. 
sq_map_distance should be discarded since there's no good cartesian 
system; real_map_distance is a good approximation for this.

square_map_iterate is a bit tricky.  For one thing, the users of 
square_map_iterate probably wouldn't actually want a square on a hex map 
(imagine unit vision as an example).  What they really want is a 
"circle" that has constant real_map_distance radius (which on a hex-map 
is very close to a true circle).  So these users will have to be 
audited, square_map_iterate updated and possibly renamed.

Who knows what other problems will crop up in implementation.  Certainly 
the math will be a bit tricky (imagine converting between the above two 
representations).


Sounds fun, eh?  But probably implementing a hex view will be even more 
work.

The first obstacle is map_to_canvas_pos and canvas_to_map_pos.  We have 
to convert from one of the above forms into a canvas position.  And 
_much_ harder, we have to be able to convert back.  This is easy in the 
current code because the tiles are squares.  Even iso-tiles are squares 
after the transformation.  But with a hex tile you need to know not just 
tile NORMAL_TILE_WIDTH and NORMAL_TILE_HEIGHT but also the TILE_OFFSET, 
the *horizontal* amount by which the northeast and southeast tiles are 
offset from the current tile.  Note that the diagonal lines of the 
hexagon can slant at a 30 degree angle or a 60 degree angle.  Even if 
you fix this value to make a regular hexagon (60 degree slant) the 
problem isn't really easier.  It's not just a simple range test like it 
is with rectangles.  It's not immediately clear to me how the math works 
out.

Then we have the drawing code.  This probably won't actually be too 
hard, EXCEPT that the current drawing code is fragmented. 
update_map_canvas and update_map_canvas_visible will have to get new 
cases.  fill_tile_sprite_array and fill_tile_sprite_array_iso should be 
merged into one function; once that's done the tilespec.c code will 
probably only need a few special-cases for hex tiles.

Maybe the biggest task will be creating a hex tileset.  This could be 
done as a variant of trident (like isotrident was), created from 
scratch, or stolen from another game that uses hex tiles.


All of this is only speculation at this point.  But while I was thinking 
about it I wanted to get some of it down.  One thing that we would want 
to do is look at the code for other games that use hex maps, and see if 
their algorithms are good.

jason