Title: Building the Board (part II)

The hexes on the board need to be ordered into some sort of grid according to requirement Hex/Board-1. One of the most important gains from putting the hexes into a grid is the ability to determine relative positions. A grid is traditionally built as a set of indices with two coordinates indicating the location of any grid element in a planer surface. Since the game board is a planer surface, it makes sense to start with a two coordinate system. Figure 1 is an effort to place the hexes within such a grid.

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

To test the appropriateness of this grid, it is necessary to check and see if it is possible to calculate the distance between hexes. The traditional way to calculate the distance between two points is to take the absolute value of the difference between the ordinates. Consider two points on the grid (x1, y1) and (x2, y2). The distance between the two points is given by the formula:

Delta = SQR((x1-x2)2 + (y1-y2)2)

This formula is determined by drawing an imaginary right triangle. One side of the triangle is the along the x-axis, one side is along the y-axis (these two sides are perpendicular, thus making the triangle a right triangle), and the third is a diagonal between the two points. Since the shortest distance between two points is a straight line, the diagonal line is the distance between the two points. To calculate the length of a triangle's diagonal from its sides (remember the length of the sides are given by the coordinates) the formula shown above is used.

The hex at (0, 0) touches the hex at (2, 0), so the distance between them should be one hex (it would be necessary to move once to go from one hex to the other). Using the formula derived above, the distance is SQR((0-2)2 + (0-0)2) which is SQR(4+0) or 2. Thus, the distance formula gives a distance of 2 units. This is not good. In addition, it is difficult to tell which faces of the hexes are touching just by using the coordinates.

All of these problems stem from the fact that the two coordinate planer grid system was designed for handling four sided objects (squares) and the hexes used in the game are six sided. The axes in a two coordinate system bisect all sides of a square, so relationships between squares are well defined. In order for the hexes to share the same relationship qualities, it would be necessary for the axes to bisect the sides of the hexes. If this were to happen, then there would have to be three axes separated by 60 degrees instead of the normal 90 degrees. It is worthwhile to investigate that possibility.

In this scenario, each hex position would be defined by a triple instead of a pair. Thus, Figure 1 would be renumbered as shown in Figure 2.

In this strange coordinate system, however, how is it possible to calculate the distance between two hexes? The game board sits in a plane but there are three axes presenting values (generally associated with three dimensional space). This third axis does make it easier to determine which faces a pair of touching hexes have in common, but the extra information generated by the third axis actually overwhelms the calculations for determining distance.

   / \     / \     / \
  /   \   /   \   /   \
 /     \ /     \ /     \
|       |       |       |
|1,-1,0 | 1,0,1 | 1,1,2 |
|       |       |       |
 \     / \     / \     / \
  \   /   \   /   \   /   \
   \ /     \ /     \ /     \
    |       |       |       |
    | 0,0,0 | 0,1,1 | 0,2,2 |
    |       |       |       |
   / \     / \     / \     /
  /   \   /   \   /   \   /
 /     \ /     \ /     \ /
|       |       |       |
|-1,0,-1|-1,1,0 |-1,2,1 |
|       |       |       |
 \     / \     / \     /
  \   /   \   /   \   /
   \ /     \ /     \ /
         Figure 2

What now? Stumped I turned to Mark Stowell (<stowell@gang.umass.edu>) who is an expert in graphical geometry. He kindly lent his time and helped resolve this problem. Clearly three axes do not work, so it is necessary to return to a two axis solution. It is possible, however, to generate an oblique set of axes that do the job. By creating new axes (u and v) with u 30 degrees below the traditional x-axis and v 30 degrees above the traditional x-axis, it is possible to generate a coordinate system that will show accurate distances between hexes. This new mapping is shown in Figure 3.

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

Using some moderately complicated derivations which I will gladly review on the mailing list should anyone be interested, Mr. Stowell determined that the distance between any two hexes is given by the following formula:

Delta = SQR((u1-u2)2 +(u1-u2)(v1-v2)+(v1-v2)2)

where the first hex is at location (u₁, v₁) and the second hex is at location (u₂, v₂).

Using this coordinate system, the hex at (0, 0) does not touch the hex at (2, 0) and the two hexes are 2 units apart. Applying the equation above, the difference between the two hexes is:

Delta = SQR((0-2)2 + (0-2)(0-0) + (0-0)2)
      = SQR(4 + (-2)(0) + 0)
      = SQR(4) = 2

