So I’m having a crucial issue with a pathfinding system, and I need help figuring it out.
Firstly I can’t use roblox’s pathfinding service because of how inefficient it is, especially in my use case.
What I’ve done is set up pre-placed path points all around the game’s environment, and I simply have an AI travel along the path points until it has a direct line of sight to the target cframe, then it B-lines it straight there. The path points are non-sequential so I can’t just increment along the path in a set order.
What I’m basically doing is finding the nearest pathpoint that’s closest to the direction the target is in, and this works really well for most cases. However I have an issue with this exact situation that I just can’t seem to figure out. The AI is at point H, and is trying to get to point A, the black line is a wall the AI can’t get through.
Through my current method the AI goes to point I, because that’s the point closest to the target, and it keeps doing this until it eventually gets stuck repeating through points K and J.
I’ve already got no issue detecting if the path is obstructed, that’s not the problem.
I need to know how I can make a system that can efficiently determine the correct path in this exact scenario, without having to manually define like “if at H and target at A then move to G” etc.
Key points being I need to be able to call this system to get the next valid pathpoint no matter where the AI and the target are; and as I mentioned above the points are non-sequential.
I’m not asking for someone to code for me, that’s ridiculous. I’m just really having a hard time with this problem, and I need some help brainstorming practical ways to solve it.
The issue is as I mentioned, my path points are already pre-defined. The pathfinding service would create a whole new set of it’s own path points. Not to mention, because the target position and AI position are constantly dynamically changing, I need to call the path-finding service ALOT. This is extremely inefficient for me, and I’ve already tried using it here only to find that it stutters really badly due to the sheer amount of times it’s needed.
1 Like
I suggest marking the blocked waypoints, and when calculating the path, exclude those blocked waypoints.
I appreciate the suggestion, but this idea has already occurred to me. It fails drastically when upon first detection the goal is unreachable… ok then lets compute a path. Then a very short time later the target changes positions, but is still unreachable. Now it needs to compute a new updated path. This stacks up alot, to lead to alot of lag and issues.
Well in this specific example, which isn’t a perfect recreation of every possible scenario, the next needed point is point G, however you can see that is blocked as well. Point F only works in this specific example, but probably wouldn’t be an option all the time.
It looks like you’re going to have to do a proper path-finding search here, most probably A*.
And for that to work, you need to turn your way-points into a connected graph of some kind.
This means every point needs to have a list of its nearest neighbours, with things like walls taken into account.
The good news is you only have to calculate it once, and could then toss it in a datastore.
The bad news is A* is pretty complicated, are you sure you can’t just use the roblox pathing?
I do need it to follow my predefined points very strictly, especially since there isn’t an ignorelist feature in the pathfinding service either, that also adds additional issues.
As I mentioned above, the target points isn’t always on the path, the AI just follows the path until it can see the target point. Then it just moves to it. That’s why when the target changes, I have to find a new path.
I already did some short skimming of some A* related content, and man it does look like a headache. All my predefined points and things are pretty solid, it’s just literally this one type off pathfinding issue is the only problem I have. I really hope there is a better option than A*, especially for just such a seemingly simple problem.
Well the target point is controlled by the user, so not really “placed” and pretty random.
Perhaps Raycasting from points closest to point H, and finding the point that can either:
raycast to the target, then continue to find a path from that point,
OR
closest point to point H and point A, and repeating the process on that point.
That was a good idea that I did consider, the issue I’m having currently is the sheer amount of path points involved, especially sifting though all the points that wouldn’t be used at all. I basically have to iterate through everything multiple times slowly finding the right path, and while that would work, just doesn’t feel right to me.
Yeah, sadly this is exactly what A* is designed to solve…
Well in this specific example, there is only one obstruction. But on bigger scales, that wouldn’t really work. Like if the AI is in an enclosed room with only one exit, but the target is already like 3 rooms away.
You did mention something though that might help.
I wasn’t going to expand too far into it, because I didn’t want to complicate the issue and confuse people. But here’s how it basically works.
First I have several pre-defined areas. Like Area1A and Area1B and Area2A, etc. Then I have path points leading from one area into the next. Like one point is 1A-1B, and so on.
I detect which area the target is in, then which area the AI is in, and try to find the path to them.
You mentioned storing the preset found paths, which I could actually do. However I’d probably just make a customish algorithm, to iterate through every area combination finding the correct order of paths ONCE when the server first fires up. Then simply just calling the stored values later on as needed.
Then perhaps setting up some closest points to search for a path could work. Example:
local ThirtyStudsAway = {} -- stores points that are 30 studs away, like a search radius for computing a path
local searchRadius = 30 -- the search radius size
local currentPoint = pointH -- the point eg. point H
for _, point in pairs (--[[your points here]]) do -- This loop gathers a bunch of points that is within a 30 stud radius to currentPoint
if (currentPoint.Position - point.Position).magnitude <= searchRadius then
table.insert(ThirtyStudsAway,point)
end
end
-- use the points in ThirtyStudsAway to generate/find a path