Applying A* Pathfinding with Tilemap and Hexagonal

[Opache]

I’ve been working on implementing A* Pathfinding onto my hexgrid tile map. They are flat tops.

I have gone through and added a point to each hextile and then connected those tiles. However, I came across an issue. I have specifically mentioned in my code which are the neighbour tile co-ordinates:

var neighbour_cells = [Vector2i(1,0), Vector2i(1,-1), Vector2i(0,-1), 
					Vector2i(-1,0), Vector2i(-1,1), Vector2i(0,1)]

Seems like it should work, but I will notice that sometimes it will connect tiles from a ‘further’ distance than it should. I’ve then added in the co-ordinates of each tile to see what was going on.

As you can see above, with the tile at 2,1 it will not connect to the tile at 3,-1 because that is 1,-2 and not included in the neighbour cells to check for. However, the 3,1 tile will include the 4,0 because according to the neighbour cells, it is a neighbour.

Looking at the tile 4,3 it does correctly need to connect to the tile at 5,2 (so the neighbour cell of 1,-1 is correct to check for) and the problem from above doesn’t exist here as it will not connect to 5,1

What do I need to do to ensure that a proper neighbour at 1,-1 is included but when it is essentially ‘two’ tiles away, it isn’t included?

[Sduic]

I think the problem is that, in your coordinate system, the offsets of the cell neighbours vary with the column parity.

You’ll need two sets of offsets:

Even:
[[+1, 0], [+1, -1], [ 0, -1], [-1, -1], [-1, 0], [ 0, +1]],

Odd:
[[+1, +1], [+1, 0], [ 0, -1], [-1, 0], [-1, +1], [ 0, +1]],

See https://www.redblobgames.com/grids/hexagons/#neighbors-offset for further details.

(I believe your coordinates are of the type “odd-q” on that site.)

[Opache]

Thanks shrooms and sduic.

While I could understand what the documents were trying to say, I wasn’t really sure how to apply it to my code shrooms but it did make me go and re-evaluate the Godot documentation and I came across this here:

TileSet

Specifically the enum CellNeighbor

I was able to manually check all neighbours like this:

for tile in all_walkable_tiles:
		var neighbour_cells = []
		var directions = [
			TileSet.CELL_NEIGHBOR_TOP_SIDE,
			TileSet.CELL_NEIGHBOR_TOP_RIGHT_SIDE,
			TileSet.CELL_NEIGHBOR_TOP_LEFT_SIDE,
			TileSet.CELL_NEIGHBOR_BOTTOM_SIDE,
			TileSet.CELL_NEIGHBOR_BOTTOM_RIGHT_SIDE,
			TileSet.CELL_NEIGHBOR_BOTTOM_LEFT_SIDE
		]

		for direction in directions:
			var neighbour_coords = get_neighbor_cell(tile,direction)
			if all_walkable_tiles.has(neighbour_coords):
				neighbour_cells.append(get_neighbor_cell(tile, direction))

It’s a little rough, but it does the trick

I did originally come across the article you linked Sduic and I had those neighbours in there but I still came across the same problem, so I am not sure. Luckily in this case the engine had a solution it seems.