Cool! I love it when the tools i need have already been built. I will check it out.
First I am adding a Next button to my test bed to iterate through the switch settings, to speed up manual review of the grid.
Thus spake pgeerkens:
Okay, maybe Reversed can be left out of this chain, but that is still
384 cases to be checked on.
I do not consider this to be a large number of tests. Something I’m
working on presently in my day job will have millions of tests (which
were produced by another program I wrote).
A few hundred test cases is something that’s easily handleable with JUnit’s
parameterized tests. For testing coordinate systems, each test amounts to
one line of code.
Here’s a first cut of how I think the CoordinateSystem interface should
look:
public interface CoordinateSystem {
/** Maps a point in the plane to the coordinate containing it. */
public toCoordinate(Point p);
/** Maps a coordinate to the point in the plane which is its center. */
public toPoint(Coordinate c);
}
We probably also need a CoordinateFormatter, so that we don’t have to
store alphabetic coordinates as text:
public interface CoordinateFormatter {
public String format(Coordinate c);
}
Here’s a simple implementation which prints standard numeric coordinates:
public class ZeroPaddedNumericCoordinateFormatter {
public String format(Coordinate c) {
return String.format(“%02d%02d”, c.row, c.col);
}
}
Or, more generally we could have a “basic” configurable one, which can
handle anything that printf format strings can:
public class GeneralCoordinateFormatter {
protected final String fstr;
public GeneralCoordinateFormater(String fstr) {
this.fstr = fstr;
}
public String format(Coordinate c) {
return String.format(fstr, c.row, c.col);
}
}
I haven’t specified what Coordinate should look like yet, mainly because
I have a worry about whether we will want any three-axis coordinate systems.
(one axis crosses each pair of parallel hexsides, i.e., the axes are offset
120 degrees from each other), but I suspect that there must be some. I have
this vague memory of some space-combat game I saw at a convention once using
a three-axis system, but I can’t recall what it was anymore.
It might even be that we want Coordinate to be in a canonical form, and
have the formatter do all the translation work, so that we can eliminate
all of the variation between different types of grids in the rest of the
code. It’s not too hard to convert two-axis coordinates to three-, so
maybe Coordinate can be a two-field data object. (Or, conversely, maybe
it would be easier to use three-axis coordinates internally, though that
third coordinate would be useless for square grids…) Hmm.
(BTW: I’ve spent quite a lot of time thinking about grids. See here, e.g.:
nomic.net/~uckelman/mkhexgrid/)
–
J.
I think 3-D should be a sub-class of 2-D; you don’t want the 2-D code cluttered with the extra baggage that 3-D needs.
More when I have had a chance to look through your comments in more detail.
Pieter
Thus spake pgeerkens:
I think 3-D should be a sub-class of 2-D; you don’t want the 2-D code
cluttered with the extra baggage that 3-D needs.
It’s not 3-D, it’s 2-D with a third, redundant axis.
See here:
www-cs-students.stanford.edu/~am … agon2.html
A three-axis coordinate system makes certian kinds of calculations,
such as point containment and walk distance, very simple.
–
J.
Thus spake pgeerkens:
[This message has been edited.]
Okay, maybe Reversed can be left out of this chain, but that is still
384 cases to be checked on.To be practical one would need an automated regression suite:
a) probably 6 different grids, to capture these:
____7) MaxRows odd/even
____8) Mox Columns odd/even
____9) MaxObliques odd/even (if oblique)
b) some means of efficiently selecting points to ensure coverage of
this:
____minimum of 4 points, to have odd & even rows and columns checked
c) a test engine to run through these 64 cases for each grid, for the
entire point set selected.
____1) Oblique/Standard
____2) H-Descending
____3) V-Descending
____4) Sideways
____5) Reversed
____6) Stagger (if Standard) or NW_SE (if oblique)
It occurred to me just now that there’s a general way to represent all of
these:
Any coordinate system for hex grids (or square grids, for that matter)
is determined completely by three variables:
-
the location in the plane of the center of (0,0)
-
the angle between a horizontal line passing through the center of (0,0)
and a line passing through the centers of (0,0) and (0,1) -
the distance between the centers of (0,0) and (0,1) (which is also the
same as the hex height)
This means that it should be possible to confine the various options to
a small section of the code.
–
J.
Very elegant. I will study further. I mis-understood your 3-D reference on first reading.
Thus spake Joel Uckelman:
It occurred to me just now that there’s a general way to represent all of
these:Any coordinate system for hex grids (or square grids, for that matter)
is determined completely by three variables:
the location in the plane of the center of (0,0)
the angle between a horizontal line passing through the center of (0,0)
and a line passing through the centers of (0,0) and (0,1)the distance between the centers of (0,0) and (0,1) (which is also the
same as the hex height)This means that it should be possible to confine the various options to
a small section of the code.
Eh, that’s not quite right, because it’s not enough to tell you which
direction the rows increase in.
This works, though:
- a vector from the center of (0,0) to the center of (0,1)
- a vector from the center of (0,0) to the center of (1,0)
The first one tells you in which direction the columns are increasing,
the second in which direction the rows are increasing. Either one will
tell you the hex size and how the grid is oriented in the plane. Together,
they tell you whether (0,0) is in a ‘high’ or a ‘low’ column (high if the
angle they make is 60 degrees, low if the angle is 120).
–
J.
Hold onto those thoughts, and I’ll see what I can have ready for later today.
You wouldn’t know I once was a math-physics whiz from the sluggish start I made on this material, but things are starting to come back to me. Once things start rolling they should go quite quicly.
Pieter
On Dec 16, 2010, at 5:31 AM, Joel Uckelman wrote:
Thus spake Joel Uckelman:
It occurred to me just now that there’s a general way to represent
all of
these:Any coordinate system for hex grids (or square grids, for that
matter)
is determined completely by three variables:
the location in the plane of the center of (0,0)
the angle between a horizontal line passing through the center
of (0,0)
and a line passing through the centers of (0,0) and (0,1)the distance between the centers of (0,0) and (0,1) (which is
also the
same as the hex height)This means that it should be possible to confine the various
options to
a small section of the code.Eh, that’s not quite right, because it’s not enough to tell you which
direction the rows increase in.This works, though:
- a vector from the center of (0,0) to the center of (0,1)
- a vector from the center of (0,0) to the center of (1,0)
The first one tells you in which direction the columns are increasing,
the second in which direction the rows are increasing. Either one will
tell you the hex size and how the grid is oriented in the plane.
Together,
they tell you whether (0,0) is in a ‘high’ or a ‘low’ column (high
if the
angle they make is 60 degrees, low if the angle is 120).
This still isn’t right.
The vectors work fine for the oblique grids.
What this doesn’t properly handle is the currently common staggered
grid.
You need additional information about the odd and even rows or
columns, depending on the hex grid orientation. That is because for
the staggered grid, the angle between 0,0 and 1,0 will be 30° above or
below horizontal but between 0,0 and 2,0 it will be perfectly
horizontal.
So to handle this one needs to have and odd or even offset to go with
what is essentially a right-angle coordinate system.
Thus spake Thomas Russ:
Eh, that’s not quite right, because it’s not enough to tell you which
direction the rows increase in.This works, though:
- a vector from the center of (0,0) to the center of (0,1)
- a vector from the center of (0,0) to the center of (1,0)
The first one tells you in which direction the columns are increasing,
the second in which direction the rows are increasing. Either one will
tell you the hex size and how the grid is oriented in the plane. =Together,
they tell you whether (0,0) is in a ‘high’ or a ‘low’ column (high =if the
angle they make is 60 degrees, low if the angle is 120).This still isn’t right.
The vectors work fine for the oblique grids.What this doesn’t properly handle is the currently common staggered =
grid.You need additional information about the odd and even rows or =
columns, depending on the hex grid orientation. That is because for =
the staggered grid, the angle between 0,0 and 1,0 will be 30=B0 above or =
below horizontal but between 0,0 and 2,0 it will be perfectly =
horizontal.
I agree with this last sentence, but this is the reason I would give for
why it works, not for why it fails. The vector from the center of (0,0)
to the center of (0,1) is locally vertical (i.e., vertical w/r/t the grid,
but not necessarily w/r/t the plane), so a line perpendicular to that which
passes through the center of (0,0) will be locally horizontal, and also
happens to pass through the center of (2,0). Looking at the angle between
this line and the line to the center of (1,0) is one way of determining
which way the grid is staggered.
Are we not talking abou the same thing here?
–
J.
Yes, I know, but the basic premise is that the oblique numbering is a more basic patern to work from , rather than our current way of going from regular to oblique.
Thus spake pgeerkens:
Yes, I know, but the basic premise is that the oblique numbering is a
more basic patern to work from , rather than our current way of going
from regular to oblique.
Would someone state which numbering they think is “regular” and which
“oblique”? I’m not sure anymore that we’re using the terms in the same
way.
–
J.
Regular is what you find on modern wargames today - as found on Squad Leader
etc… since. Oblique applies to old 60s era AH games such as Afrika Korps,
3R
-----Original Message-----
From: messages-bounces@vassalengine.org
[mailto:messages-bounces@vassalengine.org] On Behalf Of Joel Uckelman
Sent: Friday, December 17, 2010 3:02 AM
To: messages@vassalengine.org
Subject: Re: [messages] [Developers] Re: Oblique Hex-grid Numbering uploaded
Thus spake pgeerkens:
Yes, I know, but the basic premise is that the oblique numbering is a
more basic patern to work from , rather than our current way of going
from regular to oblique.
Would someone state which numbering they think is “regular” and which
“oblique”? I’m not sure anymore that we’re using the terms in the same
way.
–
J.
Thus spake “Tim McCarron”:
Regular is what you find on modern wargames today - as found on Squad Leader
etc… since. Oblique applies to old 60s era AH games such as Afrika Korps,
3R
So you’re saying that regular is this? (Hopefully the ASCII art is
readable for you.)
__
__/10
/00_/
_/11
/01_/
_/
All the old AH games I have are either in storage right now or don’t
have a coordinate system on their hex grids (The Longest Day. WTF? How
could you make a game that size and NOT have coordinates on the map?).
Can you show me what oblique is?
–
J.
On Dec 17, 2010, at 1:49 AM, Joel Uckelman wrote:
Thus spake “Tim McCarron”:
Regular is what you find on modern wargames today - as found on Squad Leader
etc… since. Oblique applies to old 60s era AH games such as Afrika Korps,
3RSo you’re saying that regular is this? (Hopefully the ASCII art is
readable for you.)
__
__/10
/00_/
_/11
/01_/
_/
Well, here comes more ASCII art. Hope everyone uses fixed width fonts.
You really need a slightly bigger example to see the difference.
The top item is the “modern” numbering convention which I like to call a “staggered” grid, since it tries to have a standard right-angle coordinate system where the axes are 90° apart. But since that doesn’t map to a hex grid, one column is a half hex higher than the other. The format is CCRR
/0101\ /0301\ /
/ _/ _/
\ /0201\ /0401
_/ _/
/0102\ /0302\ /
/ _/ _/
\ /0202\ /0402
_/ _/
/0103\ /0303\ /
/ _/ _/
The next item is something like a typical older AH numbering convention which we are calling an “oblique” grid, since the axes are 60° apart. It is called oblique because one of the coordinates runs down the hex grain at an oblique angle. These are the lettered coordinates in the diagram below. Unlike the row numbers in the example above, the letters follow a hex grain in a straight line rather than bouncing up and down while cutting across the grain. The format is RRCC, but the “rows” angle downward to the right.
____ ____
aa/aa01\ z/ z03\ y/
/ _/ _/
\ /aa02\ / z04\
_/ _/
bb/bb01\ /aa03\ /
/ _/ _/
\ /bb02\ /aa04\
_/ _/
cc/cc01\ /bb03\ /
/ _/ _/
\ /cc02\ /bb04\
_/ _/
dd/dd01\ /cc03\ /
/ _/ _/
\ /dd02\ /cc04\
_/ _/ \
That is why I suggested you needed to know the vector to the hex one column over and the hex two columns over as well. So you could tell if the row numbering was staggered or in a straight oblique line.
Thus spake Thomas Russ:
The next item is something like a typical older AH numbering convention whi=
ch we are calling an “oblique” grid, since the axes are 60=B0 apart. It is=
called oblique because one of the coordinates runs down the hex grain at a=
n oblique angle. These are the lettered coordinates in the diagram below. =
Unlike the row numbers in the example above, the letters follow a hex grai=
n in a straight line rather than bouncing up and down while cutting across =
the grain. The format is RRCC, but the “rows” angle downward to the right.
Ah, yes, I remember those now. Thanks.
You’re correct, the representation I proposed assumes that the axes are
at right angles, so it wouldn’t be possible to represent oblique
coordinates directly.
For alphanumeric coordinates, I was assuming that a CoordinateFormatter
would do the translation from the internal numeric form to the display
format; numeric oblique coordinates could be accomodated the same way.
This makes me think that a three-axis internal representation might
well be what we want. For the oblique case, the translation is just
a projection function—dropping the third coordinate gives you the
oblique representation.
–
J.
OK. Having found the two silly errors in my affine transformation, I am ready to move forward.
My thoughts are that a hex-grid should incorporate a ‘batural’ numbering, whihc would be an old-style oblique one beacues of its benefical properties. then the user-friendly grid numbering would be a decorated grid with decorations for each of h-descending, v-descending, rectangular (ie modern), staggered-up (instead of down if rectangular), nw_se (instead of ne_sw if oblique). Does this make sense. Then each decoration would transform the co-ordinates of the input point for operations usch as getRow(), etc, and/or transform the resulting indices before returning to its parent. The base grid would simply have a single affine transformation for the case of origin at upper left, scaled for the grid size and aspect ratio.
Does this seem sensible?
Pieter
An oblique numbering is chosen as the intrinsic grid numbering because the algorithms for ranging, target-visibility, etc. are very much simpler from this numbering scheme.
It is still a work in progress, but in pgeerkens … mapgrid\HexGridNumberingY(Test) you can see our new hex-grid numbering code under construction. I abandoned the decorator concept as there was too little content to each layer of decoration, in favor of two methods toWorldCoords(c) and toCanonCoords(c).
The numbering algorithm used is this one
http://playtechs.blogspot.com/2007/04/hex-grids.html
which I imagine we wish to archive as documentation.
The i + j + k = constant concept can easily be incorporated internally for use on canonical coordinates, with k calculated as required.
Comments and suggestions welcome.
Pieter