🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Hex to Hex Distance

Started by
5 comments, last by Alberth 2 years ago

I am stubbing out some distance code which calculates the distance from one hex center to the next hex center, my only problem is that I get a complier error of “expression must have pointer-to-object type,” this error appears at the “col” variable in the map array here is my stubbed-out code.

	int *closest = nullptr;
	int numRows = 10;
	int numCols = 10;
	int mouseClickX = 5;
	int mouseClickY = 5;
	int *map = 0;
	int fromClosestCenterToClick = INT_MAX;
	for (int row = 0; row < numRows; row++)
	{
		for (int col = 0; col < numCols; col++)
		{
			int distance = sqrt(pow(map[row][col]->center.x - mouseClickX, 2)+pow(map[row][col]->center.y-mouseClickY,2) < fromClosestCenterToClick);
			if (distance < fromClosestCenterToClick)
			{
				closest = map[row][col];
				fromClosestCenterToClick = distance;
			}
		}
	}
Advertisement

You describe code “which calculates the distance from one hex center to the next hex center” but it seems like you are looking at a location of a mouse click (stored in mouseClickX and mouseClickY), and trying to find the nearest hex center to that point, and then getting the distance from that mouse point to the nearest hex center. That is not the "distance from one hex center to the next hex center.” (unless your mouse happens to click in the next hex center) I mention this fact because you need to know what you want to do before you can do it.

Getting to more specific problems with the code. . .

When you set up things as

int *map = 0;

That is a pointer to an int, and you've set it to 0 (which is setting it to NULL).

If you try to use an int pointer in the following way “ map[row][col]->center.x ” that will lead to problems.

Also “map” is a data storage type (which you can read about here, if you want), so I suggest not calling your variable by that name. You should probably use some other variable name instead (like maybe HexGrid).

Anyway, if you want a 2D array, you need to either set that up as follows. . .

int HexGrid[10][10];

Or if you want to allocate a 2D array dynamically, you can set it up as follows. . .

int ** HexGrid;

However, no matter how you set it up, if you're dealing with a 2D array of integers, you don't want to reference it as follows “map[row][col]->center.x”

That way of referencing the data looks like you're dealing with a 2D array of pointers to some type of hex struct, but that is not a good way to deal with an array of integers or integer pointers.

It seems you do not know how to declare a pointer to a 2D array.
Some example:

int myMap[100][100];
int (*myPointer)[100] = myMap; // We must tell the compiler we are pointing at an array of size 100 for its first dimension. 
myPointer[5][20] = 1; // now we can access elements, but our pointer can not be used so we know the 2d coordinates (5,20) to our matrix

I'm not sure, but i think there is no nice way to encode map coordinates into a single pointer.

So i propose you use something like:

int closestX, closestY; // two indices instead one pointer for our 2D coordinates
for (x...) 
for (y...)
if (closer) {closestX = x; closestY = y;} 

It's issues like this, why i personally never use multidimensional arrays.
Instead i use one dimensional arrays for everything, and care about 2D indexing myself:

int myMap[100 * 100];
int  y=5, x=20;
myMap[y*100 + x] = 1;

Makes things easier, not harder. And when i learned C, this was even advised for performance reasons.

If we use power of two array dimensions, we can replace multiplications and expensive divisions with bit shifts:

int myMap = 256 * 256;
int  y=5, x=20;
myMap[(y<<8) | x] = 1;

Now we can efficiently encode coordinates into a single integer number:

int  y=5, x=20;
int index = (y<<8) | x;
myMap[index] = 1;

//convert back:
int myY = index >> 8;
int myX = index & 0xff;

So this finally is fast and convenient to use, but you need to be used at bit math.

