HexGrid: get fields in line (not even AI could solve)

Unity Engine
,
1

Hello everyone

I have tried for 8 hours now to get this working, with and without the help of AI and whatever I do, it doesn’t work although it should be easy af. Possibly have been sitting in front of it for too long =.=

I have a hexgrid where north and south are the easy directions (no change in x-coord) and left/right have 2 possibilites each.

The method I want and couldn’t get to work is one that gives me all the HexTiles in a line starting from srcTile via neighborTile. It’s only possible to have one of the 6 neighbors as second argument.

    public static class Direction {

        public static List<Vector3Int> directionsOffsetOdd = new List<Vector3Int>() {
            new Vector3Int(0,0,1), // N
            new Vector3Int(0,0,-1), // S
            new Vector3Int(-1,0,0), // W1
            new Vector3Int(-1,0,-1), // W2
            new Vector3Int(1,0,0), // E1
            new Vector3Int(1,0,-1), // E2
        };

        /** muss noch herausfinden, wie ich das einbinden/ändern muss */
        public static List<Vector3Int> directionsOffsetEven = new List<Vector3Int>() {
            new Vector3Int(0,0,1), // N
            new Vector3Int(0,0,-1), // S
            new Vector3Int(-1,0,0), // W1
            new Vector3Int(-1,0,1), // W2
            new Vector3Int(1,0,0), // E1
            new Vector3Int(1,0,1), // E2
        };

        public static List<Vector3Int> getDirectionList(int x) {
            return x % 2 == 0 ? directionsOffsetEven : directionsOffsetOdd;
        }       
    }

A small visualisation of how the field looks

hex terror
hex terror1467×512 182 KB

Expected results would be
1,3–>2,2 (lower right) should return (2,2),(3,2),(4,1),(5,1) (blue frames)
1,2–>2,1 (lower right) should return (2,1),(3,1),(4,0)
0,2–>1,2 (lower right) should return (1,2),(2,1),(3,1),(4,0)
2,0–>3,1 (upper right) should return (3,1),(4,1),(5,2),(6,2) (orange frames)

    public List<HexTile> getTilesInDirection(HexTile sourceTile, HexTile neighborTile, int range) {
        List<HexTile> tilesInDirection = new List<HexTile>();

        (int deltaX, int deltaZ) = getDelta(sourceTile, neighborTile);

        List<Vector3Int> directionOffsets = Direction.getDirectionList(sourceTile.getHexCoords().x); // oder sourceTile.r, je nach deinem Koordinatensystem

        int directionIndex = -1;
        for (int i = 0; i < directionOffsets.Count; i++) {
            if (directionOffsets[i].x == deltaX && directionOffsets[i].z == deltaZ) {
                directionIndex = i;
                break;
            }
        }

        if (directionIndex == -1) return tilesInDirection; // invalid dir

        tilesInDirection.Add(neighborTile);

        HexTile currentTile = neighborTile;

        for (int i = 1; i < range; i++) {
            directionOffsets = Direction.getDirectionList(currentTile.getHexCoords().x);
            // Suche die Richtung in der Direction-Liste
            directionIndex = -1;
            for (int fff = 0; fff < directionOffsets.Count; fff++) {
                if (directionOffsets[fff].x == deltaX && directionOffsets[fff].z == deltaZ) {
                    directionIndex = fff;
                    break;
                }
            }
            if (directionIndex == -1) return tilesInDirection;            

            int nextQ = currentTile.getHexCoords().x + directionOffsets[directionIndex].x;
            int nextR = currentTile.getHexCoords().z + directionOffsets[directionIndex].z;

            HexTile nextTile = GetTileAt(nextQ, nextR);
            if (nextTile != null) tilesInDirection.Add(nextTile);
        }

        return tilesInDirection;
    }

    private (int deltaX, int deltaZ) getDelta(HexTile sourceTile, HexTile neighborTile) {
        int deltaX = neighborTile.getHexCoords().x - sourceTile.getHexCoords().x;
        int deltaZ = neighborTile.getHexCoords().z - sourceTile.getHexCoords().z;
        return (deltaX, deltaZ);
    }

