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.