# Making A* pathfinding work for hexagons (Complex)

WARNING: This is a lot of math and requires a high level of coding. I’ve been struggling at this for about half a week now.

I found an A* pathfinding script and imported it into my game. On a grid of squares it works flawlessly. I’m using hexagons. The issue is that moving from tile to tile makes the unit move in a zig-zag pattern, and I want it to move in a straight line. I can handle optimizing the amount of pathfinding points, I just need the points to be in a realistic position. There’s a video below that shows the zigzagging pattern I’m talking about.

The script I’m using to do this was not written by me, but I rewrote a bit of the code to work for my game. I’ll be honest, I don’t understand how much of the math works and why. I’ve tried looking stuff up online but there isn’t much about A* pathfinding, and if it is it’s usually not Roblox.

Here is the pathfinder script:

``````function Service:CanTraverse(tile)
if not tile then
return false
end

if tile.Tags.HasWater.Value then
return false
end

if tile.Data.Blocked.Value then
return false
end

return true
end

function Service:IsLineClear(nodeA, nodeB)
local grid = self.Grid

-- Define the offsets for the six neighboring hexagons
local offsets = {{-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}}

-- Calculate the x and z distances between the two nodes
local dx = nodeB.X - nodeA.X
local dz = nodeB.Z - nodeA.Z

-- Calculate the axial distances between the two nodes
local ax1 = nodeA.X
local az1 = nodeA.Z - math.floor((nodeA.X + 1) / 2)
local ax2 = nodeB.X
local az2 = nodeB.Z - math.floor((nodeB.X + 1) / 2)

-- Use a modified version of Bresenham's line algorithm to calculate the hexagons that the line passes through
local x, z = ax1, az1
local xstep, zstep = dx > 0 and 1 or -1, dz > 0 and 1 or -1
local longest, shortest = math.abs(dx), math.abs(dz)
if longest < shortest then
longest, shortest = shortest, longest
xstep, zstep = zstep, xstep
end
local numerator = longest * 0.5
for i = 0, longest - 1 do
if not self:CanTraverse(grid[x][z]) then
--return false
end
numerator = numerator + shortest
if numerator >= longest then
numerator = numerator - longest
x = x + xstep
z = z + zstep
else
x = x + xstep
end
end

return true
end

-- Define the function to get the neighbors of a node
function Service:GetNeighbors(node)
local grid = self.Grid
local neighbors = {}

-- Define the offsets for the six neighboring hexagons
local offsets = {{-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}}

-- Loop through the six neighboring hexagons
for _, offset in ipairs(offsets) do
-- Get the neighbor's position
local x = node.X + offset[1]
local z = node.Z + offset[2]

-- Check if the neighbor is within the grid
if grid[x] and grid[x][z] then
local neighbor = Node.new(x, z)
-- Check if the line between the current node and the neighbor is clear
if self:IsLineClear(node, neighbor) then
-- Check if the neighbor can be traversed
if self:CanTraverse(grid[x][z]) then
table.insert(neighbors, neighbor)
end
end
end
end

return neighbors
end

-- Define the function to get the path from the start node to the end node
function Service:GetPath(startNode, endNode)
-- Create the path list
local path = {}

-- Add the end node to the path list
table.insert(path, endNode)

-- Loop through the nodes' parents until the start node is reached
local currentNode = endNode
while currentNode.Parent do
table.insert(path, 1, currentNode.Parent)
currentNode = currentNode.Parent
end

return path
end

-- Define the function to find the optimal path between the start and end nodes
function Service:FindPath(start:Vector2, goal:Vector2)
-- Create the start and end nodes
local startNode = Node.new(start.X, start.Y)
local endNode = Node.new(goal.X, goal.Y)

-- Create the lists for open and closed nodes
local openList = {startNode}
local closedList = {}

