August 5, 2011 at 17:27Finding a path on a hexagonal grid
In fact, I won’t reveal anything new to anyone, but what I found was with tricky mathematics (more precisely, not so tricky, but still difficult for me personally to understand), and here it seemed to be my own bike.
And so what we already have:
Search on a regular rectangular grid.
What we need:
Search the hexagonal grid with minimal effort.
The first idea is simply to shift everything through the column:
Then the neighbors of the current cell look something like this:
As you can see, the connections between the cells should form just a hex: in theory, it
immediately creeps in that there should be no squares at all, but rectangles:
How not it is difficult to calculate k in the figure it will be equal to sqrt (3) / 2
As a result, we get a grid
where the sizes of each cell are respectively w = sqrt (3) / 2, h = 1, and each odd column (if you start counting from 0) is shifted by 0 ,5
Then everything goes easier to translate the coordinates into the cell number, adjusted for an even / odd column:
To vice versa, translate the field cell into coordinates:
Now we need to get all the neighbors of the selected cell.
They will look something like this for even columns (and symmetrical for odd columns).
Now, for a full-fledged implementation, only the way to find the distance between two cells is lacking, of course you can use the trivial Euclidean, but this is not our option. For the basic basis, we take the diagonal distance on a regular grid: Our situation is similar (there are also diagonal moves), only to shift vertically (considering the grid orientation as in the example), you can either take one step vertically or 2 horizontally. But there is a small detail here, if the distance is measured between two cells from different columns, then there will be an unaccounted displacement into the floor of the cell. Therefore, yd must be defined a little differently: Now it remains to set A * on it all, for example, as I did here , and tadam:
Of course, there are more beautiful mathematical methods for manipulating the hexagonal grid, but in my opinion this method turned out to be simple enough to have the right to life (and the plus in the performance test showed quite good results).
And so what we already have:
Search on a regular rectangular grid.
What we need:
Search the hexagonal grid with minimal effort.
General grid structure
The first idea is simply to shift everything through the column:
Then the neighbors of the current cell look something like this:
As you can see, the connections between the cells should form just a hex: in theory, it
immediately creeps in that there should be no squares at all, but rectangles:
How not it is difficult to calculate k in the figure it will be equal to sqrt (3) / 2
As a result, we get a grid
where the sizes of each cell are respectively w = sqrt (3) / 2, h = 1, and each odd column (if you start counting from 0) is shifted by 0 ,5
Coordinate transformation
Then everything goes easier to translate the coordinates into the cell number, adjusted for an even / odd column:
(x,y)=>(x/w, (y-(x/w)%2)/h)To vice versa, translate the field cell into coordinates:
(i,k)=>(i*w, k*h+h/2*(i%2))Neighbors
Now we need to get all the neighbors of the selected cell.
They will look something like this for even columns (and symmetrical for odd columns).
(i,k)=>(
(i+1,k),
(i-1,k),
(i,k+1),
(I,k-1),
(i+1,k+(1-2*i%2)),
(i-1,k+(1-2*i%2)))
Distance between two cells
Now, for a full-fledged implementation, only the way to find the distance between two cells is lacking, of course you can use the trivial Euclidean, but this is not our option. For the basic basis, we take the diagonal distance on a regular grid: Our situation is similar (there are also diagonal moves), only to shift vertically (considering the grid orientation as in the example), you can either take one step vertically or 2 horizontally. But there is a small detail here, if the distance is measured between two cells from different columns, then there will be an unaccounted displacement into the floor of the cell. Therefore, yd must be defined a little differently: Now it remains to set A * on it all, for example, as I did here , and tadam:
xd = abs(p1.X - p2.X);
yd = abs(p1.Y - p2.Y);
diagonal = min(xd, yd);
straight = xd + yd;
result = sqrt(2) * diagonal + (straight - (2 * diagonal)));
//если хватает горизонтального расстояния
if (xd >= yd * 2)
{
result = xd;
}
//если всеже придется идти строго вверх
else
{
result = xd + (yd – xd/2);
}
yd =abs((p1.Y + (p1.X%2)/2) – (p2.Y + (p2.X%2)/2));Instead of an afterword
Of course, there are more beautiful mathematical methods for manipulating the hexagonal grid, but in my opinion this method turned out to be simple enough to have the right to life (and the plus in the performance test showed quite good results).