HURRAY! This works as expected. For comfort, consider one more case where the two hexes are touching, so the distance should be 1. The difference between (1, 0) and (1, -1) is:

Delta = SQR((1-1)2 + (1-1)(0-(-1)) + (0-(-1))2)
      = SQR(0 + 0 + 1)
      = SQR(1) = 1

Yes! We can conclude from this small sample that the derivation is indeed correct and we now have a way of calculating the distance between any two hexes. Thus the coordinate system to use is defined and the initial requirement is met.

Now, using this coordinate system, it is necessary to figure out which faces of any two given hexes are touching. It is reasonable to assume that from this point forward that the hexes being analyzed have already been found to have a distance between them of 1 (i.e. that they are indeed touching).

Hexes that are along either the u or v axis will have a coordinate in common. Since the u axis bisects the Southeast and Northwest faces, hexes with a common u coordinate will be touching on those faces. Whichever hex has a larger v coordinate will be touching on the Southeast face, the smaller v coordinate will be touching on the Northwest face. Similarly, the v axis bisects the West and East faces. Thus, when hexes have the same v coordinate, whichever has the larger u component will be touching on the West face, whereas the hex with the smaller u component will be touching on the East face.

This leaves one more set of faces to resolve. If both the u and v coordinates are larger, then the hex with the larger coordinates will be touching on the Southwest face. In the reverse case, the hex with the smaller coordinates will be touching on the Northeast face.

This information is summarized in Table 1.

The grid system defined makes it possible to determine how far apart any two hexes are and which faces of two touching hexes are held in common. Thus, the grid system defined meets requirement Board-5 and part of requirement Hex/Board-3.

An additional requirement (Hex/Board-2) is that the board be able to determine what hex is diametrically opposed to another on opposite edges of the board. Given the 19 hex arrangement being considered, edge hexes will always have at least one coordinate with an absolute value of 2. No interior hexes will have a coordinate with an absolute value of 2. In this manner the set of edge hexes can be easily identified as required by requirement Hex/Board-3.

The next step after finding the set of edge hexes, is to figure out how to calculate the coordinate pair of a diametrically opposed hex. Because the coordinate system is centered on the center hex, the coordinates of a diametrically opposed hex can be determined simply by multiplying both coordinates of the current hex by -1. Thus, the diametrically opposed hex to (2, 2) is (-2, -2). Simple analysis of a 19 hex board with the hexes properly labeled with their coordinates shows this to be true. In this manner, the grid system fulfills requirement Hex/Board-2.

To determine a starting position for a new player, it is necessary to pick a set of three hexes. Once one starting position has been determined the starting positions available to other players are deterministic, although which player takes which position remains a player decision. To build this three hex starting position, it is necessary to take an edge hex and determine which two additional edge hexes are touching it.

Keeping in mind that all edge hexes have a 2 in at least one of the (u,v) coordinate pair, it should be possible to:

Given the knowledge that we have from Table 1, it is possible to calculate which hexes would appear on which faces. The calculations for each face are shown in Table 2

Using table two, it is now possible to calculate the six possible hexes, remove the hexes outside the edges of the board and identify the two neighbor edge hexes. This meets requirement Board-6 and Board-7.

Since the grid system can be represented as a two-dimensional array, it seems like a good starting place for the 19 hex board to store the hexes in a two-dimensional array. Given the configuration of the board from requirement Board-1, it will be necessary to have an array with dimensions of -2 to 2 on both the u and v axes. This is reflected in the pseudo-code for the board seen in Listing 1.

The board also requires a number of functions for determining the possible starting positions as defined in requirement Board-7 (find_start), determining whether a hex is on an edge (is_edge), finding a diametrically opposed hex as defined in requirement Hex/Board-2 (find_opposed), finding the neighbors of a given hex as defined in requirement Board-5 (find_neighbors), determining which faces are touching on a pair of hexes (faces_touching), and the distance between two hexes (distance_between). These functions are generally defined in the pseudo code of Listing 1.

To facilitate error checking and bounds checking, the board also contains minimums and maximums for u and v. While this will not guarantee that there is a hex with coordinates bounded by the minimums and maximums, it will assure that the boundaries of the array will not be exceeded. It is worthwhile to discuss what happens in the array when a pair of coordinates is given that is within the minimum/maximum boundary values, but is not on the board. In this case, the hex will be NULL and any functions that work on the board need to check for NULL returns as a result. The first most likely application of this will be in the find_neighbors routine.