-- Loop until the open list is empty or the end node is found
while #openList > 0 do
-- Get the node with the lowest fCost in the open list
local currentNode = openList[1]
for i = 2, #openList do
if openList[i].FCost < currentNode.FCost then
currentNode = openList[i]
end
end

-- Remove the current node from the open list and add it to the closed list
local openListPosition = table.find(openList, currentNode)
if openListPosition then
table.remove(openList, openListPosition)
end

table.insert(closedList, currentNode)

-- Check if the current node is the end node
if currentNode.X == endNode.X and currentNode.Z == endNode.Z then
return self:GetPath(startNode, currentNode)
end

-- Get the neighbors of the current node
local neighbors = self:GetNeighbors(currentNode)

-- Loop through the neighbors
for i = 1, #neighbors do
local neighbor = Node.new(neighbors[i].X, neighbors[i].Z)

-- Check if the neighbor is already in the closed list
if not self:TableContains(closedList, neighbor) then
-- Calculate the tentative gCost of the neighbor
local tentativeGCost = currentNode.GCost + self:GetDistance(currentNode, neighbor)

-- Check if the neighbor is already in the open list
local isInOpenList = self:TableContains(openList, neighbor)

if not isInOpenList or tentativeGCost < neighbor.GCost then
-- Set the neighbor's parent to the current node
neighbor.Parent = currentNode

-- Update the neighbor's gCost, hCost, and fCost
neighbor.GCost = tentativeGCost
neighbor.HCost = self:GetDistance(neighbor, endNode)
neighbor.FCost = neighbor.GCost + neighbor.HCost

-- Add the neighbor to the open list if it's not already in it
if not isInOpenList then
table.insert(openList, neighbor)
end
end
end
end
end

-- No path was found
return nil
end

-- Define the function to calculate the distance between two nodes
function Service:GetDistance(nodeA, nodeB)
local distX = math.abs(nodeA.X - nodeB.X)
local distZ = math.abs(nodeA.Z - nodeB.Z)

if distX > distZ then
return 14 * distZ + 10 * (distX - distZ)
else
return 14 * distX + 10 * (distZ - distX)
end
end

-- Define the function to check if a table contains a specific value
function Service:TableContains(table, value)
for i = 1, #table do
if table[i].X == value.X and table[i].Z == value.Z then
return true
end
end

return false
end

function Service:AStar(startPosition:Vector2, endPosition:Vector2)
local calculatedPath = Service:FindPath(startPosition, endPosition)

return calculatedPath
end
``````
``````-- Grid example:
self.Grid = {
[1] = {
[1] = TileReference;
[2] = TileRecerence;
};

[2] = {
[1] = TileReference;
[2] = TileReference;
}
}

--[[
Grid[1] = X column
Grid[1][1] = (1, 1)

Each TileReference is a reference to a part that has data, including coordinates, and other things that aren't useful information
I prefer keeping the data under the tile instead of in the table for replication reasons
]]
``````

Video of the “zigzagging” pattern:
Video Link

The path generates properly and the unit avoids obstacles, but it moves in a zigzagging pattern. The script I took has comments in it which might help you, I didn’t edit the comments much. If you need any more information or questions, feel free to ask. Again, sorry if I forgot to put useful/needed information in the post as I’m at a loss and stuff like this is my weakest area in programming. Thanks for your time spent reading this long post.

2 Likes

If anyone has anything to help please let me know, even ideas or suggestions would help.

First you should try to visualize the path way points, every pathfinding system needs one.

From my experience the factors that influence the smoothness of the path is the :GetNeighbors function I had the same problem even for square grids, using 4 adjacent neighbors is not enough, realistically you will try to cut corners to move faster. This should apply the same for hexagons.

Therefore consider using corners of a hexagon as possible pathfinding nodes in your :GetNeighbors function.

Sample image from redblob games, the red path drawn would be more smoother but the grey path only forces travel to hexagons instead. However you will also need to consider checking the blue arrows to see if this “Shortcut” corner path is available as well.

2 Likes

