Overview
If you have been following my “adventures’ with the development of a turn-based strategy game, you have probably already noted that this is a very slow development process. It is without a doubt one of the most difficult aspects in game development outside of aerial simulations that one can endeavor to take on. This is mostly due to the lack of tools and flexible information sources that would allow a developer to mold either source-code or libraries to their own technical interpretation of what they are trying to build.
As a result, I have been making my own interpretation of how such code could be designed and implemented freely available to the game development community at the MonoGame Forums since that is the graphics engine I am using to build my project.
With this article, a lot of my original source code has been updated and somewhat refined to accommodate the new algorithms that will allow for the selection of a single tile\hexagon in a hexagonal map.
This implementation has entered the area of high complexity due to the difficulty level in designing such code. As a result, I am going to provide as much detailed information as I can to assist newcomers to this area of game development.
As with my previous articles on this subject, all of the source-code, inclusive of the Visual Studio project files, are provided for download at the end of this article.
Options for Creating Such Algorithms
When one begins to research how such a process of tile\hexagon selection could be implemented, the most common recommendations and source-code examples provide mathematical based solutions. One such solution that I came across I posted on the MonoGame Forums with the following link:
This is a very nice article that does rely to some extent on the mathematical approach to the process of selecting tiles\hexagons in a hexagonal map. And I did try for a number of days to wrap my head around this approach tinkering with the source code in the process. I went through at least three complete iterations in attempting to implement the article’s code to my own design. Though I was partly successful in these attempts, complete success was always just out of my reach.
Unfortunately, even though I was quite competent with advanced and college-level Algebras as well as with Geometry, it has been many, many, many years since I have done work with these mathematical sciences. Thus, to use such formulas successfully, I would have had to have taken some online courses in these areas of math to refresh my aging memory to obtain a good working knowledge of the techniques involved. I didn’t see this as a feasible option for what I wanted to spend my time on so I decided to come up with my own set of algorithms that rely on XY positioning coordinates and offsets.
Though this recent effort took a bit of time, I have been quite successful and my algorithms may be better suited for those who would like to avoid the mathematical approach. However, it should be noted that my approach is not nearly as efficient as the mathematical ones, just probably easier to understand and work with.
For those who would still like to try the mathematical approach, you may download the excellently designed algorithms from Amit Patel at Red Blob Games (http://www.redblobgames.com/) in PDF format from the following link:
The PDF contains the exact same presentations and discussions that are available at Amit’s web-site at the link noted above. I just put them into PDF format for easier reading
For those who want try out my approach, let’s get started.
Basic Configuration Parameters
If you have downloaded the original project and source code as a result of my previous articles on hexagonal maps, you would have noted that I have two different sets of declared configuration variables. The first set is defined in a structure entitled, Global.cs. The second set can be found at the top of the MainGame.cs module. About half of these variable declarations in each set are currently important to the project as they define all of the basic numbers you will have to work with.
No doubt, setting up these declarations in this manner is somewhat sloppy as both sets of declarations can be contained in a single module. However, since I spent quite a bit of time experimenting and testing my implementations, I haven’t yet refactored these declarations into a more concise format.
Right now, I am considering as the next phase of this project a development of an application that will create and update these same variables to a database, which in turn will see such data loaded to a globally accessible module. This way, you would be able to update such variables at will without having to constantly go into the code to do so.
If I finesse the application well enough over time, any changes to these variable values will simply be reflected properly in the running of the application basics.
The Global.cs Declarations
private static int siActualTileHeightInPixels = 72;
private static int siActualTileWidthInPixels = 72;
private static int siMaximumMapHeightInTiles = 50;
private static int siMaximumMapWidthInTiles = 50;
private static int siActualMapHeightInTiles = 15;
private static int siActualMapWidthInTiles = 15;
private static int siBaseX = 0;
private static int siBaseY = 0;
private static int siMapTileOffsetX = 54;
private static int siMapTileOffsetY = 36;
private static int siMapTileOddRowOffsetX = 57;
private static string ssSelectedHexTileId = "";
private static ArrayList soTexture2dArrayList = new ArrayList();
private static HexMapEngine.Structures.HexTile[,] soMapHexTileArray = null;
private static string[] soHexTileXYOffsetsArray;
The declaration list above shows the internal variable declarations for the publicly available properties in the structure. As you can see, I align my defined declarations in a somewhat symmetrical manner. I have been coding this way for so many years that I now do such indentations automatically.
Each declaration, as you will note, has a two letter prefix. The first letter in this case will always be an “s”, which will indicate that the declaration is declared in a structure. The second letter denotes the data-type of the variable being declared. In this case then, i=integer, s=string, and o=an object type. Again, I have been using this very primitive form of Hungarian notation for several decades in all of my projects.
The standard size of my tiled images is 72 by 72 pixels; a perfect square. Thus, the variable declarations of siActualTileHeightInPixels and siActualTileWidthInPixels represent this information to the application where required.
Interestingly enough, tiles defined as complete squares are not necessarily the norm for hexagonal maps as there are many implementations that use more of rectangular construct. Even prior to starting to develop this game application, I always thought that squares would be the normal geometry for a tile so I just settled on what I thought would be a convenient size to work with while allowing for overlayed images within a hexagonal outline.
If you were to review the mathematical approaches to this type of graphic design, you would see that a number of them use more of a rectangular geometric. In either case, offsets will still be used, which we get to.
The next two variable declarations of siMaximumMapHeightInTiles and siMaximumMapWidthInTiles are no longer used anywhere within the application. They have been kept for possible later use but at this time they can be ignored.
The variable declarations of siBaseX and siBaseY are also not used at this time within the application.
The variable declarations of siMapTileOffsetX and siMapTileOffsetY are two critical variables that are used for calculations that involve offset placements for the display of tiles. These offsets are used to place successive tiles next to each other at both the column and row levels as the graphic below demonstrates:
The variable declaration of siMapTileOddRowOffsetX is not used at this time.
The variable declaration of ssSelectedHexTileId is used for comparative purposes of tile-id selection. It will probably be eliminated as the application develops.
Please remember that the list of variable declarations above are the internal place-holders for the actual properties in the Global.cs structure.
You may wonder why I chose to leave so many unused variables in place and it would be an appropriate question. Simply put, they have been left in place because the associated application project is a work-in-progress that still has quite a bit of development left to be done and such currently unused declarations act as place-holders for possible future development or will be refactored out of the code as development in the graphics area becomes more refined and begins to reach a stage of finality.
The MainGame.cs Declarations
private int ciScreenHeight = 600;
private int ciScreenWidth = 800;
private int ciBackBufferScreenHeightAdditionalIncrement = 216;
private int ciBackBufferScreenWidthAdditionalIncrement = 108;
private int ciRowPosition = 0;
private int ciColumnPosition = 0;
private int ciMovementOffset = 14;
private int ciSelectedMouseXPosition = 0;
private int ciSelectedMouseYPosition = 0;
private bool cboolSelectedHexFound = false;
private string csMouseClickInBoundedRectangle = "";
private string csScrollDirection = "";
private HexMapEngine.Classes.HexTileMap coHexTileMap;
private HexMapEngine.Structures.HexTexture2D coHexTexture2D;
private Microsoft.Xna.Framework.Input.KeyboardState coKeyboardState;
private Microsoft.Xna.Framework.Graphics.Texture2D coTexture2DTile;
private Microsoft.Xna.Framework.Graphics.SpriteBatch coSpriteBatch;
private Microsoft.Xna.Framework.Graphics.SpriteFont coSpriteFont;
private Microsoft.Xna.Framework.GraphicsDeviceManager coGraphicsDeviceManager;
private Microsoft.Xna.Framework.Input.MouseState coMouseState;
private MonoGame.Extended.BitmapFonts.BitmapFont coBitmapFont;
The first two variable declarations of ciScreenHeight and ciScreenWidth are used to hold the actual dimensions of the screen to be displayed.
This may provide some confusion to MonoGame developers who are new to the framework since both of these variables are used to initialize the following framework graphic properties.
coGraphicsDeviceManager.PreferredBackBufferHeight = ciScreenHeight;
coGraphicsDeviceManager.PreferredBackBufferWidth = ciScreenWidth;
It is somewhat odd that the graphics device manager uses the properties of PreferredBackBufferHeight and PreferredBackBufferWidth to determine the dimension of the displayed screen considering that the nomenclature appears to refer to the unseen buffer where graphics drawing can be performed invisibly to the user. If you had done work with far older frameworks in the DOS world, this is what would immediately come to mind.
MonoGame’s use of these properties can also be confused with the entire area of your map including that unseen part of it that is not being displayed to the user as it may be larger than the actual dimensions of the screen. However, after tinkering with these properties, this does not appear to be the case and they are simply used to provide the actual displayed dimensions of the screen and if your map takes up more space than the screen dimensions account for, they will be hidden off-screen until you move your camera over these unseen areas.
The following two variable declarations of ciBackBufferScreenHeightAdditionalIncrement and ciBackBufferScreenWidthAdditionalIncrement were originally set up to account for this misunderstanding of the use of the above noted properties but are now no longer required and as a result, have had the code used to initialize the graphic device manager properties with these declarations commented out.
The variable declarations of ciRowPosition and ciColumnPosition are used simply to keep track of the row and column positions in the Process_UpdateEvent method. Currently, there is no real use for these variables but they are being kept as place-holders for later development if necessary.
The variable declaration, ciMovementOffset, is used to determine how much the camera view should be moved around the map at any one time during right, left, up, down movement requests by placing your mouse outside the borders of the displayed screen.
The value of 14 was an experimental number that appears to work quite nicely for the current processes being used. If you begin changing the configuration of your tile sizes and how they are to be viewed by camera movement, you may want to consider experimenting with a different number for this value.
The next variable declaration, cboolSelectedHexFound, is an indicator that is updated in the Find_MouseSelectedHex() method in the MainGame.cs module, which is the master method that is called from the Process_UpdateEvent() and is the method that is called from the standard game-loop event UpdateEvent(). The cboolSelectedHexFound variable tells UpdateEvent\Process_UpdateEvent methods if a user-selection of a selected hexagon tile has been successfully found. If so, this information will be correctly updated to the current on-screen information display in terms of the hexagon tile coordinates.
The variable declaration of csMouseClickInBoundedRectangle is not currently being used. As a result, this variable can currently be ignored.
The csScrollDirection variable declaration is merely an indicator that is updated in the Process_UpdateEvent method with a value that describes which direction the user is currently moving in.
The following variable\object declarations are made either for in-application object instances or MonoGame Framework object instances.
private HexMapEngine.Classes.HexTileMap coHexTileMap;
private HexMapEngine.Structures.HexTexture2D coHexTexture2D;
private Microsoft.Xna.Framework.Input.KeyboardState coKeyboardState;
private Microsoft.Xna.Framework.Graphics.Texture2D coTexture2DTile;
private Microsoft.Xna.Framework.Graphics.SpriteBatch coSpriteBatch;
private Microsoft.Xna.Framework.Graphics.SpriteFont coSpriteFont;
private Microsoft.Xna.Framework.GraphicsDeviceManager coGraphicsDeviceManager;
private Microsoft.Xna.Framework.Input.MouseState coMouseState;
private MonoGame.Extended.BitmapFonts.BitmapFont coBitmapFont;
The last variable\object declaration is for the Myra.UI interface library, which the application currently uses for the information display on the game screen. The Myra.UI default font is loaded from the MonoGame Content Pipeline.
MainGame Module Master Hex Selection Method
private void Find_MouseSelectedHex()
{
HexMapEngine.Structures.HexTile loHexTile;
HexMapEngine.Classes.HexTileMap loHexTileMap = new
HexMapEngine.Classes.HexTileMap(coGraphicsDeviceManager);
ciSelectedMouseXPosition = coMouseState.X;
ciSelectedMouseYPosition = coMouseState.Y;
loHexTile = loHexTileMap.Find_SelectedHexBasedOnMouseClick(ciSelectedMouseXPosition,
ciSelectedMouseYPosition);
if (loHexTile.HEX_TILE_SELECTED)
{
cboolSelectedHexFound = true;
}
else
{
cboolSelectedHexFound = false;
}
}
The Find_MouseSelectedHex() method is the master call in the MainGame.cs module, which determines which hexagon tile a user has selected by clicking the left mouse-button on his or her mouse. The method makes use of the structure, HexTile and the class, HexTileMap; the latter which contains the methods and algorithms that determine the selection.
HexTileMap Class & The "<code>Find_SelectedHexBasedOnMouseClick()" Method</code>
From the MainGame module, the Find_SelectedHexBasedOnMouseClick method is called in the HexTileMap class. It is here that we begin the process of determining which hexagonal tile has been selected and just as importantly that the selection is done within the boundaries of the Hexagon image displayed.
internal HexMapEngine.Structures.HexTile Find_SelectedHexBasedOnMouseClick(int
piXMousePosition, int piYMousePosition)
{
bool lboolBreakFromForLoops = false;
HexMapEngine.Classes.HexTileMath loHexTileMath = new
HexMapEngine.Classes.HexTileMath(coGraphicsDeviceManager);
HexMapEngine.Structures.HexTile loHexTileSelected = new HexMapEngine.Structures.HexTile();
if (loHexTileMath.Is_PointInHexMapRectangle(piXMousePosition, piYMousePosition))
{
for (int liLengthDim0 = 0; liLengthDim0 <
HexMapEngine.Structures.Global.MAP_HEX_TILE_ARRAY.GetLength(0); liLengthDim0++)
{
for (int liLengthDim1 = 0; liLengthDim1 <
HexMapEngine.Structures.Global.MAP_HEX_TILE_ARRAY.GetLength(1); liLengthDim1++)
{
loHexTileSelected = HexMapEngine.Structures.Global.MAP_HEX_TILE_ARRAY[liLengthDim0,
liLengthDim1];
if (loHexTileMath.IsPoint_InsideHexagon(ref loHexTileSelected, piXMousePosition,
piYMousePosition))
{
lboolBreakFromForLoops = true;
break;
}
}
if (lboolBreakFromForLoops)
{
break;
}
}
}
return (loHexTileSelected);
}
In the code of the above method, you will note that the first “if” statement calls the method, Is_PointInHexMapRectangle, which first determines if the user selected a point anywhere within the dimensions of the displayed screen. If not, then the rest of the code is ignored since no hexagonal image would be outside such boundaries. This method can be found in the HexTileMath.cs class.
Then we enter two “for loops” which allows the code to interrogate the HexTile structures within an array that have been displayed on the screen in the two dimensions that correspond to the Y(row) and X(column) positions that the tiles are displayed with. These structures are loaded through the Load_MapHexTileArray() method in the class, HexMapTileLoad.cs.
Currently, the loading of the hexagon tile structures are based solely on the generation of information within the method. This will be modified over time as the development of the application becomes more sophisticated and it begins moving into the phase where specific tile images are required for specific positions in the map.
Getting back to the method above, we finally use each tile’s positional information as well as the selected X and Y positions to determine if the selected point is within a hexagon image of a tile itself. This determination is accomplished through the IsPoint_InsideHexagon() method shown below. This method is also found in the HexTileMath.cs class.
internal bool IsPoint_InsideHexagon(ref HexMapEngine.Structures.HexTile poHexTileSelected,
int piXMousePosition, int piYMousePosition)
{
int liXIndex = 0;
int liYIndex = 0;
bool lboolXIndexFound = false;
bool lboolYIndexFound = false;
HexMapEngine.Structures.HexTile loHexTileSelected;
for (liXIndex = 0; liXIndex < HexMapEngine.Structures.Global.ACTUAL_MAP_WIDTH_IN_TILES;
liXIndex++)
{
if (Is_XMousePositionWithinHexTileBoundaries
(HexMapEngine.Structures.Global.MAP_HEX_TILE_ARRAY[0, liXIndex].MAP_TILE_POSITION_X,
piXMousePosition))
{
lboolXIndexFound = true;
break;
}
}
if (lboolXIndexFound)
{
for (liYIndex = 0; liYIndex <
HexMapEngine.Structures.Global.ACTUAL_MAP_HEIGHT_IN_TILES; liYIndex++)
{
if (Is_YMousePositionWithinHexTileBoundaries
(HexMapEngine.Structures.Global.MAP_HEX_TILE_ARRAY
[liYIndex, liXIndex].MAP_TILE_POSITION_Y,
piYMousePosition))
{
lboolYIndexFound = true;
break;
}
}
if (lboolYIndexFound)
{
loHexTileSelected = HexMapEngine.Structures.Global.MAP_HEX_TILE_ARRAY
[liYIndex, liXIndex];
HexMapEngine.Structures.Global.SELECTED_HEX_TILE_ID =
loHexTileSelected.TILE_ID.Trim();
return (true);
}
}
return (false);
}
Finding the X-Column Selected
The first for-loop in this method simply moves across the X columns using the global property of ACTUAL_MAP_WIDTH_IN_TILES as the maximum condition for the loop. For each column, we then test the passed selected X coordinate to determine which set of tile X coordinates it falls between, using the Is_XMousePositionWithinHexTileBoundaries() method (also defined in the HexTileMath.cs class).
The Is_XMousePositionWithinHexTileBoundaries() method is shown below:
private bool Is_XMousePositionWithinHexTileBoundaries(int piXPositionOffset, int
piXMousePosition)
{
int liXStartPosition = 0;
int liXEndPosition = 0;
string[] loXYPositions;
foreach (string lsXBoundaries in coHexLineXAxisStartAndEndPointsArrayList)
{
loXYPositions = lsXBoundaries.Split(',');
liXStartPosition = Convert.ToInt32(loXYPositions[0]);
liXEndPosition = Convert.ToInt32(loXYPositions[1]);
if ((piXMousePosition >= (piXPositionOffset + liXStartPosition)) && (piXMousePosition
<= (piXPositionOffset + liXEndPosition)))
{
return (true);
}
}
return (false);
}
This method uses a pre-defined array-list of start and end X positions that defines the each line of pixels within an actual hexagon image. This array is loaded in the Load_HexLineXAxisStartAndEndPointsArrayList() method in the HexTileMath.cs class.
To visualize how this array-list is defined, please look at the image below:
Notice at the top of the image the two small elliptical shapes that are on each end of the top-most positions of the hexagon. This top line as well as the bottom-most line are the only two rows of pixels that are not duplicated for the drawing of a hexagon image. All other outer positions of the hexagon require two rows of pixels to form the image of a hexagon (except for the top-most and bottom-most rows as just noted). As a result, the first item of data in the array-list has the following information.
loHexLineXAxisStartAndEndPointsArrayList.Add("18,53,0");
Note that the array-list object variable as shown above is transferred to the class level array-list declaration at the end of the load method.
coHexLineXAxisStartAndEndPointsArrayList
This first item in the array-list shows that for this row of pixels (the top-most row) the beginning X-position is at 18 and the last X-position for the row is at 53. This information pertains only to the actual image X positions in terms of starting and ending positions of the actual hexagon image, not the entire square of the 72×72 image in which the hexagon image resides.
The two lower elliptical shapes in the image above demonstrates the two duplicate rows of pixels required to make up each staggered set of rows in the subsequent Y positions as the hexagon image grows and then shrinks again in size in order to form the complete hexagon. Again, the last row, like the top-most row requires only a single row of pixels. These two noted rows above are defined in the array-list with the following two items.
loHexLineXAxisStartAndEndPointsArrayList.Add("15,56,5");
loHexLineXAxisStartAndEndPointsArrayList.Add("15,56,6");
The question may arise as to why use two duplicate items within the array-list to define such rows. You don’t have to and can, if preferred, develop an additional part of the algorithm that calculates each of the two lines with using only one item in the array-list. However, part of the point of devising this technique was to eliminate as much of the mathematical as possible to allow non-math oriented developers to better understand this construct. And though this construct is somewhat redundant, it is nonetheless, simpler.
Using this array-list alone will of course not allow the application to accurately find a correct X-position in any one column as the only thing this array-list provides is information as to where a hexagonal image within a 72×72 image actually resides. We need additional information for this type of determination and that comes with the interrogation of the tile structures that are held in the global hex tile array each with the property, MAP_HEX_TILE_ARRAY, which is held by the internal object declaration, soMapHexTileArray, in the Global.cs structure noted in the section, Basic Configuration Parameters.
For the X-position information, we use each structure being passed from the array to the method above, IsPoint_InsideHexagon, which in turn passes the structure’s X-offset information to the other method above, Is_XmousePositionWithinHexTileBoundaries().
The commented code in the IsPoint_InsideHexagon() method above (again shown below) was left in place to bookmark some information regarding the actual X and Y offsets that each tile structure actually holds. It should be noted that the tile structure array is indexed as [Y, X] or [row, column] as the index information, which is left-most data item in the sample tile array information below:
Thus, the structure that holds the tile information for the upper left-most hexagon tile in the actual screen display contains 0 for both the X and Y offsets since this tile is placed at actual screen coordinates 0,0. When calculated in the method, Is_XmousePositionWithinHexTileBoundaries() with the following code:
if ((piXMousePosition >= (piXPositionOffset + liXStartPosition)) && (piXMousePosition
<= (piXPositionOffset + liXEndPosition)))
{
return (true);
}
the actual beginning position then of the hexagonal image begins at X-position of 18 and ends at X-position, 53 for the top-most row. Subsequently, for a hexagonal tile that appears on the screen in the upper left-most corner having X,Y coordinates of 0 each will only require the actual starting and ending positions of the actual hexagon image within the 72×72 pixel tile.
For all hexagonal tile images that appear to the right of the upper left-most image, the corresponding X-offset, which will be other than zero, is then used in the same “if” comparison above.
For example, if we were then to test for the selection of the second hexagon tile in the top row of the display screen, our X-offset would be 54. Using this with the first row X-positions of the hexagon image itself, we would then have a starting X-position of the actual hexagon image of (54 + 18) and an ending X-position (54 + 53) compared to let's say a mouse-selected point of X = 65. The result, if this case is true, would be that the user had selected an X-position within the second column of hexagon tiles.
However, at this point, we do not know what row of hexagon tiles has been selected yet.
Finding the Y-Row Selected
Finding the row the selected mouse position was made in is similar in style to that of determining the column by the selected mouse X-position.
Once the selected column has been found through the use of the selected mouse X-position in the code above, we can then find the row through the use of the mouse selected Y-position by calling the method below, Is_YmousePositionWithinHexTileBoundaries().
Like the similar method that determines the column using the mouse selected X-position, this second method uses the same concepts by using the passed hex tile Y-offset.
private bool Is_YMousePositionWithinHexTileBoundaries(int piYPositionOffset, int
piYMousePosition)
{
int liYEndPosition = 71;
if ((piYMousePosition >= piYPositionOffset) && (piYMousePosition <= (piYPositionOffset +
liYEndPosition)))
{
return (true);
}
return (false);
}
However, in the case of finding a row, we need only the ending Y-position for each hexagon image, which given the fact that we are using a 72×72 pixel square to contain a hexagon image would always be the passed Y-offset plus the actual height of a hexagon image, which will always be 71 (liYEndPosition) in terms of positional accuracy assuming the base Y-position is 0.
Thus, if we find that a user selected a mouse Y-position in the second row of the second column of displayed hexagon tiles, the mouse selected Y-position would have to be compared against the starting Y-offset (36 for the beginning of the second row) for the tile and the ending Y-offset, which includes the height (in coordinate numbers 0-71) of the tile (36 + 71 for the end of the second row), noting the data points in the commented code above.
By processing both of the sub methods, Is_XmousePositionWithinHexTileBoundaries() and Is_YmousePositionWithinHexTileBoundaries(), through for-loops in the IsPoint_InsideHexagon() method, we can find both the X and Y index of the tile in the structure array. The result is then the tile on the screen display that the user selected.
Finally, please note that with hexagon tile maps, we have the even and odd columns where one column is displayed lower than the previous column. If you note in the sample tile structure information above (which based on a Y,X set of indices), the first column has a Y-offset of 0 since the upper left-most hexagon tile displayed for the first column begins at coordinate Y-position 0. The second column for the first row has a Y-offset of 36. This repeats itself for the entire first row of hexagon tile images being displayed.
When we move down a row, the offsets are increased by 72 and (36 + 72) respectively. This information is generated automatically for the tile structure array elements in the application.
The entire project and source code are freely available and can be downloaded from the following link:
Since the Myra.UI is used in this project, the version of this library that my project is using is also included in the download for your convenience. The Myra.UI library is also offered freely through the MonoGame forums.
If you have any questions or comments, feel free to email me at the address below.
Steve Naidamast
Sr. Software Engineer
blackfalconsoftware@outlook.com
