Works well, although I have an issue of it not being able to find the path if it’s on the opposite side of an obstacle.
Here is what I came up with:
local Players = game:GetService("Players")
local Debris = game:GetService("Debris")
local CollectionService = game:GetService("CollectionService")
local player = Players.LocalPlayer
local mouse = player:GetMouse()
local character = player.Character or player.CharacterAdded:Wait()
local humanoid = character:WaitForChild("Humanoid")
local PART_SIZE = 4
local MAX_ITERATIONS = 2000
local DEBOUNCE_TIME = 0.5
local lastClickTime = 0
local currentMove = nil -- Keep track of the current move
local function getEuclideanDistance(nodeA, nodeB)
local dx = (nodeB.X - nodeA.X) * PART_SIZE
local dy = (nodeB.Y - nodeA.Y) * PART_SIZE
return math.sqrt(dx * dx + dy * dy)
end
local function getNeighbors(node, grid)
local neighbors = {}
local directions = {
Vector2.new(-1, 0), Vector2.new(1, 0),
Vector2.new(0, -1), Vector2.new(0, 1),
Vector2.new(-1, -1), Vector2.new(1, 1),
Vector2.new(-1, 1), Vector2.new(1, -1)
}
for _, direction in ipairs(directions) do
local neighborPos = node + direction
if grid[neighborPos.X] and grid[neighborPos.X][neighborPos.Y] and grid[neighborPos.X][neighborPos.Y] == 0 then
table.insert(neighbors, neighborPos)
end
end
return neighbors
end
local function aStar(start, goal, grid)
local openSet = {[start] = true}
local cameFrom = {}
local gScore = {[start] = 0}
local fScore = {[start] = getEuclideanDistance(start, goal)}
local iterations = 0
while next(openSet) do
if iterations >= MAX_ITERATIONS then
warn("A* algorithm exceeded maximum iterations. Terminating.")
return nil
end
iterations = iterations + 1
local current
for node in pairs(openSet) do
if not current or fScore[node] < fScore[current] then
current = node
end
end
if current == goal then
local path = {}
while current do
table.insert(path, 1, current)
current = cameFrom[current]
end
return path
end
openSet[current] = nil
for _, neighbor in ipairs(getNeighbors(current, grid)) do
local tentativeGScore = gScore[current] + getEuclideanDistance(current, neighbor)
if not gScore[neighbor] or tentativeGScore < gScore[neighbor] then
cameFrom[neighbor] = current
gScore[neighbor] = tentativeGScore
fScore[neighbor] = gScore[neighbor] + getEuclideanDistance(neighbor, goal)
openSet[neighbor] = true
end
end
if iterations % 100 == 0 then
task.wait()
end
end
return nil
end
local function createGrid()
local grid = {}
local workspace = game:GetService("Workspace")
local parts = workspace:FindFirstChild("MapParts"):GetChildren()
for _, part in ipairs(parts) do
local gridX = math.floor(part.Position.X / PART_SIZE)
local gridY = math.floor(part.Position.Z / PART_SIZE)
if not grid[gridX] then
grid[gridX] = {}
end
if not CollectionService:HasTag(part, "Obstacle") then
grid[gridX][gridY] = 0 -- Walkable
else
grid[gridX][gridY] = 1 -- Not walkable
end
end
return grid
end
local function visualizePath(path)
for _, node in ipairs(path) do
local centerX = (node.X * PART_SIZE) + (PART_SIZE / 2)
local centerZ = (node.Y * PART_SIZE) + (PART_SIZE / 2)
local pathPart = Instance.new("Part")
pathPart.Anchored = true
pathPart.CanCollide = false
pathPart.Size = Vector3.new(1, 0.2, 1)
pathPart.Position = Vector3.new(centerX, character.PrimaryPart.Position.Y, centerZ)
pathPart.Color = Color3.fromRGB(128,0,128)
pathPart.Parent = workspace
Debris:AddItem(pathPart, 3)
end
end
local function moveCharacter(path)
if currentMove then
currentMove:Disconnect() -- Cancel the current movement
end
currentMove = humanoid.MoveToFinished:Connect(function()
if #path > 0 then
local node = table.remove(path, 1)
local centerX = (node.X * PART_SIZE) + (PART_SIZE / 2)
local centerZ = (node.Y * PART_SIZE) + (PART_SIZE / 2)
humanoid:MoveTo(Vector3.new(centerX, character.PrimaryPart.Position.Y, centerZ))
else
currentMove:Disconnect()
currentMove = nil
end
end)
-- Start the movement
local firstNode = table.remove(path, 1)
local firstCenterX = (firstNode.X * PART_SIZE) + (PART_SIZE / 2)
local firstCenterZ = (firstNode.Y * PART_SIZE) + (PART_SIZE / 2)
humanoid:MoveTo(Vector3.new(firstCenterX, character.PrimaryPart.Position.Y, firstCenterZ))
end
mouse.Button1Down:Connect(function()
local currentTime = tick()
if currentTime - lastClickTime < DEBOUNCE_TIME then
return
end
lastClickTime = currentTime
local targetPos = mouse.Hit.p
local gridStartPos = Vector2.new(math.floor(character.PrimaryPart.Position.X / PART_SIZE), math.floor(character.PrimaryPart.Position.Z / PART_SIZE))
local gridGoalPos = Vector2.new(math.floor(targetPos.X / PART_SIZE), math.floor(targetPos.Z / PART_SIZE))
local grid = createGrid()
local path = aStar(gridStartPos, gridGoalPos, grid)
if path then
visualizePath(path)
moveCharacter(path)
end
end)
I put a max iteration check so the game doesn’t freeze if it can’t path, however I am unable to go around obstacles (tiled red) unless it’s decently close, even if I raise the iteration count.