This method is an abomination right now and was mostly written by the AI. I tried to insert a correcting factor and somehow the mistake must be connected with the alternating directionOffsets. Take note of the expected results and how z is diminished only every second time.
Currently, from 1/3 to 2/2, I get 2/2 and 3/1.

I’m sure there’s a few people who already wrote this kind of method, just take care about the orientation (north/south = easy) and coordinate-system. Currently, I’m giving up on this.

Maybe an even more helpful function would get some kind of a “shape” that could also be rotated according to src and neighborTile. Currently, I only started with a straight line, but different shapes are actually already in the back of my head. Did someone already make something like this?

Hope you can help, thank you :slight_smile:

2

For simplicity, just use A*.
Problem solved.

1 Like
3

As Anty points out, use Astar, then the shape of your map is irrelevant: you will produce a graph from that state and a hex simply means that nodes by default have 6 connections not 4, and AStar doesn’t care at all.

Here’s some resources on getting comfortable with hexagonal maps (hexmaps):

2 Likes
4

At least for a line, it is: If each tile has an array of references to six neighbors that go around the tile in order, then you simply get the index of the neighborTile in the srcTile’s array, and that is the “direction” you travel for all subsequent tiles. In other words, you use the index of the neighborTile in the srcTile’s array to iteratively walk down tiles until you reach a tile with no neighborTile set for that index, which means you’ve reached the end of the line.

So, for example, assume the array starts at the top of the tile and goes around it clockwise:
image

Then the “directions” for your examples would be:
1,3–>2,2 ==> 2
1,2–>2,1 ==> 2
0,2–>1,2 ==> 2
2,0–>3,1 ==> 1

I’m going to assume you mean “shapes” as in paths that go in the direction of the srcTile to neighborTile. You would define these paths by saying when (and by how many tiles) to turn left or right. For example, you could have a zig-zag path that turns left or right every two tiles. On your first example, that would look like this:

image
image1467×512 72.1 KB

5

