Since I wanna make a “custom” pathfinding system for a character to walk in a grid I tried writing code for a A* pathfinding algorithm , but got stuck since its been hard finding Roblox refrences and especially code. How would I get the order of the nodes where the character has to go?
Also I am not sure how to gettheneighbors since I looked up tutorials on A* and there was no refrence to the nodes only the start and end node so how would this know about the other nodes?
local function getNeighbors(pos)
end
local function heuristic(a, b)
return math.abs(a.X - b.X) + math.abs(a.Y - b.Y) + math.abs(a.Z - b.Z)
end
local function distance(a, b)
return (a - b).magnitude
end
local function findPath(startPos, endPos)
local startNode = {
position = startPos,
g = 0,
h = heuristic(startPos, endPos),
f = 0,
parent = nil
}
local endNode = {
position = endPos,
g = 0,
h = 0,
f = 0,
parent = nil
}
local openSet = {startNode}
local closedSet = {}
while #openSet > 0 do
local currentNode = openSet[1]
for i = 2, #openSet do
if openSet[i].f < currentNode.f then
currentNode = openSet[i]
end
end
if currentNode == endNode then
local path = {endNode}
local parent = currentNode.parent
while parent do
table.insert(path, 1, parent)
parent = parent.parent
end
return path
end
table.remove(openSet, table.find(openSet, currentNode))
table.insert(closedSet, currentNode)
for _, neighbor in ipairs(getNeighbors(currentNode.position)) do
if not table.find(closedSet, neighbor) then
local tentative_g = currentNode.g + distance(currentNode.position, neighbor)
if not table.find(openSet, neighbor) or tentative_g < neighbor.g then
neighbor.parent = currentNode
neighbor.g = tentative_g
neighbor.h = heuristic(neighbor.position, endPos)
neighbor.f = neighbor.g + neighbor.h
if not table.find(openSet, neighbor) then
table.insert(openSet, neighbor)
end
end
end
end
end
return nil
end
I had planned another scipt since this one might not be the one for this, but I am not sure how to go thru the nearby parts / neighbors , also is there no other way to make a grid pathfinding system since I can’t find too many posts about any of this. I have not even found enough lua refrence to methods like a* except for Pathfinding Algorithm Simulation
A* assumes a grid is already created, and you can do this in a number of ways. If your grid is labeled sufficiently, or is based on a coordinate system, you can infer the neighbors based on their coordinates. If your grid isn’t uniform, you’ll need to manually form the connections. In one of my games, I wrote a plugin to help draw out the pathfinding manually.
But to go back on my first suggestion, if you have a grid of parts like so:
[1,1] [2,1]
[2,1] [2,2]
You can get [1,1]'s neighbors by doing something like this:
local neighbors = {}
local node = workspace:FindFirstChild("1,1") -- assuming our name matches our coordinates
for i,v in {Vector2.new(1,0),Vector2.new(0,1),Vector2.new(-1,0),Vector2.new(0,-1)} do
local coordinateX = node:GetAttribute("X") -- we could also parse the name but this is for demo purposes
local coordinateY = node:GetAttribute("Y")
local neighborX = coordinateX + v.X
local neighborY = coordinateY + v.Y
local neighbor = workspace:FindFirstChild(neighborX .. "," .. neighborY)
if neighbor then
table.insert(neighbors, neighbor)
end
end
--next, return the neighbors
If you have obstacles or want to have your node graph represented more clearly (in code), you should look into Laplacian Matrices to represent your nodes, which can be represented as 2D tables in Lua
In my short little script, the nodes would be in workspace directly. In my example, I assume the parts are named “X,Y” where x and y are their coordinates, but they also have two attributes, one called X and one called Y which are just number attributes corresponding to their position. You could possibly come up with a better system that’s less redundant.