Now, this wasn’t actually made from scratch in of itself. I got it from here:
All I did was clean up the code and move everything into an OOP-styled modulescript for easier use. I’ll be using this for personal use.
I want to know if there are any optimizations to the code to make it faster. Any recommendations are appreciated.
AStar ModuleScript
@author: reteach, Downrest
@link: https://devforum.roblox.com/t/how-does-apathfinding-work/271356/3?u=downrest
@dependencies: Node
This is a modified version of the A* algorithm implementation of @reteach.
I moved the code to a modulescript for easier use, and also modified it for actual 3D use
]]
local astar = {}
local node = require(script.Node)
astar.__index = astar
type params = {[string]: any}
local function RemoveFromTable(t, value)
for i = 1, #t do
if t[i] == value then
table.remove(t,i)
break;
end
end
end
local function CheckInclusion(t, value)
for i = 1,#t do
if t[i] == value then
return true;
end
end
return false;
end
function astar.new(params)
local self = setmetatable({}, astar)
self.Rows = params.Rows
self.Cols = params.Cols
self.Start = params.Start
self.Goal = params.Goal
self.OpenSet = {}
self.ClosedSet = {}
self.Path = {}
return self
end
function astar:ComputeAsync()
local grid = {}
local start
local goal
local path = self.Path
local rows = self.Rows
local cols = self.Cols
local openset = self.OpenSet
local closedset = self.ClosedSet
--[[SETUP]]
for x = 1, rows do
grid[x] = {}
for y = 1,cols do
local isNonWall = false
if x == 1 and y == 1 then
isNonWall = true
elseif x == rows and y == cols then
isNonWall = true
end
grid[x][y] = node.new({
X = x,
Y = y,
IsNonWall = isNonWall
})
end
end
for x = 1,rows do
for y = 1,cols do
grid[x][y]:Show();
grid[x][y]:AddNeighbors(grid);
end
if x % 5 == 0 then
task.wait(.1)
end
end
--[[START]]
start = grid[self.Start.x][self.Start.y]
goal = grid[self.Goal.x][self.Goal.y]
table.insert(openset, start)
local startTick = tick()
local time = 0
while #openset > 0 do
task.wait()
local min = 1
for i,v in ipairs(openset) do
if openset[i].f < openset[min].f then
min = i;
end
end
local current = openset[min];
if current == goal then
break
end
RemoveFromTable(openset, current)
table.insert(closedset, current)
local neightbors = current.Neighbors
for i,v in ipairs(neightbors) do
local neighbor = neightbors[i];
local newPath = false
if (not CheckInclusion(closedset, neighbor) and not neighbor.Wall) then
local tempG = current.g + 1;
if CheckInclusion(openset, neighbor) then
if tempG < neighbor.g then
neighbor.g = tempG
newPath = true
warn("BLOCKED PATH: RECALCULATING")
end
else
neighbor.g = tempG
newPath = true
warn("BLOCKED PATH: RECALCULATING")
table.insert(openset, neighbor)
end
end
if newPath then
neighbor:Heuristic(goal)
neighbor.f = neighbor.g + neighbor.h
neighbor.previous = current
end
end
for i,v in ipairs(closedset) do
closedset[i]:ShowClosed();
end
for i,v in ipairs(openset) do
openset[i]:ShowOpen();
end
path = {};
local temp = current;
table.insert(path, temp);
local val = 1;
while temp.previous do
val = val + 1;
table.insert(path, temp.previous)
temp = temp.previous;
end
for i,v in ipairs(path) do
path[i]:ShowPath();
end
end
end
return astar
Node ModuleScript
--[[
@author: reteach, Downrest
@link: https://devforum.roblox.com/t/how-does-apathfinding-work/271356/3?u=downrest
]]
local node = {};
node.__index = node;
function node.new(params)
local self = setmetatable({}, node);
self.f = 0;
self.g = 0;
self.h = 0;
self.x = params.X
self.y = params.Y
self.IsNonWall = params.IsNonWall
self.Neighbors = {};
if Random.new():NextNumber() <= .3 and self.IsNonWall == false then
self.Wall = true
end
return self;
end
function node:AddNeighbors(Grid)
if not self.Wall then
local x = self.y;
local y = self.x;
local neighbors = self.Neighbors
if x < #Grid[1] then
table.insert(neighbors, Grid[y][x + 1]);
end
if x > 1 then
table.insert(neighbors, Grid[y][x - 1]);
end
if y < #Grid then
table.insert(neighbors, Grid[y+1][x]);
end
if y > 1 then
table.insert(neighbors, Grid[y-1][x]);
end
if x < #Grid[1] and y > 1 then
table.insert(neighbors, Grid[y-1][x+1]);
end
if x > 1 and y > 1 then
table.insert(neighbors, Grid[y-1][x-1]);
end
if x < #Grid[1] and y < #Grid then
table.insert(neighbors, Grid[y+1][x+1]);
end
if x > 1 and y < #Grid then
table.insert(neighbors, Grid[y+1][x-1]);
end
end
end
function node:Heuristic(End)
local Start = Vector2.new(self.x,self.y)
local Stop = Vector2.new(End.x,End.y)
self.h = (Start-Stop).magnitude
end
function node:Show()
if not self.Instance then
local part = Instance.new("Part")
part.Name = "AStarNode"
part.BrickColor = BrickColor.White()
part.Anchored = true
part.CFrame = CFrame.new(self.x,0,self.y)
part.Parent = workspace
part.Size = Vector3.new(.8,.8,.8)
if self.Wall then
part.BrickColor = BrickColor.Black()
end
self.Instance = part
end
end
function node:ShowOpen()
if self.Instance then
self.Instance.BrickColor = BrickColor.Blue();
end
end
function node:ShowNeighbors()
local neighbors = self.Neighbors
for i = 1, #neighbors do
if not neighbors[i].Wall then
neighbors[i].Instance.BrickColor = BrickColor.new("Royal purple")
end
end
self.Instance.BrickColor = BrickColor.new("Bright orange")
end
function node:ShowClosed()
if self.Instance then
self.Instance.BrickColor = BrickColor.Red();
end
end
function node:ShowPath()
if self.Instance then
self.Instance.BrickColor = BrickColor.Yellow();
end
end
return node;
Usage Script:
local astar = require(script.AStar)
local rows = 25
local cols = 25
local path = astar.new({
Cols = cols,
Rows = rows,
Start = {
x = 1,
y = 1
},
Goal = {
x = rows,
y = cols
}
})
while true do
for i,v in ipairs(workspace:GetChildren()) do
if v.Name == "AStarNode" then
v:Destroy()
end
end
local clock = os.clock()
path:ComputeAsync()
print("A* PATHFINDING TOOK " .. os.clock() - clock .. " TO FINISH!")
end