Fixed it. The issue was in the way it calculated the “IsLineClear” function. Threw out the old one, rewrote it, and fixed it.

Thanks for your advice, visualizing it made me realize immediately what the issue is and I got it fixed really quickly. Here’s the code if anyone wants it, although you’ll need to do a lot of work to get it to be functional for your codebase:

Pathfinder:

``````function Service:CanTraverse(tile)
if not tile then
return false
end

if tile.Tags.HasWater.Value then
return false
end

if tile.Data.Blocked.Value then
return false
end

return true
end

-- Define the function to smooth the path using string pulling
function Service:SmoothPath(path)
local smoothedPath = {}

-- Add the start node to the smoothed path
table.insert(smoothedPath, path[1])

-- Loop through the path and remove any unnecessary nodes
for i = 2, #path - 1 do
local previousNode = path[i-1]
local currentNode = path[i]
local nextNode = path[i+1]

-- Check if the line between the previous node and the next node is clear
if nextNode and self:IsLineClear(previousNode, nextNode) then
-- Remove the current node from the path
table.remove(path, i)
else
-- Add the current node to the smoothed path
table.insert(smoothedPath, currentNode)
end
end

-- Add the end node to the smoothed path
table.insert(smoothedPath, path[#path])

return smoothedPath
end

function Service:IsLineClear(nodeA, nodeB)
local grid = self.Grid

local direction:Vector2 = nodeB:GetDirectionV2(nodeA:ToVector2())

if math.abs(direction.X) > 0 and math.abs(direction.Y) <= 0 then
local inc = 1

if direction.X < 0 then
inc = -1
end

for xOffset = inc, direction.X, inc do
local x = nodeA.X + xOffset
local z = nodeA.Z

local tile = grid[x][z]

if tile then
if not self:CanTraverse(tile) then
return false
end
else
return false
end
end
elseif math.abs(direction.X) <= 0 and math.abs(direction.Y) > 0 then
local inc = 1

if direction.Y < 0 then
inc = -1
end

for yOffset = inc, direction.Y, inc do
local x = nodeA.X
local z = nodeA.Z + yOffset

local tile = grid[x][z]

if tile then
if not self:CanTraverse(tile) then
return false
end
else
return false
end
end
elseif math.abs(direction.X) > 0 and math.abs(direction.Y) > 0 then
local xInc = 1
local yInc = 1

if direction.X < 0 then
xInc = -1
end

if direction.Y < 0 then
yInc = -1
end

for xOffset = 0, direction.X, xInc do
for yOffset = 0, direction.Y, yInc do
local x = nodeA.X + xOffset
local z = nodeA.Z + yOffset

print(x, z)

local tile = grid[x][z]

if tile then
if not self:CanTraverse(tile) then
return false
end
else
return false
end
end
end
else
print("What?")
end

return true
end

-- Define the function to get the neighbors of a node
function Service:GetNeighbors(node)
local grid = self.Grid
local neighbors = {}

-- Define the offsets for the six neighboring hexagons
local xOffset = 1
local yOffset = 1

local offsets = {{-xOffset, 0}, {-xOffset, yOffset}, {0, -yOffset}, {0, yOffset}, {xOffset, -yOffset}, {xOffset,0}}

-- Loop through the six neighboring hexagons
for _, offset in ipairs(offsets) do
-- Get the neighbor's position
local x = node.X + offset[1]
local z = node.Z + offset[2]

-- Check if the neighbor is within the grid
if grid[x] and grid[x][z] then
local neighbor = Node.new(x, z)

-- Check if the neighbor can be traversed
if self:CanTraverse(grid[x][z]) then
table.insert(neighbors, neighbor)
end
end
end

return neighbors
end

-- Define the function to get the path from the start node to the end node
function Service:GetPath(startNode, endNode)
-- Create the path list
local path = {}

-- Add the end node to the path list
table.insert(path, endNode)

-- Loop through the nodes' parents until the start node is reached
local currentNode = endNode
while currentNode.Parent do
table.insert(path, 1, currentNode.Parent)
currentNode = currentNode.Parent
end

return path
end

-- Define the function to find the optimal path between the start and end nodes
function Service:FindPath(start:Vector2, goal:Vector2)
-- Create the start and end nodes
local startNode = Node.new(start.X, start.Y)
local endNode = Node.new(goal.X, goal.Y)

-- Create the lists for open and closed nodes
local openList = {startNode}
local closedList = {}

-- Loop until the open list is empty or the end node is found
while #openList > 0 do
-- Get the node with the lowest fCost in the open list
local currentNode = openList[1]
for i = 2, #openList do
if openList[i].FCost < currentNode.FCost then
currentNode = openList[i]
end
end

-- Remove the current node from the open list and add it to the closed list
local openListPosition = table.find(openList, currentNode)
if openListPosition then
table.remove(openList, openListPosition)
end

table.insert(closedList, currentNode)

-- Check if the current node is the end node
if currentNode.X == endNode.X and currentNode.Z == endNode.Z then
return self:GetPath(startNode, currentNode)
end

-- Get the neighbors of the current node
local neighbors = self:GetNeighbors(currentNode)

-- Loop through the neighbors
for i = 1, #neighbors do
local neighbor = Node.new(neighbors[i].X, neighbors[i].Z)

-- Check if the neighbor is already in the closed list
if not self:TableContains(closedList, neighbor) then
-- Calculate the tentative gCost of the neighbor
local tentativeGCost = currentNode.GCost + self:GetDistance(currentNode, neighbor)

-- Check if the neighbor is already in the open list
local isInOpenList = self:TableContains(openList, neighbor)

if not isInOpenList or tentativeGCost < neighbor.GCost then
-- Set the neighbor's parent to the current node
neighbor.Parent = currentNode

-- Update the neighbor's gCost, hCost, and fCost
neighbor.GCost = tentativeGCost
neighbor.HCost = self:GetDistance(neighbor, endNode)
neighbor.FCost = neighbor.GCost + neighbor.HCost

-- Add the neighbor to the open list if it's not already in it
if not isInOpenList then
table.insert(openList, neighbor)
end
end
end
end
end

-- No path was found
return nil
end

-- Define the function to calculate the distance between two nodes
function Service:GetDistance(nodeA, nodeB)
local distX = math.abs(nodeA.X - nodeB.X)
local distZ = math.abs(nodeA.Z - nodeB.Z)

if distX > distZ then
return 14 * distZ + 10 * (distX - distZ)
else
return 14 * distX + 10 * (distZ - distX)
end
end

-- Define the function to check if a table contains a specific value
function Service:TableContains(table, value)
for i = 1, #table do
if table[i].X == value.X and table[i].Z == value.Z then
return true
end
end

return false
end

function Service:AStar(startPosition:Vector2, endPosition:Vector2)
local calculatedPath = Service:FindPath(startPosition, endPosition)

if calculatedPath then
local smoothedPath = self:SmoothPath(calculatedPath)

if smoothedPath then
return smoothedPath
else
return calculatedPath
end
end
end
``````

Node:

``````local Object = {}
Object.__index = Object

function Object:GetDirectionV3(position:Vector3)
return self:ToVector3() - position
end

function Object:GetDirectionV2(position:Vector2)
return self:ToVector2() - position
end

function Object:ToVector3()
return Vector3.new(self.X, 0, self.Z)
end

function Object:ToVector2()
return Vector2.new(self.X, self.Z)
end

function Object.new(x:number, z:number)
local self = {}
setmetatable(self, Object)

local trove = Trove.new()
self.Trove = trove

self.X = x
self.Z = z

self.GCost = 0
self.HCost = 0
self.FCost = 0
self.Parent = nil

return self
end

function Object:Destroy()
self.Trove:Destroy()

self = nil
end

return Object
``````

Thanks for your help!

1 Like

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.