Oblique Hex-grid Numbering uploaded

Joel,

I agree with everything you’ve said here and much of it carries over from C.

But it makes me wonder, does the Java compiler optimise all this anyway?

  • M

On 15 December 2010 11:25, Joel Uckelman uckelman@nomic.net wrote:

Thus spake pgeerkens:

OK That should have resolved it. The little black star beside my folders
has disappeared now. :wink:

Some initial comments on your code:

  1. Don’t use

“” + foo

to convert foo to a String. Use String.valueOf(), it’s more efficient.

  1. Don’t use ‘new Boolean()’, ever. There are only two possible Boolean
    values, and instances of them already exist; creating more only makes
    more work for the garbage collector. If you want to get a Boolean from
    a String, use Boolean.valueOf().

  2. Use prefix ++ and – unless you actually need the values returned
    first.

  3. Any variable which you’re not going to reassign should be final.

I’ll try to make a more thorough review soon.

Also, there is a comprehensive test bed included in the module for the
use of anyone who wants to try it out. The old AH games all need oblique
numbering.

Tests belong under the test/ hierarchy. (Note that this is not yet observed
everywhere—there are still some tests floating around under src/, which
still need to be moved.)


J.

Thus spake Michael Kiefte:

Joel,

I agree with everything you’ve said here and much of it carries over from C.

But it makes me wonder, does the Java compiler optimise all this anyway?

‘new Boolean’ it definitely doesn’t optimize away. (The fact that there’s
even a public ctor for Boolean is a bug, in my opinion.)

I believe String conversion using “” + ends up happening via a StringBuilder,
while something more efficient can happen if you use String.valueOf().


J.

Yes, the extent of optimizations is limited by the fact that only partial compilation is occurring, and run-time binding must be allowed for.

Also, the more completely the programmer describes and constrains the solution, the less likely it is that erros occur later.

It might be worth knowing that the classes for Oblique Hex grid numbering had already been written as custom class imports, they just had not been included with standard Vassal for whatever reason…

An interesting exercise might be to compare these already written classes with what you’ve come up with for fun and giggles. The two classes, HexGridNumbering.java and ObliqueHexGridNumbering.java can be found in the VQSL-src/trunk/afk directory in the repository

Yes, I actually started from Brent’s implementation of ObliqueHexGridNumbering in the Afrika Korps module. However his approach was the more practical one of tackling the multiple scenarios singly, as needed for each game, and Waterloo needed settings not available in the Afrika Korps implementation. Then I discovered some subtle bugs and short-cuts in the HexGridNumbering, followed by the inability to auto-load from the Editor, and with the goal of learning quickly more about both Java and VASSAL I accepted the challenge of producing a single class that implements every hex-grid numbering known to man (any Vulcans out there?). While I do not claim to have fully succeeded, the work is good and I know a lot more Java and VASSAL now.

Pieter

I’ve run out of time this evening to finish reviewing your patch, unfortunately. Your code looks ok, on the whole, but what this has reminded me of is what an awful mess the existing grid code is generally. We had a discussion about this a few months ago:

https://forum.vassalengine.org/t/adc2-to-vassal-coversion/2635/1

Adding more grid code without refactoring sends us further down the rabbit hole. I think a large part of the difficulties you had in extending HexGridNumbering stem from it’s kitchen-sink design. This is one of those places where it would be relatively easy to disentangle all of the parts so that everything is coded to an interface and each class does one thing, and also write unit tests for them. Would you be interested in doing this if I helped you get started?

When you flatter me like that, how can I say no. ;-)

Yes, I believe you are correct, and I could spend some time to at least get it properly started.

Pieter

For Hex-Grid-Numbering, one issue is the staggering number of scenarios to be be verified on every code change. The independent switches are these:

  1. Oblique/Standard
  2. H-Descending
  3. V-Descending
  4. Sideways
  5. Reversed
  6. Stagger (if Standard) or NW_SE (if oblique)
  7. MaxRows odd/even
  8. Mox Columns odd/even
  9. MaxObliques odd/even (if oblique)

Then for each test case you need to check a minimum of 4 points, to have odd & even rows and columns checked.

By my count this makes for (128 + 64) * 4 = 768 opportunites on evey code change to break an existing module.

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)

Then one outputs the entire set as a suite of reports, that can be text-differenced to the standard and manually checked set.

By checking in each small, self-contained, change independently, and running the test suite on each build, one can get an email each morning announcing whicn code changes broke which test-cases. Before one even has time to forget why one made the change.

Some work to set up, but it is a real charmer once set-up. I had the privilege of creating this for the report engine that I built in the '90’s.

Pieter

Thus spake pgeerkens:

By checking in each small, self-contained, change independently, and
running the test suite on each build, one can get an email each morning
announcing whicn code changes broke which test-cases. Before one even
has time to forget why one made the change.

Some work to set up, but it is a real charmer once set-up. I had the
privilege of creating this for the report engine that I built in the
'90’s.

It isn’t necessary to build a system like this from scratch. It already
exists. We have a testing framework (JUnit). If you’re using the Makefile
for building, you can run all of the tests using ‘make test’. There’s
some way to do that from Eclipse, as well, in case you’re using that. You
don’t need to wait for an automated system to notify you—you can run
the tests immediately.

There’s also Hudson, which is a continuous integration framework. It will
email you when tests fail. Right now, we’re using a Hudson instance that
Ken set up, but sometime in the new year we’ll have our own at
vassalengine.org.


J.

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.