Making A* pathfinding work for hexagons (Complex)

Help and Feedback Scripting Support
#1

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
#2

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

#3

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.

image

2 Likes
#4

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!

2 Likes
#5

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