What do you mean, Use A*?
I already used an implementation for finding paths, that’s not the problem.
Afaik, A* has nothing to do with defining “shapes” (like: from src to lower right, to lower right, (to lower right and upper right).

The problem is properly defining the direction from a srcTile.

6

Okay, I think I see what you mean. We can do this instead (similar to what’s in your OP):
image

So the direction of srcTile to neighborTile would be:

direction_x = neighbor_x - src_x;
direction_y = (direction_x == 0) ? neighbor_y - src_y : (neighbor_y - src_y + src_x % 2);

And the next tile after the current tile in that direction would be:

current_y += (direction_x == 0) ? direction_y : direction_y - current_x % 2;
current_x += direction_x;

Here’s a demo of that (you can run it on Online C# Compiler (Editor) - Programiz):

// HexGrid demo

using System;

public class HexGrid
{
    public static void Main()
    {
        // Set srcTile, neighborTile, and number of steps to walk
        int srcTile_x = 1, srcTile_y = 3;
        int neighborTile_x = 2, neighborTile_y = 2;
        int stepCount = 4;
        
        // Get direction from srcTile to neighborTile
        int dx, dy;
        GetDirection(srcTile_x, srcTile_y, neighborTile_x, neighborTile_y, out dx, out dy);
        Console.WriteLine ($"Direction: ({dx}, {dy})");
        
        // Walk tiles in the direction starting from srcTile
        int cx = srcTile_x, cy = srcTile_y; for (int i = 0; i < stepCount; i++)
        {
            // Get next tile
            GetNextTile(ref cx, ref cy, dx, dy);
            Console.WriteLine ($"Step {i + 1}: ({cx}, {cy})");
        }
        
    }
    
    // Gets the direction of *neighboring* tiles
    // Range of X coordinate is [-1,1], where -1 = left, 0 = none (vertical), 1 = right
    // Range of Y coordinate is [-1,1], where -1 = down, 1 = up
    static void GetDirection(int sx, int sy, int nx, int ny, out int dx, out int dy)
    {
        dx = nx - sx;
        dy = (dx == 0) ? ny - sy : (ny - sy + sx % 2);
    }
    
    // Gets the next tile after the current tile in the given direction
    static void GetNextTile(ref int cx, ref int cy, int dx, int dy)
    {
        cy += (dx == 0) ? dy : dy - cx % 2;
        cx += dx;
    }
}

Tested this with all directions, and they all match your grid and examples. Should also work with direction changes, so you can make paths & shapes just by changing the direction as you walk.

7

Well, the main issue here is that you have a hex grid but you’re just using a vector with -+1 values at max as if you are on a rectangular grid. This doesn’t work. Have a look at the image I posted on this old answer.

First of all the distances on the rectangular grid do not have the same distances. also as you can see when applying a 4 step grid in one direction and a 2 step in the other, the hex cells are 1 unit apart in the 2 step direction and 3 steps apart in the 4 steps direction.

8

Thank you so much!!
Could you explain why GetDirection() and GetNextTile() both use a modulo operator? I don’t really understand why it works, but it does!

Edit: Gives a wrong result for (1,2) to (1,1) (it gives 0,0 for dx, dy in GetTilesInDirection()) :frowning:
I changed it a bit, now this seems to work in all direction.

    public List<HexTile> getTilesInDirection(HexTile sourceTile, HexTile neighborTile, int range) {
        List<HexTile> tilesInDirection = new();

        int dx, dz; // Get direction from srcTile to neighborTile
        getDirectionOfNeighboringTile(sourceTile.getX(), sourceTile.getZ(), neighborTile.getX(), neighborTile.getZ(), out dx, out dz);

        // Walk tiles in the direction starting from srcTile
        int cx = sourceTile.getX(), cz = sourceTile.getZ();
        for (int i = 0; i < range; i++) {
            getNextTileCoords(ref cx, ref cz, dx, dz);
            HexTile nextTile = GetTileAt(cx, cz);
            if (nextTile != null) tilesInDirection.Add(nextTile);
        }

        return tilesInDirection;
    }

    // Gets the direction of *neighboring* tiles
    // Range of X coordinate is [-1,1], where -1 = left, 0 = none (vertical), 1 = right
    // Range of Y coordinate is [-1,1], where -1 = down, 1 = up
    static void getDirectionOfNeighboringTile(int sx, int sz, int nx, int nz, out int dx, out int dz) {
        dx = nx - sx;
        dz = (dx == 0) ? nz - sz : (nz - sz + (sx % 2)); // <<<<<< Change here
    }

    /** Beim Errechnen der nächsten Tile, wenn ich einer Linie folge (dx,dz) */
    static void getNextTileCoords(ref int cx, ref int cz, int dx, int dz) {
        cx += dx;
        cz += (dx == 0) ? dz : dz - ((cx + 1) % 2);  // <<<<<< Change here
    }

Again, thanks a lot for your help

1 Like
9

Oops, yeah, I didn’t convert the vertical-down direction to -1. Thanks for the fix; I’ll add it to my code.

You’re welcome!

The modulo there is to get whether the number is even or odd: an even number will return a 0, and an odd number will return a 1. When moving sideways on your grid, only tiles with an even x coordinate increment the y coordinate when going up, and only tiles with an odd x coordinate decrement the y coordinate when going down. So the modulo is used to switch on or off the incrementing/decrementing based on whether the current tile’s x coordinate is even or odd.

10

This is why cubic coordinates are better.

Line drawing

11

Whoever reads this and wants to implement a hexgrid system: don’t code it yourself :wink:
My system with x,z coords was unfortunately already in place because I thought it couldn’t be too difficult. Well … reminder to myself: it is more complicated than it looks :wink:

12

Well your last sentence contradicts your first sentence. The reason why you discovered this is exactly because you coded it yourself. It’s a learning experience and this is inevitably what makes you a better programmer in the long run, so it’s futile to advise others to be safe and stay inexperienced.

To be perfectly honest with you, a cursory glance on the internet would’ve given you ample information on the subject before trying to implement any of it. Hex grids are everywhere, there are zillion articles, videos, and tutorials. When I decided to build a hex grid system I used cubic coordinates right from the get go. The X,Z coordinates are only ever useful to actually show or serialize the coordinates, but internally you want something more robust than that.

1 Like