I’m having trouble with me code listed below. I plan to make it into a publicly available module eventually but It’s just not functioning like an A* algorithm should and seems to get snagged at some points in the heuristic. Any help is appreciated, thanks!
-->>Created by uwuanimsyt with help from ChatGPT
local NodeSpacing = 2
local Start = workspace.Start
local End = workspace.End
local OpenList = {}
local ClosedList = {}
local NodeCache = {}
local FinalizedPath = {}
local TestPositionHolder = {}
local ValidDirections = {
Vector3.new(1, 0, 0), Vector3.new(-1, 0, 0)
, Vector3.new(1, 0, 1), Vector3.new(-1, 0, -1)
,Vector3.new(1, 0, -1), Vector3.new(-1, 0, 1)
, Vector3.new(0, 0, 1), Vector3.new(0, 0, -1)
, Vector3.new(0, 1, 0), Vector3.new(0, -1, 0)
, Vector3.new(1,1,0), Vector3.new(-1,-1,0)
,Vector3.new(0,1,1), Vector3.new(0,-1,-1)
,Vector3.new(-1,1,0), Vector3.new(1,-1,0)
,Vector3.new(0,1,-1), Vector3.new(0,-1,1)
}
function createNode(position)
-- Check if a node already exists at the given position
local cachedNode = NodeCache[position]
if cachedNode then
return cachedNode
else
-- Create a new node object
local node = {
Position = position,
-- Initialize additional properties as needed
G = 0,
H = 0,
Parent = nil
-- Add more properties as needed
}
-- Store the node in the cache
NodeCache[position] = node
-- Return the newly created node
return node
end
end
--[[function raycast(origin, direction)
-- Create raycasting parameters
local params = RaycastParams.new()
params.FilterDescendantsInstances = {game.Players:GetPlayers()}
params.FilterType = Enum.RaycastFilterType.Exclude
params.IgnoreWater = true
params.RespectCanCollide = true
-- Normalize the direction vector to ensure consistent ray length
direction = direction.Unit
-- Perform raycasting
local ray = workspace:Raycast(origin, direction * NodeSpacing, params)
-- Check if the ray hit anything
if ray then
-- Return the raycast result
return ray
else
-- Handle case where ray doesn't hit anything
return nil
end
end]] --original raycast function
function raycast(origin, direction)
-- Create raycasting parameters
local params = RaycastParams.new()
params.FilterDescendantsInstances = {game.Players:GetPlayers()}
params.FilterType = Enum.RaycastFilterType.Exclude
params.IgnoreWater = true
params.RespectCanCollide = true
-- Normalize the direction vector to ensure consistent ray length
direction = direction.Unit
-- Check if the ray hit anything
--return workspace:Raycast(origin, direction * NodeSpacing, params)
return workspace:FindPartOnRay(Ray.new(Start.Position, direction * NodeSpacing))
end --New Raycast function
function Backtrack(FinalNode)
-- Initialize the current node as the final node
local current = FinalNode
-- Create an empty table to store the final path
local path = {}
-- Keep backtracking until reaching the start node
while current do
-- Insert the current node at the beginning of the path table
table.insert(path, 1, current)
-- Update the current node to its parent (previous node in the path)
current = current.Parent
end
-- Store the final path
FinalizedPath = path
end
function AStar()
local Final = nil
local StartNode = createNode(Start.Position)
StartNode.G = 0
StartNode.H = (Start.Position - End.Position).Magnitude * NodeSpacing
table.insert(OpenList,StartNode)
local BestNode = nil
local F = math.huge
print("F Value1 = ".. F)
repeat task.wait()
for i, NODE in ipairs(OpenList) do
-- Calculate the actual cost from the start node to the current node (G)
local distance = (NODE.Position - Start.Position).Magnitude
local G = math.round(distance)
print(G)
NODE.G = G
-- Calculate the heuristic (H) as the Euclidean distance to the goal node
local H = (NODE.Position - End.Position).Magnitude * NodeSpacing
--print(H)
NODE.H = H
-- Calculate the total cost (F) as the sum of G and H
local TotalCost = NODE.G + NODE.H
print(BestNode[1])
-- Update the best node if the current node has a lower total cost
print("Before if statement")
if TotalCost < F then
print("After if statement")
F = TotalCost
workspace("F Value = ".. F)
BestNode = {NODE, i}
end
end
if not BestNode then
warn("No valid nodes found in OpenList")
break
end
-- Remove the best node from the open list and add it to the closed list
if BestNode then
table.insert(ClosedList, BestNode[1])
table.remove(OpenList, BestNode[2]-1)
end
for index,vector in ipairs(ValidDirections) do
local rayPart, raypos = raycast(BestNode[1],vector)
if not rayPart then
local Node = createNode(raypos)
table.insert(OpenList, Node)
end
end
print("BestNode:", BestNode[1])
Final = BestNode[1]
until #OpenList == 0 or (BestNode and (BestNode[1].Position - End.Position).Magnitude <= NodeSpacing * 1.5)
Backtrack(Final)
end
AStar()
print("Finished", FinalizedPath)
for i,v in pairs(FinalizedPath) do
local part = Instance.new("Part", workspace)
part.Anchored = true
part.CanCollide = false
part.Size = Vector3.one/4
part.Shape = Enum.PartType.Ball
part.CastShadow = false
part.Material = "Neon"
part.Color = Color3.new(0,1,0)
part.Position = v
end