Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><img src="https://i.stack.imgur.com/9m62y.png" alt="hexagonal and orthogonal grids "></p> <h2>What is a hexagonal grid?</h2> <p>What you can see above are the two grids. It's all in the way you number your tiles and the way you understand what a hexagonal grid is. The way I see it, a hexagonal grid is nothing more than a deformed orthogonal one.</p> <p>The two hex tiles I've circled in purple are theoretically still adjacent to <code>0,0</code>. However, due to the deformation we've gone through to obtain the hex-tile grid from the orthogonal one, the two are no longer <em>visually</em> adjacent. </p> <h2>Deformation</h2> <p>What we need to understand is the deformation happened in a certain direction, along a <code>[(-1,1) (1,-1)]</code> imaginary line in my example. To be more precise, it is as if the grid has been elongated along that line, and <em>squashed</em> along a line perpendicular to that. So naturally, the two tiles on that line got spread out and are no longer visually adjacent. Conversely, the tiles <code>(1, 1)</code> and <code>(-1, -1)</code> which were diagonal to <code>(0, 0)</code> are now unusually close to <code>(0, 0)</code>, so close in fact that they are now <em>visually adjacent</em> to <code>(0, 0)</code>. Mathematically however, they are still diagonals and it helps to treat them that way in your code.</p> <h2>Selection</h2> <p>The image I show illustrates a radius of 1. For a radius of two, you'll notice <code>(2, -2)</code> and <code>(-2, 2)</code> are the tiles that should not be included in the selection. And so on. So, for any selection of radius <strong>r</strong>, the points <code>(r, -r)</code> and <code>(-r, r)</code> should not be selected. Other than that, your selection algorithm should be the same as a square-tiled grid.</p> <p>Just make sure you have your axis set up properly on the hexagonal grid, and that you are numbering your tiles accordingly.</p> <h2>Implementation</h2> <p>Let's expand on this for a bit. We now know that movement along any direction in the grid costs us 1. And movement along the <em>stretched</em> direction costs us 2. See <code>(0, 0)</code> to <code>(-1, 1)</code> for example.</p> <p>Knowing this, we can compute the shortest distance between any two tiles on such a grid, by decomposing the distance into two components: a diagonal movement and a straight movement along one of the axis. For example, for the distance between <code>(1, 1)</code> and <code>(-2, 5)</code> on a normal grid we have:</p> <pre><code>Normal distance = (1, 1) - (-2, 5) = (3, -4) </code></pre> <p>That would be the distance vector between the two tiles were they on a square grid. However we need to compensate for the grid deformation so we decompose like this:</p> <pre><code>(3, -4) = (3, -3) + (0, -1) </code></pre> <p>As you can see, we've decomposed the vector into one diagonal one <code>(3, -3)</code> and one straight along an axis <code>(0, -1)</code>.</p> <p>We now check to see if the diagonal one is along the deformation axis which is any point <code>(n, -n)</code> where <code>n</code> is an integer that can be either positive or negative. <code>(3, -3)</code> does indeed satisfy that condition, so this diagonal vector is along the deformation. This means that the length (or cost) of this vector instead of being <code>3</code>, it will be double, that is <code>6</code>.</p> <p>So to recap. The distance between <code>(1, 1)</code> and <code>(-2, 5)</code> is the length of <code>(3, -3)</code> plus the length of <code>(0, -1)</code>. That is <code>distance = 3 * 2 + 1 = 7</code>.</p> <h2>Implementation in C++</h2> <p>Below is the implementation in C++ of the algorithm I have explained above:</p> <pre><code>int ComputeDistanceHexGrid(const Point &amp; A, const Point &amp; B) { // compute distance as we would on a normal grid Point distance; distance.x = A.x - B.x; distance.y = A.y - B.y; // compensate for grid deformation // grid is stretched along (-n, n) line so points along that line have // a distance of 2 between them instead of 1 // to calculate the shortest path, we decompose it into one diagonal movement(shortcut) // and one straight movement along an axis Point diagonalMovement; int lesserCoord = abs(distance.x) &lt; abs(distance.y) ? abs(distance.x) : abs(distance.y); diagonalMovement.x = (distance.x &lt; 0) ? -lesserCoord : lesserCoord; // keep the sign diagonalMovement.y = (distance.y &lt; 0) ? -lesserCoord : lesserCoord; // keep the sign Point straightMovement; // one of x or y should always be 0 because we are calculating a straight // line along one of the axis straightMovement.x = distance.x - diagonalMovement.x; straightMovement.y = distance.y - diagonalMovement.y; // calculate distance size_t straightDistance = abs(straightMovement.x) + abs(straightMovement.y); size_t diagonalDistance = abs(diagonalMovement.x); // if we are traveling diagonally along the stretch deformation we double // the diagonal distance if ( (diagonalMovement.x &lt; 0 &amp;&amp; diagonalMovement.y &gt; 0) || (diagonalMovement.x &gt; 0 &amp;&amp; diagonalMovement.y &lt; 0) ) { diagonalDistance *= 2; } return straightDistance + diagonalDistance; } </code></pre> <p>Now, given the above implemented <code>ComputeDistanceHexGrid</code> function, you can now have a naive, unoptimized implementation of a selection algorithm that will ignore any tiles further than the specified selection range:</p> <pre><code>int _tmain(int argc, _TCHAR* argv[]) { // your radius selection now becomes your usual orthogonal algorithm // except you eliminate hex tiles too far away from your selection center // for(x-range;x+range;x++); for(y-range;y+range;y++); Point selectionCenter = {1, 1}; int range = 1; for ( int x = selectionCenter.x - range; x &lt;= selectionCenter.x + range; ++x ) { for ( int y = selectionCenter.y - range; y &lt;= selectionCenter.y + range; ++y ) { Point p = {x, y}; if ( ComputeDistanceHexGrid(selectionCenter, p) &lt;= range ) cout &lt;&lt; "(" &lt;&lt; x &lt;&lt; ", " &lt;&lt; y &lt;&lt; ")" &lt;&lt; endl; else { // do nothing, skip this tile since it is out of selection range } } } return 0; } </code></pre> <p>For a selection point <code>(1, 1)</code> and a range of <code>1</code>, the above code will display the expected result:</p> <pre><code>(0, 0) (0, 1) (1, 0) (1, 1) (1, 2) (2, 1) (2, 2) </code></pre> <h2>Possible optimization</h2> <p>For optimizing this, you can include the logic of knowing how far a tile is from the selection point (logic found in <code>ComputeDistanceHexGrid</code>) directly into your selection loop, so you can iterate the grid in a way that avoids out of range tiles altogether.</p>
    singulars
    1. This table or related slice is empty.
    1. POHexagonal tiles and finding their adjacent neighbours
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USEd Rowlett-Barbu
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POHexagonal tiles and finding their adjacent neighbours
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload