okay, I am not sure how to make this so I made a random grid with these already existing nodes.
I have been looking around for a roblox example or tutorial on this and there were only a few I found so I am going to ask based on those. Also ended up watching a 40 minute video about A star pathfinding that I half watched.
I found this “example” or something , and thought I could use it , but there was no context behind variables.
function findShortestPath(src, dest)
local queue = {src}
local visited = {[src] = true}
local parent = {}
while #queue > 0 do
local node = table.remove(queue, 1)
if node == dest then break end
for _, neighbor in ipairs(node.neighbors) do
if not neighbor.isObstructed then
-- you can have another separate routine updating this property
if not visited[neighbor] then
visited[neighbor] = true
parent[neighbor] = node
table.insert(queue, neighbor)
end
end
end
end
if parent[dest] then
-- if destination has a parent, there exists a path from start to finish
local path = {}
local temp = dest
while temp do
table.insert(path, temp)
temp = parent[temp]
end
-- list of nodes from destination to source (start)
return path
end
end
It’s a Lua port of the code from either the BFS or an incorrect one of the A* Wikipedia pages, probably the latter because it looks susily similar (especially the path reconstructing function).
It’s wrong if it’s an attempt at A* because it doesn’t visit nodes in the correct order. It just takes the first element of queue, and just inserts nodes into the end of the queue as they’re discovered, making it a breadth-first search.
BFS is not a good search alg for your use case. Check out these visualizations to see why.
A* is a great starting point, and depending on your use case it might be a really good choice because it’s pretty simple but fast-ish and correct (always finds the shortest path). There should be looooots of tutorials out there, video and text, it’s one of the most well known pathfinding algs and is commonly taught in machine intelligence courses. I can also post an A* implementation if you want.
As I said here I did watch a tutorial on “how it works” .
Also looked at this post Pathfinding Algorithm Simulation
Didn’t really check out his data structures, so don’t know about any of that.
If you are experienced with the topic you could help providing some info on how to make a grid for a pathfinding npc so that it walks in that grid.
Also this pathfinding system is really old I saw some video back 11 years ago when the Roblox pathfinding did not exist, so I was thinking that when there is stuff like pathfinding links and modifiers do those have to be implemented yourself then too?
Firstly it needs a way to tell where it can go. This is usually done by listing neighbors. Like in a grid you could tell the pathfinder which tiles next to it are valid for pathfinding.
You also need to track the shortest path to each area. This is so that as your searching out, getting to the next tile just requires you to link it to a previous path.
A very basic implementation is just that
Get neighbors
Store the path up to that point, loop through all the new cells get neighbors…
A* adds a distance check on top of that so that it can spend more time going in the right direction than to go behind it. I also recommend learning how to implement A* as it’s a really good one to apply.
Roblox has one pathfinding library that is general purpose for the world. To create custom pathfinding behavior you have to make pretty much all of it from scratch. There are technically some tricks you could do to get Roblox to do it, but it’s more complicated and annoying to do that then to write your own
function findShortestPath(src, dest)
local queue = {src}
local visited = {[src] = true}
local parent = {}
while #queue > 0 do
local node = table.remove(queue, 1)
if node == dest then break end
for _, neighbor in ipairs(node.neighbors) do
if not neighbor.isObstructed then
-- you can have another separate routine updating this property
if not visited[neighbor] then
visited[neighbor] = true
parent[neighbor] = node
table.insert(queue, neighbor)
end
end
end
end
if parent[dest] then
-- if destination has a parent, there exists a path from start to finish
local path = {}
local temp = dest
while temp do
table.insert(path, temp)
temp = parent[temp]
end
-- list of nodes from destination to source (start)
return path
end
end
I don't know what the src and dest are supposed to be, I assume dest is destination and is scrc the start node, or what part of this has all the nodes / grid
Also didn't a* have some equation.
Can a new system and roblox pathfinding be used together somehow.
For ex,using pathfinding links to make a teleporter , maybe first calculate a path with roblox pathfinding and the costs if it has the teleporting (checking for the waypoint labels to do so) then do something (maybe create a path with the custom path but this time with the twist of going to the teleporter) or if teleporting isn’t required by the calculations of the Roblox pathfinding then just use the custom one as normal.
