Find hexes a certain distance from a target hex in C#

[hex]

My post Draw a hexagonal grid in C# shows how you can draw a grid made up of hexagons. This post shows how you can find the hexes that are a given distance N from a target hex.

Basic Idea

The basic idea is relatively straightforward. Start N hexes south of the target hex. Then move in the following directions.

  • N hexes northeast
  • N hexes north
  • N hexes northwest
  • N hexes southwest
  • N hexes south
  • N hexes southeast

At this point you will have visited all of the hexes that are distance N away from the target hex.

[hex]

Navigation Methods

The idea is straightforward. Figuring out exactly how you move from one hex to the next can be a bit confusing. In a square grid, you simply add or subtract one from the row or column to move from one square to the next. In a hex grid, you may need to add or subtract one to both the row and column, and which you do depends on whether the target hex’s column is odd or even. For example, to move southeast from hex (1, 1), you add one to both the row and column to get (2, 2). Then to move southeast from hex (2, 2), you add one only to the column to get (2, 3).

To make navigation eassier, this example uses the following methods to move row and column values to the next hex in the desired direction.

// Adjust the row and column to move
// to the northeast neighbor.
private void MoveNE(ref int row, ref int col)
{
    if (col % 2 == 0) row--;
    col++;
}

// Adjust the row and column to move
// to the southeast neighbor.
private void MoveSE(ref int row, ref int col)
{
    if (col % 2 == 1) row++;
    col++;
}

// Adjust the row and column to move
// to the northwest neighbor.
private void MoveNW(ref int row, ref int col)
{
    if (col % 2 == 0) row--;
    col--;
}

// Adjust the row and column to move
// to the southwest neighbor.
private void MoveSW(ref int row, ref int col)
{
    if (col % 2 == 1) row++;
    col--;
}

// Adjust the row and column to move
// to the north neighbor.
private void MoveN(ref int row, ref int col)
{
    row--;
}

// Adjust the row and column to move
// to the south neighbor.
private void MoveS(ref int row, ref int col)
{
    row++;
}

The methods that move in the northeast, northwest, southeast, and southwest directions check the starting column and then add or subtract one from the row if appropriate. They then update the column.You can study the picture earlier that showed the hex numbering system to verify that these methods work.

The methods that move north and south simply add or subtract one from the starting row.

The following FindAtRange method puts those methods together to find the hexes at a given distance from a target hex.

// Return a list of hexes that are a given
// distance from the target hex.
private List FindAtRange(int row, int col, int range)
{
    List neighbors = new List();

    // Start in the south.
    row += range;

    // Move northeast.
    for (int i = 0; i < range; i++)
    {
        MoveNE(ref row, ref col);
        neighbors.Add(new PointF(row, col));
    }

    // Move north.
    for (int i = 0; i < range; i++)
    {
        MoveN(ref row, ref col);
        neighbors.Add(new PointF(row, col));
    }

    // Move northwest.
    for (int i = 0; i < range; i++)
    {
        MoveNW(ref row, ref col);
        neighbors.Add(new PointF(row, col));
    }

    // Move southwest.
    for (int i = 0; i < range; i++)
    {
        MoveSW(ref row, ref col);
        neighbors.Add(new PointF(row, col));
    }

    // Move south.
    for (int i = 0; i < range; i++)
    {
        MoveS(ref row, ref col);
        neighbors.Add(new PointF(row, col));
    }

    // Move southeast.
    for (int i = 0; i < range; i++)
    {
        MoveSE(ref row, ref col);
        neighbors.Add(new PointF(row, col));
    }

    return neighbors;
}

This method creates a list of points to hold the hex names. It then sets variables row and col to represent the hex that is N spaces below the target hex.

The method then uses the movement methods to follow the instructions given earlier and adds the corresponding hexes to its result list. Then method then returns the list and is done.

Using FindAtRange

The following code shows how the main program’s MouseClick event handler displays the hexes at a given range from the hex clicked.

// Add the clicked hexagon to the Hexagons list.
private void picGrid_MouseClick(object sender, MouseEventArgs e)
{
    int row, col;
    PointToHex(e.X, e.Y, HexHeight, out row, out col);
    
    int range = int.Parse(txtRange.Text);
    Hexagons = FindAtRange(row, col, range);

    string txt = "";
    foreach (PointF point in Hexagons)
    {
        txt += "(" + point.X.ToString("0") +
            ", " + point.Y.ToString("0") + ") ";
    }
    txtCells.Text = txt;

    picGrid.Refresh();
}

This code calls the PointToHex method described in the previous post to see which hex you clicked. it then parses the range entered in the txtRange TextBox and passes the row, column, and range into the FindAtRange method. It saves the results in the Hexagon list so the Paint event handler can fill those hexes later. (Download the example to see how that works.)

The event handler finishes by building a string that lists the hexes that it found.

See the previous post and download the example to see additional details such as how the program determines which hex contains the point you clicked, how the Paint event handler draws the hexes, and how that event handler highlights the hexes at a given range from a target.


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, drawing, geometry, graphics, mathematics and tagged , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.