Package com.strangelight.misc.hex

So, I came home from the Extreme Programming thing last night, got kind of baked and decided that the problem my programming partner had presented might be a fun doodle with which to while away an hour or two before bed.

See:
          Description

Class Summary
HexDirection One of the six points on our hexagonal compass.
HexGrid A hexagonal grid of hexagonal cells or tiles.
HexPath A List of HexLocation objects.
 

Package com.strangelight.misc.hex Description

So, I came home from the Extreme Programming thing last night, got kind of baked and decided that the problem my programming partner had presented might be a fun doodle with which to while away an hour or two before bed. As the project grew, I decided to do an experiment: I would only write code for this project while stoned, as an informal experiment to see how I code stoned compared to sober. My tentative conclusion is that, while stoned, I code slightly slower, but the code produced is of superior quality. (My theory is that I tend to be more patient while high, and so I'm less likely to cut corners in order to get things done fast.)

The problem was this: Given an hexagonal grid, find the path from one cell to another that most closely approximated a straight line.

The solution (arrived at over the course of the next bowl) requires first that we define a coordinate system with which to label the hexagonal cells. My original design used a staggered addressing scheme. I later refactored the design The cells are numbered on an x-y grid like so:


[ under construction...]

This gives us a simple and robust way to specify which hexagonal cell we're talking about. ("Robust" because there is a one-to-one pairing between integer pairs and cells, and thus the coordinate system will never introduce ambiguities.)

Now, if we're trying to find a closest-to-straight-line path from our current cell A to a target cell B, all we need to do is recursively move to the neighboring cell which brings us the most closer to B. In other words, given a HexLocation I could (and did) code a getShortestPathTo method recursively like so:

    public HexPath getShortestPathTo( HexLocation target ) {
        HexLocation cur_location = this;
        HexPath path = new HexPath();
        path.add( this );
        while ( ! cur_location.equals(target) ) {
            cur_location = cur_location.getNeighborClosestTo(target);
            path.add( cur_location );
        }
        return path;
    }
Where getNeighborClosestTo is coded in dumb-but-correct fashion like so:
    public HexLocation getNeighborClosestTo( HexLocation target ) {
        HexLocation current_closest = null;
        HexLocation neighborN = this.getNeighbor( HexDirection.N );
        HexLocation neighborS = this.getNeighbor( HexDirection.S );
        HexLocation neighborNE = this.getNeighbor( HexDirection.NE );
        HexLocation neighborSE = this.getNeighbor( HexDirection.SE );
        HexLocation neighborNW = this.getNeighbor( HexDirection.NW );
        HexLocation neighborSW = this.getNeighbor( HexDirection.SW );
        
        current_closest = this;
        
        if ( current_closest.geomDistanceTo(target) >= neighborN.geomDistanceTo(target) ) {
            current_closest = neighborN;
        }
        if ( current_closest.geomDistanceTo(target) >= neighborS.geomDistanceTo(target) ) {
            current_closest = neighborS;
        }
        if ( current_closest.geomDistanceTo(target) >= neighborNE.geomDistanceTo(target) ) {
            current_closest = neighborNE;
        }
        if ( current_closest.geomDistanceTo(target) >= neighborSE.geomDistanceTo(target) ) {
            current_closest = neighborSE;
        }
        if ( current_closest.geomDistanceTo(target) >= neighborNW.geomDistanceTo(target) ) {
            current_closest = neighborNW;
        }
        if ( current_closest.geomDistanceTo(target) >= neighborSW.geomDistanceTo(target) ) {
            current_closest = neighborSW;
        }
        
        return current_closest;
    }
Also, note the following clever (if I do say so myself) idiom for creating "object constants":
public class HexDirection implements Cloneable, _Testable {

	public static final HexDirection N  = new HexDirection();
	public static final HexDirection NE = new HexDirection();
	public static final HexDirection SE = new HexDirection();
	public static final HexDirection S  = new HexDirection();
	public static final HexDirection SW = new HexDirection();
	public static final HexDirection NW = new HexDirection();
		
	protected HexDirection() { }
	
	[...]
Each of the six directions are objects which can be compared to one another, rotated, etc. They are not integers or anything else that might be ambiguous: because of Java's strong type checking, you are in absolutely no danger of confusing a HexDirection with something else. Furthermore, I've removed most of the temptation to that excessive cleverness which is the root of all evil (or at least of most bugs). No, you may not convert between directions using bitwise operators: you'll just have to use the documented API like everyone else. Deal with it.