by the way I meant working I missed spelled.
also I do want to point out there’s this error occurs, “exhausted allowed execution time” in your scripts
not for part 2 or anything just part 1, also I know that I’m complaining about the script im self-aware (maybe I am complaining). but I just want to know from your code can maybe improve to were the A* can detect walls and go around them. That’s all I want to know. I can show you because I’ve might’ve found out how to record and show you (also the code is your source the part 2)
No Walls:
With Walls:
(sorry for the lag)
Script To Prove:
local SIZE = 5
local DIRECTIONS = {
Vector3.xAxis;
Vector3.zAxis;
Vector3.xAxis * -1;
Vector3.zAxis * -1;
Vector3.zAxis + Vector3.xAxis;
Vector3.xAxis * -1 + Vector3.zAxis;
Vector3.xAxis + Vector3.zAxis * -1;
}
for i, dir in DIRECTIONS do
DIRECTIONS[i] = dir * SIZE -- scale the directions with the grid size
end
local function RoundToNearest(v)
return Vector3.new(
math.round(v.X / SIZE) * SIZE,
math.round(v.Y / SIZE) * SIZE,
math.round(v.Z / SIZE) * SIZE
)
end
local function NodeIsTraversable(point: Vector3)
local collisions = workspace:GetPartBoundsInBox(CFrame.new(point), Vector3.new(SIZE, 0, SIZE))
if collisions[1] then
return false
end
return true
end
local function ConstructNode(worldPos: Vector3, target: Vector3)
local D = math.sqrt(2) -- A constant
local function HeuristicFunction(a: Vector3, b: Vector3): number
local D2 = 1
local dx = math.abs(a.X - b.X)
local dy = math.abs(a.Y - b.Y)
local dz = math.abs(a.Z - b.Z)
return D * math.min(dx, dy, dz) + (D2 - D) * math.max(0, dx + dy + dz - 2 * math.min(dx, dy, dz))
end
local Object = setmetatable({
Traversable = false;
Position = worldPos;
Costs = setmetatable({
G = 0;
H = 0;
}, {
__index = function(t, k)
if k == 'F' then
return rawget(t, 'H') + rawget(t, 'G') -- F is the sum of H and G
end
return rawget(t, k)
end,
});
HeapIndex = 0; -- For our new heap
Parent = nil; -- No more storing Parents table
}, {
__sub = function(a, b)
local compare = a.Costs.F - b.Costs.F -- Substract a's F and b's F
if compare == 0 then -- If the F costs are equal, compare the H cost instead
compare = a.Costs.H - b.Costs.H
end
return -compare -- Return the negated comparison
end,
__eq = function(a, b)
return a.Position == b.Position
end,
})
Object.Costs.G = (worldPos - target).Magnitude
Object.Costs.H = HeuristicFunction and HeuristicFunction(worldPos, target) or 0 -- Heuristic is 0 if no function is set
Object.Traversable = NodeIsTraversable(worldPos)
return Object
end
local function FindPath(start: Vector3, target: Vector3)
start = RoundToNearest(start)
target = RoundToNearest(target)
local StartNode = ConstructNode(start, target)
local TargetNode = ConstructNode(target, target)
-- Safety precaution checks so we don't waste time computing the path
assert(StartNode.Traversable, 'Starting Node is intraversable, thus path is intraversable')
assert(TargetNode.Traversable, 'Target Node is intraversable, thus path is intraversable')
local Grid = {[start] = StartNode, [target] = TargetNode}
local Heap = require(script:WaitForChild("Heap"))
local OpenSet = Heap.new()-- :: Heap.Heap<typeof(ConstructNode(Vector3, Vector3))>
local ClosedSet = {}
OpenSet:Add(StartNode)
while OpenSet:Count() > 0 do
local CurrentNode = OpenSet:RemoveFirst()
ClosedSet[CurrentNode.Position] = true
local function RetracePath()
local Path = {}
local CurrentPathNode = TargetNode
while CurrentPathNode ~= StartNode do
table.insert(Path, 1, CurrentPathNode)
CurrentPathNode = CurrentPathNode.Parent
end
return Path
end
if CurrentNode == TargetNode then
return RetracePath()
end
for _, direction in DIRECTIONS do
local NeighborPos = CurrentNode.Position + direction
-- If neighbor already evaluated/not traversable, skip
if ClosedSet[NeighborPos] or not NodeIsTraversable(NeighborPos) then
continue
end
-- Get neighbor node
local NeighborNode = Grid[NeighborPos] or ConstructNode(NeighborPos, target)
Grid[NeighborPos] = NeighborNode
-- Get new G cost to the neighbor
local CostToNeighbor = CurrentNode.Costs.G + (CurrentNode.Position - NeighborPos).Magnitude
-- If cost turns out to be better or not in openset
if CostToNeighbor < NeighborNode.Costs.G or not OpenSet:Contains(NeighborNode) then
NeighborNode.Costs.G = CostToNeighbor
NeighborNode.Costs.H = (NeighborPos - target).Magnitude
NeighborNode.Parent = CurrentNode
if not OpenSet:Contains(NeighborNode) then -- If it doesn't have the neighbor node yet, add the node
OpenSet:Add(NeighborNode)
end
end
end
end
end
local function roundToStep(pos : Vector3)
return Vector3.new(math.floor(pos.X/3)*3+1.5,math.floor(pos.Y/3)*3+1.5, math.floor(pos.Z/3)*3+1.5)
end
local ai = workspace.ai
local hum = ai:WaitForChild("Humanoid")
while wait() do
ai:MoveTo(workspace.Start.Position)
local path = FindPath(roundToStep(workspace.Start.Position), roundToStep(workspace.Target.Position))
for _, node in pairs(path) do
if workspace:FindFirstChild(tostring(_)) then
workspace:FindFirstChild(tostring(_)):Destroy()
end
local a = Instance.new("Part", workspace)
a.Name = _
a.Position = node.Position
a.Size = Vector3.new(1, 1, 1)
a.Anchored = true
a.CanCollide = false
end
for _, node in pairs(path) do
hum:MoveTo(node.Position)
hum.MoveToFinished:Wait()
end
end also I’m using part 2 because part 1 wasn’t working from your script (for some reason might’ve been an error) so if you can help me with this.
Sorry for the inactivity; I was feeling extremely lightheaded. Looking at your code, there doesn’t seem to be anything wrong with it. It might be that the wall just barely misses the collision node box. Try making the wall extend deeper into the floor or make the SIZE smaller. If those doesn’t work, try printing collisions in NodeIsTraversable
Oh dont worry your fine. ill check and see.
so when printing lower numbers 1-3 (havent tried 0 but will now0 it says in the collisions that the npcs bodyparts are getting detected heres for 3:
{
[1] = HumanoidRootPart,
[2] = Left Arm,
[3] = Torso,
[4] = Right Arm
}
and thens prints again with nothing also it gives the error from the asset. (I tried 0 but then it just gives me NaN
You should use an overlap params to filter out the agent body parts. Also what do you mean by printing nothing or getting NaN
When SIZE = 0 it prints out A NaN message
also what does it need in the overlapparams
Making SIZE 0 will just make it not go anywhere, use a number that isn’t 0. you can use decimals
nothing, you just need to fill in FilterDescendantsInstances and the FilterType
local Params = OverlapParams.new()
Params.FilterDescendantsInstances = {workspace.ai}
Params.FilterType = Enum.RaycastFilterType.Exclude
local function NodeIsTraversable(point: Vector3)
local collisions = workspace:GetPartBoundsInBox(CFrame.new(point), Vector3.new(SIZE, 0, SIZE), Params)
if collisions[1] then
return false
end
return true
end
I’d say it does work (also my pc turned off so if I make video’s on a different part of the baseplate I’m sorry) but when its completed it returns the traversable node (the final node) heres the message
AnyService.A* 2:108: Target Node is intraversable, thus path is intraversable
Nevermind it was the local D = math.sqrt(2) I just putted it out of the ConstructNode function
well not really when its in a loop when the ai is currently walking to the nodes
This is because the target node is colliding with something, make sure your node is not too low on the ground and the start node and end node y position should be the same if you only have 2d directions
Elaborate?
so when ai (NPC) is finished the walking so basically walking to the end of nodes lets say in the debug form lets say the end node part is (which is is like i+1) named 30 in the while loop loops again when the ai finished going to end node then goes back to the start and (remember the assert) the assert prints out that the target is intraversable but the mention that the target node is colliding with something, well its not its still on the ground. ( I’m sorry if my message is saying that it is being sarcastic) here’s the code:
local SIZE = 3
local DIRECTIONS = {
Vector3.xAxis;
Vector3.zAxis;
Vector3.xAxis * -1;
Vector3.zAxis * -1;
Vector3.zAxis + Vector3.xAxis;
Vector3.xAxis * -1 + Vector3.zAxis;
Vector3.xAxis + Vector3.zAxis * -1;
}
for i, dir in DIRECTIONS do
DIRECTIONS[i] = dir * SIZE -- scale the directions with the grid size
end
local function RoundToNearest(v)
return Vector3.new(
math.round(v.X / SIZE) * SIZE,
math.round(v.Y / SIZE) * SIZE,
math.round(v.Z / SIZE) * SIZE
)
end
local Params = OverlapParams.new()
local filterdDescendantsInstances = {}
local function CheckForHumanoids()
for _, Object in ipairs(workspace:GetChildren()) do
if Object:IsA("Model") then
if Object:FindFirstChildWhichIsA("Humanoid") then
print(Object)
Params.FilterDescendantsInstances = {Object}
Params.FilterType = Enum.RaycastFilterType.Exclude
end
end
end
end
CheckForHumanoids()
local function NodeIsTraversable(point: Vector3)
local collisions = workspace:GetPartBoundsInBox(CFrame.new(point), Vector3.new(SIZE, 0, SIZE), Params)
if collisions[1] then
return false
end
return true
end
local D = math.sqrt(2) -- A constant
local function ConstructNode(worldPos: Vector3, target: Vector3)
local function HeuristicFunction(a: Vector3, b: Vector3): number
local D2 = 1
local dx = math.abs(a.X - b.X)
local dy = math.abs(a.Y - b.Y)
local dz = math.abs(a.Z - b.Z)
return D * math.min(dx, dy, dz) + (D2 - D) * math.max(0, dx + dy + dz - 2 * math.min(dx, dy, dz))
end
local Object = setmetatable({
Traversable = false;
Position = worldPos;
Costs = setmetatable({
G = 0;
H = 0;
}, {
__index = function(t, k)
if k == 'F' then
return rawget(t, 'H') + rawget(t, 'G') -- F is the sum of H and G
end
return rawget(t, k)
end,
});
HeapIndex = 0; -- For our new heap
Parent = nil; -- No more storing Parents table
}, {
__sub = function(a, b)
local compare = a.Costs.F - b.Costs.F -- Substract a's F and b's F
if compare == 0 then -- If the F costs are equal, compare the H cost instead
compare = a.Costs.H - b.Costs.H
end
return -compare -- Return the negated comparison
end,
__eq = function(a, b)
return a.Position == b.Position
end,
})
Object.Costs.G = (worldPos - target).Magnitude
Object.Costs.H = HeuristicFunction and HeuristicFunction(worldPos, target) or 0 -- Heuristic is 0 if no function is set
Object.Traversable = NodeIsTraversable(worldPos)
return Object
end
local function FindPath(start: Vector3, target: Vector3)
start = RoundToNearest(start)
target = RoundToNearest(target)
local StartNode = ConstructNode(start, target)
local TargetNode = ConstructNode(target, target)
-- Safety precaution checks so we don't waste time computing the path
assert(StartNode.Traversable, 'Starting Node is intraversable, thus path is intraversable')
assert(TargetNode.Traversable, 'Target Node is intraversable, thus path is intraversable')
local Grid = {[start] = StartNode, [target] = TargetNode}
local Heap = require(script:WaitForChild("Heap"))
local OpenSet = Heap.new()-- :: Heap.Heap<typeof(ConstructNode(Vector3, Vector3))>
local ClosedSet = {}
OpenSet:Add(StartNode)
while OpenSet:Count() > 0 do
local CurrentNode = OpenSet:RemoveFirst()
ClosedSet[CurrentNode.Position] = true
local function RetracePath()
local Path = {}
local CurrentPathNode = TargetNode
while CurrentPathNode ~= StartNode do
table.insert(Path, 1, CurrentPathNode)
CurrentPathNode = CurrentPathNode.Parent
end
return Path
end
if CurrentNode == TargetNode then
return RetracePath()
end
for _, direction in DIRECTIONS do
local NeighborPos = CurrentNode.Position + direction
-- If neighbor already evaluated/not traversable, skip
if ClosedSet[NeighborPos] or not NodeIsTraversable(NeighborPos) then
continue
end
-- Get neighbor node
local NeighborNode = Grid[NeighborPos] or ConstructNode(NeighborPos, target)
Grid[NeighborPos] = NeighborNode
-- Get new G cost to the neighbor
local CostToNeighbor = CurrentNode.Costs.G + (CurrentNode.Position - NeighborPos).Magnitude
-- If cost turns out to be better or not in openset
if CostToNeighbor < NeighborNode.Costs.G or not OpenSet:Contains(NeighborNode) then
NeighborNode.Costs.G = CostToNeighbor
NeighborNode.Costs.H = (NeighborPos - target).Magnitude
NeighborNode.Parent = CurrentNode
if not OpenSet:Contains(NeighborNode) then -- If it doesn't have the neighbor node yet, add the node
OpenSet:Add(NeighborNode)
end
end
end
end
end
local function roundToStep(pos : Vector3)
return Vector3.new(math.floor(pos.X/3)*3+1.5,math.floor(pos.Y/3)*3+1.5, math.floor(pos.Z/3)*3+1.5)
end
local debugFinished = false
function debugParts(path)
debugFinished = false
for _, node in pairs(path) do
for _, child in pairs(workspace:GetChildren()) do
if child.Name == tostring(_) then
child:Destroy()
end
end
local a = Instance.new("Part", workspace)
a.Name = _
a.Position = node.Position
a.Size = Vector3.new(1, 1, 1)
a.Anchored = true
a.CanCollide = false
end
debugFinished = true
end
local ai = workspace:WaitForChild("ai")
local humanoid = ai:WaitForChild("Humanoid")
local rootPart = ai:WaitForChild("HumanoidRootPart")
while wait() do
ai:MoveTo(workspace.Start.Position)
local path = FindPath(rootPart.Position, roundToStep(workspace.Goal.Position))
debugParts(path)
if debugFinished then
for _, node in pairs(path) do
humanoid:MoveTo(node.Position)
humanoid.MoveToFinished:Wait()
end
end
end
still part 2 heres the video:
Use :AddToFilter instead:
Params:AddToFilter(Object)
Do you know what was going on the while loop just thinks when while loop goes again it just think the target position is changed when its just the same position, lemme know if you found a solution because I don’t know
Edit: Don’t worry about the scripts, also I had to use adobe to do it, since the original one wasn’t working at a 20.0 MB
2 Likes
please do respond if you got something to help with me. Its the same script when I said
“so when ai (NPC) is finished the walking so basically walking to the end of nodes lets say in the debug form lets say the end node part is (which is is like i+1) named 30 in the while loop loops again when the ai finished going to end node then goes back to the start and (remember the assert) the assert prints out that the target is intraversable but the mention that the target node is colliding with something, well its not its still on the ground. ( I’m sorry if my message is saying that it is being sarcastic) here’s the code:”
[quote=“tracedrounds, post:34, topic:2714504, username:tracedrounds”]
its the same script.
That’s because the waypoint parts you got + the starting/ending node is being collided, set CanCollide, CanTouch, and CanQuery to false
I’ve now modified it to the waypoints all the things that you told, but there is no errors but the ai (NPC) is not moving does it take time?
Edit: I’ve realized that the return in the modified script