How to implement movement along hexagon fields

Question

Hi all,

I want to create a simple board game with Godot where units can be moved along the borders of hexagon fields. What would be the most efficient data structure and implementation for this type of movement?
Each hexagon field and its 6 nodes could be stored in a dictionary, which then could be used for a basic pathfinding algorithm. Does already an automatic way to create such a dictionary for a specific map size exist? And what would be the simplest way to show the actual movement on the map from one node to another? Should I define NavigationPolygonInstances for the roads and move the sprites with getsimplepath and the moveandslide function from node to node? Are those NavigationPolygons useful at all in this case?

Answer 1

Hello,
You ask many questions and I need to Godot, but I think I can answer to 'What would be the most efficient data structure and implementation for this type of movement?. Each hexagon field and its 6 nodes could be stored in a dictionary, which then could be used for a basic pathfinding algorithm. Does already an automatic way to create such a dictionary for a specific map size exist? '

I don't recommend to store each node in a dictionary for all hexagons, since node are shared between hexagons. My advice is to get a sheet of paper and calculate some vectors than allow you to create the grid using for loops through the dimensions of the broad, later you might be able to perform the movements. I'm working in a project where the movement takes place between hexagons, not their edges, here is how I generate the grid (it's a 3D game):

var position : Vector3
var nodeToAdd : Node
for xi in range(xdim):
    for zi in range(zdim):
        if zi%2 == 0:
            position = Vector3(xi*General.v0.x, 0, zi*General.v1.z)
        else:
            position = Vector3(xi*General.v0.x+General.v0.x/2, 0, zi*General.v1.z)
        nodeToAdd = Tile.instance()
        nodeToAdd.translation = position
        nodeToAdd.hexTranslation = Vector3(xi, 0, zi)
        nodeToAdd.changeCenter(MapTiles.centerMaterialKeys[0])
        scenarioTiles.add_child(nodeToAdd)

Where I use vectors General.v0 and General.v1 to obtain the translation and I do some unrelevant thing to your problem.

I think the best option is to store the edges/hexagons as children of another node, in my code scenarioTiles is a Spatial node containing all tiles so I can use a for loop getting its children and make things with them.

This might help you (it's about moving between hexagons, not their edges):
https://www.redblobgames.com/grids/hexagons/