pbivens67 said:

	for (int row = 0; row < numRows; row++)
	{
		for (int col = 0; col < numCols; col++)
		{
			int distance = sqrt(pow(map[row][col]->center.x - mouseClickX, 2)+pow(map[row][col]->center.y-mouseClickY,2) < fromClosestCenterToClick);

This code is very very bad. It exposes you did not mind to optimize anything.

First: To find a closest point out of many, we do NOT need a expensive square root! No - we work with squared distances directly. If a < b, then aa < bb as well, as long as our numbers are all positive, which they are.
If we need the distance to the closest point, we calculate it only AFTER the closest point has been found. That's one sqrt vs. 10000 sqrt for the same result.

Second: The whole idea of searching a grid to find a closest cell is ridiculous. Instead we transform our search coordinate to the domain of the grid, and then round the transformed coordinates to get our cell indices directly! That's O(1) vs. O(N^2), so the speedup is huge.
For a regular grid, the transformation is usually a simple scale and an offset, eventually a rotation as well.
For a skewed grid like in hex games the transformation also contains a sheer, which makes it more difficult to set the transformation up.

At this point, a linear math library like glm would become very handy. You could use ivec2 for grid indices, vec2 for coordinates, and a 3x3 matrix for the transformation.
For example, to get the inverse transform from skewed hex space to index space you could just invert your matrix to do this. No need to figure out all the math again the other way around.

But that's optional. What you really need is to look up on hex grid conventions, indexing, etc.
Found a tutorial here, usually the site is a good resource: https://www.redblobgames.com/grids/hexagons/

However, all this information we give is useless, as long as you do not get the really important things right.

I think you treat programming as an exercise to make a computer do something you want.
But that's only half of it.
You do not only write code so it works for the computer - you MAINLY write code for yourself, so YOU (or others) can work with it. So it can be further developed. ← That's the most important aspect, which you seemingly missed your whole life long.
Which means your teachers sucked at their job, or they really tried, gave up, but did let you slip still for whatever reason.

You must change this. You may think you are too old to do changes. But there is no other way. The alternative is to keep wasting time with no outcome. You decide.

Ok, now let's make an example of what situation we we would have if you had taken my advice of yesterday serious:

class HexGrid
{
	int *cellData; // can be std::vector, or two dimensional array... whatever
	int width, weight;
	float originInWorldspace[2]; // ... and whatever we need to define our map space
	
	// We add our conversation functions here:
	
	void WorldSpaceToHexGrid (int hexGrid[2], const float worldSpaceCoords[2]);
	void HexGridToWorldSpace (float worldSpaceCoords[2], const int hexGrid[2]);
};
TankGame::ProcessUserInput (HexGrid &myHexMap, Tank &playerTank)
{
	float cursorInWorldSpace[2];
	ConvertMouseCoordsToWorldSpace(cursorInWorldSpace, mouseX, mouseY); // yes - we made such cool tool function as well somewhere, eventually
	
	int hooveredHexGrid[2];
	myHexMap WorldSpaceToHexGrid (hooveredHexGrid, cursorInWorldSpace); 
	// i call this usefull function also from game logic update, physics update, rendering, and dozens of other stuff :) 
	// Thus i never need to think about annoying mapping of world space to grid space again! :D 
	
	if (mouseButtonClicked)
	{
		playerTank.SetGoal (hooveredHexGrid); 
	}
}

Notice: Once i have those nasty conversation helper functions, problem solved, and i use them to move tanks, map mouse pos to grid, and anything else.

But you do not. You may think: ‘I'll do those functions eventually later. Right now, all i want is to find the hex tile where the mouse pointer is.’

I can understand this, and sometimes i do the same thing, even i know i should not.
But seemingly you ALWAYS go this ‘one problem after another' route, so you have no real progress, and you do not build up a code base which provides you with tools and solutions of frequent problems.
You solve the same problems again and again with slight variations, even if it leads to terribly inefficient solutions as you have just shown.
And something stupid like a compiler error becomes your new ‘actual problem’, so let's make a new post and ask for help.
Then you fix the error, and it finally works, so it is done and fine.

But it is not fine, because you have achieved nothing to help you with the work still ahead of you!
Code for yourself, not for the calculator machine in front of you.

JoeJ said:
If we use power of two array dimensions, we can replace multiplications and expensive divisions with bit shifts:

Just multiply and divide by power of 2 values as well then. Compilers have progressed in the 40 years or so that they exist. They know about these things.

This topic is closed to new replies.

Advertisement