class board 
{
  private:
    short u_max, u_min, v_max, v_min, max_hex;
    std::map<hex::coordinate_pair, hex::hex> hex_list;
  public:
    hex::coordinate_pair& virtual add_hex(hex::hex& new_hex);
    std::list<hex::hex>& virtual find_start (hex::hex& new_hex);
    binary virtual is_edge(hex::hex& check_hex);
    hex::hex& virtual find_opposed(hex::hex& check_hex);
    std::list<hex::hex>& virtual find_neighbors(hex::hex& check_hex);
    binary virtual faces_touching(hex::hex& hex1, hex::hex& hex2);
    short virtual distance_between(hex::hex& hex1, hex::hex& hex2);
    binary virtual draw_board(display_type disp);
}

In addition, it seems like a good idea for the hex to know its coordinate position on the board, so the pseudo-code for the hex has been modified as shown in listing 2. This listing also shows some changes recommended by Francis who has been the only commenter on this game thus far.

A coordinate pair represents the coordinate position on the board. The coordinate pair is exhaustively defined in an effort to make manipulations using coordinates as meaningful and complete as possible. The reason for this is that there are many operations that will come in the future that are likely to make use of the coordinate class. By carefully defining that class now, it will reduce the burden later on without putting an undue burden on the current exercise.

In an effort to incorporate the concept of Data Attribute Notation where appropriate, the u and v coordinates are represented by different classes, which eases the manipulations that may be done on one coordinate without effecting the other. It will also make the code more readable and does not incur undue overhead in this case. Care to argue with this skimpy reasoning? Post on the mailing list!

enum hex_sides {W_side = 0, NW_side, NE_side, E_side, SE_side, SW_side, Center_side };
enum hex_color { Brown=0, Green, Blue };
enum display_type { Character=0 };
class colored_area {
  private:
    hex_color color;
    std::map<hex_sides, float> sides_touched;
  public:
    int draw_color();
    boolean touching_side(hex_sides side,float portion);
};
class coordinate {
  private:
    short coord;
  public:
    coord operator short();
    coord operator + (short ord);
    coord operator - (short ord);
    coord operator ++ (short ord);
    coord operator - (short ord);
    friend ostream& operator << (coordinate& ord);
    friend ostream& operator >> (coordinate& ord);
};
class u_coordinate : private coordinate {public: operator short(); };
class v_coordinate : private coordinate {public: operator short(); };
class coordinate_pair {
  private:
    u_coordinate u;
    v_coordinate v;
  public:
    coordinate_pair& operator << (v_coordinate& ord);
    coordinate_pair& operator << (u_coordinate& ord);
    coordinate_pair& operator >> (v_coordinate& ord);
    coordinate_pair& operator >> (u_coordinate& ord);
    coordinate_pair& operator v_coordinate() const;
    coordinate_pair& operator u_coordinate() const;
    int operator - (const coordinate_pair& ord);
};
class hex {
  private:
    external_orientation ext_face;
    int color_count;
    coordinate_pair    board_location;
    hex_sides& externtointern(hex_sides side);
    hex_sides& interntoextern(hex_sides side);
    boolean virtual    build_colors();
  public:
    binary virtual draw_hex(display_type disp, int line);
    colored_area& virtual get_color(hex_sides extern_side, float portion);
    binary virtual rotate_hex(external_orientation face);
};

Something that has not really been addressed is how the board will be displayed (the display of individual hexes has already been discussed). Well, for the current time we will be using ASCII characters to display the hexes. This requires that the board be drawn a line at a time, not just a hex at a time. Thus, we have to add the display_type variable to the board that tells the draw routines what type of display is expected. For now, the display_type only has "character" as a member, but others will follow in the months to come. To draw the board and hexes, draw functions are required and they are defined in Listings 1 and 2 respectively.

OK, it is really too early to begin considering coding these two components, but this is a magazine about code, not about design. Moreover, I am itching to code this stuff after too many months of intermittent design! So, next issue, be prepared to discuss the coding of both the hex and the board objects. Heck, you could even prepare some testing software based on the interfaces defined and send it in to the list…

Editorial Comment

The code and pseudo code in this article has not been fully checked because the author had not realised that C Vu was about to go to print. I, and I hope you, am very grateful for the way that he responded to my enquiry about his column five days before the final copy was due to go to the printers (I knew he was writing a column and had simply allocated space for it, assuming he would deliver after the last weekend).

I hope that many of you will now start to participate. Francis