Introduction to the geometry of regular hexagons in the plane

    Defining a coordinate system
    When implementing moving around a map in games, it has recently become fashionable to use a
    regular hexagon (hex) for a space point. This really solves a large number of issues. For example, it does not require moving through the corners of the polygon. Six directions for movement is quite sufficient to convey the realism of movement.

    Coordinate system
    Fig. 1. Coordinate system
    Note that for fixing points on the map, the use of the Cartesian coordinate system so familiar to us becomes unprofitable, since the position of each individual cell becomes difficult to identify without using fractional values ​​in the coordinates, which complicates the calculations. Equally nontrivial will be the calculations of the distances between the cells, the calculation of the action of obstacles during the firing and with it. Thus, first you need to choose a convenient coordinate system. The fact that moving to a neighboring cell would correspond to a shift by a unit value along one axis of the coordinate grid would greatly simplify the calculations.
    Sectors
    Fig. 2. Sectors formed by coordinate axes
    Upon careful consideration of the options for the vector directions of the axes, the most convenient for me is the one where the angle between the directions of the axes corresponds to 120 °. 3 coordinate axes correspond to 6 directions of movement.
    Such a system is redundant, as long as each point in space
    can be described by an infinite number of ways, each of which becomes a trajectory of movement from the origin to a point, but the shortest path is described in a unique way by projecting onto the nearest coordinate axes. In fact, we get 6 sectors representing 3 pairs, in each of which the points located in them are described through 2 coordinate axes adjacent to it, as shown in Fig. 2.
    Point coordinates
    Fig. 3. Point coordinates
    In this representation, the coordinates of the points will be fixed as shown in Fig. 3.
    Convert coordinate to normal view
    Normal, we will call such a coordinate record when it describes the shortest path to it from the coordinate origin, which corresponds to projections onto nearby coordinate axes.

    To determine that the coordinate is in normal form, we can distinguish several properties inherent in it:
    • One of the 3 coordinates must be equal to 0, since the coordinates are recorded in the normal form through a projection on 2 axes.
      The other two coordinates should be in accordance: one> = 0, and the other <= 0 - since half of the two axes are adjacent to each of the sectors, one of which is always positive and the other negative.

      These properties are necessary and sufficient to verify that the coordinate is recorded in normal form.
      Unit shift in 3 coordinates
      Fig. 4. Unit shift in 3 coordinates
      Before solving the problem of normalizing coordinates, we pay attention to the following property of this coordinate system: a unit shift in all 3 coordinates brings us to the same point (Fig. 4). Based on this, we get the re-conversion:
      (x, y, z) = (x + c, y + c, z + c), where c is a constant

      Now, in order to get the normal view of the record, the coordinates of the point need only find 2 axes, the expression through which will give the minimum distance from the origin and bring according to the formula proposed above to the required form. We need to get
      (c1, c2, c3), where c2 = 0 and c1 <= c2 <= c3,

      which means that before the transformation we had
      c2 = c and c1 + c <= c2 + c <= c3 + c,

      it means that in the non-normalized record it is required to find such a coordinate so that its value is located between the values ​​of 2 others and subtract this value from all coordinates of the point.
      Calculation of the distance between points on the plane The
      coordinates of the points are given as the shortest path from the origin to the point, which means that the distance from the origin to the point is
      R0 = | x | + | y ​​| + | z |

      The difference of the point vectors gives the coordinate, which in the normal form corresponds to the distance between them.
      R = | x1-x2 | + | y1-y2 | + | z1-z2 |

      Finding Obstacles Between Points
      Now that we have discussed general issues, we can try to solve the problem that often arises in computer games with a card.
      A shot taken at a distance implies the possibility of hitting an obstacle that may be encountered along the way.
      Shot
      Fig. 5. Search for obstacles during a shot
      This sets us the task of finding an obstacle in which a projectile could fall. The problem has in general 2 approaches to the solution:
      1. Search for points of space where an obstacle can be located that can interfere with the movement of the projectile and check them;
        Enumeration of all obstacles in the location and check that they are not located on the line of fire.

        When considering this problem, I am inclined to the first solution, since the very first obstacle encountered along the course of the projectile’s movement, past which the projectile failed to fly, completes the solution to the problem, unlike the other approach.
        Thus, we do not always need to sort through all the points and all obstacles if we begin the path from the attacker.
        There is another argument for this approach. To check the effectiveness of a shelter (obstacle), you often need to know the distance to the shooter or victim.
        In the first case, we know it at any time and does not require calculations, and in the second, for each object satisfying the conditions of an obstacle, we need to calculate its distance from the shooter and the victim.
        Fig. 5. point A is the arrow, and B is the victim. Dots in which there may be an obstacle are marked in gray.
        The shift in the cells when passing along the "cell" line, which is the movement of the projectile, will occur in proportion to the shift along the coordinate axes. The third coordinate will not be used to solve this problem, because the shot vector will be in normal form. Since the shot starts from the middle of the cell and ends in the middle of the cell, the result will require rounding.
        y = y (AB) / x (AB) * x

        Summary
        In this review, I managed to consider only some of the particular moments encountered in games with a map, which was done in order to demonstrate a convenient coordinate grid.
        We note once again that the choice of such a coordinate system reduces most of the calculations to arithmetic. All coordinates are integers, provide a convenient opportunity to describe the character’s movement routes and clearly indicate the direction of movement.
        The cost of such a system can be considered its redundancy, which is offset by a simple rationing system.

    Also popular now: